Please enable JavaScript.
Coggle requires JavaScript to display documents.
Resolvendo Problemas Complexos - Coggle Diagram
Resolvendo Problemas Complexos
Apesar de alguns algoritmos não terem soluções em tempo polinomial, há meios de aumentar essa eficiência para resolver instâncias menores, mas ainda muito grandes
Esses meios são técnicas de design que constroem e avaliam soluções parciais para um problema
Entre essas técnicas, estão
back-tracking
e
branch-and-bound
, que se baseiam na construção de
state-space-tree
Na
state-space-tree
, é criada uma árvore em que cada nódulo corresponde a uma uma decisão relativa ao problema.
Uma solução é buscada analisando os resultados das decisões dos nódulos filhos, e depois no nódulo pai
(como em uma travessia em pós-ordem)
A análise de um nódulo termina quando é determinado que uma solução não pode ser alcançada pelos seus descendentes
Tanto
back-tracking
quanti
branch-and-bound
trabalham com a construção dessa árvore, mas diferem em como ela é construída
Back-tracking
gera os nódulos em um processo semelhante a
depth first search
Back-Tracking
Na busca exaustiva, a solução de um problema é encontrada gerando múltiplos candidatos e escolhendo os que atendem aos requisitos do problema
Back-tracking
faz um processo semelhante, mas mais inteligente
Aqui, é feita uma solução parcial para o problema
Se essa solução puder ser desenvolvida ainda mais sem violar as restrições do problema, ela segue para as opções legítimas para o próximo componente
Se não houver soluções legítimas, não há mais alternativas para o desenvolvimento do problema
Nesse caso, o algoritmo retorna para o componente anterior e substitui o último componente por uma das outras opções
Esse processo pode ser visualizado como a construção de uma árvore em que a raiz é o estado inicial do problema, e os filhos de u nódulo são as opções para os componentes seguintes
Essa é a
state-space tree
2 more items...
O resultado desse processo é um vetor em que cada componente é uma solução possível para o problema, podendo as soluções terem um tamanho uniforma ou variante
Isso somado ao fato de todo algoritmo de
back-tracking
gerar explicita ou implicitamente uma
state-space tree
mostra que essa técnica de design não é necessariamente eficiente
1 more item...
Problema das n-rainhas
O problema das n-rainhas busca saber como pôr
n
rainhas em um tabuleiro de xadrez
n x n
de forma que elas não se ataquem
Ele pode ser resolvido por um algorimo de
back-tracking
da seguinte forma:
A primeira rainha é posta na primeira posição possível, (1, 1)
Depois, já é sabido que a segunda rainha deve ser colocada em outra linha, então sobram
n
opções de colunas na segunda linha
Em um instância de problema das 4 rainhas, temos que o algoritmo chegou a uma folha da
state-space tree
Não há mais uma posição viável para a terceira rainha, então o algoritmo retorna para a decisão da segunda rainha, e a muda para (2, 4)
Depois disso, a terceira rainha é posta na posição (3, 2), outro beco-sem-saída
O algoritmo retorna para a decisão da segunda rainha, e vê que não há mais opções
1 more item...
A primeira e a segunda colunas representam nódulos não promissores, pois a segunda rainha estaria sob ataque da primeira
A segunda rainha é posta então na terceira coluna da segunda linha (2, 3)
Circuito Hamiltoniano
Para determinar se um grafo tem um circuito hamiltoniano, é possível contruir uma
state space tree
em que cada nódulo representa um vértice do grafo
Vértices que fazem parte de um ciclo fazem parte de mais de uma subárvore da árvore.
A partir da raiz, podemos seguir a árvore até chegar em uma folha
A partir daí, o algoritmo realiza o
back-tracking
para um nódulo parente e visita nódulos que já não foram visitados
Ao fim do algoritmo, teremos um circuito hamiltoniano que começa no nódulo usado para representar a raiz da árvore e passa por todos os outros antes de voltar ao primeiro