Algoritmos de Busca em Prolog
Introdução a Prolog
Histórico de Prolog
Desenvolvida de 1970 em Marselha/França
Objetivo inicial: integrar uma técnica de prova
automática de teoremas (Princípio de Resolução
de Robinson) numa linguagem de programação
para processamento de linguagem natural
Recebeu melhoramentos teóricos e uma
implementação eficiente ainda na década de 70 na
Universidade de Edimburgo/Escócia.
Características de Prolog
Programação Declarativa ao invés de
Procedimental
Deve-se buscar objetos e relações entre estes
objetos que ocorrem dentro da definição de um
problema. Ex. ‘Maria gosta de João’
Relações também podem ser expressas através de
regras. Ex. Duas pessoas A e B se gostam
mutuamente se A gosta de B e B gosta de A. Duas
pessoas são irmãs se são ambas do sexo feminino
e têm os mesmos pais.
Características de Prolog
Programação Prolog consiste em:
Declarar alguns fatos sobre objetos e suas
relações
Definir algumas regras sobre objetos e suas
relações
Fazer consultas sobre objetos e suas relações
Declarando Fatos
gosta(maria,joao).
1.
2.
3.
4.
5.
Os nomes de todas as relações e objetos devem
começar com minúsculas
A relação (gosta) vem em primeiro lugar, seguida
pelos objetos entre parêntesesis e separados por
vírgula
Deve-se colocar um ponto “.” ao final do fato
A ordem de apresentação dos objetos é arbitrária, mas
uma vez escolhida deve ser respeitada para evitar
inconsistências.
O exemplo acima significa “Maria gosta de João”
Declarando Fatos
O nome de uma relação é chamado de predicado
Os nomes dos objetos dentro dos parêntesis são
chamados de argumentos
A aridade de um predicado é o número de
argumentos que possui
Fatos em Prolog permitem expressar relações
arbitrárias entre objetos
Uma coleção de fatos em Prolog é denominada de
base de dados
Fazendo Consultas
Uma consulta é semelhante a um fato, exceto que
se coloca um símbolo especial “-?” antes dela. Ex.
?- pai(jose,joao).
Uma consulta desencadeia uma busca na base de
dados tentando-se casar o fato contido na questão
(objetivo) com um daqueles contidos na base de
dados. Se um fato é encontrado, a resposta é sim
“yes”, caso contrário não “no”.
Dois fatos casam se seus predicados são os mesmos
e se cada um de seus argumentos correspondentes
são os mesmos.
Exemplos de Consultas
gosta(maria, joao).
gosta(jose, cristina).
gosta(teresa,jose).
Consultas:
?- gosta(joao,maria).
no
?-gosta(teresa,jose).
yes
Mais Exemplos de Consultas
nasceu(jose,paraiba).
nasceu(joao,pernambuco).
brasileiro(paulo).
brasileiro(joao).
?-nasceu(jose,paraiba).
yes
?-brasileiro(joao).
yes
?-brasileiro(jose).
no
Em Prolog, a resposta negativa é utilizada com o
significado de “nada casa com a questão” e não
com o significado que a questão é falsa!
Variáveis
“X é filho de Pedro?”: neste caso Prolog
deve apresentar todas as possibilidades para
o significado de X
Nomes de variáveis representam objetos a
serem determinados por Prolog
Instanciadas: quando assumiram o valor de
um objeto
Não Instanciadas: caso contrário
Variáveis: um Exemplo
gosta(paulo,teresa).
gosta(joao,natureza).
gosta(maria,chocolate).
gosta(maria,natureza).
gosta(pedro,ana).
gosta(joao,maria).
?- gosta(joao,X).
X=natureza
Para concluir a consulta, basta pressionar RETURN
Para tentar re-satizfazer a questão, pressiona-se “;” (ponto-evírgula) seguido por RETURN.
X=natureza;
X=maria;
no
Conjunções
A consulta “Maria gosta de João e João
gosta de Maria?” pode ser expressa por:
?-gosta(joao,maria), gosta(maria,joao).
no
A vírgula “,” é lida como “e”, servindo para separar
qualquer número de objetivos diferentes.
Todos os objetivos precisam ser satisfeitos para que
a conjunção de objetivos também seja.
Conjunções e Variáveis
Existe um objeto tal que João e Maria gostam?
?- gosta(maria,X), gosta(joao,X).
1. A base de dados é pesquisada para o 1o objetivo. X é
instanciada com chocolate.
2. Agora a base de dados é pesquisada para
gosta(joao,chocolate).
3. Como não existe tal fato, o último objetivo falha e tenta-se
re-satisfazer o anterior.
4. Parte-se do ponto em que X foi instanciada pela última vez.
X é instanciada desta vez com natureza.
5. Prolog tenta satisfazer o 2o objetivo na forma
gosta(joao,natureza), o que é possivel.
6. Neste ponto como ambos os objetivos puderam ser
satisfeitos, Prolog responde então com X=natureza.
Regras
São utilizadas quando se deseja afirmar que um
fato depende de um grupo de outros fatos.
As regras também são utilizadas para expressar
definições. Ex.: “Um indivíduo X é avô de outro
indivíduo Y se existe um indivíduo Z que é filho
de X e pai de Y”
Outro exemplo: “X é um um cachorro de X é um
animal e X late”
Regras
Em Prolog uma regra consiste de uma
cabeça e um corpo. A cabeça e o corpo são
separados pelo símbolo “:-” (dois pontos e
hífen), que se pronuncia “se”.
Os dois exemplos de regras anteriores
podem ser expressos em Prolog como:
avo(X,Y) :- filho(Z,X0, pai(Z,Y).
cachorro(X) :- animal(X), late(X).
Regras
O escopo de uma variável é definido como sendo
toda a regra (da cabeça até o ponto) na qual a
variável se encontra.
Sempre que uma variável X está instanciada, todos
os outros Xs dentro do escopo da variável também
devem estar instanciados com este mesmo objeto.
A variável X que aparece na regra “avo” não tem
qualquer relação com o X que aparece na regra do
“cachorro”.
Exemplo de Regra
homem(joao).
homem(jose).
homem(pedro).
mulher(maria).
mulher(ana).
mulher(paula).
mulher(joana).
mulher(alice).
pais(joao,maria,jose).
pais(paula,alice,pedro).
pais(ana,maria,jose).
pais(joana,alice,pedro).
irma_de(X,Y) :- mulher(X), pais(X,M,P), pais(Y,M,P).
Exemplo de Regra
Como Prolog responde a consulta:
?- irma_de(joana,paula).
Processamento de Listas em Prolog
Construção de Listas
cons(X,Y,[X|Y]).
?-cons(a,b,Z).
Z=[a,b] ou Z=[a|b]
?-cons(a,[],Z).
Z=[a].
?-cons(a,X,[a,b,c]).
X=[b,c].
?-cons([a,b,c],[d,e],Z).
Elementos de uma Lista
membro(X,L).
membro(b,[a,b,c]).
membro([b,c],[a,[b,c],d]).
membro(b,[a,[b,c]]).
X é membro de L se
(1) X é a cabeça de L, ou
(2) X é membro do corpo de L
Falso!
Elementos de uma Lista
membro(X,[X|C]).
membro(X,[_|C] :- membro(X,C).
?-membro(a,[a,b,c]).
yes
?-membro(´Natal´, [´Recife´, ´Natal´, ´Campina´].
yes
?-membro(1,[[1,2],3,4]).
no
Concatenação de Listas
conc(L1,L2,L3), onde L1 e L2 são duas listas e L3 é a
concatenação resultante.
conc([a,b],[c,d],[a,b,c,d]).
Dois casos devem ser considerados para a definição de
conc/3:
1.
2.
Se o primeiro argumento é uma lista vazia, então o segundo e
oterceiro devem ser a mesma lista.
Se o primeiro argumento não for uma lista vazia então pode ser
denotado por [X|L1]. A concatenação de [X|L1] com L2 é uma
terceira lista com a mesma cabeça X da primeira e um corpo L3
que é a concatenação do corpo de L1 com L2.
Concatenação de Listas
X
X
L1
L2
L3
conc([],L,,L).
conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3).
?-conc([a,b,c],[1,2,3],L).
L=[a,b,c,1,2,3]
?-conc([a,[b,c],d],[a,[],b],L).
L=[a,[b,c],d,a,[],b]
Concatenação de Listas
Apesar de muito simples o programa conc/3 pode ser
usado em inúmeras aplicações:
Decomposição:
?-conc(L1,L2,[a,b,c]).
L1=[a,b,c]
L2=[];
L1=[a,b]
L2=[c];
L1=[a]
L2=[b,c];
L1=[]
L2=[a,b,c];
no
Concatenação de Listas
Apagando de uma lista todos os elementos
que se seguem a um determinado padrão:
?-conc(T,[sex|_],[seq,ter,qua,qui,sex,sab,dom]).
T=[seg,ter,qua,qui,sex]
Definindo a relação membro/2 em função
de conc:
membro1(X,L):-conc(_,[X|_],L).
Remoção de Elementos de uma Lista
remover(X,L,L1), onde L1 é a mesma lista L
com o elemento X removido. Existem
novamente 2 casos a estudar:
1.
2.
Se X é a cabeça de L, então L1 será seu corpo.
Se X está no corpo de L, então L1 é obtida
removendo X desse corpo.
remover(X,[X|C],C).
remover(X,[Y|C],[Y|D]):-remover(X,C,D).
Exemplos de remoção
?-remover(a,[a,b,a,a],L).
L=[b,a,a];
L=[a,b,a];
L=[a,b,a];
no
?-remover(a,L,[b,c,d]).
L=[a,b,c,d];
L=[b,a,c,d];
L=[b,c,a,d];
L=[b,c,d,a];
no
Outros usos de remover/3
inserir(X,L,L1):- remover(X,L1,L).
membro2(X,L) :- remover(X,L,_).
?-inserir(a,[b,c],L).
L=[a,b,c];
no
?-membro2(a,[c,b,a]).
yes
Inversão de Listas
inverter([a,b,c],[c,b,a]).
inverter([],[]).
inverter([a,[b,c],d],[d,[b,c],a]).
Inversão ingênua (O(N2))
1.
2.
3.
Tomar o primeiro elemento da lista
Inverter o restante
Concatenar o inverso do restante à lista formada pelo
primeiro elemento
inverter([],[]).
inverter([X|Y],Z) :- inverter(Y,Y1),
conc(Y1,[X],Z).
Inversão de Listas
Inversão eficiente (O(N))
inverter(X,Y):-aux([],X,Y).
aux(L,[],L).
aux(L,[X|Y],Z) :- aux([X|L],Y,Z).
Sublistas
S é uma sublista de L se:
(1) L pode ser decomposta em duas listas L1 e L2
(2) L2 pode ser decomposta em S e L3
sublista(S,L) :- conc(L1,L2,L),
conc(S,L3,L2).
?-sublista(S,[a,b,c]).
Somatório e Produtório
soma([],0).
soma([X|Y],S):- S is R+X, soma(Y,R).
produto([],0).
produto([X],X).
produto(L,P):- prod(L,P).
prod([],1).
prod([X|Y],P) :-prod(Y,Q)., P is Q*X.
Resolução de Problemas
Primeiros problemas por computador: prova
automática de teoremas e jogos
Capacidade de cálculo e memória dos
computadores: insuficientes perante o enorme
número de caminhos de solução
Exemplo: jogo de xadrez
Um dos objetivos de IA: resolver problemas que o
homem não sabe resolver facilmente ou num
tempo razoável, desde que sejam completamente
formalizados
Exemplos de Problemas
O fazendeiro, o lobo, a cabra e o couve: como
fazer para atravessar um rio num barco?
Os baldes: balde de 5 litros com água e um vazio
de 2 litros. Pode-se despejar água fora ou de um
balde para o outro. Como obter 1 litro de água?
O quebra-cabeças 3x3
A moeda falsa. Dispõe-se de 12 moedas idênticas
em aparência, sendo uma falsa de peso diferente.
Aual o número mínimo de pesagens para isolar a
moeda falsa?
Mais Exemplos de Problemas
O caixeiro viajante
Cálculo integral formal
Empilhamento de blocos: a partir de uma
configuração de blocos iniciais, qual a
seqüência de movimentos para se chegar a
uma configuração final?
As oito rainhas
As torres de hanoi
Espaço de Estados do Problema
Um problema pode ser visto como uma tripla:
{I,O,B}
I=estados iniciais
O=conjunto de operações
B=estados objetivo
Uma solução para o problema é uma seqüência
finita de operações que permite sair de um
elemento em I e chegar a um elemento em B.
Espaço de Estados do Problema
Assim um sistema de resolução de
problemas comporta:
Um conjunto de estruturas de dados organizada
em um grafo
Um conjunto de operadores caracterizados por
suas condições de aplicação e sua ação
Uma estrutura de controle implementando a
estratégia de resolução
Exemplo
Mundo dos blocos
Métodos de Busca
Existem basicamente 2 abordagens de busca num
espaço de estados
Busca cega: coleção de procedimentos utilizados para
pesquisar um espaço de estados, o princípio é examinar
a árvore inteira de uma forma organizada
Profundidade
Largura
Busca heurística: é uma busca cega com alguma guia
ou orientação
Busca Cega
Busca em Profundidade
Começa na raiz e avança paar baixo em níveis
cada vez mais profundos
Um operador é aplicado a um nó para gerar o
próximo nó mais profundo na seqüência
O processo continua até que uma solução é
encontrada ou um retrocesso é forçado ao
atingir-se um nó terminal que não é solução
Busca em Profundidade
Exemplo
1
2
5
3
4
6
11
8
7
9
12
10
13
14
15
16
Busca em Profundidade
Problema
Garante uma solução, mas a busca pode ser muito
demorada
Motivo: muitas ramificações diferentes podem ter que
ser consideradas até o nível mais profundo antes de
uma solução ser atingida
Busca em Profundidade
Para encontrar um caminho de solução Sol, de um
dado nó para algum nó objetivo
Se N é um nó objetivo, então Sol=[N]
Se há um nó N1 sucessor de N, tal que há um caminho
Sol1 de N1 para algum nó-objetivo, então Sol=[N|Sol1]
Em Prolog, a idéia acima pode ser traduzida para:
busca_profundidade(N,[N]) :- objetivo(N).
busca_profundidade(N,[N|Sol1]) :- s(N,N1),
busca_profundidade(N1,Sol1).
Busca em Profundidade
s(a,b).
s(a,c).
s(b,d).
s(b,e).
s(c,f).
s(c,g).
s(d,h).
s(e,i).
s(e,j).
s(f,k).
objetivo(j).
objetivo(f).
a
b
d
h
?-busca_profundidade(a,S).
S=[a,b,e,j];
S=[a,c,f];
No
c
e
i
f
j
k
g
Busca em Profundidade com Limite
Um dos maiores problemas com a busca em profundidade
é que ela pode conduzir a sub-árvores cada vez mais
profundas. Exemplo: jogo de xadrez.
Pode-se minimizar este problema restringindo a busca até
uma profundidade limite:
busca_profundidade2(No,[No],_) :- objetivo(No).
busca_profundidade2(No,[No|Sol],Prof_max):Prof_max > 0,
s(No,No1),
Max1 is Prof_max – 1,
busca_profundidade2(No1,Sol,Max1).
Busca em Largura
Os nós em cada nível da árvore são
completamente examinados antes de se mover
para o próximo nível
Uma busca em largura sempre encontrará sempre
o menor caminho entre o estado inicial e o estadoobjetivo
O menor caminho é o caminho com o menor
número de passos (não confundir com o caminho
de menor custo)
Busca em Largura
Não é tão fácil de programar em Prolog quanto a busca em
profundidade
Motivo: é necessário manter um conjunto de nós candidatos
alternativos e não apenas um nó candidato como na busca em
profundidade
O conjunto de nós candidatos é constituído por todos os nós de um
dado nível da árvore de busca
Entretanto, mesmo este conjunto de caminhos candidatos não é
suficiente se deseja-se extrair um caminho de solução do processo de
busca
Portanto, ao invés de manter-se um conjunto de nós candidatos, devese manter um conjunto de caminhos-candidatos
Busca em Largura
O predicado:
busca_largura(Caminhos,Solucao).
é satisfeito se algum caminho de um conjunto de Caminhos
candidatos pode ser estendido até um nó objetivo. Solução é um
destes caminhos estendido.
Na implementação que daremos a seguir, Caminhos será
representado por uma lista e cada caminho candidato será
uma lista de nós na ordem inversa
Em outras palavras, a cabeça de um caminho será o nó
mais recentemente gerado e o último elemento será o nó
inicial da busca
A busca é iniciada com um conjunto de candidatos com
um único elemento: [ [NoInicial] ]
Busca em Largura
Dado um conjunto de caminhos candidatos:
Se o primeiro caminho contém um nó-objetivo como
cabeça, estão este caminho é uma solução para o
problema
Caso contrário, remove-se o primeiro caminho do
conjunto de candidatos e gera-se o conjunto de todas as
possíveis extensões de um passo deste caminho,
acrescentando-se estas extensões ao final do conjunto
de candidatos e executa-se a busca em largura neste
conjunto de caminhos candidatos atualizado
Busca em Largura
1.
2.
3.
4.
5.
6.
a
Conjunto de Candidatos inicial:
b
c
[[a]]
d
e
g
f
Gera extensões de [a]:
i
j k
h
[ [b,a], [c,a] ]
Remove o 1o caminho candidato, [b,a], e gera extensões deste
caminho, colocando-as no final do conjunto:
[ [c,a], [d,b,a], [e,b,a] ]
Remove [c,a] e acrescenta sua extensão ao final do conjunto de
candidatos, produzindo:
[ [d,b,a], [e,b,a], [f,c,a], [g,c,a] ]
Em passos posteriores, [d,b,a] e [e,b,a] são estendidos e o conjunto
de candidatos torna-se: [ [f,c,a], [g,c,a], [h,d,b,a], [i,e,b,a], [j,e,b,a] ]
Agora o processo de busca encontra [f,c,a] que contém o nóobjetivo f. Portanto, este caminho é apresentado como uma solução.
Busca em Largura
Implementação Prolog
resolve_largura(Inicio, Solucao) :busca_largura( [ [Inicio] ], Solucao).
busca_largura( [ [N|Caminho] | _], [N|Caminho]):objetivo(N).
busca_largura([ [N|Caminho]| Caminhos ], Solucao) :bagof([M,N| Caminho],
(s(N,M),not(membro(M,[N|Caminho]))),
NovosCaminhos),
conc(Caminhos, NovosCaminhos, Caminhos1), !,
busca_largura(Caminhos1, Solucao);
busca_largura(Caminhos, Solucao).
Busca em Largura
O programa anterior gera caminhos de solução,
um após o outro, ordenados de acordo com seus
comprimentos, de forma que as menores soluções
aparecem primeiro
Porém não são levados em consideração quaisquer
custos associados com os arcos no espaço de
estados. Se o custo mínimo do caminho de solução
é o critério de otimização (e não seu
comprimento), então a busca em largura não é
suficiente.
Busca em Largura
Explosão combinatorial: quando o número de alternativas a
serem exploradas é tão grande que o problema de
complexidade torna-se crítico.
Por exemplo, se cada nó no espaço de estados tem N
sucessores, então o número de caminhos de comprimento
C a partir do nó inicial é NC (assumindo que não há ciclos).
Assim, o número de caminhos candidatos a solução é
exponencial com relação ao seu comprimento.
As estratégias de busca em profundidade em em largura
não fazem nada para combater esta complexidade: todos os
caminhos candidatos são tratados como igualmente
relevantes.
Busca Heurística
Conforme visto anteriormente, a busca cega sofre do
problema denominado explosão combinatória
Informação específica do domínio que pode ser usada para
guiar o processo de busca é chamada de heurística
Em muitos casos uma heurística envolve a aplicação de
uma função que avalia um nó particular e prediz a
qualidade dos seus nós sucessores
Uma função heurística de avaliação no jogo-da-velha
poderia ser o número de linhas, colunas e diagonais ainda
disponíveis, quanto maior este número maior a chance de
vitória
Busca Heurística
Um meio de utilizar informação heurística sobre um
problema é computar estimativas numéricas para os nós no
espaço de estados
Uma estimativa indica o quanto um nó é promissor com
relação ao alcance de um nó-objetivo
A idéia é continuar a busca sempre a partir do nó mais
promissor no conjunto de candidatos
O programa de busca do melhor caminho é baseado neste
princípio
Busca Heurística
Um programa de busca do melhor caminho pode
ser derivado de um refinamento do programa de
busca em largura
A busca em largura sempre escolhe para expansão
os menores caminhos-candidatos (isto é, os nós
extremos menos profundos da busca)
A busca do melhor caminho refina este princípio
calculando uma estimativa heurística para cada
candidato e escolhe para expansão o melhor
candidato de acordo com esta estimativa
Busca Heurística
Assuma que existe uma função custo associada a
cada arco do espaço de estados
Assim, c(n,ns) é o custo associado com o
movimento do nó n para o seu nó sucessor ns
Seja f uma função heurística de estimativa, tal que
para cada nó n do espaço de estados, f(n) estima o
grau de dificuldade de n
O nó candidato corrente mais promissor é aquele
que minimiza f
Busca Heurística
f(n) é definida como a soma de 2 termos:
f(n) = g(n) + h(n)
Onde g(n) é uma estimativa do custo de um caminho ótimo do nó inicial
i até n, e h(n) é uma estimativa do custo de um caminho ótimo de n
até um nó objetivo t
Quando n é encontrado pelo processo de busca, tem-se a
seguinte situação:
Um caminho de i para n já deve ter sido encontrado e seu custo pode ser
calculado como a soma dos custos dos arcos no caminho, e pode servir como
uma estimativa g(n) do custo mínimo de i para n
h(n) é mais problemático porque o espaço entre n e t ainda não foi
explorado, e portanto h(n) é meramente um palpite baseado no
conhecimento geral do algoritmo sobre o problema particular
Não existe um método universal de se construir h, pois depende do domínio
do problema
Busca Heurística
Considere o problema de encontrar a menor rota
entre a cidade inicial i e a cidade objetivo t
e
2
(7)
i
5
2
a (5)
2
(4) c
b (4)
2
f (4)
2
3
g (2)
(3) d
3
t
2
Busca Heurística
Pode-se imaginar a busca do melhor caminho como
consistindo de 2 processos, cada um dos quais explorando
um dos caminhos alternativos:
O processo 1, explora o caminho via a e
O processo 2 explora o caminho via e
processo 1
i
processo 2
f(a)=2+5=7
a
e f(e)=2+7=9
f(b)=4+4=8
b
f f(f)=7+4=11
f(c)=6+4=10
c
g f(g)=9+2=11
f(d)=9+3=12
d
t f(t)=11+0=11
Busca Heurística
Implementação Prolog
% Determina se elemento X é membro de uma lista
membro(X,[X|_]).
membro(X,[_|Y]) :- membro(X,Y).
% Anexa duas listas produzindo uma terceira
conc([],L,L).
conc([C1|L1],L2,[C1|L3]) :- anexa(L1,L2,L3).
% Espaço de estados para teste de busca heurística
s(i,e,2).
s(i,a,2).
s(a,b,2).
s(b,c,2).
s(c,d,3).
s(d,t,3).
s(e,f,5).
s(f,g,2).
s(g,t,2).
% Heuristicas
h(e,7).
h(f,4).
h(g,2).
h(d,3).
h(c,4).
h(a,5).
h(b,4).
h(t,0).
% Nó objetivo
objetivo(t).
Busca Heurística
Implementação Prolog
% Busca do Melhor Caminho usando heurísticas (uma modificação da busca em largura).
resolve_heuristica(Inicio) :melhor([[Inicio/0]],Solucao),
apresenta_solucao(Solucao).
melhor([[No/Custo_total|Caminho]|_],[No/Custo_total|Caminho]) :objetivo(No).
melhor([[N/G|Caminho]|Caminhos],Solucao) :bagof([Ns/Gs,N/G|Caminho],
(s(N,Ns,Custo),not membro(Ns/Gs,[N/G|Caminho]),Gs is G +Custo),
Extensoes),
anexa(Caminhos, Extensoes, Candidatos),
ordena(Candidatos, Candidatos_ordenados),!,
melhor(Candidatos_ordenados, Solucao) ;
melhor(Caminhos, Solucao).
Busca Heurística
Implementação Prolog
%Predicados auxiliares
ordena([],[]).
ordena(L1,L2) :estima(L1, Estimativas),
ordena_estimativas(Estimativas, Estimativas_ordenadas),
estima(L2, Estimativas_ordenadas).
estima([],[]).
ordena_estimativas(E,O) :anexa(L,[f(C1,H1), f(C2, H2)|R],E),
H2 > H1,
anexa(L, [f(C2,
H2),f(C1,H1)|R],L1),
ordena_estimativas(L1,0),!.
ordena_estimativas(E,E).
estima([[N/G|R]|Cs],[f([N/G|R],F)|Estimativas]) :h(N,H),
F is G + H,
estima(Cs, Estimativas).
Busca Heurística
Implementação Prolog
%Predicados auxiliares
apresenta_solucao([N/Custo_total|R]) :write('o caminho de solucao eh: '),
caminho([N/Custo_total|R]), nl,
write('o custo total foi '),
write(Custo_total), nl.
caminho([]) :-!.
caminho([N/_|R]) :- write(N),
write(' <-- '),
caminho(R).