Please enable JavaScript.
Coggle requires JavaScript to display documents.
Coping with the Limitations of Algorithm Power - Coggle Diagram
Coping with the Limitations of Algorithm Power
Tanto as técnicas como
backtracking
e
branch-and-bound
.
Ambas as estratégicas podem ser consideradas como buscas exaustivas melhoradas.
Refletem uma construção de uma
state-space tree
no qual reflete uma escolha especifica feita por uma solução componentes de soluções.
As técnicas se diferem pela natureza dos problemas que podem serem aplicados.
Backtracking
Pode ser usado para problemas de otimização, mas não limita-se a apenas isso, também pode ser usado para problemas de não otimização.
Os
state-space tree
geralmente são desenvolvidos por uma
depth-first
(algo similar ao DFS).
Concluindo, três coisas precisam ser ditas em nome do retrocesso.
Em segundo lugar, ao contrário do exaustivo abordagem de pesquisa, que está fadada a ser extremamente lenta para todas as instâncias de um problema, retroceder pelo menos traz uma esperança de resolver alguns casos de problemas não triviais tamanhos padrão em um período de tempo aceitável
Primeiro, é normalmente aplicado a problemas combinatórios difíceis para os quais não há algoritmo eficiente possivelmente existem ritmos para encontrar soluções exatas.
Terceiro, mesmo que o retrocesso não elimine quaisquer elementos do espaço de estados de um problema e acaba gerando todos os seus elementos, fornece uma técnica específica para fazê-lo, que pode ser valiosa por si só.
A ideia principal é construir as soluções uma de cada vez e avalia-las parcialmente.
Podemos construir possíveis candidatos da seguinte forma.
Caso uma solução parcial puder ser desenvolvida sem violar as restrições do problema, é feita a tomando como a primeira opção legitima restante para o próx. componente.
Se não houver legitimidade opção de posicionamento para o próximo componente, não há alternativas para qualquer componente restante precisa ser considerado.
Neste caso, o algoritmo recua para substituir o último componente da solução parcialmente construída com sua próxima opção.
Implementa-se pela escolha do tipo de tree chamado
state - space tree
.
A raiz é representada como um state inicial antes da busca para as soluções começarem.
Os nós no Primeiro nível da tree representam as escolhas feitas pelo primeiro componente da solução, já os nós do segundo nível representam as escolhas feitas pelo segundo componente e assim por diante.
Um nó é dito como
promissor
se ele corresponder para uma solução construída parcialmente que ainda pode levar a uma solução completa. Outrossim, o contrário tbm é vdd sendo chamado de
não-promissor
.
As folhas representam becos sem saídas, ou seja, não promissores ou soluções completas pelo algoritmo.
Na maioria dos casos, um estado A árvore espacial para um backtracking é construída na forma de busca em profundidade.
Se o nó atual for promissor, seu filho é gerado pela adição da primeira opção legítima restante para o próximo componente de uma solução, e o nó atual é promissor.
o processamento se move para esta criança.
2 more items...
Branch-and-bound
É aplicado somente para problemas de otimização porque se baseia no cálculo de um limite de valores possíveis do problema função objetiva.
Pode ter a sua geração de nós de uma modo variado. O modo mais natural é chamada da regra
best-first
.
A ideia central do Backtracking pode ser ainda mais fortalecida se trabalharmos com problemas de otimização.,
A ideia central é cortar um galho da state-space tree do problema e deduzir que ele não tem solução.
Terminologia padrão de otimização de soluções.
feasible solution
É um ponto
no espaço de busca do problema que satisfaz todas as restrições do problema
Considerando que uma solução ótima é uma solução viável com o melhor valor do função objetiva.
Em comparação ao
backtracking
, branch-and-bound requer dois add itens.
Uma maneira de fornecer, para cada nó de uma árvore de espaço de estados, um limite para o melhor valor da função objetivo em qualquer solução que possa ser obtida adicionando outros componentes para a solução parcialmente construída representada pelo nó.
O valor da melhor solução vista até agora
Se esta informação estiver disponível, podemos comparar o valor vinculado de um nó com o valor da melhor solução vista até agora.
Se o valor limite não for melhor que o valor da melhor solução vista até agora - isto é, 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 Na verdade, nenhuma solução obtida dele pode produzir uma solução melhor do que aquela já disponível . Esta é a ideia principal da técnica branch-and-bound.
Em geral, terminamos o caminho de buscas por uma dessas 3 razões.
O valor do limite do nó não é melhor que o valor da melhor solução
visto até agora.
O nó não representa soluções viáveis porque as restrições do problema já foram violados.
1 more item...
Assignment Problem
Vamos ilustrar a abordagem branch-and-bound aplicando-a ao problema de atribuir n pessoas a n empregos de modo que o custo total da atribuição seja tão pequeno que possível.
1 more item...
Knapsack Problem
2 more items...