Coping with the limitations of algorithm power
backtracking
branch-and-bound
variação da "exhasustive search"
construir soluções uma a uma e avalias na forma:
se conseguir desenvolver sem violar as restrições
escolhermos a próxima opção válida
se não conseguir desenvolver
retrocedemos
state-space tree
root = estado inicial
níveis = escolha para um componente da solução
nodes
promising
nonpromising
se corresponder a uma parte da construção da solução
leaves
podem ser:
dead-ends/becos sem saída
a solução completa
construção da árvore
DFS
se o nó for promissor adiciona o próximo componente
se for não promissor, retocede
N-QUEENS problem
colocar n rainhas em um tabuleiro nxn
HAMILTONIAN CIRCUIT problem
percorrer todos os vértices apenas uma vez
a = root
SUBSET SUM problem
achar um subconjunto em que a soma seja igual a um inteiro X
podemos usar árvore binária
general remarks
o output pode ser visto como uma n-tupla(x1, ... xn)
não é extremamente eficiente mas pode ser necessário, por exemplo, gerar todos os casos
o sucesso varia segundo a instância
possui dois mértodos adicionais quando comparado ao backtracking
uma maneira de fornecer o limite sobre cada nó
o valor da melhor solução é mantido
quando parar o algoritmo no nó atual
o valor do limite não é o melhor
o nó não tem soluções viávieis
nenhuma escolha adicional pode ser feita (comparmos com a melhor solução até agora)
ASSIGNMENT problem
atribuir n pessoas a n trabalhos com o menor custo total
etapas
1 - achamos o limite inferior
2 - construímos a state-space tree
3 - seleção do nó promissor
4 - poda de ramos não promissores
viva/live nodes
geramos todos os filhos do nó mais promissor entre as folhas
KNASPSACK problem
subconjunto mais valioso de itens que se encaixam em uma mocila de capacidade limitada
TRAVELING SALESMAN problem
menor caminho para todas as cidades, passando só uma vez em cada
general remarks
permite resolver instâncias grandes de problemas combinatórios difíceis
é impossível prever quais instâncias são solucionáveis em um tempo realista
podemos "acelerar" branch-and-bound exlorando especificidades antes de construir a árvore