28 aula grafos backtracking

Prévia do material em texto

Cap. 28 - Algoritmos com Backtracking
INF05008 - Fundamentos de algoritmos
.
Instituto de Informática
Universidade Federal do Rio Grande do Sul
Porto Alegre, Brasil
http://www.inf.ufrgs.br
2011/2
.. Grafos..
.
.
▸ Um grafo é uma dado estruturado que contém um conjunto de
nodos ou vértices e um conjunto de arcos
▸ Cada arco conecta dois nodos do grafo
▸ Muitos problemas podem ser resolvidos utilizando-se grafos
como modelo de dados
Exemplo: A
 ��
C
��
Eoo
��
Boo

D F //oo G
.. INF05008 Cap. 28 - Algoritmos com Backtracking 2/33
.. Definição de Grafo..
.
.
;; Um nodo é uma lista (list nome vizinhos) onde
;; nome: símbolo
;; vizinhos: lista de símbolos
;; Um grafo é
;; 1. empty, ou
;; 2. (cons n ln), onde
;; n: nodo
;; ln: grafo
;; tal que, para cada nodo, os nodos de sua lista
;; de vizinhos pertencem ao grafo
.. INF05008 Cap. 28 - Algoritmos com Backtracking 3/33
.. Exemplo..
.
.
(define Grafo
(list (list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
.. INF05008 Cap. 28 - Algoritmos com Backtracking 4/33
.. Exemplo (cont.)..
.
.
(define Grafo
(list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
▸ (define G Grafo)
▸ (first G) ?
▸ (list 'A (list 'B 'E))
▸ (first (first G)) ?
▸ 'A
▸ (rest (first G)) ?
▸ (list (list 'B 'E))
▸ (first (rest (first G))) ?
▸ (list 'B 'E)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 5/33
.. Exemplo (cont.)..
.
.
(define Grafo
(list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
▸ (define G Grafo)
▸ (first G) ?
▸ (list 'A (list 'B 'E))
▸ (first (first G)) ?
▸ 'A
▸ (rest (first G)) ?
▸ (list (list 'B 'E))
▸ (first (rest (first G))) ?
▸ (list 'B 'E)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 5/33
.. Exemplo (cont.)..
.
.
(define Grafo
(list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
▸ (define G Grafo)
▸ (first G) ?
▸ (list 'A (list 'B 'E))
▸ (first (first G)) ?
▸ 'A
▸ (rest (first G)) ?
▸ (list (list 'B 'E))
▸ (first (rest (first G))) ?
▸ (list 'B 'E)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 5/33
.. Exemplo (cont.)..
.
.
(define Grafo
(list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
▸ (define G Grafo)
▸ (first G) ?
▸ (list 'A (list 'B 'E))
▸ (first (first G)) ?
▸ 'A
▸ (rest (first G)) ?
▸ (list (list 'B 'E))
▸ (first (rest (first G))) ?
▸ (list 'B 'E)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 5/33
.. Exemplo (cont.)..
.
.
(define Grafo
(list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
▸ (define G Grafo)
▸ (first G) ?
▸ (list 'A (list 'B 'E))
▸ (first (first G)) ?
▸ 'A
▸ (rest (first G)) ?
▸ (list (list 'B 'E))
▸ (first (rest (first G))) ?
▸ (list 'B 'E)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 5/33
.. Exemplo (cont.)..
.
.
(define Grafo
(list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
▸ (define G Grafo)
▸ (first G) ?
▸ (list 'A (list 'B 'E))
▸ (first (first G)) ?
▸ 'A
▸ (rest (first G)) ?
▸ (list (list 'B 'E))
▸ (first (rest (first G))) ?
▸ (list 'B 'E)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 5/33
.. Exemplo (cont.)..
.
.
(define Grafo
(list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
▸ (define G Grafo)
▸ (first G) ?
▸ (list 'A (list 'B 'E))
▸ (first (first G)) ?
▸ 'A
▸ (rest (first G)) ?
▸ (list (list 'B 'E))
▸ (first (rest (first G))) ?
▸ (list 'B 'E)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 5/33
.. Exemplo (cont.)..
.
.
(define Grafo
(list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
▸ (define G Grafo)
▸ (first G) ?
▸ (list 'A (list 'B 'E))
▸ (first (first G)) ?
▸ 'A
▸ (rest (first G)) ?
▸ (list (list 'B 'E))
▸ (first (rest (first G))) ?
▸ (list 'B 'E)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 5/33
.. Exemplo (cont.)..
.
.
(define Grafo
(list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
▸ (define G Grafo)
▸ (first G) ?
▸ (list 'A (list 'B 'E))
▸ (first (first G)) ?
▸ 'A
▸ (rest (first G)) ?
▸ (list (list 'B 'E))
▸ (first (rest (first G))) ?
▸ (list 'B 'E)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 5/33
.. Exercício 1..
.
.
▸ Dado um grafo e o nome de um de seus nodos, encontrar os
nodos vizinhos a este (que são destino de arcos saindo deste
nodo).
;; vizinhos: símbolo grafo -> lista-de-símbolos
;; Dados o nome de um nodo e um grafo, devolve os nomes
;; de todos os nodos que são vizinhos a este.
;; Obs.: O nodo dado deve fazer parte do grafo.
;; Exemplos:
;; (vizinhos 'C Grafo) = (list 'D)
;; (vizinhos 'A Grafo) = (list 'B 'E)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 6/33
.. Vizinhos..
.
.
;; vizinhos: símbolo grafo -> lista-de-símbolos
;; Dados o nome de um nodo e um grafo, devolve os nomes
;; de todos os nodos que são vizinhos a este.
;; Obs.: O nodo dado deve fazer parte do grafo.
;; Exemplos:
;; (vizinhos 'C Grafo) = (list 'D)
;; (vizinhos 'A Grafo) = (list 'B 'E)
(define (vizinhos n G)
(cond
[(empty? G) empty]
[(symbol=? n (first (first G)))
(first (rest (first G)))]
[else (vizinhos n (rest G))]))
.. INF05008 Cap. 28 - Algoritmos com Backtracking 7/33
.. Exercício 2..
.
.
▸ Dados um nodo origem, um nodo destino e um grafo contendo
estes nodos, devolve um caminho que leva da origem ao
destino, se existir. Se tal caminho não existir, devolve false.
;; ListaDeSímbolosOUFalse = {false} U lista-de-símbolos
;; encontra-caminho : símbolo símbolo grafo-> ListaDeSímbolosOUFalse
;; Dados os nomes de um nodo origem e um nodo destino e um grafo
;; contendo estes nodos, devolve um caminho que leva da origem
;; ao destino, se existir. Se tal caminho não existir, devolve false
;; Exemplos:
;; (encontra-caminho 'A 'A Grafo) = (list 'A)
;; (encontra-caminho 'A 'G Grafo) = (list 'A 'B 'E 'F 'G)
;; (encontra-caminho 'D 'C Grafo) = false
;; (encontra-caminho 'E 'D Grafo) = (list 'E 'C 'D)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 8/33
.. Função encontra-caminho..
.
.
;; encontra-caminho : símbolo símbolo grafo-> ListaDeSímbolosOUFalse
;; Dados os nomes de um nodo origem e um nodo destino e um grafo
;; contendo estes nodos, devolve um caminho que leva da origem ao
;; destino, se existir. Se tal caminho não existir, devolve false
(define (encontra-caminho origem destino G) ...)
Casos:
1. caso trivial – origem e destino iguais: retorna uma lista com o destino
2. caso não trivial (origem e destino diferentes): é preciso visitar todos os
vizinhos (função vizinhos !) do nodo origem e ver se há um caminho para
o destino; isto requer uma função auxiliar !
▸ consome uma lista de nodos e determina, para cada um deles, se há
ou não um caminho para o destino▸ tal função é similar à encontra-caminho mas é orientada a listas
.. INF05008Cap. 28 - Algoritmos com Backtracking 9/33
.. Função encontra-lista-caminhos..
.
.
;; encontra-lista-caminhos : lista-de-símbolos símbolo grafo
;; -> ListaDeSímbolosOUFalse
;; Dada uma lista de nomes de nodos, o nome de um nodo destino e um
;; grafo, encontra um caminho de algum dos nodos da lista para o
;; destino, usando o grafo. Se não há tal caminho, devolve false
(define (encontra-lista-caminhos lo d G) ...)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 10/33
.. Função encontra-caminho..
.
.
;; encontra-caminho : símbolo símbolo grafo-> ListaDeSímbolosOUFalse
;; Dados os nomes de um nodo origem e um nodo destino e um grafo
;; contendo estes nodos, devolve um caminho que leva da origem ao
;; destino, se existir. Se tal caminho não existir, devolve false
(define (encontra-caminho origem destino G)
(cond
[(symbol=? origem destino) (list destino)]
[else
(local
((define caminho-possível
(encontra-lista-caminhos (vizinhos origem G) destino G)))
(cond
[(boolean? ...) ... ]
[else (cons? ...)]))]))▸ os 2 casos do cond referem-se a quando encontra-lista-caminhos retorna boolean e uma
lista, respectivamente▸ no primerio caso, a resposta deve ser false▸ no segundo, deve ser um caminho entre parâmetros de origem e destino
.. INF05008 Cap. 28 - Algoritmos com Backtracking 11/33
.. Função encontra-caminho..
.
.
;; encontra-caminho : símbolo símbolo grafo-> ListaDeSímbolosOUFalse
;; Dados os nomes de um nodo origem e um nodo destino e um grafo
;; contendo estes nodos, devolve um caminho que leva da origem ao
;; destino, se existir. Se tal caminho não existir, devolve false
(define (encontra-caminho origem destino G)
(cond
[(symbol=? origem destino) (list destino)]
[else
(local
((define caminho-possível
(encontra-lista-caminhos (vizinhos origem G) destino G)))
(cond
[(boolean? caminho-possível) false]
[else (cons origem caminho-possível)]))]))
.. INF05008 Cap. 28 - Algoritmos com Backtracking 12/33
.. Função encontra-lista-caminhos..
.
.
;; encontra-lista-caminhos : lista-de-símbolos símbolo grafo
;; -> ListaDeSímbolosOUFalse
;; Dada uma lista de nomes de nodos, o nome de um nodo destino
;; e um grafo, encontra um caminho de algum dos nodos da lista
;; para o destino, usando o grafo. Se tal caminho não existir,
;; devolve false
(define (encontra-lista-caminhos lo d G)
(cond
[(empty? lo) false]
[else (local ((define caminho-possível
(encontra-caminho (first lo) d G)))
(cond
[(boolean? caminho-possível)
(encontra-lista-caminhos (rest lo) d G)]
[else caminho-possível]))]))
.. INF05008 Cap. 28 - Algoritmos com Backtracking 13/33
.. Backtracking..
.
.
▸ O algoritmo que encontra caminhos é um exemplo de algoritmo com
backtracking
▸ Ele parte de uma possível solução e, caso se verifique que a solução não é
possível, retorna a um ponto anterior da execução a fim de buscar uma
nova solução
▸ Ou seja, ele avança e retrocede conforme a solução seja ou não
verificada como possível
▸ A função encontra-lista-caminhos processa o primeiro argumento via
recursão estrutural: para cada nodo da lista, encontra-lista-caminhos
usa encontra-caminhos para checar se há um caminho
▸ se há, o caminho é a resposta▸ se não há, encontra-caminhos produz false e a função retrocede
isto é tenta o próximo da lista
.. INF05008 Cap. 28 - Algoritmos com Backtracking 14/33
.. Backtracking (cont.)..
.
.
▸ Por exemplo, considere as chamadas sucessivas necessárias à
execução de
1 (encontra-caminho ’A ’G Grafo) = 1Expr = ?????
1Def (define caminho-possível0 2 (encontra-lista-caminhos (list ’B ’E) ’G Grafo) )
= (define caminho-possível0 (list ’B ’E ’F ’G))
1Expr (cond ((boolean? caminho-possível0) false)
(else (cons ’A caminho-possível0)))
= ?????
.. INF05008 Cap. 28 - Algoritmos com Backtracking 15/33
.. Backtracking (cont.)..
.
.
2 (encontra-lista-caminhos (list ’B ’E) ’G Grafo)) = 2Expr = ?????
2Def (define caminho-possível1 3 (encontra-caminho ’B ’G Grafo) )
= (define caminho-possível1 (list ’B ’E ’F ’G))
2Expr (cond ((boolean? caminho-possível1) ...)
(else caminho-possível1)))
= ?????
3 (encontra-caminho ’B ’G Grafo) = 3Expr = ?????
3Def (define caminho-possível2 4 (encontra-lista-caminhos (list ’E ’F) ’G Grafo) )
= (define caminho-possível2 (list ’E ’F ’G))
3Expr (cond ((boolean? caminho-possível2) false)
(else (cons ’B caminho-possível2))))
= ?????
.. INF05008 Cap. 28 - Algoritmos com Backtracking 16/33
.. Backtracking (cont.)..
.
.
4 (encontra-lista-caminhos (list ’E ’F) ’G Grafo) = 4Expr = ?????
4Def (define caminho-possível3 5 (encontra-caminho ’E ’G Grafo)) )
= (define caminho-possível3 (list ’E ’F ’G))
4Expr (cond ((boolean? caminho-possível3) ...)
(else caminho-possível3) )
= ?????
5 (encontra-caminho ’E ’G Grafo)) = 5Expr = ?????
5Def (define caminho-possível4 6 (encontra-lista-caminhos (list ’C ’F) ’G Grafo) )
= (define caminho-possível4 (list ’F ’G))
5Expr (cond ((boolean? caminho-possível4) ...)
(else (cons ’E caminho-possível4) )
= ?????
.. INF05008 Cap. 28 - Algoritmos com Backtracking 17/33
.. Backtracking (cont.)..
.
.
6 (encontra-lista-caminhos (list ’C ’F) ’G Grafo) = 6Expr = ?????
6Def (define caminho-possível5 7 (encontra-caminho ’C ’G Grafo) )
= (define caminho-possível5 false)
6Expr (cond ((boolean? caminho-possível5) false)...)
(else 12 (encontra-lista-caminhos (list ’F) ’G Grafo)
= ?????
7 (encontra-caminho ’C ’G Grafo) = 7Expr = ?????
7Def (define caminho-possível6 8 (encontra-lista-caminhos (list ’D) ’G Grafo) )
= (define caminho-possível6 false)
7Expr (cond ((boolean? caminho-possível6) false)...)
= ?????
.. INF05008 Cap. 28 - Algoritmos com Backtracking 18/33
.. Backtracking (cont.)..
.
.
8 (encontra-lista-caminhos (list ’D) ’G Grafo) = 8Expr = ?????
8Def (define caminho-possível7 9 (encontra-caminho ’D ’G Grafo) )
= (define caminho-possível7 false)
8Expr (cond ((boolean? caminho-possível7) false)...)
(else 11 (encontra-lista-caminhos empty ’G Grafo)
= ?????
9 (encontra-caminho ’D ’G Grafo) = 9Expr = ?????
9Def (define caminho-possível8 10 (encontra-lista-caminhos empty ’G Grafo) )
= (define caminho-possível8 false)
9Expr (cond ((boolean? caminho-possível8) false)...)
= ?????
.. INF05008 Cap. 28 - Algoritmos com Backtracking 19/33
.. Backtracking (cont.)..
.
.
10 (encontra-lista-caminhos empty ’G Grafo) = 10Expr = false
10Def
10Expr
= false
11 (encontra-lista-caminhos empty ’G Grafo) = 11Expr = false
11Def
11Expr
= false
.. INF05008 Cap. 28 - Algoritmos com Backtracking 20/33
.. Backtracking (cont.)..
.
.
12 (encontra-lista-caminhos (list ’F) ’G Grafo) = 12 Expr = ?????
12 Def (define caminho-possível9 13 (encontra-caminho ’F ’G Grafo) )
= (define caminho-possível9 (list ’F ’G))
12 Expr (cond ((boolean? caminho-possível9) ...)
(else caminho-possível9) )
= ?????
13 (encontra-caminho ’F ’G Grafo) = 13 Expr = ?????
13 Def (define caminho-possível10 14 (encontra-lista-caminhos (list ’D ’G) ’G Grafo) )
= (define caminho-possível10 (list ’G))
13 Expr (cond ((boolean? caminho-possível10) ...)
(else (cons ’F caminho-possível10) )
= ?????
.. INF05008 Cap. 28 - Algoritmos com Backtracking 21/33
.. Backtracking (cont.)..
.
.
14 (encontra-lista-caminhos (list ’D ’G) ’G Grafo) = 14Expr = ?????
14Def (define caminho-possível11 15 (encontra-caminho ’D ’G Grafo) )
= (define caminho-possível11 false)
14Expr (cond ((boolean? caminho-possível11) false)...)
(else 16 (encontra-lista-caminhos (list ’G) ’G Grafo) )
= ?????
15 (encontra-caminho ’D ’G Grafo) = 15Expr = ?????
15Def (define caminho-possível12 16 (encontra-lista-caminhos empty ’G Grafo) ))
= (define caminho-possível12 false)
15Expr (cond ((boolean? caminho-possível12) false)...)
= ?????
.. INF05008 Cap. 28 - Algoritmoscom Backtracking 22/33
.. Backtracking (cont.)..
.
.
16 (encontra-lista-caminhos empty ’G Grafo) = 16Expr = false
16Def
16Expr
= false
17 (encontra-lista-caminhos (list ’G) ’G Grafo) = 17Expr = ?????
17Def (define caminho-possível13 18 (encontra-caminho ’G ’G Grafo) )
= (define caminho-possível13 (list ’G))
17Expr (cond ((boolean? caminho-possível13) ...)
(else caminho-possível13) )
= ?????
18 (encontra-caminho ’G ’G Grafo) = 18Expr = (list 'G)
18Def
18Expr (cond ((symbol=? ’G ’G) (list ’G)) ...)
= (list 'G)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 23/33
.. Backtracking (cont.)..
.
.
17 (encontra-lista-caminhos (list ’G) ’G Grafo) = 17Expr = (list 'G)
17Def (define caminho-possível13 18 (encontra-caminho ’G ’G Grafo) )
= (define caminho-possível13 (list ’G))
17Expr (cond ((boolean? caminho-possível13) ...)
(else caminho-possível13) )
= (list 'G)
15 (encontra-caminho ’D ’G Grafo) = 15Expr = false
15Def (define caminho-possível12 16 (encontra-lista-caminhos empty ’G Grafo) ))
= (define caminho-possível12 false)
15Expr (cond ((boolean? caminho-possível12) false)...)
= false
.. INF05008 Cap. 28 - Algoritmos com Backtracking 24/33
.. Backtracking (cont.)..
.
.
14 (encontra-lista-caminhos (list ’D ’G) ’G Grafo) = 14Expr = (list 'G)
14Def (define caminho-possível11 15 (encontra-caminho ’D ’G Grafo) )
= (define caminho-possível11 false)
14Expr (cond ((boolean? caminho-possível11) false)...)
(else 16 (encontra-lista-caminhos (list ’G) ’G Grafo) )
= (list 'G)
13 (encontra-caminho ’F ’G Grafo) = 13 Expr = (list 'F 'G)
13 Def (define caminho-possível10 14 (encontra-lista-caminhos (list ’D ’G) ’G Grafo) )
= (define caminho-possível10 (list ’G))
13 Expr (cond ((boolean? caminho-possível10) ...)
(else (cons ’F caminho-possível10) )
= (list 'F 'G)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 25/33
.. Backtracking (cont.)..
.
.
12 (encontra-lista-caminhos (list ’F) ’G Grafo) = 12 Expr = (list 'F 'G)
12 Def (define caminho-possível9 13 (encontra-caminho ’F ’G Grafo) )
= (define caminho-possível9 (list ’F ’G))
12 Expr (cond ((boolean? caminho-possível9) ...)
(else caminho-possível9) )
= (list 'F 'G)
9 (encontra-caminho ’D ’G Grafo) = 9Expr = false
9Def (define caminho-possível8 10 (encontra-lista-caminhos empty ’G Grafo) )
= (define caminho-possível8 false)
9Expr (cond ((boolean? caminho-possível8) false)...)
= false
.. INF05008 Cap. 28 - Algoritmos com Backtracking 26/33
.. Backtracking (cont.)..
.
.
8 (encontra-lista-caminhos (list ’D) ’G Grafo) = 8Expr = false
8Def (define caminho-possível7 9 (encontra-caminho ’D ’G Grafo) )
= (define caminho-possível7 false)
8Expr (cond ((boolean? caminho-possível7) false)...)
(else 11 (encontra-lista-caminhos empty ’G Grafo)
= false
7 (encontra-caminho ’C ’G Grafo) = 7Expr = false
7Def (define caminho-possível6 8 (encontra-lista-caminhos (list ’D) ’G Grafo) )
= (define caminho-possível6 false)
7Expr (cond ((boolean? caminho-possível6) false)...)
= false
.. INF05008 Cap. 28 - Algoritmos com Backtracking 27/33
.. Backtracking (cont.)..
.
.
6 (encontra-lista-caminhos (list ’C ’F) ’G Grafo) = 6Expr = (list 'F 'G)
6Def (define caminho-possível5 7 (encontra-caminho ’C ’G Grafo) )
= (define caminho-possível5 false)
6Expr (cond ((boolean? caminho-possível5) false)...)
(else 12 (encontra-lista-caminhos (list ’F) ’G Grafo)
= (list 'F 'G)
5 (encontra-caminho ’E ’G Grafo)) = 5Expr = (list 'E 'F 'G)
5Def (define caminho-possível4 6 (encontra-lista-caminhos (list ’C ’F) ’G Grafo) )
= (define caminho-possível4 (list ’F ’G))
5Expr (cond ((boolean? caminho-possível4) ...)
(else (cons ’E caminho-possível4) )
= (list 'E 'F 'G)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 28/33
.. Backtracking (cont.)..
.
.
4 (encontra-lista-caminhos (list ’E ’F) ’G Grafo) = 4Expr = (list 'E 'F 'G)
4Def (define caminho-possível3 5 (encontra-caminho ’E ’G Grafo)) )
= (define caminho-possível3 (list ’E ’F ’G))
4Expr (cond ((boolean? caminho-possível3) ...)
(else caminho-possível3) )
= (list 'E 'F 'G)
3 (encontra-caminho ’B ’G Grafo) = 3Expr = (list 'B 'E 'F 'G)
3Def (define caminho-possível2 4 (encontra-lista-caminhos (list ’E ’F) ’G Grafo) )
= (define caminho-possível2 (list ’E ’F ’G))
3Expr (cond ((boolean? caminho-possível2) false)
(else (cons ’B caminho-possível2))))
= (list 'B 'E 'F 'G)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 29/33
.. Backtracking (cont.)..
.
.
2 (encontra-lista-caminhos (list ’B ’E) ’G Grafo)) = 2Expr = (list 'B 'E 'F 'G)
2Def (define caminho-possível1 3 (encontra-caminho ’B ’G Grafo) )
= (define caminho-possível1 (list ’B ’E ’F ’G))
2Expr (cond ((boolean? caminho-possível1) ...)
(else caminho-possível1)))
= (list 'B 'E 'F 'G)
1 (encontra-caminho ’A ’G Grafo) = 1Expr = (list 'A 'B 'E 'F 'G)
1Def (define caminho-possível0 2 (encontra-lista-caminhos (list ’B ’E) ’G Grafo) )
= (define caminho-possível0 (list ’B ’E ’F ’G)
1Expr (cond ((boolean? caminho-possível0) false)
(else (cons ’A caminho-possível0)))
= (list 'A 'B 'E 'F 'G)
.. INF05008 Cap. 28 - Algoritmos com Backtracking 30/33
.. Questão:..
.
.
Considere o seguinte grafo:
A
 ��
B
��
C

D
OO
// E
__
(define gr2
(list
(list 'A (list 'B 'C))
(list 'B (list 'D))
(list 'C (list 'D))
(list 'D (list 'A 'E))
(list 'E (list 'C ))))
O que ocorre quando fazemos a seguinte chamada?
(encontra-caminho 'A 'E gr2 )
.. INF05008 Cap. 28 - Algoritmos com Backtracking 31/33
.. Problema de encontra-caminho..
.
.
Problema: ao alcançar o nodo 'D, nós fazemos uma chamada a
(encontra-caminho 'A 'E gr2 )
que é a chamada original!
Consequência:
▸ Loop infinito na execução!
▸ Algoritmo funciona somente para grafos acíclicos!
Pergunta: como corrigir esse problema?
.. INF05008 Cap. 28 - Algoritmos com Backtracking 32/33
.. Exercício:..
.
.
1. Corrija as funções encontra-caminho e encontra-lista-caminhos
para que funcionem adequadamente em grafos com ciclos (evitando laços
infinitos).
Dica: vocês precisam registrar por onde já passaram à medida que
chamam a recursão, para evitar chamadas repetidas (com os mesmos
argumentos) à função encontra-caminho ….
2. Faça um algoritmo encontra-todos-os-caminhos, que dados dois
nodos origem e destino e um grafo (possivelmente cíclico), retorne uma
lista com todos os possíveis caminhos entre os nodos.
.. INF05008 Cap. 28 - Algoritmos com Backtracking 33/33