Please enable JavaScript.
Coggle requires JavaScript to display documents.
Coping with the Limitations of Algorithm Power, Backtracking, Branch-and…
-
Backtracking
-
A ideia principal é construir soluções, um componente de cada vez, e avaliar esses candidatos parcialmente construídos como segue.
Se uma solução parcialmente construída puder ser desenvolvida sem violar as restrições do problema, isso será feito tomando-se a primeira opção legítima restante para o próximo componente.
-
Se não existir uma opção legítima para o componente seguinte, o algoritmo recua para substituir o último componente da solução parcialmente construída pela sua próxima opção.
Constrói uma solução parcial, se esta não for promissora, volta e tenta outra
Na maioria dos casos, uma árvore de espaço de estados para um algoritmo de retrocesso é construída na forma de busca em profundidade.(depth-first)
Se o nó atual for promissor, seu filho é gerado adicionando a primeira opção legítima restante para o próximo componente de uma solução, e o processamento passa para esse filho.
Finalmente, se o algoritmo alcança uma solução completa para o problema, ele para (se apenas uma solução for necessária) ou continua procurando outras soluções possíveis.
Se o nó atual não for promissor, o algoritmo volta ao pai do nó para considerar a próxima opção possível para seu último componente;
se não houver essa opção, ele retrocede mais um nível na árvore e assim por diante.
-
É conveniente implementar esse tipo de processamento construindo uma árvore de escolhas feitas, chamada árvore de espaço de estados. (state-space trees)
-
Utilizado para tentar encontrar soluções para problemas que exigem encontrar um elemento com uma propriedade especial em um domínio que cresce exponencialmente rápido (ou mais rápido) com o tamanho da entrada do problema
-
Branch-and-Bound
-
Normalmente, expande com base no best-first =>
Nós com limite inferior à melhor solução até agora são removidos
Se o valor limite não for melhor que o valor da melhor solução vista até agora - ou seja, nem menor para um problema de minimização e nem maior para um problema de maximização - o nó não é promissor e pode ser encerrado.
terminamos um caminho de busca no nó atual em uma árvore de espaço de estados de um algoritmo branch-and-bound por qualquer um dos três motivos a seguir:
O subconjunto de soluções viáveis representado pelo nó consiste em um único ponto (e, portanto, nenhuma outra escolha pode ser feita) — neste caso, comparamos o valor da função objetivo para esta solução viável com o da melhor solução vista até agora e atualize o último com o primeiro se a nova solução for melhor.
-
-
Comparado ao backtracking(retrocesso), o branch-and-bound requer dois itens adicionais:
Para cada nó da árvore do espaço de estados, um limite para o melhor valor da função objetivo (em qualquer solução que possa ser obtida adicionando mais componentes à solução parcialmente construída representada pelo nó)
-
-
-