Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa Mental 15, \(c\), Grafo para exemplo do caminho Hamiltoniano. -…
Mapa Mental 15
Capítulo 12: "
Coping with the Limitations of Algorithm Power
".
Neste capítulo serão introduzidas duas técnicas de
design
de algoritmo:
backtracking
e
ramificar e limitar
.
Elas são utilizadas para tentar resolver os problemas que são difíceis de serem resolvidos algoritmicamente mas são importantes e não podem ser "deixados de lado".
Elas constroem soluções candidatas um componente por vez e avaliam essas soluções parcialmente construídas. Se nenhum valor potencial dos componentes restantes levam a uma solução, os componentes restantes não são gerados.
Isso torna possível resolver alguns exemplos grandes de difíceis problemas combinatórios, mas, no pior caso, ainda é encontrado o tempo exponencial.
Ambas técnicas são baseadas na construção de uma árvore de espaço de estado, cujos nós refletem escolhas específicas feitas para o componente de uma solução.
Assim que é garantido que nenhum descendente de um nó corresponde a uma escolha que pode levar à solução do problema, esse nó é encerrado.
As técnicas divergem pela natureza dos problemas aos quais elas podem ser aplicadas.
Ramificar e limitar é aplicável apenas à problemas de otimização.
Backtracking
é, na maioria das vezes, aplicado à problemas de não otimização.
Elas também diferem na ordem na qual os nós da árvore de espaço de estado são gerados.
Para
Backtracking
, a árvore é desenvolvida por profundidade-primeiro; e a outra técnica tem como regra mais comum para isso a regra de melhor-primeiro.
Seção 12.1: "
Backtracking
".
1 more item...
\(c\)
\(d\)
\(b\)
\(a\)
\(e\)
\(f\)
Grafo para exemplo do caminho Hamiltoniano.