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