O algoritmo A * no Prolog

A Seção 2.16 apresentou um esboço para um programa de pesquisa Prolog simples. Esta seção discute a pesquisa heurística usando o algoritmo A *, devido a Nilsson (1980).

A busca heurística usa uma função heurística para ajudar a orientar a busca. Quando um nó é expandido, cada um de seus filhos é avaliado usando uma função de busca. Cada filho é colocado em uma lista de nós -- chamada de lista aberta -- na ordem determinada pela avaliação da função de busca (valores menores primeiro). A função heurística estima quanto trabalho deve ser feito para atingir um objetivo do nó em questão. Normalmente, a função de busca f é expressa como...

f(n) = g(n) + h(n)

... onde g(n) representa o custo (calculado, real) de chegar ao nó n ao longo do caminho atual até ele e h é a função heurística. Assim, f(n) estima o custo ou esforço para ir com sucesso do início ao objetivo, passando pelo nó n (ao longo de algum caminho particular).

Fig. 5.1

Segue um pseudocódigo simples a partir do qual o programa Prolog será desenvolvido.

1. Comece com o nó inicial, coloque-o na lista aberta (anteriormente vazia).
2. Seja n o primeiro nó aberto. Remova n de aberto. Falha se aberto estiver vazio.
3. Se n for o objetivo, então uma solução foi encontrada. (Pode-se parar aqui.)
4. Expanda n, obtendo todos os seus filhos, e avalie f(-) para cada um deles. Insira cada um desses filhos na abertura, mantendo a ordem onde os menores valores f(-) vêm primeiro.
5. Repita a partir da etapa 2.

Quando um objetivo foi alcançado, certamente deve-se retornar o caminho da solução inicial ao objetivo. O pseudocódigo ignorou esse recurso, mas ele será incluído conforme o programa de protótipo Prolog for desenvolvido.

Uma função de custo comum g(-) é o comprimento do caminho. O custo de ir do nó inicial ao nó atual é o comprimento do caminho relevante. Isso pode ser calculado de forma incremental, como será visto.

É importante perceber que este tipo de busca pode seguir um caminho contíguo por um tempo, até que algum nó n previamente não escolhido tenha o menor valor f(-) atual, caso em que este nó n é expandido e seus filhos considerados.

Agora, o programa Prolog para a busca A *.

fira a alguma descrição do estado de uma busca. Por exemplo, Estado pode ser uma descrição do bloco do 8-puzzle para uma configuração específica, conforme desenvolvido na próxima seção. Um Nó no espaço de busca (ou grafo) precisa registrar o Estado, a Profundidade (ou comprimento do caminho desde o início), o valor de f(-) para o nó F e uma lista dos ancestrais A deste nó. Usaremos a estrutura de termos do Prolog

Nó = Estado#Profundidade#F#A

Para um nó. Quando o Nó é expandido para encontrar seus filhos ...

• O estado de cada nó será calculado como uma mudança de Estado
• cada um desses filhos terá profundidade Profundidade + 1,
• o valor f(-) de cada filho será calculado, e
• a lista de ancestrais de um filho será o termo da lista Prolog [Nó|A].

Em geral, se a Profundidade for substituída por algum outro custo, a representação do nó seria semelhante; apenas substitua Profundidade por um custo e calcule-o apropriadamente. Além disso, veremos na próxima seção (8-puzzle) que a lista de ancestrais pode ser salva mais convenientemente como uma lista de ações simbólicas (usada para alcançar estados sucessivos), em vez de uma lista dos próprios nós completos. Outras modificações do prototótipo do algoritmo A * apresentado nesta seção podem ser feitas, dependendo da aplicação.

O predicado principal do programa é...

solve(Start,Soln) :- f_function(Start,0,F),
                     search([Start#0#F#[]],S),
                     reverse(S,Soln).

f_function(State,D,F) :- h_function(State,H),
                         F is D + H.

A variável 'Start' refere-se à descrição do estado inicial. O primeiro parâmetro para o predicado de busca representa a lista aberta. A definição 'h_function' precisa ser fornecida com o aplicativo específico.

search([State#_#_#Soln | _], Soln) :- goal(State).
search([B|R],S) :- expand(B, Children),
                   insert_all(Children, R, NewOpen),
                   search(NewOpen,S).

A versão do predicado 'expand' fornecida simplesmente usa a computação do bagof do Prolog (assim, juntando boa parte do trabalho).

expand(State#D#_#A, All_My_Children) :-
         bagof(Child#D1#F#[Move|A],
               ( D1 is D + 1,
                 move(State,Child,Move),
                 f_function(Child,D1,F) ) ,
               All_My_Children).

O predicado 'move'(dependência da aplicação) deve gerar os estados 'Child', de forma a obter todos eles por backtracking. (Veja o exemplo do 8-puzzle na próxima seção). Como afirmado anteriormente, o 'Move' pode ser o próprio nó pai inteiro ou algum substituto apropriado. (Na verdade, deve-se reescrever a cláusula 'expand' se for usar o nó inteiro, em vez de alguma representação simbólica, como faremos na próxima seção).

Segue o código para insert_all. É um tipo familiar de algoritmo de ordenação por inserção ...

insert_all([F|R],Open1,Open3) :- insert(F,Open1,Open2),
                                 insert_all(R,Open2,Open3).
insert_all([],Open,Open).

insert(B,Open,Open) :- repeat_node(B,Open), ! .
insert(B,[C|R],[B,C|R]) :- cheaper(B,C), ! .
insert(B,[B1|R],[B1|S]) :- insert(B,R,S), !.
insert(B,[],[B]).

repeat_node(P#_#_#_, [P#_#_#_|_]).

cheaper( _#_#H1#_ , _#_#H2#_ ) :- H1 <  H2.

Os exercícios a seguir pedem ao leitor que formule soluções A * para vários problemas ou quebra-cabeças. Consulte a próxima seção 5.2 8-puzzle como um exemplo de como estender o programa A* geral desta seção para uma solução específica do 8-puzzle.

Exercício 5.1.1 Formule um algoritmo A* para o quebra-cabeça das N rainhas. (Consulte a seção 2.11 para uma abordagem simples, mas ineficiente.)

Exercício 5.1.2 Formule uma abordagem A * para resolver labirintos.

Veja Também

• Código do Prolog para as seções 5.1, 5.2 e 8.2.
• 2.11 Quebra-cabeça do desafio das rainhas do xadrez
• 2.16 Buscas em Prolog
• 5.2 O 8-puzzle no Prolog
• 5.3 Busca-αβ no Prolog
• Prolog Tutorial Sumário