ads:
Universidade Federal de Santa Catarina
Curso de P
´
os-Graduac¸
˜
ao em Matem
´
atica e Computac¸
˜
ao Cient
´
ıfica
Algoritmos de Busca de Caminhos em Grafos aplicados
aos problemas: Alinhamento de Prote
´
ınas e
Quebra-cabec¸a de 15 pec¸as
Diane Rizzotto Rossetto
Orientador: Prof. Dr. Cl
´
ovis Caesar Gonzaga
Florian
´
opolis
2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Universidade Federal de Santa Catarina
Curso de P
´
os-Graduac¸
˜
ao em Matem
´
atica e Computac¸
˜
ao Cient
´
ıfica
Algoritmos de Busca de Caminhos em Grafos aplicados
aos problemas: Alinhamento de Prote
´
ınas e
Quebra-cabec¸a de 15 pec¸as
Dissertac¸
˜
ao apresentada ao Curso de P
´
os
Graduac¸
˜
ao em Matem
´
atica e Computac¸
˜
ao
Cient
´
ıfica, do Centro de Ci
ˆ
encias F
´
ısicas e
Matem
´
aticas da Universidade Federal de Santa
Catarina, para obtenc¸
˜
ao do grau de Mestre em
Matem
´
atica, com
´
Area de Concentrac¸
˜
ao em
Matem
´
atica Aplicada.
Diane Rizzotto Rossetto
Florian
´
opolis
2007
ads:
Algoritmos de Busca de Caminhos em Grafos aplicados aos problemas:
Alinhamento de Prote
´
ınas e Quebra-cabec¸a de 15 pec¸as
por
Diane Rizzotto Rossetto
Esta Dissertac¸
˜
ao foi julgada adequada para obtenc¸
˜
ao do T
´
ıtulo de “Mestre
em Matem
´
atica”,
´
Area de Concentrac¸
˜
ao em Matem
´
atica Aplicada, e aprovada em sua
forma final pelo Curso de P
´
os-Graduac¸
˜
ao em Matem
´
atica e Computac¸
˜
ao Cient
´
ıfica.
Prof. Dr. Cl
´
ovis Caesar Gonzaga
(Coordenador)
Comiss
˜
ao Examinadora
Prof. Dr. Cl
´
ovis Caesar Gonzaga
(MTM - UFSC, Orientador)
Prof. Dr. Paulo Jos
´
e da Silva e Silva
(IME - USP)
Prof. Dr. J
´
auber Cavalcante de Oliveira
(MTM - UFSC)
Prof. Dr. Juliano de Bem Francisco
(MTM - UFSC)
Fevereiro de 2007
Aos meus pais, Caetano e Terezinha...
...“o amor n
˜
ao falha e a vida n
˜
ao falhar
´
a enquanto
houver amor”.
Agradecimentos
Durante estes tr
ˆ
es anos em Florian
´
opolis aprendi muitas coisas, tive muitas
alegrias e tamb
´
em momentos tristes, mas nunca estava sozinha, sempre havia perto de
mim algu
´
em para me fazer sorrir. Por isso gostaria muito de agradec
ˆ
e-los...
Aos meus pais Caetano e Terezinha por serem “o porto seguro” em minha
vida, sempre me apoiando, me guiando, me acolhendo e principalmente acreditando em
mim. A voc
ˆ
es papai e mam
˜
ae queridos todo o meu amor.
Ao meu irm
˜
ao Diego com quem compartilhei os momentos mais incr
´
ıveis
da minha inf
ˆ
ancia. A minha irm
˜
a Da
´
ısa, o melhor presente que a vida me deu, amorosa
e meiga, sempre lembrando-me que algu
´
em no mundo precisava muito de mim. A voc
ˆ
es
irm
˜
aos queridos pec¸o a Deus que sempre os mantenham perto de mim.
Ao meu noivo Patrick, a pessoa que esteve presente em todos os momentos
desta jornada, entendendo as horas ausentes, me incentivando e com muito amor e carinho
sempre me deixando feliz.
Aos meus av
ˆ
os Tranquilo e Jos
´
e, que j
´
a partiram, mas deixaram exemplos
dos valores que eu devia seguir. As minhas av
´
os Ancila e Tecla, que ao longo de seus
noventa anos ainda s
˜
ao os maiores exemplos de forc¸a e garra.
Gostaria de agradecer aos demais familiares aos quais se uniram a mim por
um sentimento muito mais nobre que
´
e a amizade.
Aos amigos que deixei em Nonoai, aos que fiz durante a faculdade em
Chapec
´
o e aos que aqui conquistei, obrigada pelo ombro amigo e por compartilharem
comigo meus instantes.
Aos colegas da p
´
os-graduac¸
˜
ao,
`
a voc
ˆ
es que sabem tanto quanto eu como
n
˜
ao
´
e f
´
acil chegar at
´
e aqui, obrigada por tamb
´
em me ajudarem a crescer nas nossas lon-
gas discuss
˜
oes sobre listas e teoremas, por n
˜
ao me deixar sozinha nos momentos de
inseguranc¸a e acima de tudo pelas tantas vezes que nossos bate-papos foram essenciais
iv
para prosseguir. A voc
ˆ
es amigos parab
´
ens por estarmos todos aqui.
Um agradecimento especial ao colega otimizador Rafael Casali que me
ensinou muito sobre Matlab, Tex e Linux, e pelas discuss
˜
oes bem humoradas sobre grafos,
joguinhos e prote
´
ınas.
Aos professores da UNOCHAPEC
´
O que sempre me incentivaram a conti-
nuar os estudos. Aos professores da UFSC que conheci durante o nivelamento e o mes-
trado minha gratid
˜
ao por tudo aquilo que possibilitaram que eu aprendece, agradecimento
especial
`
aqueles que al
´
em disto se fizeram amigos compartilhando suas experi
ˆ
encias.
A CAPES (Centro de Apoio a Pesquisa) pelo apoio financeiro.
A secret
´
aria da p
´
os-graduac¸
˜
ao, Elisa Amaral pela dedicac¸
˜
ao com que nos
serve.
Aos professores que participaram da banca agradec¸o por aceitarem corrigir
este trabalho.
Finalmente ao professor mais apaixonante que eu j
´
a encontrei, Cl
´
ovis Cae-
sar Gonzaga, pela maneira envolvente que conduz seus alunos e suas aulas, minha admi-
rac¸
˜
ao pela maneira respons
´
avel que conduz sua vida de cientista, tamb
´
em pelo amigo e
conselheiro que torna-se ao nos orientar.
v
Sum
´
ario
Lista de Figuras viii
Resumo ix
Abstract x
Introduc¸
˜
ao 1
1 Introduc¸
˜
ao a Teoria de Grafos 3
1.1 Principais conceitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Conceitos em grafos n
˜
ao orientados . . . . . . . . . . . . . . . . . . . . 6
1.3 Conceitos em grafos orientados . . . . . . . . . . . . . . . . . . . . . . . 8
2 Algoritmos de Busca de Caminhos 9
2.1 Princ
´
ıpio de Otimalidade de Bellman para Grafos . . . . . . . . . . . . . 10
2.2 Algoritmos de Rotulac¸
˜
ao . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Algoritmo de Busca Horizontal . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Algoritmo de Busca em Profundidade . . . . . . . . . . . . . . . . . . . 17
2.5 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Algoritmo A
∗
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6.1 Estimativa admiss
´
ıvel . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6.2 Estimativa consistente . . . . . . . . . . . . . . . . . . . . . . . 24
3 Alinhamento de Prote
´
ınas 26
3.1 Definic¸
˜
ao do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Definindo o grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1 N
´
o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 Ramo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.3 Alvo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Operador sucessor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4 Caminho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
vi
3.5 Super-estimativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.6 Testes num
´
ericos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.6.1 An
´
alise dos testes . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 O quebra-cabec¸a de 15 pec¸as 43
4.1 Definindo o grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.1.1 N
´
o e Ramo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Operador sucessor e custo . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 Caminho e custo de um caminho . . . . . . . . . . . . . . . . . . . . . . 48
4.4 Sub-estimativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.5 Estrutura de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.6 Testes num
´
ericos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.6.1 An
´
alise dos testes . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.7 Uma nova sub-estimativa . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.7.1 Novos testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.7.2 An
´
alise dos testes . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Conclus
˜
ao 63
A Heap 64
Refer
ˆ
encias Bibliogr
´
aficas 67
vii
Lista de Figuras
1.1 Pontes de Konisberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Exemplo de grafo infinito . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Grafo com ramos m
´
ultiplos . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 (a) Grafo, (b) Grafo parcial, (c) Subgrafo . . . . . . . . . . . . . . . . . . 6
1.5 Grafo desconexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6
´
Arvore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Caminhos guardados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Busca Horizontal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Arboresc
ˆ
encia maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Busca em Profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Grafo inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Grafo final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1 Prote
´
ına . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Emparelhamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Ilustrac¸
˜
ao do lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Definic¸
˜
ao do n
´
o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.5 Representac¸
˜
ao do grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1 Quebra-cabec¸a de 15 pec¸as . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Grafo do quebra-cabec¸a . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3 Representac¸
˜
ao do n
´
o . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4 Estimativa entre o n
´
o n e o n
´
o t . . . . . . . . . . . . . . . . . . . . . . . 50
4.5 Variac¸
˜
ao da estimativa . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.6 Representac¸
˜
ao da nova estimativa . . . . . . . . . . . . . . . . . . . . . 58
A.1 2-Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
viii
Resumo
Neste trabalho foram estudados alguns conceitos fundamentais da Teoria
de Grafos para o entendimento dos algoritmos de Busca de Caminhos em Grafos. Es-
tudamos os algoritmos de Busca Horizontal, Busca em Profundidade, Dijkstra e A
∗
. Na
aplicac¸
˜
ao do problema do alinhamento de prote
´
ınas usamos o algoritmo A
∗
para construir
um emparelhamento entre os
´
atomos de carbono de duas prote
´
ınas. Nosso objetivo era
tornar este algoritmo mais r
´
apido que o algoritmo de Programac¸
˜
ao Din
ˆ
amica, que
´
e na
literatura o algoritmo padr
˜
ao para obter tal emparelhamento. Os algoritmos de Dijkstra
e A
∗
foram aplicados ao problema do quebra-cabec¸a de 15 pec¸as. Notamos que devido
ao espac¸o de busca ser muito grande, o algoritmo A
∗
teve desempenho muito melhor que
o algoritmo de Dijkstra, isto porque A
∗
faz uso de uma informac¸
˜
ao heur
´
ıstica. Mesmo
assim a estimativa conhecida n
˜
ao
´
e suficiente para resolver este problema. Apresentamos
uma nova estimativa com que obtivemos resultados muito melhores mas que ainda n
˜
ao faz
com que o algoritmo A
∗
resolva todas as inst
ˆ
ancias do problema usando nossos recursos
computacionais.
ix
Abstract
In this work we study some fundamental concepts in Graph Theory nee-
ded to understand graph search algorithms. We studied breadth-first, depth-first, Dijkstra
and A* algorithms. In the application to protein alignment we used the A* algorithm to
construct a matching between the carbon atoms of two given proteins. Our objective was
to obtain an algorithm faster than Dynamic Programming, which appears in the literature
as the standard method for this matching. Dijkstra’s algorithm and A* were applied to
solving the fifteen puzzle. We noted that A* had a much better performance than Dijks-
tra, due to the use of the heuristic information. Even using this information, A* was not
capable of solving the problem, and then we developed a process for obtaining better es-
timated costs. These estimates greatly improved the results, but were still unable to solve
all instances of the problem with our computational resources.
x
Introduc¸
˜
ao
Esta dissertac¸
˜
ao iniciou a partir do interesse despertado pela teoria de
otimizac¸
˜
ao em grafos durante o curso de Pesquisa Operacional ministrado pelo profes-
sor Cl
´
ovis Gonzaga durante o segundo semestre de 2005.
Durante este curso tive meu primeiro contato com a teoria necess
´
aria para
o estudo dos algoritmos de busca de caminhos em grafos, na oportunidade estudei os
algoritmos de Busca Horizontal, Busca em Profundidade e Dijkstra. Neste curso tamb
´
em
tive a oportunidade de ver a correspond
ˆ
encia entre o algoritmo de Busca Horizontal e o
algoritmo de Programac¸
˜
ao Din
ˆ
amica Progressiva para problemas discretos, na ocasi
˜
ao o
exemplo tratava-se da decis
˜
ao da quantidade de
´
agua a ser utilizada na gerac¸
˜
ao de energia
em uma usina hidrel
´
etrica.
Assim como no exemplo acima a modelagem de grafos a problemas reais
´
e muito interessante, permitindo adaptar problemas complexos a representac¸
˜
oes simples
e gerais.
Entretanto em muitos problemas o grafo que o modela pode tornar-se
muito grande e consequentemente o espac¸o de busca
´
e muito vasto. Desta maneira, os
algoritmos citados acima podem n
˜
ao ser suficientes para resolver determinados proble-
mas. Um exemplo
´
e o problema do quebra-cabec¸a de 15 pec¸as que foi abordado por n
´
os
no quarto cap
´
ıtulo.
Com a informac¸
˜
ao que o algoritmo A
∗
com heur
´
ısticas convenientes en-
contra um caminho
´
otimo com um n
´
umero menor de expans
˜
oes que qualquer outro algo-
ritmo de rotulac¸
˜
ao (Busca Horizontal, Busca em Profundidade e Dijkstra) iniciamos em
2006 o estudo deste algoritmo.
O desenvolvimento deste algoritmo, originado no contexto de Intelig
ˆ
encia
Artificial, comec¸ou com o seguinte problema: em uma sala encontra-se um rob
ˆ
o, deseja-
se que ele atravesse a sala percorrendo o menor caminho poss
´
ıvel sem bater nos m
´
oveis.
Assim, os cantos dos m
´
oveis bem como a entrada e a sa
´
ıda da sala s
˜
ao interpretados
como os n
´
os do grafo, as retas sobre as quais o rob
ˆ
o pode se movimentar entre os n
´
os s
˜
ao
os ramos do grafo. Para encontrar o menor caminho que ele deve percorrer para chegar
at
´
e a sa
´
ıda da sala, em cada n
´
o estima-se quanto ele ainda precisa movimentar-se para
chegar ao destino se prosseguir num caminho atrav
´
es deste n
´
o, obviamente o caminho
com menor estimativa
´
e o escolhido para ele continuar. Neste problema a estimativa
usada foi a dist
ˆ
ancia em linha reta entre o n
´
o terminal do caminho e o n
´
o que representa
a sa
´
ıda da sala.
Neste trabalho aplicamos as t
´
ecnicas de busca de caminhos de custos
´
otimos
em um grafo a dois problemas bem distintos.
O primeiro, na
´
area de Biologia Estrutural,
´
e um sub-problema do pro-
blema de alinhamento de prote
´
ınas. Estudam-se m
´
etodos de alinhamento para medir o
grau de semelhanc¸a entre duas prote
´
ınas, atrav
´
es de uma func¸
˜
ao de pontuac¸
˜
ao. Em nosso
estudo buscamos o emparelhamento entre duas prote
´
ınas que obtem a maior pontuac¸
˜
ao
poss
´
ıvel, sendo assim buscamos o maior caminho em um grafo que represente o problema.
Em geral este emparelhamento
´
e feito utilizando Programac¸
˜
ao Din
ˆ
amica, desta forma a
modelagem feita por n
´
os
´
e nova.
O segundo, de Intelig
ˆ
encia Artificial, busca determinar o n
´
umero m
´
ınimo
de movimentos necess
´
arios para resolver o quebra-cabec¸a de 15 pec¸as a partir de uma
configurac¸
˜
ao dada arbitr
´
aria. A estimativa conhecida, baseada na dist
ˆ
ancia de Manhattan,
para este problema n
˜
ao
´
e suficiente para resolv
ˆ
e-lo, utilizando um algoritmo bem geral,
pois em muitos casos o erro em relac¸
˜
ao ao custo
´
otimo
´
e grande. Desta forma no cap
´
ıtulo
quatro propomos uma nova estimativa em que os resultados obtidos foram melhores mas
ainda n
˜
ao suficientes para resolver este problema usando o algoritmo A
∗
.
Por
´
em existem trabalhos que apresentam soluc¸
˜
oes para este problema usan-
do outras t
´
ecnicas. Em [8] Korf e Felner descrevem como encontraram soluc¸
˜
oes
´
otimas
para o quebra-cabec¸a usando o algoritmo IDA
∗
, que
´
e uma variac¸
˜
ao do algoritmo A
∗
.
Em [5] Culberson e Schaeffer resolver este problema com algoritmos feitos explorando
propriedades espec
´
ıficas do quebra-cabec¸a de 15 pec¸as.
2
Cap
´
ıtulo 1
Introduc¸
˜
ao a Teoria de Grafos
Iniciamos com alguns conceitos e resultados que entendemos ser suficien-
tes para o estudo de otimizac¸
˜
ao em grafos, em especial ao problema de busca de caminhos
em grafos que
´
e o nosso objeto de estudo. A nomenclatura e as notac¸
˜
oes que padroniza-
remos agora, assim com as demonstrac¸
˜
oes dos teoremas seguem de [12] e [13].
A teoria de grafos
´
e uma das ferramentas matem
´
aticas mais simples e po-
derosas usadas para construc¸
˜
ao de modelos e resoluc¸
˜
ao de problemas, tais como: fluxos
em redes, escolha de uma rota
´
otima, t
´
atica e log
´
ıstica.
A mais antiga citac¸
˜
ao sobre a teoria ocorreu no ano de 1736, atrav
´
es do
matem
´
atico suic¸o Leonhard Euler em seu artigo “The Seven Bridges of K
¨
onigsberg”.
Em K
¨
onisberg, Alemanha, havia uma ilha, um rio que passava pela cidade
e que logo ap
´
os passar por esta linha se bifurcava. Sobre este rio havia sete pontes, a
pergunta era:
´
e poss
´
ıvel passar pelas sete pontes numa caminhada cont
´
ınua sem passar
duas vezes por qualquer uma das pontes?
Figura 1.1: Pontes de Konisberg
Euler analisou o problema trocando as
´
areas de terra por pontos (n
´
os) e
as pontes por arcos (ramos), e modelando desta forma provou que o problema n
˜
ao tinha
3
soluc¸
˜
ao, uma an
´
alise de como Euler chegou a esta conclus
˜
ao pode ser vista em [15]. Teve
in
´
ıcio assim o que hoje conhecemos como Teoria de Grafos.
Por
´
em o desenvolvimento desta teoria veio se dar somente na segunda me-
tade do s
´
eculo XX, sob o impulso das aplicac¸
˜
oes de otimizac¸
˜
ao organizacional. Tal de-
senvolvimento se deu com a invenc¸
˜
ao do computador, sem o qual a maioria das aplicac¸
˜
oes
em grafos seria imposs
´
ıvel.
1.1 Principais conceitos
Definic¸
˜
ao 1.1. Um grafo
´
e caracterizado por um par G = (N , M) em que N
´
e um
conjunto enumer
´
avel e M
´
e um conjunto de pares ordenados de elementos de N , M ⊂
N × N ,
N
´
e um conjunto (n
1
, n
2
, n
3
, ...) n
˜
ao vazio de n
´
os.
M
´
e o conjunto dos ramos r = (n
i
, n
j
) em que n
i
´
e a extremidade inicial
e n
j
a extremidade final, com r ∈ N × N .
G
´
e um grafo finito se N e M forem finitos.
Figura 1.2: Exemplo de grafo infinito
G
´
e um grafo simples se n
˜
ao existirem ramos diferentes associados aos
mesmos n
´
os, assim dizemos que ele n
˜
ao possui ramos m
´
ultiplos. Neste trabalho s
´
o consi-
deramos grafos simples pois em problemas de busca de caminhos, ramos m
´
ultiplos podem
sempre ser eliminados.
4
Figura 1.3: Grafo com ramos m
´
ultiplos
Definic¸
˜
ao 1.2. O n
´
o n
´
e adjacente ao ramo r se n
´
e uma extremidade de r.
Observac¸
˜
ao 1.3. Dizemos que um n
´
o n
i
´
e a cauda do ramo r
i
se ele
´
e o n
´
o inicial do
ramo. Se n
j
´
e a extremidade final do ramo r
i
dizemos que ele
´
e a cabec¸a do ramo.
Definic¸
˜
ao 1.4. r ∈ M
´
e incidente a n ∈ N se e somente se n
´
e cabec¸a ou cauda de r.
Definic¸
˜
ao 1.5. Dados n, ¯n ∈ N , dizemos que ¯n
´
e sucessor de n se e somente se (n, ¯n) ∈
M.
Dizemos que P
´
e o conjunto das partes dos elementos de N .
Definic¸
˜
ao 1.6. Operador Sucessor
´
e uma aplicac¸
˜
ao Γ : N → P(N ) em que ¯n ∈ Γ(n) se
e somente se ¯n
´
e sucessor de n.
Γ
´
e uma regra para a construc¸
˜
ao dos sucessores. Um grafo simples pode
ser caracterizado por seu operador sucessor, assim uma nova designac¸
˜
ao do grafo G
´
e
dada por G = (N , Γ), desprezando a descric¸
˜
ao dos ramos.
Definic¸
˜
ao 1.7. G
= (N , M
)
´
e um grafo parcial de G(N , M) se e somente se G
=
(N , M
) com M
⊂ M.
Definic¸
˜
ao 1.8. Um grafo G
= (N
, M
)
´
e subgrafo de G = (N , M) se e somente se
N
⊂ N e M
= {(n
i
, n
j
)/n
i
, n
j
∈ N
e (n
i
, n
j
) ∈ M}.
5
Figura 1.4: (a) Grafo, (b) Grafo parcial, (c) Subgrafo
Por nossa definic¸
˜
ao os grafos s
˜
ao sempre orientados, j
´
a que os ramos s
˜
ao
pares ordenados. Para definir grafo n
˜
ao orientado, basta n
˜
ao utilizar a orientac¸
˜
ao, ou
definir os n
´
os como pares n
˜
ao orientados {n
i
, n
j
}, ou ainda exigir que sempre estejam
presentes os ramos (n
i
, n
j
) e (n
j
, n
i
).
1.2 Conceitos em grafos n
˜
ao orientados
Definic¸
˜
ao 1.9. Uma sequ
ˆ
encia C = (n
1
, r
1
, n
2
, r
2
, ..., n
p
, r
p
, n
p+1
)
´
e uma cadeia (ligando
n
1
a n
p+1
) se existir uma sequ
ˆ
encia de n
´
os (n = n
1
, n
2
, ..., n
p+1
), tais que r
i
´
e adjacente
a n
i
e n
i+1
, i = 1, ..., p.
Dizemos que os n
´
os n e ¯n est
˜
ao ligados se existe uma cadeia entre eles.
Definic¸
˜
ao 1.10. Um grafo G = (N , M)
´
e conexo se quaisquer dois n
´
os s
˜
ao ligados por
alguma cadeia, caso contr
´
ario o grafo
´
e dito desconexo.
Figura 1.5: Grafo desconexo
6
Definic¸
˜
ao 1.11. G
= (N
, M
)
´
e uma componente conexa de G = (N , M) se e somente
se G
´
e um subgrafo conexo de G e nenhum n
´
o de G
´
e ligado a nenhum n
´
o em N − N
.
Um subgrafo conexo maximal de G
´
e uma componente conexa de G.
Definic¸
˜
ao 1.12. Um ciclo
´
e uma cadeia de um n
´
o n a ele mesmo.
Definic¸
˜
ao 1.13. Uma
´
arvore
´
e um grafo conexo sem ciclos.
Figura 1.6:
´
Arvore
Definic¸
˜
ao 1.14. Uma folha
´
e um n
´
o com no m
´
aximo um ramo incidente.
Na figura 1.6 os n
´
os n
4
, n
6
, n
8
, n
9
, n
10
, n
11
e n
12
s
˜
ao folhas.
Lema 1.15. Toda
´
arvore tem folhas.
Teorema 1.16. Uma
´
arvore com n n
´
os tem exatamente n − 1 ramos.
Demonstrac¸
˜
ao:
Seja G = (N , M) uma
´
arvore com n n
´
os e m ramos. Como G tem uma folha ¯n, G
=
(N − {¯n}, M−{¯r}), com ¯r ramo ligado a ¯n,
´
e uma
´
arvore com n −1 n
´
os e m −1 ramos.
Por recorr
ˆ
encia, chega-se a um grafo com apenas um n
´
o e nenhum ramo
ap
´
os n − 1 passos.
Teorema 1.17. Seja G = (N , M) uma
´
arvore. Ent
˜
ao qualquer par de n
´
os n, ¯n
´
e ligado
por uma
´
unica cadeia.
Demonstrac¸
˜
ao:
Suponha que existe um par de n
´
os n, ¯n que est
´
a ligado por duas cadeias distintas.
n = n
1
, r
1
, n
2
, r
2
, ..., n
p
= ¯n, n = n
1
, r
1
, n
2
, r
2
, ..., n
p
= ¯n
7
Se r
1
= r
1
, fac¸amos n = n
2
e reindexamos as cadeias. Repetindo o processo chegamos a
situac¸
˜
ao em que r
1
= r
1
.
Se n
2
= n
2
chegamos a um ciclo n, r
1
, n
2
, n
2
, r
1
, n.
Sen
˜
ao buscamos o primeiro n
´
o comum as cadeias, sabemos que existe pois n
p
= n
p
, e
assim chegamos a um ciclo.
Mas isto contradiz a definic¸
˜
ao de
´
arvore.
1.3 Conceitos em grafos orientados
Definic¸
˜
ao 1.18. Um caminho de n ∈ N a ¯n ∈ N
´
e uma sequ
ˆ
encia (n = n
1
, n
2
, ...,
n
p
= ¯n) de n
´
os tais que (n
i
, n
i+1
) ∈ M, i = 1, ..., p − 1.
Definic¸
˜
ao 1.19. ¯n ∈ N
´
e acess
´
ıvel a partir de n se existir um caminho de n a ¯n.
Definic¸
˜
ao 1.20. Circuito
´
e um caminho de um n
´
o n ∈ N a ele mesmo.
Definic¸
˜
ao 1.21. Um n
´
o n ∈ N
´
e raiz do grafo se e somente se todos os n
´
os s
˜
ao acess
´
ıveis
a partir de n.
Definic¸
˜
ao 1.22. Uma arboresc
ˆ
encia
´
e uma
´
arvore com raiz.
Uma arboresc
ˆ
encia possui somente uma raiz e cada n
´
o
´
e acess
´
ıvel a partir
da raiz por um
´
unico caminho.
Dado um grafo G = (N , M), uma
´
arvore (arboresc
ˆ
encia) maximal de G
´
e um grafo parcial de G que
´
e
´
arvore (arboresc
ˆ
encia).
Dada uma aplicac¸
˜
ao c : M → R, chamada de custo associado ao ramo,
podemos definir o que
´
e o custo de um caminho.
Definic¸
˜
ao 1.23. Custo de um caminho P = (n
1
, n
2
, ..., n
p
)
´
e dado por
C(P ) =
p−1
i=1
c(n
i
, n
j
),
isto
´
e,
´
e a soma dos custos de todos os ramos do caminho.
Observac¸
˜
ao 1.24. Definimos caminho por uma sequ
ˆ
encia de n
´
os P = (n
1
, n
2
, ..., n
p
).
Poder
´
ıamos tamb
´
em caracterizar o caminho pela sequ
ˆ
encia de ramos P = (r
1
, r
2
, ...,
r
p−1
), com r
i
= (n
i
, n
i+1
), i = 1, 2, ..., p − 1. Utiliza-se esta caracterizac¸
˜
ao quando for
mais conveniente.
8
Cap
´
ıtulo 2
Algoritmos de Busca de Caminhos
Ap
´
os definir conceitos b
´
asicos da teoria de grafos, definiremos neste ca-
p
´
ıtulo o nosso problema e em seguida os algoritmos de otimizac¸
˜
ao em grafos que s
˜
ao
usados para resolv
ˆ
e-lo.
Na teoria de grafos, o problema do Caminho de Custo M
´
ınimo consiste na
minimizac¸
˜
ao do custo de travessia de um grafo entre dois n
´
os.
Dizemos que um caminho P tem custo m
´
ınimo se C(P ) ≤ C(P
) para
todo caminho P
que tenha a mesma origem e o mesmo destino que P .
Para definir nosso problema, atrav
´
es da caracterizac¸
˜
ao do grafo pelo ope-
rador sucessor, considere:
• um grafo G = (N , Γ);
• um n
´
o s ∈ N , chamado n
´
o inicial ou raiz do grafo;
• um subconjunto T ⊂ N chamado alvo.
Problema
Encontrar, se existir, um caminho de s a algum n
´
o do alvo com custo
m
´
ınimo entre todos os caminhos de s ao alvo.
Sempre que este caminho exista ele
´
e dito caminho
´
otimo.
Este problema sempre admite soluc¸
˜
ao se o grafo for finito, sem circuitos
de custo negativo, e se algum n
´
o do alvo for acess
´
ıvel a partir de s. De agora em diante
consideramos apenas grafos finitos.
9
2.1 Princ
´
ıpio de Otimalidade de Bellman para Grafos
Teorema 2.1. Suponha que s = n
1
, n
2
, ..., n
p
= t
´
e um caminho de custo m
´
ınimo de s ao
alvo. Ent
˜
ao n
k
, n
k+1
, ..., n
k+j
, com 1 ≤ k, k + j ≤ p
´
e um caminho de custo m
´
ınimo de
n
k
a n
k+j
.
Demonstrac¸
˜
ao:
Suponha que s = n
1
, n
2
, ..., n
p
= t
´
e um caminho de custo m
´
ınimo.
Por contradic¸
˜
ao, suponha que o caminho n
k
= n
1
, n
2
, ..., n
r
= n
k+j
satisfaz
C(n
1
, n
2
, ..., n
r
) < C(n
k
, n
k+1
, ..., n
k+j
),
ou seja, existe outro caminho de n
k
a n
k+j
com custo menor.
Temos que n
1
, n
2
, ..., n
k
= n
1
, n
2
, ..., n
r
= n
k+j
, ..., t
´
e um caminho de s a t com custo
C(s, ..., t) − C(n
k
, n
k+1
, ..., n
k+j
) + C(n
1
, n
2
, ..., n
r
) < C(s, ..., t).
A desigualdade acima contradiz a hip
´
otese que o caminho s = n
1
, n
2
, ..., n
p
= t tem
custo m
´
ınimo.
2.2 Algoritmos de Rotulac¸
˜
ao
Definic¸
˜
ao 2.2. Dados dois n
´
os n, ¯n, define-se (usando a convenc¸
˜
ao inf ∅ = +∞):
• h(n, ¯n) = inf{C(P )| P = (n = n
1
, n
2
, ..., n
p
= ¯n)};
• c
∗
(n) = h(s, n);
• h(n) = inf{h(n, t)| t ∈ T }.
Temos:
− h(n, ¯n)
´
e o custo de um caminho de custo m
´
ınimo de n a ¯n, que chamaremos de
“dist
ˆ
ancia de n a ¯n”;
− c
∗
(n)
´
e a dist
ˆ
ancia do n
´
o inicial a n;
− h(n)
´
e a dist
ˆ
ancia de n ao alvo T ;
− h(s)
´
e o custo de um caminho
´
otimo.
10
Utilizando a notac¸
˜
ao introduzida por Gonzaga em [17] representamos os
caminhos por triplas ordenadas:
η = (n, c, p),
em que:
• η representa um caminho (s = n
1
, n
2
, ..., n
q
= n);
• n representa o n
´
o terminal do caminho;
• c
´
e o custo do caminho;
• p
´
e um apontador para o caminho (s = n
1
, n
2
, ..., n
q−1
).
Poder
´
ıamos guardar, ao inv
´
es do apontador, todo o caminho mas em grafos
com muitos n
´
os, isto geraria um gasto muito grande de mem
´
oria. Assim, esta estrutura
serve somente para mem
´
oria de computador. Para construir um caminho completo, basta
seguir os apontadores de tr
´
as para frente.
Exemplo:
Figura 2.1: Caminhos guardados
a - η
1
= (a, ., 0)
ab - η
2
= (b, ., 1)
abc - η
3
= (c, ., 2)
ad - η
4
= (d, ., 1)
abcd - η
5
= (d, ., 3)
ade - η
6
= (e, ., 4)
abcde - η
7
= (e, ., 5)
abce - η
8
= (e, ., 3)
Definic¸
˜
ao 2.3. Seja G = (N , Γ) um grafo finito em que o alvo
´
e acess
´
ıvel a partir de s.
Ent
˜
ao um elemento η = (n, c, p)
´
e dito minimal se
c = c
∗
(n) e c + h(n) = h(s),
11
ou seja, η coincide em parte com um caminho
´
otimo.
Como consequ
ˆ
encia imediata da Princ
´
ıpio de Otimalidade temos que se
η = (n, c, p)
´
e minimal e aponta para ˜η = (˜n, ˜c, ˜p), ent
˜
ao ˜η tamb
´
em
´
e minimal.
Definic¸
˜
ao 2.4. Dados dois caminhos η
i
= (n
i
, c
i
, p
i
), η
j
= (n
j
, c
j
, p
j
), dizemos que η
i
domina η
j
se e somente se n
i
= n
j
e c
i
≤ c
j
.
Definic¸
˜
ao 2.5. Dado um caminho η = (n, c, p), os sucessores de η s
˜
ao os caminhos
{¯η = (¯n, ¯c, ¯p)| ¯n ∈ Γ(n), ¯p apontador para η}.
Apresentaremos agora um algoritmo geral de rotulac¸
˜
ao. Esse algoritmo
ser
´
a estudado em detalhes adiante.
Dados G = (N , Γ), s ∈ N , T ⊂ N . Dizemos que um caminho j
´
a foi
expandido por um algoritmo quando j
´
a foram gerados os seus sucessores.
Um algoritmo de rotulac¸
˜
ao gera iterativamente caminhos a partir de s, que
s
˜
ao guardados em duas listas, chamadas Aberto e Fechado.
A lista Aberto
´
e a dos caminhos η = (n, c , p) ainda n
˜
ao expandidos. Dize-
mos que um n
´
o n est
´
a aberto quando existe um caminho aberto com n
´
o terminal n.
A lista Fechado
´
e a dos caminhos η = (n, c, p) j
´
a expandidos. O n
´
o termi-
nal
´
e dito n
´
o fechado.
Desta forma cada caminho possui um r
´
otulo, Aberto ou Fechado, a
´
ı est
´
a o
motivo de tamb
´
em chamarmos o algoritmo de Algoritmo de Rotulac¸
˜
ao.
Nos Algoritmos de Rotulac¸
˜
ao os elementos
1
s
˜
ao gerados iterativamente.
A cada iterac¸
˜
ao escolhe-se um elemento em Aberto para ser expandido, que passar
´
a a
ter o r
´
otulo Fechado. Os elementos sucessores gerados poder
˜
ao ou n
˜
ao receber o r
´
otulo
Aberto, segundo um crit
´
erio de eliminac¸
˜
oes.
Seja G = (N , Γ) um grafo finito, sem circuitos de custo negativo, cujo
alvo
´
e acess
´
ıvel a partir de s, ent
˜
ao o algoritmo descrito abaixo resolve o problema de
busca.
1
Utilizaremos as palavras “elemento” e “caminho” de modo equivalente, lembrando que os elementos
listados η representam caminhos no grafo.
12
Algoritmo 1 Algoritmo de Rotulac¸
˜
ao
1: Introduza em Aberto o elemento η
1
= (s, 0, 0)
2: Enquanto Aberto n
˜
ao est
´
a vazia
3: Escolha um elemento η = (n, c, p) em Aberto para fechar.
4: Construa os elementos sucessores ¯η
1
, ¯η
2
, ..., ¯η
q
, associados aos n
´
os Γ(n) =
{¯n
1
, ¯n
2
, ..., ¯n
q
}
¯η
i
= (¯n
i
, c + c(n, ¯n
i
), ¯p
i
),
¯p
i
´
e o apontador para η
5: Elimine os elementos sucessores dominados por algum elemento listado (aberto
ou fechado).
6: Elimine os elementos listados dominados por algum sucessor.
7: Introduza em Aberto os sucessores remanescentes
8: Fim Enquanto
9: Se h
´
a caminhos at
´
e o alvo em Fechado, encontrar um de custo m
´
ınimo e obter o
caminho correspondente, seguindo os apontadores.
A regra de eliminac¸
˜
ao faz com que exista nas listas em cada instante no
m
´
aximo um caminho listado at
´
e cada n
´
o. Note que o fato de serem feitas eliminac¸
˜
oes n
˜
ao
interfere no algoritmo, elas apenas s
˜
ao feitas com a finalidade de economizar mem
´
oria de
computador.
Este formato do algoritmo
´
e muito geral. Adiante comentaremos o crit
´
erio
para a escolha do aberto a expandir em cada iterac¸
˜
ao e a regra de parada.
Proposic¸
˜
ao 2.6. Um elemento listado minimal, η
i
= (n
i
, c
∗
(n
i
), .), nunca pode ser elimi-
nado.
Demonstrac¸
˜
ao:
Para eliminar um elemento seria necess
´
ario um sucessor η
j
= (n
i
, c
j
, .) com
c
j
< c
∗
(n
i
).
Mas obrigatoriamente
c
j
≥ c
∗
(n
i
)
pois c
∗
(n
i
)
´
e o custo de um caminho de custo m
´
ınimo de s at
´
e n
i
.
Proposic¸
˜
ao 2.7. O caminho correspondente a um elemento listado n
˜
ao tem circutos.
A demonstrac¸
˜
ao desta proposic¸
˜
ao pode ser vista em [12].
13
Teorema 2.8. Seja G um grafo finito sem circuito de custo negativo. Ent
˜
ao o algoritmo
p
´
ara em um n
´
umero finito de iterac¸
˜
oes.
Demonstrac¸
˜
ao:
Pela proposic¸
˜
ao 2.7, cada elemento listado corresponde um caminho sem circuitos. O
mesmo caminho n
˜
ao pode ser listado duas vezes, pois o elemento correspondente a se-
gunda obtenc¸
˜
ao do caminho seria eliminado.
O n
´
umero de caminhos sem circuitos em um grafo finito
´
e finito e portanto
o n
´
umero de iterac¸
˜
oes
´
e finito, uma vez que a cada iterac¸
˜
ao fecha-se um aberto.
O lema a seguir
´
e de grande valia. Ele afirma que enquanto n
˜
ao se encon-
trou um caminho de custo m
´
ınimo a um n
´
o arbitr
´
ario, todos os caminhos de custo m
´
ınimo
`
aquele n
´
o est
˜
ao sendo pesquisados pelo algoritmo.
Lema 2.9. Em uma iterac¸
˜
ao qualquer, seja ¯n um n
´
o arbitr
´
ario acess
´
ıvel a partir de s.
Seja P = (s = n
1
, n
2
, ..., n
p
= ¯n) um caminho de custo m
´
ınimo de s a ¯n. Ent
˜
ao:
Se n
˜
ao existe um fechado com a forma ¯η = (¯n, c
∗
(¯n), .) ent
˜
ao existe um aberto com a
forma η
q
= (n
q
, c
∗
(n
q
), .), q = 1, 2, ..., p.
Demonstrac¸
˜
ao:
Seja ¯n um n
´
o arbitr
´
ario acess
´
ıvel a partir de s por um caminho de custo m
´
ınimo (s =
n
1
, n
2
, ..., n
p
= ¯n).
Na primeira iterac¸
˜
ao (s, 0, 0) est
´
a aberto e nada h
´
a a provar.
Em outra iterac¸
˜
ao: suponha que n
˜
ao existe fechado (¯n, c
∗
(¯n), .).
Seja q − 1 o mais alto
´
ındice tal que algum (n
q−1
, c
∗
(n
q−1
), .) est
´
a fechado,
1 ≤ q − 1 ≤ p
• q − 1 existe pois (s, 0, 0) est
´
a fechado
• q − 1 < p por hip
´
otese
Como (n
q−1
, c
∗
(n
q−1
), .) est
´
a fechado, foi expandido anteriormente, ge-
rando o sucessor
(n
q
, c
∗
(n
q
), .) pois c
∗
(n
q
) = c
∗
(n
q−1
) + c(n
q−1
, n
q
)
uma vez que P
´
e um caminho de custo m
´
ınimo.
Se esse sucessor n
˜
ao foi eliminado, foi aberto.
14
Se foi eliminado, havia um aberto (n
q
, c
q
, p
q
) que o eliminou, com c
q
≤ c
∗
(n
q
). Obvia-
mente c
q
= c
∗
(n
q
).
Em qualquer caso, foi listado em aberto
(n
q
, c
∗
(n
q
), p
q
).
Esse elemento n
˜
ao
´
e eliminado e n
˜
ao
´
e fechado por definic¸
˜
ao de q.
Portanto permanece aberto, completando a demonstrac¸
˜
ao.
Corol
´
ario 2.10. Quando o algoritmo termina, todos os elementos listados (fechados por
construc¸
˜
ao) correspondem a caminhos de custo m
´
ınimo. Isto
´
e, para todo
¯η = (¯n, ¯c, ¯p) listado,
¯c = c
∗
(¯n).
Al
´
em disso, todos os n
´
os acess
´
ıveis a partir de s est
˜
ao fechados.
Desta forma a lista Fechado descreve uma arboresc
ˆ
encia maximal m
´
ınima
do subgrafo acess
´
ıvel por s.
Corol
´
ario 2.11. Se G
´
e grafo finito sem circuitos de custo negativo e existe n
´
o do alvo
acess
´
ıvel a partir de s, ent
˜
ao o algoritmo termina com um caminho de custo m
´
ınimo entre
s e o alvo, ou seja, um caminho
´
otimo.
Em nenhum momento especificamos o procedimento de escolher um ele-
mento para expandir em cada iterac¸
˜
ao. Esta escolha
´
e um procedimento muito importante
e pode ser feito de diferentes maneiras,
´
e esta escolha que d
´
a origem a diferentes algorit-
mos de rotulac¸
˜
ao.
A seguir apresentaremos os algoritmos de Busca Horizontal, Busca em
Profundidade e Algoritmo de Dijkstra que n
˜
ao utilizam nenhuma informac¸
˜
ao quanto a
proximidade do alvo em cada iterac¸
˜
ao. Em seguida apresentaremos o Algoritmo A
∗
que
usa esta informac¸
˜
ao. O estudo dos tr
ˆ
es primeiros algoritmos foram iniciados por n
´
os
atrav
´
es de [13] e depois foi fortemente enriquecido pela abordagem feita em [12]. Em
[12], Gonzaga faz um estudo bastante detalhado do algoritmo A
∗
ficando evidente a im-
port
ˆ
ancia de pensar em caminhos os inv
´
es de n
´
os.
15
2.3 Algoritmo de Busca Horizontal
Este algoritmo, tamb
´
em conhecido como m
´
etodo Breadth-First ou FIFO
( first in first out), escolhe o elemento mais antigo da lista Aberto para expandir, ou seja,
expande caminhos na ordem em que eles s
˜
ao gerados. Desta maneira o primeiro elemento
a entrar na lista Aberto
´
e tamb
´
em o primeiro a sair.
Figura 2.2: Busca Horizontal
No grafo da figura 2.2 mostramos seis iterac¸
˜
oes deste algoritmo. Os n
´
u-
meros em vermelho indicam a ordem em que eles foram abertos e conseq
¨
uentemente a
ordem em que foram fechados. A cor amarela representa os n
´
os abertos ao fim da sexta
iterac¸
˜
ao e a magenta representa os n
´
os fechados ao fim dessa iterac¸
˜
ao.
Note que este algoritmo desenvolve o grafo sistematicamente, evoluindo
“de camada em camada”.
´
E conveniente se o alvo for pequeno, ou em grafos naturalmente
estruturados em camadas, sem circuitos.
Neste caso, que ocorre por exemplo em problemas de decis
˜
oes sequenciais,
as listas podem ser manipuladas de maneira simplificada: em cada iterac¸
˜
ao s
´
o s
˜
ao proces-
sados n
´
os de duas camadas. Os n
´
os de uma camada somente s
˜
ao fechados quando todos
os n
´
os da camada anterior j
´
a est
˜
ao fechados em caminhos de custo m
´
ınimo. O algoritmo
ent
˜
ao coincide com o m
´
etodo de programac¸
˜
ao din
ˆ
amica discreta progressiva.
Se prosseguirmos no grafo da figura 2.2 segundo o algoritmo 1 estaremos
construindo uma arboresc
ˆ
encia maximal de custo m
´
ınimo para o subgrafo formado pelos
n
´
os acess
´
ıveis a partir de s descrita pela figura 2.3.
16
Figura 2.3: Arboresc
ˆ
encia maximal
2.4 Algoritmo de Busca em Profundidade
Este algoritmo, tamb
´
em conhecido como m
´
etodo Depth-First ou LIFO
(last in first out), escolhe o elemento mais recente da lista Aberto para expandir. Assim o
´
ultimo elemento que entra em Aberto
´
e o primeiro a sair.
Figura 2.4: Busca em Profundidade
Na figura 2.4 representamos cinco iterac¸
˜
oes do algoritmo de Busca em
profundidade. Os n
´
umeros em vermelho indicam a ordem em que eles foram abertos. A
cor amarela representa os n
´
os abertos e a magenta representa os n
´
os fechados ao fim da
quinta iterac¸
˜
ao.
Note que se algum sucessor do elemento expandido em uma iterac¸
˜
ao for
listado, a pr
´
oxima iterac¸
˜
ao vai fechar um desses sucessores, seguindo assim at
´
e atingir
uma folha do grafo, ou at
´
e que todos os sucessores de um elemento sejam eliminados.
Esta
´
e a busca mais “arrojada”, procurando obter rapidamente soluc¸
˜
oes n
˜
ao
´
otimas.
´
E conveniente se o alvo
´
e grande e se o tempo de computac¸
˜
ao
´
e cr
´
ıtico: pode-se
parar o processamente antes de obter uma soluc¸
˜
ao
´
otima.
17
Tamb
´
em neste m
´
etodo as listas podem ser manipuladas de maneira sim-
plificada: em cada instante todos os n
´
os abertos s
˜
ao sucessores de n
´
os pertencentes a um
caminho originado em s.
Se algum caminho, η de s a T
´
e conhecido, seu custo pode ser usado como
limitante na busca de novos caminhos. Desta forma elementos com custo, ou estimativa
para o custo, maior que o custo de η podem ser eliminados, pois n
˜
ao nos levar
˜
ao a ca-
minhos
´
otimos at
´
e o alvo. Algoritmos que procedem desta forma s
˜
ao conhecidos como
Branch and Bound e foram desenvolvidos para resolver problemas de Programac¸
˜
ao Li-
near Inteira.
2.5 Algoritmo de Dijkstra
O algoritmo de Dijkstra
´
e o mais importante dos algoritmos para encontrar
um caminho de custo m
´
ınimo entre n
´
os de um grafo com custos n
˜
ao negativos e
´
e o
primeiro estudado por n
´
os que leva em considerac¸
˜
ao nas expans
˜
oes o custo.
Este algoritmo escolhe em cada iterac¸
˜
ao um elemento com custo m
´
ıni-
mo entre os custos de todos os elementos da lista Aberto para expandir. Empates s
˜
ao
resolvidos arbitrariamente, mas sempre dando prefer
ˆ
encia a caminhos cujos n
´
os j
´
a est
˜
ao
no alvo.
Os pr
´
oximos dois teoremas, extra
´
ıdos de [13], nos transmitem as seguin-
tes informac¸
˜
oes: para grafos com custos n
˜
ao negativos, todos os caminhos fechados s
˜
ao
caminhos de custo m
´
ınimo. Ou seja, no momento em que o n
´
o terminal de um caminho
´
e expandido, j
´
a foi encontrado um caminho de custo m
´
ınimo at
´
e ele. Desta forma, no
momento em que um n
´
o do alvo for fechado, o problema de busca est
´
a resolvido.
Teorema 2.12. Seja G = (N , Γ) um grafo finito tal que todos os ramos tem custos n
˜
ao
negativos. Ent
˜
ao o elemento fechado, η = (n, c, p), em cada iterac¸
˜
ao tem custo m
´
ınimo,
ou seja
c = c
∗
(n).
Demonstrac¸
˜
ao:
Suponha que em uma iterac¸
˜
ao
´
e fechado um elemento
η = (n, c, p).
Por construc¸
˜
ao, todos os abertos η
i
nessa iterac¸
˜
ao tem custos c
i
≥ c.
18
O mesmo ocorrer
´
a com todos os sucessores gerados no futuro, pois os
custos s
˜
ao n
˜
ao negativos.
O elemento η nunca poder
´
a ser eliminado.
Pelo corol
´
ario (2.10), η tem custo m
´
ınimo.
Teorema 2.13. Seja G = (N , Γ) um grafo finito tal que todos os ramos tem custos n
˜
ao
negativos e que o alvo
´
e acess
´
ıvel a partir de s. Ent
˜
ao o primeiro caminho cujo n
´
o
terminal n est
´
a no alvo, fechado pelo algoritmo de Dijkstra fornece uma soluc¸
˜
ao
´
otima
para o problema.
Demonstrac¸
˜
ao:
Pelo teorema (2.12), o elemento η = (n, c, p), com n ∈ T , fechado tem custo m
´
ınimo.
Assim qualquer caminho fechado posteriormente tem custo maior ou igual a c. Portanto,
posteriormente nenhum caminho melhor poder
´
a ser encontrado.
Com este teorema podemos estabelecer um novo crit
´
erio de parada para o
algoritmo de Dijkstra para grafos com custos n
˜
ao negativos: parar ao fechar um n
´
o do
alvo.
O algoritmo pode ser usado sobre grafos orientados ou n
˜
ao, e admite que
todos os ramos possuem custos n
˜
ao negativos. Esta restric¸
˜
ao
´
e satisfeita por redes de
transportes, onde os ramos representam normalmente dist
ˆ
ancias ou tempos m
´
edios de
percurso; poder
˜
ao existir, no entanto, aplicac¸
˜
oes onde h
´
a ramos com custos negativos,
nestes casos o algoritmo com este crit
´
erio de parada n
˜
ao funcionar
´
a corretamente.
Ainda, em [12] Gonzaga conclui que o algoritmo de Dijkstra avanc¸a pelo
grafo em “frentes de onda de custo constante” e observa que o algoritmo de Busca Ho-
rizontal corresponde
`
a aplicac¸
˜
ao do algoritmo de Dijkstra ao problema de caminhos de
comprimento m
´
ınimo.
Apresentamos abaixo uma ilustrac¸
˜
ao do algoritmo de Dijkstra para o grafo
dado pela figura 2.5.
19
Figura 2.5: Grafo inicial
1. Primeira Iterac¸
˜
ao
Fechou: η
1
= (n
1
, 0, 0), a raiz do grafo.
Abriu:
− η
2
= (n
2
, 23, 1)
− η
3
= (n
3
, 5, 1)
− η
4
= (n
4
, 19, 1)
− η
5
= (n
5
, 15, 1)
2. Segunda Iterac¸
˜
ao
Fechou: η
3
= (n
3
, 5, 1)
Abriu:
− η
6
= (n
6
, 7, 3)
− η
7
= (n
7
, 23, 3)
3. Terceira Iterac¸
˜
ao
Fechou: η
6
= (n
6
, 7, 3)
Abriu:
− η
8
= (n
10
, 11, 6)
− η
9
= (n
7
, 13, 6)
η
7
pode ser eliminado, pois 13 < 23.
4. Quarta Iterac¸
˜
ao
Fechou: η
8
= (n
10
, 11, 6)
Abriu:
− η
10
= (n
13
, 18, 8)
5. Quinta Iterac¸
˜
ao
Fechou: η
5
= (n
5
, 15, 1)
Abriu:
20
− η
11
= (n
9
, 25, 5)
− η
12
= (n
8
, 28, 5)
6. Sexta Iterac¸
˜
ao
Fechou: η
9
= (n
7
, 13, 6)
Abriu:
− η
13
= (n
12
, 24, 9)
7. Sexta Iterac¸
˜
ao
Fechou: η
10
= (n
13
, 18, 8)
Como n
13
est
´
a no alvo, o algoritmo p
´
ara.
A figura 2.6 ilustra o grafo ao fim do algoritmo. Os n
´
os em magenta repre-
sentam os caminhos cujos n
´
os terminais foram expandidos, os em amarelo representam
os n
´
os terminais dos caminhos que est
˜
ao na lista Aberto e, o tracejado em vermelho re-
presenta os caminhos eliminados.
Observe que os n
´
os em magenta com os ramos entre eles representam uma
arboresc
ˆ
encia de custo m
´
ınimo. Por
´
em esta arboresc
ˆ
encia n
˜
ao
´
e maximal pois a lista
Aberto n
˜
ao est
´
a vazia.
Figura 2.6: Grafo final
2.6 Algoritmo A
∗
O algoritmo A
∗
foi introduzido por Hart, Nilsson e Raphael em [9] e am-
plamente discutido por Nilsson em [14]. Este algoritmo
´
e id
ˆ
entico ao algoritmo de Dijks-
tra, exceto pelo uso de alguma informac¸
˜
ao heur
´
ıstica a respeito da estrutura do grafo,
atrav
´
es de uma func¸
˜
ao “estimativa”.
21
A abordagem adotada por n
´
os, assim como definic¸
˜
oes e resultados que
hora apresentamos, seguem as id
´
eias de Gonzaga em [12] e [17].
Definic¸
˜
ao 2.14. O custo de um caminho de custo m
´
ınimo de n ao alvo
´
e definido pela
aplicac¸
˜
ao:
h : N −→ R
Em adic¸
˜
ao define-se para cada caminho η = (n, c, p) a aplicac¸
˜
ao:
η −→ f(η) = c
∗
(n) + h(n),
´
e o custo de um caminho de custo m
´
ınimo entre s e o alvo, que cont
´
em η
como trecho inicial.
Em problemas em que
´
e poss
´
ıvel associar a cada n
´
o n do grafo uma esti-
mativa para o custo de um caminho ao alvo, o valor da estimativa de custo de um caminho
entre s e o alvo,
ˆ
f, ser
´
a utilizado como crit
´
erio de escolha do caminho a expandir em cada
iterac¸
˜
ao. Esta estimativa
´
e obtida em geral resolvendo um problema relaxado. Veremos
exemplos de estimativas assim nos pr
´
oximos cap
´
ıtulos.
Definic¸
˜
ao 2.15. A estimativa de custo de um caminho de custo m
´
ınimo de n ao alvo
´
e
uma aplicac¸
˜
ao:
ˆ
h : N −→ R
com
ˆ
h(t) = h(t) = 0 para todo t ∈ T.
A estimativa de custo de um caminho de custo m
´
ınimo, entre s e o alvo que
cont
´
em η = (n, c, p) como trecho inicial,
´
e definida por:
η −→
ˆ
f(η) = c +
ˆ
h(n).
Observac¸
˜
ao 2.16. Note que:
−
ˆ
h(n)
´
e associada ao n
´
o n e deve estimar o valor de h(n);
−
ˆ
f(η)
´
e uma estimativa do custo do melhor caminho que se pode obter expandido o
caminho η.
2.6.1 Estimativa admiss
´
ıvel
Definic¸
˜
ao 2.17. Uma estimativa
ˆ
h(.)
´
e dita admiss
´
ıvel se para qualquer n ∈ N :
ˆ
h(n) ≤ h(n).
22
Teorema 2.18. Seja G = (N , Γ) um grafo finito sem circuitos de custo negativo. Se a
estimativa
´
e admiss
´
ıvel e se o alvo
´
e acess
´
ıvel a partir de s, ent
˜
ao a qualquer iterac¸
˜
ao
antes de A
∗
fechar o primeiro n
´
o do alvo e para qualquer caminho
´
otimo P do n
´
o s at
´
e
um n
´
o t ∈ T , existe um caminho aberto η
= (n
, c
, p
) com n
em P e
ˆ
f(η
) ≤ h(s).
Demonstrac¸
˜
ao:
Considere uma iterac¸
˜
ao k = 1 do algoritmo.
Seja P = (s = n
1
, n
2
, ..., n
j
= t) um caminho
´
otimo de s ao alvo.
Sabemos que s est
´
a fechado e que n
j
n
˜
ao est
´
a fechado.
Pelo lema 2.9 existe um aberto com a forma η
q
= (n
q
, c
∗
(n
q
), p
q
).
Ainda, por definic¸
˜
ao tem-se
ˆ
f(η
q
) = c
∗
(n
q
) +
ˆ
h(n
q
). Como a estimativa
´
e
admiss
´
ıvel
ˆ
f(η
q
) ≤ c
∗
(n
q
) + h(n
q
) = h(s).
Em [14], Nilsson conclui que o teorema 2.18 garante que quanto maior a
precis
˜
ao da sub-estimativa menor ser
´
a o n
´
umero de elementos n
˜
ao minimais fechados.
Teorema 2.19. Seja G = (N , Γ) um grafo finito sem circuitos de custos negativos. Se a
estimativa
´
e admiss
´
ıvel e se o alvo
´
e acess
´
ıvel a partir de s, ent
˜
ao na primeira iterac¸
˜
ao
em que o algoritmo A
∗
fecha um caminho at
´
e o alvo esse caminho
´
e soluc¸
˜
ao
´
otima do
problema.
Demonstrac¸
˜
ao:
Pelo corol
´
ario 2.10 n
´
os do alvo s
˜
ao fechados.
Seja ¯η = (¯n, ¯c, ¯p) o primeiro caminho at
´
e o alvo a ser fechado, em alguma iterac¸
˜
ao k > 1.
Como ¯n ∈ T ,
ˆ
f(¯η) = ¯c
Ent
˜
ao pela regra de escolha
¯c =
ˆ
f(¯η) ≤
ˆ
f(η)
para todo η aberto nesta iterac¸
˜
ao.
Pelo teorema 2.18 existe um caminho ˜η aberto tal que
ˆ
f(˜η) ≤ h(s).
Segue-se que ¯c ≤ h(s).
Como ¯c ≥ h(s) por definic¸
˜
ao de h(s), s
´
o pode ocorrer ¯c = h(s), como quer
´
ıamos.
23
Desta forma o crit
´
erio de parada para este algoritmo pode ser mudado para:
at
´
e fechar um n
´
o no alvo.
2.6.2 Estimativa consistente
A definic¸
˜
ao seguinte, extra
´
ıda de [12], estabelece para o algoritmo A
∗
pro-
priedades an
´
alogas
`
aquelas do algoritmo de Dijkstra mostradas nos teoremas 2.12 e 2.13.
Definic¸
˜
ao 2.20. Uma estimativa
ˆ
h : N −→ R
´
e consistente se
´
e admiss
´
ıvel e se para
todo n
1
, n
2
∈ N ,
ˆ
h(n
1
) ≤ h(n
1
, n
2
) +
ˆ
h(n
2
).
Teorema 2.21. Suponha que
ˆ
h
´
e uma estimativa consistente e seja ¯η o elemento escolhido
em uma iterac¸
˜
ao do algoritmo A
∗
. Ent
˜
ao nessa iterac¸
˜
ao
ˆ
f(η
i
) ≥
ˆ
f(¯η), i = 1, 2, ..., q,
onde os η
i
s
˜
ao os sucessores do elemento ¯η.
Demonstrac¸
˜
ao:
Seja η
i
= (n
i
, c
i
, p
i
) um sucessor do elemento ¯η = (¯n, ¯c, ¯p).
ˆ
f(η
i
) = c
i
+
ˆ
h(n
i
)
= ¯c + c(¯n, n
i
) +
ˆ
h(n
i
)
≥ ¯c + h(¯n, n
i
) +
ˆ
h(n
i
)
≥ ¯c +
ˆ
h(¯n), pois a estimativa
´
e consistente.
=
ˆ
f(¯η)
logo
ˆ
f(η
i
) ≥
ˆ
f(¯η).
Corol
´
ario 2.22. Se o algoritmo utiliza uma estimativa consistente, ent
˜
ao
ˆ
f(η
j
)
´
e cres-
cente com as iterac¸
˜
oes (onde η
j
´
e o elemento escolhido em cada iterac¸
˜
ao).
Teorema 2.23. Se a estimativa
´
e consistente, ent
˜
ao todo elemento fechado ¯η = (¯n, ¯c, ¯p)
satisfaz ¯c = c
∗
(¯n).
Demonstrac¸
˜
ao:
Suponha que ¯η = (¯n, ¯c, ¯p)
´
e fechado em alguma iterac¸
˜
ao, com ¯c > c
∗
(¯n).
Pelo lema 2.9, existe um aberto η = (n, c, p) tal que:
c = c
∗
(n), c + h(n, ¯n) = c
∗
(¯n).
24
Portanto,
ˆ
f(η) = c
∗
(n) +
ˆ
h(n)
≤ c
∗
(n) + h(n, ¯n) +
ˆ
h(¯n), pois a estimativa
´
e consistente.
= c
∗
(¯n) +
ˆ
h(¯n)
<
ˆ
f(¯η) pois ¯c > c
∗
(¯n),
o que contraria a escolha de ¯η para ser expandido.
Do teorema 2.18 conclu
´
ımos que:
• nenhum caminho η com
ˆ
f(η) > h(s) ser
´
a expandido pelo algoritmo;
• se
ˆ
h(.) = h(.) (estimativa perfeita), ent
˜
ao ser
˜
ao fechados somente caminhos η que
s
˜
ao trechos iniciais de caminhos
´
otimos;
• se
ˆ
h(n) ≤ h(n) (estimativa admiss
´
ıvel), o n
´
umero de elementos fechados depende
do erro da estimativa: poder
˜
ao ser fechados os elementos η = (n, c, p) com c +
ˆ
h(n) ≤ h(s).
A melhor situac¸
˜
ao ocorre no caso de estimativas consistentes. Nesse caso,
todos os fechados s
˜
ao caminhos de custo m
´
ınimo (como ocorre no algoritmo de Dijkstra)
e
ˆ
f(η
k
)
´
e crescente com as iterac¸
˜
oes k . O algoritmo explora o grafo em “frentes de onda”
de
ˆ
f crescente.
Em [9]
´
e demonstrado que nenhum algoritmo de rotulac¸
˜
ao pode encontrar
um caminho
´
otimo ao alvo com menos expans
˜
oes que A
∗
, se a
´
unica informac¸
˜
ao adicional
dispon
´
ıvel sobre o grafo
´
e dada por
ˆ
h(.).
25
Cap
´
ıtulo 3
Alinhamento de Prote
´
ınas
Neste cap
´
ıtulo propomos uma abordagem matem
´
atica computacional, uti-
lizando algoritmos de busca em grafos, para o problema de alinhamento de prote
´
ınas. A
id
´
eia para esta abordagem surgiu a partir de um semin
´
ario feito pelo Prof. Jos
´
e M
´
ario
Martinez em uma visita ao Dep. de Matem
´
atica da Universidade Federal de Santa Cata-
rina. Em seu trabalho Martinez constr
´
oi o melhor emparelhamento entre
´
atomos de duas
prote
´
ınas utilizando programac¸
˜
ao din
ˆ
amica. Propomos uma nova modelagem para este
problema via algoritmos de busca em grafos.
Prote
´
ınas s
˜
ao corpos r
´
ıgidos definidos por sequ
ˆ
encias de amino
´
acidos. Em
[20] encontramos a seguinte definic¸
˜
ao: um amino
´
acido
´
e constitu
´
ıdo por um
´
atomo cen-
tral de carbono ligado a quatro grupos: hidrog
ˆ
enio, grupo carbox
´
ılico (COOH), grupo
am
´
ınico (NH
2
), comum a todos os amino
´
acidos, e um outro grupo R, ou cadeia lateral,
que os distingue entre si.
Figura 3.1: Prote
´
ına
Em sua estrutura prim
´
aria cada prote
´
ına
´
e representada por uma sequ
ˆ
encia
de amino
´
acidos (uma sequ
ˆ
encia de letras). Em nosso estudo, como estamos interessados
em alinhamento estrutural, uma prote
´
ına com N
´
atomos de carbono
´
e representada por N
26
pontos no espac¸o Euclidiano tri-dimensional, onde cada ponto refere-se
`
as coordenadas
espaciais de cada
´
atomo de carbono. Desta forma uma prote
´
ına tem dimens
˜
ao N × 3.
O objetivo de alinhar prote
´
ınas [19]
´
e estabelecer par
ˆ
ametros de semelhanc¸a
entre duas ou mais prote
´
ınas, respeitando crit
´
erios espec
´
ıficos. Ent
˜
ao desenvolvem-se
algoritmos para que sejam feitas pesquisas em bancos de dados e possam-se comparar
prote
´
ınas. Comparac¸
˜
ao de prote
´
ınas
´
e um importante problema em Biologia Estrutural
[3] pois prote
´
ınas semelhantes ou com pedac¸os semelhantes podem ter a mesma func¸
˜
ao.
Tendo em vista que o n
´
umero de prote
´
ınas obtidas experimentalmente est
´
a
se tornando maior a cada ano [3],
´
e preciso desenvolver algoritmos que sejam r
´
apidos na
pesquisa em bancos de dados e que tenham uma boa maneira de medir semelhanc¸as entre
prote
´
ınas.
Para alinhar prote
´
ınas, deve-se respeitar a seq
¨
uencialidade dos
´
atomos.
Tamb
´
em pode ocorrer que seja melhor n
˜
ao emparelhar algum
´
atomo de uma das prote
´
ınas,
neste caso dizemos que ocorreu um gap. Sempre que ocorrem gaps
´
e preciso penaliz
´
a-los.
3.1 Definic¸
˜
ao do problema
Para definir o problema de alinhamento de prote
´
ınas considere:
• Uma prote
´
ına fixa espacialmente, caracterizada pelas coordenadas de seus
´
atomos
de carbono y
1
, y
2
, ..., y
M
∈ R
3
.
• Uma prote
´
ına caracterizada por pontos x
1
, x
2
, ..., x
N
∈ R
3
.
• Uma func¸
˜
ao de pontuac¸
˜
ao (score) que associa a um par de vetores x, y ∈ R
3
o valor
f(x, y) =
20
1 + ( x − y /2.24)
2
(3.1)
Esta func¸
˜
ao
´
e usada na literatura em [3].
Vamos separar o problema em duas fases:
1. Emparelhamento: nesta fase consideram-se duas prote
´
ınas fixas no espac¸o e busca-
se um emparelhamento entre pontos de duas prote
´
ınas
{(x
i
k
, y
j
k
)|k = 1, 2, ..., p} ou simplesmente {(i
k
, j
k
)}
k=1,2,...,p
27
com p ≤ min{M, N} e i
k
, j
k
crescentes com k (respeita-se a sequencialidade).
Figura 3.2: Emparelhamento
A figura 3.2 mostra um emparelhamento entre duas prote
´
ınas com a seguinte cor-
respond
ˆ
encia entre
´
ındices:
i
k
1 2 3 5 6
j
k
1 4 5 6 7
Neste emparelhamento vemos que x
4
n
˜
ao est
´
a emparelhado, o mesmo ocorrendo
com y
2
e y
3
. O emparelhamento apresenta um gap em cada prote
´
ına. Neste pro-
blema os gaps s
˜
ao penalizados com lucro igual a −10, que independe da extens
˜
ao
do gap.
A cada emparelhamento E = {(i
k
, j
k
)}
k=1,2,...,p
, associa-se uma pontuac¸
˜
ao
F (E) =
p
k=1
f(x
i
k
, y
j
k
) − 10n
g
, (3.2)
em que n
g
´
e o n
´
umero total de gaps do emparelhamento.
O problema da primeira fase
´
e: entre todos os emparelhamentos poss
´
ıveis E =
{(i
k
, j
k
)}
k=1,2,...,p
, p ≤ min{M, N}, encontrar um com o m
´
aximo valor de F (E).
Este
´
e o problema que vamos resolver nesta dissertac¸
˜
ao.
2. Deslocamento: uma vez estabelecido um emparelhamento dos
´
atomos, desloca-se
a prote
´
ına (x
1
, ..., x
N
) por meio de uma translac¸
˜
ao e uma rotac¸
˜
ao (mantendo r
´
ıgida
a estrutura), de modo a otimizar um crit
´
erio dado.
Existem duas abordagens na literatura:
28
• O problema de Procrustes
1
:
´
e um problema de quadrados m
´
ınimos em que minimiza-
se
p
k=1
x
i
k
− y
j
k
2
.
A resoluc¸
˜
ao deste problema
´
e simples: faz-se uma translac¸
˜
ao de prote
´
ına para fa-
zer coincidir os centros de massa e busca-se uma matriz de rotac¸
˜
ao da prote
´
ına em
torno do centro de massa para minimizar o crit
´
erio acima. Este problema
´
e cl
´
assico
(problema de Procrustes) e admite soluc¸
˜
ao anal
´
ıtica (que faz parte do pacote Ma-
tlab).
• O crit
´
erio de pontuac¸
˜
ao: busca-se um deslocamento que maximize o crit
´
erio de
pontuac¸
˜
ao.
O algoritmo completo consiste em ciclos emparelhamento-deslocamento.
Dada uma posic¸
˜
ao da prote
´
ına, faz-se um emparelhamento seguido de um deslocamento.
Ap
´
os o deslocamento, o emparelhamento pode deixar de ser
´
otimo, e deve ser refeito. O
processo
´
e repetido at
´
e que se estabilize, ou entre em um ciclo.
O m
´
etodo Structal
O m
´
etodo Structal [10]
´
e o mais utilizado atualmente, e usa o problema de
Procrustes para o deslocamento. O m
´
etodo
´
e descrito em Andreani, Martinez e Martinez
[3]. Tem desvantagens
´
obvias: utiliza dois crit
´
erios distintos nas duas fases e n
˜
ao maxi-
miza a pontuac¸
˜
ao [2]. Pode entrar em ciclo e isto de fato ocorre frequentemente
2
. Como
vantagem, tem a simplicidade do problema de Procrustes.
M
´
etodo LOVO para alinhamento de prote
´
ınas
Este m
´
etodo [3], [2] utiliza o mesmo crit
´
erio em ambas as fases, produ-
zindo resultados melhores. Mas o problema de deslocamento
´
e muito mais dif
´
ıcil, devido
`
a dificuldade do crit
´
erio, que n
˜
ao
´
e convexo.
Neste trabalho n
˜
ao mencionaremos mais o problema de deslocamento. Va-
mos descrever um novo m
´
etodo para o problema de emparelhamento utilizando a mode-
lagem de grafos, que
´
e comum a ambos m
´
etodos. A partir de agora, consideramos dadas
duas prote
´
ınas fixas no espac¸o.
1
Processo de obter a superposic¸
˜
ao de corpos r
´
ıgidos que minimiza um crit
´
erio entre correspondente
´
atomos de carbono de duas prote
´
ınas [2].
2
Afirmac¸
˜
ao de Andreani, Martinez e Martinez em [3].
29
Em ambas as abordagens citadas, o problema de emparelhamento
´
e resol-
vido por programac¸
˜
ao din
ˆ
amica. Em um problema discreto, o algoritmo de programac¸
˜
ao
din
ˆ
amica tem o desempenho de Busca Horizontal.
Como o problema
´
e de maximizac¸
˜
ao com custos positivos, o que equivale
`
a minimizac¸
˜
ao com custos negativos, n
˜
ao podemos utilizar o algoritmo de Dijkstra, mas
mostraremos como usar o algoritmo A
∗
.
A matriz de pontuac¸
˜
ao
Para o problema de emparelhamento, constru
´
ımos uma matriz de pontuac¸
˜
ao
ou lucro (score) L, (N × M), com
L(i, j) =
20
1 + (d(i, j)/2, 24)
2
, d(i, j) = x
i
− y
j
(3.3)
A qualidade do alinhamento
´
e medida atrav
´
es da equac¸
˜
ao (3.2), isto
´
e
pela soma dos pontos obtidos atrav
´
es deste emparelhamento menos as penalidades pela
introduc¸
˜
ao de gaps.
3.2 Definindo o grafo
Estamos buscando um emparelhamento {(i
k
, j
k
)}
k=1,2,...,p
que maximize
p
k=1
f(x
i
k
, y
j
k
) − 10n
g
, com p ≤ min{M, N} (3.4)
O lema a seguir, feito por n
´
os, limita a distribuic¸
˜
ao de gaps em um empa-
relhamento
´
otimo.
Lema 3.1. Suponha que {(i
k
, j
k
)}
k=1,2,...,p
´
e um emparelhamento
´
otimo. Ent
˜
ao n
˜
ao po-
dem ocorrer simultaneamente i
k+1
> i
k
+1 e j
k+1
> j
k
+1 para nenhum k = 1, ..., p−1.
Demonstrac¸
˜
ao:
Suponha que {(i
k
, j
k
)}
k=1,2,...,p
´
e
´
otimo e que para algum q = 1, ..., p − 1, i
q+1
> i
q
+ 1
(h
´
a um gap entre i
q
e i
q+1
) e j
q+1
> j
q
+ 1 (h
´
a um gap entre j
q
e j
q+1
). Ent
˜
ao podemos
30
construir um novo emparelhamento unindo os
´
atomos i
q
+ 1 e j
q
+ 1:
{(i
1
, j
1
), ..., (i
q
, j
q
), (i
q
+ 1, j
q
+ 1), (i
q+1
, j
q+1
), ..., (i
p
, j
p
)}
Este novo emparelhamento tem um n
´
umero de gaps menor ou igual ao do antigo, e
pontuac¸
˜
ao excedente em L(i
q
+ 1, j
q
+ 1), contradizendo a otimalidade do alinhamento.
Figura 3.3: Ilustrac¸
˜
ao do lema
Para construir um grafo que represente o problema, partimos do seguinte
racioc
´
ınio: suponha que j
´
a decidimos como emparelhar os
´
atomos i = 1, 2, ...,
α − 1 e j = 1, 2, ..., β − 1, e queremos decidir se α ser
´
a ligado a β ou n
˜
ao. Considerando
o lema 3.1, existem tr
ˆ
es situac¸
˜
oes poss
´
ıveis:
• α − 1 e β − 1 est
˜
ao emparelhados;
• α − 1 n
˜
ao faz parte do emparelhamento (ocorreu gap
`
a esquerda de α);
• β − 1 n
˜
ao faz parte do emparelhamento (ocorreu gap
`
a esquerda de β).
3.2.1 N
´
o
Os n
´
os N do grafo correspondem a todas as combinac¸
˜
oes de i, j e gaps
compat
´
ıveis com as situac¸
˜
oes acima. Um n
´
o n
´
e uma trinca (α, β, gap) em que:
• α
´
e um
´
atomo da primeira prote
´
ına;
• β
´
e um
´
atomo da segunda prote
´
ına;
• gap indica se h
´
a ou n
˜
ao gaps
`
a esquerda de α ou β:
− gap= 1 se h
´
a gap
`
a esquerda de α
− gap= 2 se h
´
a gap
`
a esquerda de β
− gap= 0 se n
˜
ao h
´
a gaps
`
a esquerda de α ou β.
31
N
´
o inicial: s = (1, 1, 0).
Figura 3.4: Definic¸
˜
ao do n
´
o
O n
´
o n = (3; 2; 1) representa que no emparelhamento da figura 3.4, houve
um gap a esquerda do terceiro
´
atomo da prote
´
ına A.
3.2.2 Ramo
Os ramos do grafo correspondem
`
as decis
˜
oes que podemos tomar a partir
de um n
´
o (α, β, gap). As decis
˜
oes poss
´
ıveis s
˜
ao: ligar α e β ou rejeitar um dos
´
atomos.
O lucro da decis
˜
ao (lucro do ramo) ser
´
a L(α, β) se eles forem ligados, −10 se for criado
um novo gap ou 0 se nenhuma dessas opc¸
˜
oes ocorrer.
3.2.3 Alvo
Sempre que emparelharmos o
´
ultimo
´
atomo de uma das prote
´
ınas n
˜
ao h
´
a
mais emparelhamentos a fazer pois devemos respeitar a sequencialidade dos
´
atomos.
Sendo assim qualquer n
´
o que
´
e cabec¸a de um ramo indicando que o
´
ultimo
´
atomo de
uma das prote
´
ına foi emparelhado, este n
´
o
´
e um n
´
o do alvo.
Note que os n
´
os do conjunto alvo correspondem as folhas do grafo.
Para simplificar a exposic¸
˜
ao, vamos definir os seguintes n
´
os fict
´
ıcios:
T = {(N + 1, j, gap), (i, M + 1, gap)| i = 1, ..., N + 1, j = 1, ..., M + 1, gap = 0, 1, 2}.
32
Considere duas prote
´
ınas tais que N = 3 e M = 3,
Figura 3.5: Representac¸
˜
ao do grafo
Desta forma, no grafo da figura 3.5:
• o ramo ligando o n
´
o (1, 2, 2) ao n
´
o (2, 3, 0) indica que emparelhamos o primeiro
´
atomo da primeira prote
´
ına com o segundo
´
atomo da segunda prote
´
ına;
• o ramo ligando o n
´
o (2, 2, 0) ao n
´
o (2, 3, 2) indica que houve um gap
`
a esquerda do
terceiro
´
atomo da segunda prote
´
ına;
• o ramo ligando o n
´
o (2, 2, 0) ao n
´
o (3, 2, 1) indica que houve um gap
`
a esquerda do
segundo
´
atomo da primeira prote
´
ına;
• os n
´
os (4, 2, 1), (4, 3, 0), (3, 4, 0) e (2, 4, 2) s
˜
ao n
´
os do alvo.
Observac¸
˜
ao 3.2. Um n
´
o (α, β, gap) n
˜
ao cont
´
em nenhuma informac¸
˜
ao sobre o empare-
lhamento dos
´
atomos α e β. S
˜
ao os ramos que informam sobre a decis
˜
ao que tomamos.
Se examinarmos um emparelhamento das prote
´
ınas descrita por uma sequ
ˆ
encia de n
´
os
(α
i
, β
i
, gap
i
), saberemos que α
i−1
e β
i−1
foram emparelhados se gap
i
= 0.
3.3 Operador sucessor
Cada n
´
o tem no m
´
aximo tr
ˆ
es sucessores e n
´
os fict
´
ıcios n
˜
ao tem sucessores.
33
Definic¸
˜
ao 3.3. Operador sucessor
´
e uma aplicac¸
˜
ao Γ : n = (α, β, gap) ∈ N −→ Γ(n),
em que Γ(n) tem elementos descritos a seguir com os custos dos ramos correspondentes:
• Ligac¸
˜
ao de α e β:
u = (α + 1, β + 1, 0) com lucro c(n, u) = L(α, β).
• Criac¸
˜
ao de um novo gap:
Se gap= 0
v = (α + 1, β, 1), lucro =
0 se α = N ou α = 1
−10 no caso contr
´
ario
w = (α, β + 1, 2), lucro =
0 se β = M ou β = 1
−10 no caso contr
´
ario
• Aumento de um gap (respeitando o lema 3.1):
Se gap=1 e α < N
v = (α + 1, β, 1), lucro = 0
Se gap=2 e β < M
w = (α, β + 1, 2), lucro = 0
Observac¸
˜
ao 3.4. No operador sucessor, n
˜
ao permitimos o aumento de gap na situac¸
˜
oes
que contradizem o lema 3.1 e nem quando o
´
atomo
´
e o
´
ultimo da prote
´
ına. Poder
´
ıamos
aceitar esses sucessores, mas eles nunca poderiam pertencer a um emparelhamento
´
otimo
e aumentariam o tamanho do grafo.
3.4 Caminho
Um caminho (n
1
, n
2
, ..., n
p
) no grafo corresponde a um emparelhamento.
Sejam n
r
= (i
r
, j
r
, gap
r
). Ent
˜
ao para r = 1, ..., p − 1 (i
r
, j
r
) est
˜
ao emparelhados se e
somente se gap
r+1
= 0. O lucro do emparelhamento
´
e o lucro do caminho.
3.5 Super-estimativas
No problema de busca de caminhos de custo m
´
ınimo usando o algoritmo
A
∗
procur
´
avamos uma subestimativa que fosse a maior poss
´
ıvel. Neste problema, em que
34
estamos interessados em maximizar o lucro, procuramos por uma super-estimativa que
seja a menor poss
´
ıvel. Para isto analisamos a matriz L.
Definic¸
˜
ao 3.5. Considere um n
´
o n = (α, β, gap). Queremos calcular uma super-estima-
tiva
ˆ
h(α, β, gap) para a lucro h(α, β, gap) de um caminho
´
otimo entre (α, β, gap) e o
alvo, ou seja, de um emparelhamento
´
otimo entre os
´
atomos (α, α + 1, ..., N) e os
´
atomos
(β, β + 1, ..., M).
A estimativa
´
e calculada relaxando a exig
ˆ
encia de sequencialidade, e per-
mitindo que um
´
atomo seja ligado a v
´
arios outros. Temos duas estimativas:
• Tomando como refer
ˆ
encia a primeira prote
´
ına e ligando cada um de seus
´
atomos i
ao
´
atomo de m
´
axima pontuac¸
˜
ao L(i, j), obtemos
h(α, β, gap) ≤
N
i=α
max{L(i, j)|j = β, ..., M}) (3.5)
• Tomando como refer
ˆ
encia a segunda prote
´
ına e agindo de modo similar, obtemos
h(α, β, gap) ≤
M
j=β
max{L(i, j)|i = α , ..., N}) (3.6)
A estimativa
ˆ
h(α, β) ser
´
a calculada pelo menor entre esses dois limitantes
superiores. O valor de gap n
˜
ao
´
e levado em conta no c
´
alculo da estimativa.
O c
´
alculo de
ˆ
h
´
e feito facilmente a partir de L, gerando uma matriz HCHA-
PEU de mesma dimens
˜
ao.
HCHAP EU(α, β) =
ˆ
h(n), (3.7)
para todo n = (α, β, .), tal que n n
˜
ao est
´
a no alvo, pois
ˆ
h(t) = 0 para t no alvo.
Observac¸
˜
ao 3.6. Obtemos esta matriz de uma maneira bastante pr
´
atica. Primeiro so-
mamos para todo par (α, β) o m
´
aximo por linhas da matriz L(α : N, β : M), obtendo
uma matriz que denotamos Linha. Depois somamos o m
´
aximo por colunas obtendo uma
matriz que denotamos Coluna. Temos HCHAPEU fazendo o m
´
ınimo entre as entradas
correspondentes das duas matrizes.
35
Vamos analisar o seguinte exemplo, onde a matriz representa que estamos
tentando emparelhar uma prote
´
ınas com quatro
´
atomos e outra com cinco:
L =
34 28 25 24 27
33 35 34 31 29
40 26 27 32 25
30 31 26 28 36
Coluna =
177 137 102 68 36
177 137 102 68 36
166 126 95 68 36
151 121 95 64 36
Linha =
145 131 129 126 117
111 103 102 99 90
76 68 68 68 61
36 36 36 36 36
HCHAPEU =
145 131 102 68 36
111 103 102 68 36
76 68 68 68 36
36 36 36 36 36
3.6 Testes num
´
ericos
Neste problema n
˜
ao foi poss
´
ıvel utilizar o algoritmo de Dijkstra puro pois
como este grafo possui ramos com custos negativos, o crit
´
erio de parada geralmente
usado, “at
´
e fechar n
´
o do alvo” n
˜
ao se aplica. Sendo assim, acreditando termos uma boa
estimativa, testamos resolver este problema com o algoritmo A
∗
. Como estamos interes-
sados em analisar o desempenho da modelagem feita com grafos em relac¸
˜
ao ao algoritmo
de Programac¸
˜
ao Din
ˆ
amica, considerando o que foi exposto na sec¸
˜
ao 2.3, comparamos o
algoritmo A
∗
com o algoritmo de Busca Horizontal.
Para podermos comparar o desempenho dos dois algoritmos guardamos o
n
´
umero de caminhos: abertos, fechados, reabertos, eliminados. Guardamos tamb
´
em o
n
´
umero de elementos sucessores guardados, o tempo gasto por cada algoritmo e, como
neste problema o alvo
´
e um conjunto, guardamos tamb
´
em o n
´
umero de caminhos at
´
e o
36
alvo que foram abertos antes de se encontrar um caminho
´
otimo.
Estes testes foram feitos em um computador com um processador de 3Ghz
e 512 MB de mem
´
oria.
Exemplo 3.7. Este exemplo se refere a uma prote
´
ına com 100
´
atomos de carbono e outra
com 60
´
atomos de carbono que est
˜
ao pr
´
oximas em tr
ˆ
es trechos.
Algoritmo Abertos Fechados Reabertos Alvos Eliminados Sucessores
Horizontal 51949 49499 34167 67 63073 115088
A
∗
16013 15444 0 1 20024 36037
Algoritmo
Tempo total
Horizontal 48 segundos
A
∗
14 segundos
Lucro
´
otimo = 1040
Exemplo 3.8. Os pr
´
oximos exemplos s
˜
ao id
ˆ
enticos ao do item anterior exceto pela intro-
duc¸
˜
ao de uma perturbac¸
˜
ao aleat
´
oria.
Algoritmo Abertos Fechados Reabertos Alvos Eliminados Sucessores
Horizontal 50949 46595 31222 66 57357 108371
A
∗
16431 15444 0 1 19606 36037
Algoritmo Tempo total
Horizontal 44 segundos
A
∗
14 segundos
Lucro
´
otimo = 460,3477
Exemplo 3.9. Os pr
´
oximos exemplos s
˜
ao id
ˆ
enticos ao do item anterior exceto pela intro-
duc¸
˜
ao de uma perturbac¸
˜
ao aleat
´
oria.
Algoritmo Abertos Fechados Reabertos Alvos Eliminados Sucessores
Horizontal 43906 39011 23634 50 46702 90657
A
∗
17212 15444 0 1 18824 36036
Algoritmo Tempo total
Horizontal 31 segundos
A
∗
12 segundos
Lucro
´
otimo = 263,4077
37
Exemplo 3.10. Este exemplo se refere a uma prote
´
ına com 200
´
atomos de carbono e
outra com 110
´
atomos de carbono que est
˜
ao pr
´
oximas em quatro trechos.
Algoritmo Abertos Fechados Reabertos Alvos Eliminados Sucessores
Horizontal 342988 334448 273120 106 434469 777562
A
∗
62514 61491 0 1 80966 143480
Algoritmo Tempo total
Horizontal 6,7 minutos
A
∗
47 segundos
Lucro
´
otimo = 2050
Exemplo 3.11. O pr
´
oximo exemplo
´
e id
ˆ
entico ao do item anterior exceto pela introduc¸
˜
ao
de uma perturbac¸
˜
ao aleat
´
oria.
Algoritmo Abertos Fechados Reabertos Alvos Eliminados Sucessores
Horizontal 340985 326147 264779 113 418717 759814
A
∗
63384 61486 0 6 80077 143466
Algoritmo Tempo total
Horizontal 6,3 minutos
A
∗
42 segundos
Lucro
´
otimo = 857,5231
A seguir apresentamos o emparelhamentos obtido em cada um dos exem-
plos acima. Esta apresentac¸
˜
ao
´
e importante para analisarmos o comportamento da esti-
mativa.
38
Exemplo 3.7
Emparelhou Lucro Estimativa
ˆ
f(η)
90 53 1040 0 1040
89 52 1020 20 1040
88 51 1000 40 1040
87 50 980 60 1040
86 49 960 80 1040
85 48 940 100 1040
84 47 920 120 1040
83 46 900 140 1040
82 45 880 160 1040
81 44 860 180 1040
80 43 840 200 1040
79 42 820 220 1040
78 41 800 240 1040
77 40 780 260 1040
76 39 760 280 1040
75 38 740 300 1040
74 37 720 320 1040
73 36 700 340 1040
72 35 680 360 1040
71 34 660 380 1040
70 33 640 400 1040
50 32 630 420 1050
49 31 610 440 1050
48 30 590 460 1050
47 29 570 480 1050
46 28 550 500 1050
45 27 530 520 1050
44 26 510 540 1050
43 25 490 560 1050
42 24 470 580 1050
41 23 450 600 1050
40 22 430 620 1050
30 21 420 640 1060
29 20 400 660 1060
28 19 380 680 1060
27 18 360 700 1060
26 17 340 720 1060
25 16 320 740 1060
24 15 300 760 1060
23 14 280 780 1060
22 13 260 800 1060
21 12 240 820 1060
20 11 220 840 1060
19 10 200 860 1060
18 9 180 880 1060
17 8 160 900 1060
16 7 140 920 1060
15 6 120 940 1060
14 5 100 960 1060
13 4 80 980 1060
12 3 60 1000 1060
11 2 40 1020 1060
10 1 20 1040 1060
Exemplo 3.8
Emparelhou Lucro Estimativa
ˆ
f(η)
92 53 460 0 460
91 52 456 4 460
90 51 439 22 461
89 50 436 27 463
88 49 433 34 467
87 48 429 49 478
86 47 423 58 482
85 46 405 85 490
84 45 398 112 510
83 44 390 152 541
82 43 385 166 551
81 42 368 184 552
80 41 366 189 555
79 40 357 212 569
76 39 352 230 581
75 38 346 237 583
74 37 330 258 589
73 36 326 281 607
72 35 315 301 616
71 34 300 322 622
70 33 296 337 634
52 32 293 351 644
46 31 290 365 654
45 30 283 372 654
44 29 263 395 658
43 28 251 417 669
42 27 247 437 684
41 26 228 456 684
40 25 208 476 684
37 24 206 490 696
36 23 188 508 696
35 22 185 526 712
34 21 181 540 721
33 20 179 542 721
32 19 160 561 721
31 18 157 565 721
30 17 140 583 722
29 16 125 599 724
28 15 121 605 727
27 14 119 613 732
26 13 111 632 744
24 12 105 668 773
23 11 86 696 782
22 10 79 704 784
21 9 75 715 790
20 8 59 747 805
19 7 56 751 807
18 6 52 761 813
17 5 37 778 815
14 4 37 807 844
13 3 27 818 845
12 2 9 849 858
11 1 4 859 863
39
Exemplo 3.9
Emparelhou Lucro Estimativa
ˆ
f(η)
87 53 263 0 263
86 52 261 2 263
85 51 246 18 264
84 50 242 22 264
83 49 237 39 276
82 48 218 60 279
81 47 216 81 297
80 46 215 90 305
79 45 214 94 308
73 44 216 121 337
72 43 204 133 337
71 42 203 149 352
66 41 194 174 368
65 40 174 199 374
64 39 174 215 389
63 38 171 218 389
62 35 176 256 432
61 34 157 277 435
60 33 147 301 447
59 32 146 319 465
58 31 145 321 466
57 30 142 340 482
56 29 140 347 487
55 28 138 364 502
53 27 143 381 524
52 26 138 387 525
51 25 122 406 528
50 24 120 412 532
49 23 117 427 544
44 22 109 462 572
43 21 107 474 581
42 20 105 478 583
41 19 92 495 587
40 18 91 505 596
39 17 87 511 598
38 16 86 516 602
37 15 85 523 608
36 14 84 539 623
35 13 83 552 635
34 12 80 564 645
33 11 65 584 648
32 10 62 594 656
31 9 45 614 658
30 7 50 638 687
29 6 48 644 692
28 5 30 670 700
21 4 26 722 748
20 3 25 734 759
13 2 16 808 824
12 1 15 810 825
Exemplo 3.10
Emparelhou Lucro Estimativa
ˆ
f(η)
160 104 2050 0 2050
159 103 2030 20 2050
158 102 2010 40 2050
157 101 1990 60 2050
156 100 1970 80 2050
155 99 1950 100 2050
154 98 1930 120 2050
153 97 1910 140 2050
152 96 1890 160 2050
151 95 1870 180 2050
150 94 1850 200 2050
149 93 1830 220 2050
148 92 1810 240 2050
147 91 1790 260 2050
146 90 1770 280 2050
145 89 1750 300 2050
144 88 1730 320 2050
143 87 1710 340 2050
142 86 1690 360 2050
141 85 1670 380 2050
140 84 1650 400 2050
139 83 1630 420 2050
138 82 1610 440 2050
137 81 1590 460 2050
136 80 1570 480 2050
135 79 1550 500 2050
134 78 1530 520 2050
133 77 1510 540 2050
132 76 1490 560 2050
131 75 1470 580 2050
130 74 1450 600 2050
129 73 1430 620 2050
128 72 1410 640 2050
127 71 1390 660 2050
126 70 1370 680 2050
125 69 1350 700 2050
124 68 1330 720 2050
123 67 1310 740 2050
122 66 1290 760 2050
121 65 1270 780 2050
120 64 1250 800 2050
119 63 1230 820 2050
118 62 1210 840 2050
117 61 1190 860 2050
116 60 1170 880 2050
115 59 1150 900 2050
114 58 1130 920 2050
113 57 1110 940 2050
112 56 1090 960 2050
111 55 1070 980 2050
110 54 1050 1000 2050
90 53 1040 1020 2060
89 52 1020 1040 2060
88 51 1000 1060 2060
40
Continuac¸
˜
ao 3.10
Emparelhou Lucro Estimativa
ˆ
f(η)
87 50 980 1080 2060
86 49 960 1100 2060
85 48 940 1120 2060
84 47 920 1140 2060
83 46 900 1160 2060
82 45 880 1180 2060
81 44 860 1200 2060
80 43 840 1220 2060
79 42 820 1240 2060
78 41 800 1260 2060
77 40 780 1280 2060
76 39 760 1300 2060
75 38 740 1320 2060
74 37 720 1340 2060
73 36 700 1360 2060
72 35 680 1380 2060
71 34 660 1400 2060
70 33 640 1420 2060
50 32 630 1440 2070
49 31 610 1460 2070
48 30 590 1480 2070
47 29 570 1500 2070
46 28 550 1520 2070
45 27 530 1540 2070
44 26 510 1560 2070
43 25 490 1580 2070
42 24 470 1600 2070
41 23 450 1620 2070
40 22 430 1640 2070
30 21 420 1660 2080
29 20 400 1680 2080
28 19 380 1700 2080
27 18 360 1720 2080
26 17 340 1740 2080
25 16 320 1760 2080
24 15 300 1780 2080
23 14 280 1800 2080
22 13 260 1820 2080
21 12 240 1840 2080
20 11 220 1860 2080
19 10 200 1880 2080
18 9 180 1900 2080
17 8 160 1920 2080
16 7 140 1940 2080
15 6 120 1960 2080
14 5 100 1980 2080
13 4 80 2000 2080
12 3 60 2020 2080
11 2 40 2040 2080
10 1 20 2060 2080
41
3.6.1 An
´
alise dos testes
Nestes testes o algoritmo de Busca Horizontal e o algoritmo A
∗
agiram
dentro do esperado. Em todos os testes o algoritmo A
∗
foi superior pois o n
´
umero de
caminhos que ele precisa fechar at
´
e encontrar um caminho
´
otimo
´
e menor que o algoritmo
de Busca Horizontal, que precisa fechar todos os caminhos at
´
e o alvo.
Notamos tamb
´
em que o n
´
umero de caminhos reabertos pelo algoritmo de
Busca Horizontal
´
e grande isto faz com que o tempo gasto por este algoritmo seja maior.
Em relac¸
˜
ao ao tempo, observamos que a medida que aumentamos o tamanho do pro-
blema a diferenc¸a do tempo gasto pelo algoritmo de Busca Horizontal e pelo algoritmo
A
∗
aumenta.
Em relac¸
˜
ao a estimativa, nos exemplos onde n
˜
ao inserimos uma perturba-
c¸
˜
ao aleat
´
oria ela foi excelente, nos outros exemplos ela comec¸ou alta em relac¸
˜
ao ao custo
´
otimo. Por
´
em, mesmo assim n
˜
ao diminuiu a superioridade do algoritmo A
∗
.
Foram testados alguns exemplos fict
´
ıcios, o que d
´
a ao m
´
etodo alguma ex-
pectativa boa quanto ao seu comportamento. Para testar o m
´
etodo efetivamente seria
necess
´
ario introduzi-lo nos algoritmos Structal ou LOVO e fazer testes pr
´
aticos utilizando
banco de dados de prote
´
ınas. Isso excede os objetivos deste trabalho.
A metodologia introduzida aqui pode tamb
´
em ser aplicada ao sequencia-
mento em gen
ˆ
omica, em que h
´
a problemas semelhantes.
42
Cap
´
ıtulo 4
O quebra-cabec¸a de 15 pec¸as
Na
´
area de Intelig
ˆ
encia Artificial, algoritmos de busca em espac¸o de esta-
dos e planejamento de trajet
´
oria e ac¸
˜
oes s
˜
ao usados para o desenvolvimento de jogos tais
como: 8 puzzle, 15 puzzle, Resta 1, Xadrez. Neste cap
´
ıtulo apresentamos uma aplicac¸
˜
ao
do problema de busca de caminhos em grafos para o quebra-cabec¸a de 15 pec¸as (fifteen
puzzle).
O quebra-cabec¸a de 15 pec¸as consiste em 15 quadrados numerados de 1
a 15 mais um quadro branco que s
˜
ao colocados em uma caixa 4 × 4. Os quadrados
numerados simbolizam as 15 pec¸as do quebra-cabec¸a.
O jogo consiste no seguinte: dada uma configurac¸
˜
ao inicial arbitr
´
aria dese-
jamos chegar
`
a configurac¸
˜
ao original, figura 4.1, que chamaremos de configurac¸
˜
ao alvo.
Em cada passo desliza-se uma pec¸a do quebra-cabec¸a, fazendo-a ocupar o quadrado n
˜
ao
numerado que de agora em diante chamaremos de posic¸
˜
ao vazia.
Figura 4.1: Quebra-cabec¸a de 15 pec¸as
Em 1878 o americano Sam Loyd dizia estar conduzindo o mundo
`
a lou-
43
cura, quando desafiava as pessoas a resolver o problema citado acima oferecendo recom-
pensa de 1000 dol
´
ares a primeira soluc¸
˜
ao correta. Por
´
em a configurac¸
˜
ao que ele propunha
ser resolvida era imposs
´
ıvel, id
ˆ
entica a da figura acima exceto pela troca da pec¸a 14 com
a pec¸a 15. A loucura comec¸ou segundo [21] nos Estados Unidos em Janeiro de 1880 e na
Europa em Abril do mesmo ano.
Sabe-se agora que se trocarmos a posic¸
˜
ao de duas pec¸as, levantando-as da
caixa, a configurac¸
˜
ao resultante n
˜
ao tem soluc¸
˜
ao, pois para que exista soluc¸
˜
ao o n
´
umero
de trocas deve ser par. Por esta raz
˜
ao ningu
´
em conseguia resolver o jogo proposto por
Sam Loyd.
Loyd foi realmente quem popularizou o quebra-cabec¸a mas segundo [25]
ele foi inventado por Noyes Chapman, um agente de correio de Canastota no estado de
Nova Iorque, em 1874. Em [21] temos a informac¸
˜
ao que Chapman obteve sua patente em
Marc¸o de 1880.
Este problema chamou tanto a atenc¸
˜
ao do mundo como o Cubo de Rubik
ou Cubo m
´
agico cem anos mais tarde. O inventor (Erno Rubik) teve inspirac¸
˜
ao no quebra
cabec¸a de 15 pec¸as para desenvolver este jogo de racioc
´
ınio visto como uma vers
˜
ao tri-
dimensional do quebra cabec¸a.
´
E evidente que uma configurac¸
˜
ao pode ser restaurada para a configurac¸
˜
ao
alvo se ela foi obtida a partir da configurac¸
˜
ao alvo por meio de deslocamentos permitidos:
para obter a soluc¸
˜
ao
´
e preciso apenas percorrer o caminho inverso.
Dada uma configurac¸
˜
ao inicial, existem regras simples (descritas em v
´
arios
sites da internet) que levam a uma soluc¸
˜
ao do quebra-cabec¸as. Nosso problema
´
e encon-
trar uma soluc¸
˜
ao com o menor n
´
umero poss
´
ıvel de movimentos. Neste trabalho ten-
taremos resolver este problema utilizando dois dos algoritmos estudados, algoritmo de
Dijkstra e algoritmo A
∗
. Existem na literatura, [7] e [5], v
´
ariac¸
˜
oes do algoritmo A
∗
que
resolvem este problema.
4.1 Definindo o grafo
O problema de encontrar uma sequ
ˆ
encia de operac¸
˜
oes tranformando uma
configurac¸
˜
ao em outra
´
e equivalente ao problema de encontrar um caminho em um grafo.
Ent
˜
ao tratamos este problema como o de busca de caminho de custo m
´
ınimo atrav
´
es de
um grafo orientado. Esta modelagem para o quebra-cabec¸a de 15 pec¸as
´
e muito comum e
pode ser vista por exemplo em [14], [23], [24].
44
Figura 4.2: Grafo do quebra-cabec¸a
4.1.1 N
´
o e Ramo
Um n
´
o do grafo representa uma configurac¸
˜
ao do quebra-cabec¸a e cada
deslizamento de pec¸a para uma determinada posic¸
˜
ao corresponde a um ramo.
Como
´
e poss
´
ıvel termos 16! configurac¸
˜
oes para o quebra-cabec¸a, este pro-
blema
´
e representado por um grafo G de 16! n
´
os. Este grafo
´
e sempre bipartido em duas
componentes conexas, uma consistindo das configurac¸
˜
oes que podem ser restauradas at
´
e
a configurac¸
˜
ao alvo e outra das que n
˜
ao podem.
Representamos um n
´
o por um vetor coluna n ∈ R
16
. Cada componente
do vetor representa uma posic¸
˜
ao do quebra-cabec¸a e o valor de cada componente indica a
pec¸a que est
´
a ocupando tal posic¸
˜
ao. O n
´
umero 16 indica qual posic¸
˜
ao est
´
a vazia.
45
Figura 4.3: Representac¸
˜
ao do n
´
o
Na figura 4.3 a pec¸a 14 est
´
a ocupando a primeira posic¸
˜
ao do quebra-cabec¸a,
assim o n
´
umero 14 est
´
a na primeira componente do vetor n. Desta forma o n
´
o correspon-
dente a esta configurac¸
˜
ao
´
e dado por:
n = (14, 2, 15, 4, 5, 16, 7, 8, 9, 10, 1, 12, 13, 3, 6, 11)
T
.
Note que a posic¸
˜
ao 6 est
´
a vazia, logo o n
´
umero 16 aparece na sexta componente do vetor.
O n
´
o inicial
´
e o n
´
o que representa a configurac¸
˜
ao que queremos resolver.
4.2 Operador sucessor e custo
Observe que dada uma configurac¸
˜
ao arbitr
´
aria a partir dela com apenas um
deslocamento
´
e poss
´
ıvel obter duas, tr
ˆ
es ou quatro configurac¸
˜
oes. Isto equivale a dizer
que dado um n
´
o n ele admite dois, tr
ˆ
es ou quatro sucessores. Para definir o operador
sucessor usamos uma matriz dada, de dimens
˜
ao 16 × 4, que chamamos de matriz A.
Na matriz A as 16 linhas indicam as 16 posic¸
˜
oes vazias poss
´
ıveis para o
quebra-cabec¸a e as 4 colunas indicam a pec¸a de qual posic¸
˜
ao pode ser deslizada para a
posic¸
˜
ao vazia. Cada componente A(i, j), com i = 1, 2, ..., 16 e j = 1, 2, 3, 4, representa
as poss
´
ıveis mudanc¸as para uma pec¸a em func¸
˜
ao da posic¸
˜
ao que est
´
a vazia. Por exemplo:
• O elemento A(1, 1) representa que a pec¸a que ocupa a posic¸
˜
ao 2 pode ser deslizada
at
´
e a posic¸
˜
ao 1;
• A(1, 2) representa que a pec¸a que ocupa a posic¸
˜
ao 5 pode ser deslizada at
´
e a posic¸
˜
ao
1;
• Os elementos A(1, 3) e A(1, 4) est
˜
ao indicando que n
˜
ao
´
e poss
´
ıvel fazer mais des-
lizamentos se a posic¸
˜
ao que estiver vazia
´
e a posic¸
˜
ao 1.
46
A =
2 5 0 0
1 3 6 0
2 4 7 0
3 8 0 0
1 6 9 0
2 5 7 10
3 6 8 11
4 7 12 0
5 10 13 0
6 9 11 14
7 10 12 15
8 11 16 0
9 14 0 0
10 13 15 0
11 14 16 0
12 15 0 0
Definic¸
˜
ao 4.1. Definimos um n
´
o ¯n sucessor ao n
´
o n pelo seguinte procedimento:
Suponha que n(i) = 16 para um dado i ∈ {1, 2, ..., 16}.
Se A(i, j) = 0 para j = 1, 2, 3, 4
¯n(i) = n(A(i, j)),
¯n(A(i, j)) = 16
as demais componentes de n permanecem iguais as respectivas componentes de ¯n.
O operador sucessor Γ(n)
´
e definido pela aplicac¸
˜
ao do procedimento des-
crito acima a n.
Exemplo: n = (6, 3, 14, 4, 10, 2, 16, 8, 9, 7, 13, 12, 11, 1, 15, 5)
T
Nesta configurac¸
˜
ao n(7) = 16, ou seja, a s
´
etima posic¸
˜
ao est
´
a vazia. Logo
47
• A(7, 1) = 3, indica que a pec¸a que ocupa a posic¸
˜
ao 3 pode ser deslizada at
´
e a
posic¸
˜
ao 7, ¯n
1
(7) = n(3) = 14 e ¯n
1
(3) = 16, assim
¯n
1
= (6, 3, 16, 4, 10, 2, 14, 8, 9, 7, 13, 12, 11, 1, 15, 5)
T
.
• A(7, 2) = 6, indica que a pec¸a que ocupa a posic¸
˜
ao 6 pode ser deslizada at
´
e a
posic¸
˜
ao 7, ¯n
2
(7) = n(6) = 2 e ¯n
2
(6) = 16, assim
¯n
2
= (6, 3, 14, 4, 10, 16, 2, 8, 9, 7, 13, 12, 11, 1, 15, 5)
T
.
• A(7, 3) = 8, indica que a pec¸a que ocupa a posic¸
˜
ao 8 pode ser deslizada at
´
e a
posic¸
˜
ao 7, ¯n
3
(7) = n(8) = 8 e ¯n
3
(8) = 16, assim
¯n
3
= (6, 3, 14, 4, 10, 2, 8, 16, 9, 7, 13, 12, 11, 1, 15, 5)
T
.
• A(7, 4) = 11, indica que a pec¸a que ocupa a posic¸
˜
ao 11 pode ser deslizada at
´
e a
posic¸
˜
ao 7, ¯n
4
(7) = n(11) = 13 e ¯n
4
(11) = 16, assim
¯n
4
= (6, 3, 14, 4, 10, 2, 13, 8, 9, 7, 16, 12, 11, 1, 15, 5)
T
.
Note que ao gerarmos os sucessores de qualquer um dos n
´
os: ¯n
1
, ¯n
2
, ¯n
3
,
¯n
4
, um destes sucessores
´
e o n
´
o n. Desta forma ao expandirmos um caminho η = (n, c, p),
exclu
´
ımos o caminho sucessor cujo n
´
o terminal corresponde ao predecessor de n em η,
este caminho sucessor seria sempre eliminado.
Observe tamb
´
em que ao gerarmos um sucessor ¯n do n
´
o n estamos apenas
deslocando uma pec¸a do quebra-cabec¸a entre duas configurac¸
˜
oes. Desta forma o custo
associado ao ramo que representa este deslizamento
´
e 1.
4.3 Caminho e custo de um caminho
Um caminho P = (n
1
, n
2
, ..., n
p
) no grafo corresponde a uma sequ
ˆ
encia
de movimentos para a partir da configurac¸
˜
ao representada pelo n
´
o n
1
se chegar na confi-
gurac¸
˜
ao representada pelo n
´
o n
p
. O custo do caminho P
´
e p − 1, pois para se chegar em
n
p
a partir de n
1
foram precisos p − 1 deslocamentos.
4.4 Sub-estimativa
Procuramos uma sub-estimativa para o custo de um caminho at
´
e o alvo a
partir de um determinado n
´
o n que seja a maior poss
´
ıvel.
48
Um sub-estimativa conhecida se baseia na dist
ˆ
ancia de Manhattan tamb
´
em
conhecida como dist
ˆ
ancia pombalina ou dist
ˆ
ancia de t
´
axi e foi desenvolvida por Her-
mann Minkowski [26] no s
´
eculo 19. Ela recebeu esse nome pois define a menor dist
ˆ
ancia
poss
´
ıvel que um carro
´
e capaz de percorrer numa malha urbana reticulada ortogonal, tal
como se encontram em zonas como Manhattan ou a Baixa Pombalina.
Para um sistema de coordenadas fixo, a dist
ˆ
ancia de Manhattan entre dois
pontos S e Q
´
e simplesmente S − Q
1
.
Pensando em uma configurac¸
˜
ao do quebra-cabec¸a, consiste em determinar
quantos movimentos seriam necess
´
arios para mover cada pec¸a da posic¸
˜
ao que ela ocupa
at
´
e a posic¸
˜
ao em que desejamos que ela esteja, se fosse poss
´
ıvel levant
´
a-la com a m
˜
ao e
mover.
Definiremos agora a estimativa de custo de caminho entre um n
´
o n e o alvo
T , onde T n
˜
ao necessariamente
´
e o n
´
o que representa a configurac¸ao da figura 4.1, que
dizemos ser o alvo padr
˜
ao.
Para isso representamos as 16 posic¸
˜
oes do quebra-cabec¸a (as 16 compo-
nentes do vetor n) por 16 pontos em um sistema de coordenadas: a posic¸
˜
ao 1 corresponde
ao ponto S
1
= (1, 1), a posic¸
˜
ao 15 corresponde ao ponto S
15
= (4, 3).
Dados dois n
´
os n e t, com n representado por 16 pontos S
i
, com i =
1, 2, ..., 16, e t ∈ T representado por 16 pontos Q
i
, com i = 1, 2, ..., 16, cada pec¸a n(i)
ocupa uma posic¸
˜
ao que corresponde a um ponto S
i
em n, gostar
´
ıamos de desloc
´
a-la at
´
e a
posic¸
˜
ao que corresponde a um ponto Q
j
tal que t(j) = n(i), com j = 1, 2, ..., 16, em t.
Logo,
Definic¸
˜
ao 4.2. A estimativa de custo
ˆ
h de um caminho de custo m
´
ınimo entre n e um alvo
t
´
e:
ˆ
h(n, t) =
16
i=1
n(i)=16
t(j)=n(i)
S
i
− Q
j
1
, j = 1, 2, ..., 16 (4.1)
49
A estimativa de custo entre o n
´
o n e o alvo T
´
e dada por:
ˆ
h(n, T ) = min
t∈T
{
ˆ
h(n, t)} (4.2)
Exemplo:
(a) n (b) t
Figura 4.4: Estimativa entre o n
´
o n e o n
´
o t
Para n e t acima tem-se que:
− A pec¸a n(1) = 9 est
´
a no ponto S
1
gostar
´
ıamos que estivesse em Q
9
,
S
1
− Q
9
1
= 2;
− A pec¸a n(2) = 3 est
´
a no ponto S
2
gostar
´
ıamos que estivesse em Q
2
,
S
2
− Q
2
1
= 0;
Prosseguindo desta maneira chega-se a
ˆ
h(n, t) = 19.
Se o alvo for dado pelo n
´
o que representa a configurac¸
˜
ao da figura 4.1
utilizamos uma matriz D, de dimens
˜
ao 16 × 16, para obter esta estimativa. Neste caso
desejamos sempre que a pec¸a i esteja na posic¸
˜
ao i, i = 1, 2, ..., 15. Os elementos D(i, j)
indicam a dist
ˆ
ancia da pec¸a j (que deveria estar na posic¸
˜
ao j) at
´
e a posic¸
˜
ao i.
50
D =
0 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6
1 0 1 2 2 1 2 3 3 2 3 4 4 3 4 5
2 1 0 1 3 2 1 2 4 3 2 3 5 4 3 4
3 2 1 0 4 3 2 1 5 4 3 2 6 5 4 3
1 2 3 4 0 1 2 3 1 2 3 4 2 3 4 5
2 1 2 3 1 0 1 2 2 1 2 3 3 2 3 4
3 2 1 2 2 1 0 1 3 2 1 2 4 3 2 3
4 3 2 1 3 2 1 0 4 3 2 1 5 4 3 2
2 3 4 5 1 2 3 4 0 1 2 3 1 2 3 4
3 2 3 4 2 1 2 3 1 0 1 2 2 1 2 3
4 3 2 3 3 2 1 2 2 1 0 1 3 2 1 2
5 4 3 2 4 3 2 1 3 2 1 0 4 3 2 1
3 4 5 6 2 3 4 5 1 2 3 4 0 1 2 3
4 3 4 5 3 2 3 4 2 1 2 3 1 0 1 2
5 4 3 4 4 3 2 3 3 2 1 2 2 1 0 1
6 5 4 3 5 4 3 2 4 3 2 1 3 2 1 0
Lembrando a definic¸
˜
ao 4.2, onde padronizamos h(n) sendo o custo de um
caminho de custo m
´
ınimo entre n e o alvo padr
˜
ao, define-se:
Definic¸
˜
ao 4.3. A estimativa de custo de um caminho entre um n
´
o n at
´
e o alvo
´
e:
ˆ
h(n) =
16
i=1,n(i)=16
D(i, n(i)) (4.3)
Exemplo:
n = (2, 3, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
• Para i = 1, n(1) = 2 na posic¸
˜
ao 1 est
´
a a pec¸a 2, temos que D(1, 2) = 1.
51
• Para i = 2, n(2) = 3 na posic¸
˜
ao 2 est
´
a a pec¸a 3, temos que D(2, 3) = 1.
• Para i = 3, n(3) = 1 na posic¸
˜
ao 3 est
´
a a pec¸a 1, temos que D(3, 1) = 2.
• Para i de 4 a 16 n(i) = i e D(i, n(i)) = 0.
Portanto a estimativa de custo de um caminho a partir do n
´
o ¯n at
´
e o alvo
´
e
4.
Observac¸
˜
ao 4.4.
´
E importante observar que a estimativa de um n
´
o n e de seu n
´
o sucessor
¯n varia em 1 ou −1 para um alvo fixo.
(a)
ˆ
h(n) = 21 (b)
ˆ
h(¯n) = 20 (c)
ˆ
h(¯n) = 22
Figura 4.5: Variac¸
˜
ao da estimativa
Para um alvo T a variac¸
˜
ao
´
e -1, 0 ou 1.
Na sec¸
˜
ao 2.6.2 definimos estimativa consistente e constatamos que com
estimativas consistentes se estabelece propriedades an
´
alogas entre o algoritmo de Dijkstra
e o algoritmo A
∗
.
Teorema 4.5. A sub-estimativa dada pela definic¸
˜
ao 4.2
´
e consistente.
Demonstrac¸
˜
ao:
Seja P = (n = n
0
, n
1
, ..., n
p
= n
) um caminho de custo
´
otimo entre n e n
. Pela
observac¸
˜
ao acima temos que
ˆ
h(n
i+1
, t) ≥
ˆ
h(n
i
, t) − 1 para todo t ∈ T , e portanto
ˆ
h(n
i+1
, T ) ≥
ˆ
h(n
i
, T ) − 1.
Desta forma
ˆ
h(n
, T ) ≥
ˆ
h(n, T ) − p, mas h(n, n
) = p j
´
a que P
´
e um
caminho de custo m
´
ınimo.
Portanto
ˆ
h(n
, T ) + h(n, n
) ≥
ˆ
h(n, T ), o que prova que a sub-estimativa
´
e consistente.
52
Ent
˜
ao, de acordo com o teorema 2.23, uma vez que um caminho
´
e fechado
j
´
a se encontrou um caminho de custo m
´
ınimo at
´
e seu n
´
o terminal. Sendo assim, nenhum
caminho pode ser reaberto pelo algoritmo A
∗
.
Tendo uma sub-estimativa consistente para o quebra-cabec¸a pode-se usar
o algoritmo A
∗
para “tentar” resolver este problema.
4.5 Estrutura de dados
Neste problema a lista aberto cresce rapidamente pois o grafo
´
e muito
grande. Para se ter uma id
´
eia: para armazenarmos todas as configurac¸
˜
ao do quebra-
cabec¸a que est
˜
ao na mesma componente conexa que a configurac¸
˜
ao alvo seriam ne-
cess
´
arios 150000 Gigabytes de mem
´
oria de computador, ou, se pudessemos escrever cada
configurac¸
˜
ao em 1 cm
2
de papel, seria necess
´
ario uma
´
area maior que a
´
area da Ilha de
Santa Catarina para armazenarmos todas as configurac¸
˜
ao que podem ser resolvidas. Na
implementac¸
˜
ao apenas os caminhos gerados pelo algoritmo s
˜
ao armazenados em uma
estrutura {η
i
}
i=1,...,q
k
, em que q
k
´
e o n
´
umero de elementos listados na iterac¸
˜
ao k.
H
´
a duas operac¸
˜
oes de alto custo computacional em cada iterac¸
˜
ao, para as
quais utilizamos estruturas de dados apropriadas:
1. busca de um aberto de custo (ou estimativa) m
´
ınimo, que utiliza a estrutura heap;
2. eliminac¸
˜
ao ou introduc¸
˜
ao de um sucessor na lista, que utiliza a estrutura hashing.
Os custos, ou as estimativas de custos, e um indicador para um caminho da
lista Aberto s
˜
ao armazenados em um Heap. Os custos, ou as estimativas, representam as
chaves do Heap sendo os itens os indicadores para os caminhos. Os itens s
˜
ao dispostos
de maneira que um caminho com chave m
´
ınima esteja na raiz do heap.
Assim com apenas uma consulta ao Heap pode-se extrair um caminho com
m
´
ınima chave, e
´
e este caminho que escolhemos para expandir. Ap
´
os extrair este elemento
de um maneira muito r
´
apida se reordena o Heap.
Uma breve explicac¸
˜
ao sobre Heap encontra-se no Ap
ˆ
endice A.
No processo de eliminac¸
˜
oes
´
e preciso varrer listas para verificar se os ca-
minhos j
´
a foram listados. Fazemos isto usando um vetor de Hashing.
53
A cada caminho η
i
= (n
i
, c
i
, p
i
) uma func¸
˜
ao de espalhamento (Hash) as-
socia um valor H(n
i
). O Hashing
´
e um vetor inicialmente com componentes nulas. Na
linha deste vetor correspondente ao valor H(n
i
) guarda-se o valor i. Assim sempre que
um caminho ¯η = (¯n, ¯c, ¯p) for gerado, a componente i do Hashing correspondente a H(¯n)
nos d
´
a a seguinte informac¸
˜
ao: se a componente
´
e nula, o n
´
o n
˜
ao est
´
a listado; sen
˜
ao, est
´
a
listado um n
´
o n com H(n) = H(¯n)
´
e
´
e necess
´
ario comparar n e ¯n diretamente.
Uma explicac¸
˜
ao sobre Hash pode ser vista em [11].
4.6 Testes num
´
ericos
Como dados relevantes a observar guardamos os seguintes n
´
umeros: ca-
minhos abertos, caminhos fechados, caminhos eliminados, colis
˜
oes feitas pela func¸
˜
ao de
hashing. Guardamos tamb
´
em a quantidade de n
´
os gerados pelo operador sucessor, a esti-
mativa de custo de um caminho atrav
´
es do n
´
o inicial e o alvo.
Os pr
´
oximos dois exemplos obtivemos deslizando as pec¸as do quebra-
cabec¸a a partir da configurac¸
˜
ao alvo pois sabemos que eles t
ˆ
em soluc¸
˜
ao pois est
˜
ao na
mesma componente conexa que a configurac¸
˜
ao alvo e, deslizando as pec¸as temos uma
super-estimativa para o custo de um caminho de custo
´
otimo. Para estes testes adotamos
como 100000 o n
´
umero m
´
aximo de iterac¸
˜
oes, a aus
ˆ
encia do n
´
umero de passos indica que
o algoritmo termina sem encontrar uma soluc¸
˜
ao.
Estes testes foram feitos em Matlab em um computador com um processa-
dor de 3Ghz e 512 MB de mem
´
oria.
Exemplo 4.6.
Algoritmo Abertos Fechados Eliminados Sucessores Passos Colis
˜
oes
ˆ
f
Dijkstra 197085 100001 13709 210793 - 2314 -
A
∗
2108 1040 28 2141 27 1 21
54
Algoritmo Tempo total
Dijkstra 68,3 minutos
A
∗
2,2 segundos
Exemplo 4.7.
Algoritmo Abertos Fechados Eliminados Sucessores Passos Colis
˜
oes
ˆ
f
Dijkstra 198782 100001 12434 211215 - 2326 -
A
∗
10016 4972 230 10267 36 5 28
Algoritmo Tempo total
Dijkstra 68,8 minutos
A
∗
17,2 segundos
Os pr
´
oximos exemplos foram obtidos fazendo-se um n
´
umero par de trocas
entre as pec¸as do quebra-cabec¸a pois desta forma as configurac¸
˜
oes apresentadas est
˜
ao na
mesma componente conexa que a configurac¸
˜
ao alvo e assim possuem soluc¸
˜
ao.
Exemplo 4.8. Duas trocas:
Algoritmo Abertos Fechados Eliminados Sucessores Passos Colis
˜
oes
ˆ
f
Dijkstra 198075 100001 13469 211543 - 2380 -
A
∗
3536 1755 122 3684 20 0 4
Algoritmo Tempo total
Dijkstra 66,4 minutos
A
∗
4 segundos
Nos pr
´
oximos testes aumentamos o n
´
umero m
´
aximo de iterac¸
˜
oes para
200000.
55
Exemplo 4.9. Quatro trocas:
Algoritmo Abertos Fechados Eliminados Sucessores Passos Colis
˜
oes
ˆ
f
Dijkstra 393417 200001 28939 422355 - 9184 -
A
∗
36576 18774 2011 38872 28 103 8
Algoritmo Tempo total
Dijkstra 4,4 horas
A
∗
2,7 minutos
Exemplo 4.10. Seis trocas:
Algoritmo Abertos Fechados Eliminados Sucessores Passos Colis
˜
oes
ˆ
f
A
∗
316278 164812 24722 341179 34 6024 12
Algoritmo Tempo total
A
∗
3,1 horas
No pr
´
oximo exemplo usamos 550000 para o limite de iterac¸
˜
oes.
Exemplo 4.11. Oito trocas:
Algoritmo Abertos Fechados Eliminados Sucessores Passos Colis
˜
oes
ˆ
f
A
∗
1036695 550001 93101 1129795 - 63827 16
56
Algoritmo Tempo total
A
∗
54,6 horas
O algoritmo p
´
ara com 550000 iterac¸
˜
oes sem resolver o problema.
4.6.1 An
´
alise dos testes
Ao fim destes testes confirmamos a superioridade do algoritmo A
∗
em
relac¸
˜
ao ao algoritmo de Dijkstra na tentativa de resolver este problema.
´
E importante
salientar que devido ao espac¸o de busca ser muito grande
´
e indispens
´
avel o uso desta
informac¸
˜
ao quanto a proximidade do alvo para se chegar nele com maior rapidez e con-
sequentemente diminuir o esforc¸o computacional.
Embora, em algumas configurac¸
˜
oes, o algoritmo A
∗
tem sido muito efici-
ente, notamos que a medida que aumentamos o n
´
umero de trocas o n
´
umero de iterac¸
˜
oes
e o tempo computacional aumentaram significativamente. Al
´
em disso encontramos con-
figurac¸
˜
oes que o algoritmo A
∗
n
˜
ao conseguiu resolver, exemplo 4.11 onde o algoritmo
atingiu 550000 iterac¸
˜
oes em mais de 54 horas.
Analisando o comportamento da estimativa dos primeiros caminhos fecha-
dos observamos que o erro em relac¸
˜
ao ao custo
´
otimo
´
e grande, em especial a estimativa
do caminho a partir da raiz. Por exemplo, no exemplo 4.8 a estimativa do caminho atrav
´
es
de seu n
´
o inicial
´
e 4, enquanto que o custo
´
otimo
´
e 20, no exemplo 4.9 a estimativa
´
e 8
e o custo
´
otimo
´
e 28. Sendo assim propomos uma nova estimativa que continue sendo
admiss
´
ıvel mas que diminua o erro em relac¸
˜
ao ao custo
´
otimo.
4.7 Uma nova sub-estimativa
Sugerimos aumentar o alvo, que originalmente
´
e T = {t
0
}, t
0
a configurac¸
˜
ao
padr
˜
ao, construindo um novo alvo definido por:
˜
T = {n ∈ N |h(n, t
0
) = k},
com k ∈ N. Utilizaremos valores de k entre 8 e 16.
57
Figura 4.6: Representac¸
˜
ao da nova estimativa
Para um dado k, esse conjunto pode ser constru
´
ıdo pelo algoritmo de Dijks-
tra, que neste caso equivale a Busca Horizontal. Utilizamos o algoritmo at
´
e fechar o
´
ultimo elemento de custo k − 1. Neste momento os n
´
os abertos s
˜
ao a frente de onda de
custo k, que coincide com
˜
T .
Seja
˜
N = {n ∈ N |h(n, t
0
) < k}. Se s ∈
˜
N ou s ∈
˜
T , ent
˜
ao o problema
de otimizac¸
˜
ao
´
e simples: basta procurar s entre os n
´
os listados pelo algoritmo de Dijkstra
e l
´
a se encontrar
´
a um caminho
´
otimo de t a s (que invertido
´
e um caminho
´
otimo de s a
t).
Vamos supor que o n
´
o inicial s
´
e tal que s ∈ N −
˜
N . Ent
˜
ao h(s) ≥ k.
Definic¸
˜
ao 4.12. A estimativa de custo
˜
h associada a cada n
´
o n ∈ N −
˜
N
´
e:
˜
h(n) = min
t∈
˜
T
{
ˆ
h(n, t)} (4.4)
Os seguintes fatos s
˜
ao imediatos:
•
˜
h(.)
´
e admiss
´
ıvel, pois para qualquer t ∈
˜
T ,
˜
h(n) ≤
ˆ
h(n, t) ≤ h(n, t).
•
˜
h(.)
´
e consistente. Isso se demonstra exatamente como no teorema 4.5.
• h(n, t
0
) = k + h(n,
˜
T ) para todo n ∈ N −
˜
N . Todo caminho
´
otimo de s a t tem
seus k
´
ultimos n
´
os na lista gerada pelo algoritmo de Dijkstra.
• k +
˜
h(n)
´
e sub-estimativa para h(n, t
0
).
O algoritmo
Roda-se o algoritmo A
∗
com alvo
˜
T e estimativa
˜
h(.). Ao se fechar um
caminho ¯η = (¯n, ¯c, ¯p) com ¯n ∈
˜
T , obt
´
em-se um caminho
´
otimo de custo h(s) = k + ¯c,
recuperando o caminho de s a ¯n associado a ¯η e o caminho de ¯n ∈
˜
T a t
0
com k n
´
os a
partir da lista constru
´
ıda por Dijkstra.
58
4.7.1 Novos testes
Iniciamos guardando alguns conjuntos
˜
T . Analisamos o tempo e o n
´
umero
de iterac¸
˜
oes gastos para gerar este conjunto:
k Alvos Fechados Tempo
8 446 414 1 seg
9 946 860 1,9 seg
10 1948 1806 3,8 seg
11 3938 3754 9,8 seg
12 7808 7692 29,8 seg
13 15544 15500 2,1 min
14 30821 31044 7,1 min
15 60842 61865 27 min
16 119000 122707 1,7 horas
Observac¸
˜
ao 4.13.
´
E importante ressaltar que estes conjuntos obtidos acima n
˜
ao s
˜
ao
gerados toda vez que vamos resolver um problema, eles s
˜
ao gerados uma
´
unica vez e em
seguida guardados na mem
´
oria do computador. Sendo assim para analisarmos o tempo
para resolver o problema
´
e necess
´
ario apenas olhar para o tempo gasto pelo algoritmo
A
∗
.
Para comparar com as dados obtidos na sec¸
˜
ao 4.6 guardamos o n
´
umero de
caminhos fechados, o tempo total gasto pelo algoritmo (A
∗
e suas func¸
˜
oes: listagem de
caminho, heap, hashing,...), o valor da estimativa de custo de cada caminho a partir do n
´
o
inicial e, considerando que o c
´
alculo da estimativa
´
e muito mais complexo, o tempo gasto
para a estimativa.
Para cada exemplo analisamos diferentes conjuntos de alvos. A primeira
linha da tabela repete os resultados obtidos pelo algoritmo A
∗
na sec¸
˜
ao 4.6.
Exemplo 4.6, custo
´
otimo 27.
k Fechados
˜
f Estimativa Total
1 1040 21 - 2,2 seg
9 208 23 0,2 seg 2 seg
10 173 21 0,2 seg 2 seg
11 132 23 0,2 seg 2 seg
12 133 23 0,3 seg 3 seg
Exemplo 4.7 custo
´
otimo 36.
59
k Fechados
˜
f Estimativa Total
1 4972 28 - 17,2 seg
10 1985 30 1,6 seg 8 seg
11 975 30 1,1 seg 5 seg
12 898 30 1,4 seg 6 seg
13 772 32 1,7 seg 6 seg
Exemplo 4.8 custo
´
otimo 20.
k Fechados
˜
f Estimativa Total
1 1755 4 - 4 seg
8 507 16 0,4 seg 3 seg
9 122 16 0,2 seg 1 seg
10 83 16 0,2 seg 1 seg
11 59 16 0,2 seg 2 seg
12 39 16 0,1 seg 3 seg
15 12 20 0,2 seg 7 seg
Exemplo 4.9 custo
´
otimo 28.
k Fechados
˜
f Estimativa Total
1 18774 8 - 2,7 min
10 2500 18 2,1 seg 11 seg
11 2207 20 2,6 seg 10 seg
12 1647 20 2,4 seg 8 seg
13 644 20 1,6 seg 6 seg
14 552 20 2,3 seg 8 seg
Exemplo 4.10 custo
´
otimo 34.
k Fechados
˜
f Estimativa Total
1 164812 12 - 3,1 h
10 17832 20 13 seg 2,9 min
11 20028 22 19 seg 3,8 min
12 16694 22 21,4 seg 2,9 min
13 11154 22 22,4 seg 1,6 min
14 4522 22 16,5 seg 36 seg
15 4056 24 31 seg 52 seg
Exemplo 4.11
60
k Fechados
˜
f Estimativa Total
13 39315 26 1,3 min 13,8 min
14 44932 26 2,5 min 18,5 min
15 36863 28 4,4 min 15,4 min
16 27442 28 8,8 min 15,3 min
Este problema
´
e resolvido em 40 passos.
Exemplo 4.14. oito trocas
k Fechados
˜
f Estimativa Total
13 200001 64 5.6 min 3,4 horas
14 200001 64 10.6 min 4,01 horas
15 200001 64 21.9 min 4,2 horas
16 200001 64 57.7 min 4,9 horas
Com 200000 iterac¸
˜
oes este problema n
˜
ao foi resolvido.
4.7.2 An
´
alise dos testes
Comparando com as testes feitos na sec¸
˜
ao 4.6 vemos que com a nova es-
timativa, o desempenho do algoritmo A
∗
teve uma melhora bem consider
´
avel, principal-
mente nos exemplos obtidos fazendo-se trocas. Isto se deve ao fato que o erro entre o
custo
´
otimo e a estimativa de custo do caminho entre o n
´
o inicial e o alvo ter diminu
´
ıdo,
j
´
a que para estas configurac¸
˜
oes iniciais
ˆ
f(η)
´
e bem menor que o custo
´
otimo do caminho
representado pelo caminho inicial η.
Outro dado importante a comentar
´
e o n
´
umero de caminhos Fechados
(equivalente ao n
´
umero de iterac¸
˜
oes). Como a estimativa est
´
a mais pr
´
oxima do custo
´
otimo o algoritmo tende a fechar um n
´
umero menor de caminhos que n
˜
ao fazem parte
de caminhos
´
otimos, esta
´
e uma explicac¸
˜
ao para o n
´
umero de caminhos fechados ter di-
minu
´
ıdo em relac¸
˜
ao ao testes da sec¸
˜
ao 4.6, contribuindo assim para o melhora do tempo
computacional.
61
Note tamb
´
em que a medida que aumentamos o custo de
˜
T o tempo gasto
para calcular
˜
h(.) aumenta, isto porque o n
´
umero de n
´
os em
˜
T cresce bastante ao aumentar
o custo de k − 1 para k.
Entretanto a melhora n
˜
ao foi t
˜
ao boa como esper
´
avamos, pois ainda encon-
tramos configurac¸
˜
oes que n
˜
ao conseguimos obter a soluc¸
˜
ao. No exemplo 4.14 com oito
trocas, testamos diferentes custos para o alvo com 200000 iterac¸
˜
oes e para nenhum deles
conseguimos obter soluc¸
˜
ao.
62
Conclus
˜
ao
Este trabalho propiciou-me uma boa oportunidade para entender como s
˜
ao
feitas as modelagens em problemas de grafos. Percebi que o estudo do modelo deve ser
feito com muito cuidado pois a resoluc¸
˜
ao do problema depende da qualidade do modelo.
Em relac¸
˜
ao aos algoritmos estudados e implementados, os resultados obti-
dos com os problemas propostos vieram confirmar o que hav
´
ıamos visto na teoria. Con-
firmamos que se
´
e poss
´
ıvel obter uma estimativa de custo para um problema, nenhum
algoritmo de rotulac¸
˜
ao supera o algoritmo A
∗
, pois ele realiza menos expans
˜
oes.
Concluo tamb
´
em que devido ao fato de que o tamanho das listas pode ficar
muito grande
´
e necess
´
ario sabermos administr
´
a-las usando ferramentas essenciais, por
isso o uso do Heap e do Hashing foi fundamental. Desta forma creio ser indispens
´
avel
o conhecimento de estruturas de dados que facilitem o trabalho diminuindo o esforc¸o
computacional.
As aplicac¸
˜
oes que foram feitas possibilitaram-me entender como
´
e cons-
tru
´
ıdo um modelo e qu
˜
ao rica a Matem
´
atica pode ser ao descrev
ˆ
e-los. No problema de
alinhamento de prote
´
ınas n
˜
ao obtive grandes surpresas quanto ao desempenho dos algorit-
mos, pois esperava pela superioridade do algoritmo A
∗
. No problema do quebra-cabec¸a
percebi como um problema pode ficar grande e entendi porque o algoritmo A
∗
n
˜
ao
´
e
suficiente para resolver este problema.
63
Ap
ˆ
endice A
Heap
Um heap
´
e uma arboresc
ˆ
encia com as seguintes propriedades:
A cada n
´
o x associam-se:
• Um item i (elemento de algum conjunto pr
´
e-definido como vetores ou estruturas).
• Uma chave c(i) ∈ R (custos).
• Se um n
´
o y contendo o item j
´
e sucessor de x ent
˜
ao c(j) ≥ c(i).
Da definic¸
˜
ao acima conclui-se que a chave da raiz do heap
´
e m
´
ınima.
Mais ainda, a raiz de qualquer sub-arboresc
ˆ
encia do heap tem chave m
´
ınima nesta sub-
arboresc
ˆ
encia.
Heaps s
˜
ao usados para ordenar listas, e s
˜
ao muito eficientes quando se
necessita manter atualizada a informac¸
˜
ao sobre itens de custo m
´
ınimo em uma lista, como
ocorre nesta dissertac¸
˜
ao: a cada iterac¸
˜
ao dos algoritmos escolhe-se um elemento aberto
de m
´
ınimo custo ou estimativa.
Como de costume vamos associar a um n
´
o do grafo
`
a tripla η = (n, c, p)
em que p
´
e um apontador para o antecessor do n
´
o na arboresc
ˆ
encia.
1
d-Heap
Um d-heap
´
e um heap em que cada n
´
o possui no m
´
aximo d sucessores,
d ∈ N. O caso mais comum, que utilizaremos neste trabalho, e d=2 (
´
arvore bin
´
aria).
1
No texto η representa um caminho da raiz ao n
´
o. Aqui, como o grafo
´
e uma arboresc
ˆ
encia, caminhos e
n
´
os s
˜
ao bi-univocamente associados.
64
Figura A.1: 2-Heap
Um 2-heap
´
e armazenado em um vetor (array) com componentes h(j),
j = 1, 2, ..., 2
p
: os sucessores do n
´
o h(j) s
˜
ao h(2j) e h(2j + 1).
Procedimentos b
´
asicos de reodenac¸
˜
ao: siftup e siftdown
Dado um heap, suponha que η = (i, c(i), p)
´
e um n
´
o. Suponha que por
alguma raz
˜
ao mudamos o valor de c(i) de modo a romper a ordenac¸
˜
ao exigida para o
heap. Podem ocorrer dois casos que necessitam de reordenac¸
˜
ao:
1. Seja ¯η = (j, c(j), ¯p) o antecessor de η (apontado por η). Se c(j) ≥ c(i), deve-se
trocar os itens nos dois n
´
os, empurrando para cima o item i que est
´
a barato. Agora
η = (j, c(j), p) n
˜
ao viola a regra de ordenac¸
˜
ao, mas ¯η = (i, c(i), ¯p) pode violar e o
procedimento deve ser executado novamente.
Constr
´
oi-se o seguinte procedimento recursivo para η = (i, c(i), p)
siftup(η) :
se p = 0, pare (o n
´
o
´
e raiz).
recupere o n
´
o ¯η = (j, c(j), ¯p) antecessor de η.
se c(j) > c(i)
¯η = (i, c(i), ¯p)
η = (j, c(j), p)
siftup(¯η)
2. Seja ¯η = (j, c(j), ¯p) o sucessor de menor custo de η. Se c(i) > c(j), devem-se
trocar os
´
ıtens dos dois n
´
os, empurrando para baixo o item i que est
´
a caro. Proce-
dimento:
65
siftdown(η) :
se η
´
e folha do grafo, pare.
recupere o n
´
o ¯η = (j, c(j), ¯p) de menor custo entre os sucessores de η.
se c(j) < c(i)
¯η = (i, c(i), ¯p)
η = (j, c(j), p)
siftdown(¯η)
Com esses procedimentos pode-se operar no heap:
• Inserir um novo item i: precisamos criar um novo n
´
o ¯η = (i, c(i), ¯p):
Basta escolher arbitrariamente um n
´
o da arboresc
ˆ
encia que n
˜
ao tem ainda o n
´
umero
m
´
aximo de sucessores (em um 2-heap, adiciona-se uma componente nova no final
do array). Seja ¯p um apontador para esse n
´
o.
adiciona-se o n
´
o ¯η = (i, c(i), ¯p) ao grafo
siftup(¯η)
• Descartar (deletar) um item i: seja η = (i, c(i), p) o n
´
o que cont
´
em o item i.
Se ¯η
´
e uma folha, basta elimin
´
a-lo da
´
arvore.
Sen
˜
ao, escolhe-se uma folha qualquer ¯η = (j, c(j), ¯p) e faz-se:
eliminar ¯η da
´
arvore
η = (j, c(j), p)
siftdown(η)
Complexidade: em um 2-heap com profundidade p guardam-se 2
p
− 1
itens. Cada inserc¸
˜
ao faz um m
´
aximo de p passos (siftup) consistindo de comparac¸
˜
ao e
troca de elementos.
Em termos do n
´
umero de itens, cada inserc¸
˜
ao tem complexidade
O(log
2
p). Para ordenar uma lista de p itens fazendo p inserc¸
˜
oes a partir de um heap vazio,
fazem-se O(p.log
2
p) operac¸
˜
oes.
Para descartar itens, a complexidade
´
e semelhante.
Este estudo foi baseado em [16].
66
Refer
ˆ
encias Bibliogr
´
aficas
[1] ANDREANI, R., MART
´
INEZ, J. M., MART
´
INEZ, L., YANO F., Continuous Opti-
mization Methods for Structural Alignments, To appear im Mathematical Program-
ming, 2006. Currently available at http://www.ime.unicamp.br/ martinez/
[2] ANDREANI, R., MART
´
INEZ, J. M., MART
´
INEZ, L., Low Order Value Optimiza-
tion Methods for Protein Alignment. To be published, 2006. Currently available at
http://www.ime.unicamp.br/ martinez/
[3] ANDREANI, R., MART
´
INEZ, J. M., MART
´
INEZ, L., Protein structal alignment:
Interpretation as a Low Order Value Optimization problem ans resulting practial
algorithms. Currently available at http://www.ime.unicamp.br/ martinez/
[4] ARCHER, A. F., A Modern Treatment of the 15 puzzle, The American Mathematical
Montly, november 1999.
[5] CULBERSON, J., C., SCHAEFFER, J., Efficiently Searching the 15-Puzzle, Depar-
tament of Computing Science, University of Alberta, 1994.
[6] KARLEMO, F.,R.,W., OSTERGARD, P., R., J., On Sliding block puzzles, Journal of
Combinatorial Mathematics and Combinatorial Computing, vol 34, 97-107, 2000.
[7] KORF, R., Depth-First Iterative-Deepening an Optimal Admissible Treesearch, Ar-
tificial Inteligence, vol. 27, n
o
1: 97-109, 1985.
[8] KORF, R., FELNER, A., Disjoint Pattern Database Heuristics, Artificial Inteli-
gence, vol. 134, n
o
1-2: 9-22, 2002.
[9] HART, P., NILSSON, N., RAPHAEL, B., A formal basis for the Heuristic Deter-
mination of Minimun Cost Paths, IEEE Trans. Syst. Cybernetics 4, N
o
2: 100-107,
julho, 1968.
[10] SUBBIAH, S., LAURENTS, D. V., LEVITT, M., Structural similarity of
DNA-binding domains of bacteriophage repressors and globin core Curr. Biol.
1993;3:141-148.
67
[11] AHO, A., V., H0PCROFT, J., E., ULLMANN, J., D., Data Structures ans Algo-
rithms, Addison-Wesley, Boston, 1983.
[12] GONZAGA, C., Busca de Caminhos em Grafos e Aplicac¸
˜
oes, I Reuni
˜
ao de Ma-
tem
´
atica Aplicada, IBM, Rio de Janeiro, 1978.
[13] GONZAGA, C., Notas de aula de Pesquisa Operacional, Universidade Federal de
Santa Catarina, Florian
´
opolis, 2005.
[14] NILSSON, N., Problem-Solving Methods in Artificial Intelligence, McGRAW-
HILL, 1971.
[15] RABUSKE, M. A., Introduc¸
˜
ao
`
a teoria de grafos, Editora da UFSC, 1992.
[16] TARJAN, R., Data Structures and Network Algorithms, Society for Industrial and
Applied Mathematics, 1983.
[17] GONZAGA, C., Estudo de Algoritmos de Busca em Grafos e sua Aplicac¸
˜
ao a Pro-
blemas de Planejamento, Tese de Doutorado, Dpto. de Engenharia de Sistemas e
Computac¸
˜
ao, COPPE, Universidade Federal do Rio de Janeiro, 1973.
[18] KAGOIKI, K. C., Estudo e implementac¸
˜
ao de algoritmos de busca em grafos, Mo-
nografia de Graduac¸
˜
ao, Dpto. de Matem
´
atica, Universidade Federal de Santa Cata-
rina, 2005.
[19] OLIVEIRA, D. C., Alinhamento de Sequ
ˆ
encias, Monografia de Graduac¸
˜
ao, Dpto.
de Ci
ˆ
encia da Computac¸
˜
ao, Universidade Federal de Lavras, 2002.
[20] SILVA, S. G. O., Previs
˜
ao da Estrutura Secund
´
aria de Prote
´
ınas utilizando Redes
Neurais, Dissertac¸
˜
ao de Mestrado, Dpto. de Inform
´
atica, Universidade de Lisboa,
1999.
[21] http://bd.thrijswijk.nl/15puzzle/15puzzen.htm, acessado em 17/12/2006.
[22] http://www.cut-the-knot.org/pythagoras/history15.shtml, acessado em 20/06/2006.
[23] www.eternallyconfuzzled.com/brain.html, acessado em 20/06/2006.
[24] http://mathworld.wolfram.com/15Puzzle.html, acessado em 20/06/2006.
[25] http://en.wikipedia.org/wiki/N-puzzle, acessado em 20/06/2006.
[26] http://pt.wikipedia.org/wiki/Geometria pombalina, acessado em 28/12/2006.
68
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
