Re: Busca em Profundidade?

[Carlos Eduardo Ferreira <cef@ime.usp.br>]

On Wednesday 05 June 2002 16:23, Domingos wrote:
> Olá,
>
> Andei dando uma consultada na Internet e vi que a busca em
> profundidade no Branch & Bound é, em geral, mais eficiente que aquela
> que está sempre olhando nós na mesma profundidade, isso é verdade?
> [ nesta busca em profundidade, o nó (o problema atual) gera 2 filhos
> e um deles torna-se o problema atual ]

Defina eficiente... Lembre que estamos resolvendo um problema 
computacionalmente difícil, e portanto não existe estratégia que sempre 
leva à solução ótima mais rapidamente. 

>
> Estava pensando em implementar a segunda opção porque achava que esta
> seria mais eficiente, mas agora fiquei em dúvida, não posso me dar ao
> luxo de implementar os dois tipos e testar, então estou apelando pra
> lista :-)

Eu acho que vocês têm de implementar a busca de pelo menos três jeitos: 
busca em profundidade, largura e usando o heap e melhorando o limitante 
a cada passo. Mas, é claro que quem define isso é nosso chefe 
(egbirgin) ;-) 

--
carlinhos