11.3. Backtracking
11.3. Backtracking
Idéia Geral: 4 Pesquisa recursiva em um conjunto de dados
para resolver um problema. Ex.: Caixeiro Viajante
- Para cada chamada recursiva existem diversas opções
que podem ser seguidas
Ex.: Muitos vértices podem ser o próximo.
- Diversos dados do subconjunto de dados de entrada ainda não
incluídos na solução são candidatos.
Pode ser que todos sejam.
Pode existir uma restrição (constraint) reduzindo o número
de candidatos.
Ex.: Só vértices vizinhos são candidatos a serem o
próximo.
- O algoritmo pode tentar uma chamada recursiva para cada um
dos candidatos (solução para pesquisa exaustiva).
Ex.: O Caixeiro Viajante tenta todos os caminhos.
- O algoritmo pode escolher um ou poucos dados segundo um critério
qualquer.
- O processo de busca cria uma árvore de chamadas recursivas.
Ex.: Todos os caminhos parciais do caixeiro viajante.
- Folhas dessa árvore são de dois tipos:
- Representam uma possível solução para o problema.
- Representam um ponto onde o algoritmo não pôde mais ir
adiante (failure) sem ferir alguma precondição para que a
solução gerada até então seja válida.
Ex.: Caminho encontrado até agora é muito longo, embora aind
aexistam vértices por percorrer.
11.3.1. Vantagens
- Forma bastante fácil de implementar um problema que de outra
forma seria muito mais complexo de se resolver.
- Linguagens da Área de Programação em Lógica
(PROLOG, KL-ONE, OPS5) geralmente trazem algum mecanismo embutido que dá
suporte ao backtracking.
11.3.2. Desvantagens
- Programas de backtracking, a não ser que se programe restrições
(constraints) executam sempre uma busca exaustiva
e tenderão à explosão combinatória.
Programas de Backtracking são por natureza, Combinatórios
!
- Necessitam de muita memória no Stack, já
que a quantidade de variáveis locais transportada por cada chamada
recursiva é diretamente proporcional ao tamanho do problema.
Isto significa que a quantidade de memória requerida para um programa
de backtracking pode crescer exponencialmente com o tamanho do problema.
11.3.3. Caracterírtica marcante do Back-Tracking
4 Como o nome diz, retornar pelo caminho, os algoritmos de backtracking
constroem sempre o conjunto de solução ao retornarem das
chamadas recursivas.
11.3.4. Algoritmo Caixeiro Viajante
Caixeiro(conjSolução, nãoVisitados, caminho, limite)
variáveis
aVisitar
início
SE nãoVisitados não está vazio ENTÃO
aVisitar <- nãoVisitados.
PARA cada vértice V em aVisitar FAÇA
Retire V de aVisitar.
SE V é adjacente ao último(caminho) ENTÃO
SE comprimento(caminho)+
distância(V,ultimo(caminho)) < limite ENTÃO
soluçãoPar<-Caixeiro((),(nãoVisitados-V),
(caminho + V), limite).
adicione soluçãoPar ao conjSolução.
FIM SE
FIM SE
FIM PARA
RETORNE conjSolução.
SEN[Atilde]O
SE primeiro(caminho) é adjacente a ultimo(caminho) ENT[Atilde]O
SE comprimento(caminho)+
distância(primeiro(caminho),ultimo(caminho)) <
limite ENTÃO
adicione primeiro(caminho) a caminho.
inclua caminho no conjSolução.
RETORNE conjSolução.
FIM SE
FIM SE
RETORNE conjSolução.
FIM SE
fim
11.3.5. Caracterírtica marcante do Back-Tracking
- Como o nome diz, retornar pelo caminho, os algoritmos de backtracking
constroem sempre o conjunto de solução ao retornarem das
chamadas recursivas.