next_inactive up previous




===============================================
Algoritmos de Busca Heurística (PARTE 2)



Busca Heurística em Grafos-OU



Prof. Alexandre Direne - DInf-UFPR ===============================================






Recomendação de Bibliografia:

Recomendação de Páginas Web: 

http://www.cs.dartmouth.edu/~brd/Teaching/AI/Lectures/Summaries/search.html

http://www.decom.ufop.br/prof/guarda/CIC250/index.htm

http://aima.cs.berkeley.edu/

http://aima.cs.berkeley.edu/newchap05.pdf

Recomendação de Software:

Busca Heurística em Grafos-OU

Os principais algoritmos de busca desta parte são as variações da busca em Grafos-OU. Tais variações se baseiam em uma série de formalismos que podem ser definidos como abordagens mais específicas de busca sobre o conceito de árvores de estados como espaços de solução de problemas. Estes formalismos estão apresentados nas seções seguintes, logo antes das descrições das variações dos algoritmos propriamente ditos.

Métodos de Busca Cega ou Força Bruta

Busca em Amplitude

Considere a ávore de busca genericamente apresentada na Figura [*]. Observe o seguinte: 

          [ r(5,h), r(1,c), r(raiz,b) ]


          Fila = [ [ r(1,c), r(raiz,b) ],
                   [ r(2,d), r(raiz,b) ],
                   [ r(3,e), r(raiz,b) ] ]

Figura: Exemplo de árvore com ordem de busca em aplitude
\begin{figure}\centerfig{arvore_generica_amplitude.eps}[50]\end{figure}

          ListaExtensoes = [ [ r(4,g), r(1,c), r(raiz,b) ],
                             [ r(5,h), r(1,c), r(raiz,b) ],
                             [ r(6,i), r(1,c), r(raiz,b) ] ]


          FilaEstendida = [ [ r(2,d), r(raiz,b) ],
                            [ r(3,e), r(raiz,b) ],
                            [ r(4,g), r(1,c), r(raiz,b) ],
                            [ r(5,h), r(1,c), r(raiz,b) ],
                            [ r(6,i), r(1,c), r(raiz,b) ] ]


          Fila= [ [ r(3,e), r(raiz,b) ],
                  [ r(4,g), r(1,c), r(raiz,b) ],
                  [ r(5,h), r(1,c), r(raiz,b) ],
                  [ r(6,i), r(1,c), r(raiz,b) ] ]


          FilaEstendida = [ [ r(4,g), r(1,c), r(raiz,b) ],
                            [ r(5,h), r(1,c), r(raiz,b) ],
                            [ r(6,i), r(1,c), r(raiz,b) ],
                            [ r(7,j), r(3,e), r(raiz,b) ],
                            [ r(8,k), r(3,e), r(raiz,b) ] ]


          Fila = [ [ r(9, n), r(5,h), r(1,c), r(raiz,b) ],
                   [ r(10,m), r(5,h), r(1,c), r(raiz,b) ] ]

\fbox{\Large $b \stackrel{1}{\longrightarrow} c \stackrel{5}{\longrightarrow} h \stackrel{9}{\longrightarrow} n$\ }

Em resumo, o algoritmo de busca em amplitude pode ser resumidamente descrito assim:

Para ilustrar a implementação do algoritmo de busca em amplitude, será considerado o problema de como posicionar duas fichas pretas entre duas fichas brancas. Para especificar melhor tal problema, tome como objeto de apoio uma bandeja que possui cinco lacunas de encaixe. Em seu estado inicial, as quatro fichas podem ocupar qualquer posição relativa das lacunas, ficando sempre uma lacuna vazia. A Figura [*] mostra uma das possíveis configurações de Estados Iniciais para o problema referido.

Figura: Um estado inicial para o problema de movimentação das fichas
\begin{figure}\centerfig{um_estado_inicial_fichas.eps}[35]\end{figure}

As duas operações atômicas possíveis são as seguintes:

Por enquanto, para simplificar a apresentação dos conceitos de implementação, é importante notar que os custos de ambas as operação atômicas são os mesmos.

A Figura [*] mostra um fragmento da árvore de busca para o problema de movimentação das fichas o qual inclui a ocorrência em altura mínima de um dos possíveis Estados Finais.

Figura: Fragmento da árvore de busca para o problema de movimentação das fichas
\begin{figure}\centerfig{arvore_busca_fichas.eps}[75]\end{figure}

O programa em Prolog que segue é capaz de realizar a busca em amplitude. Um dos possíveis Estados Iniciais está listado (como comentário) no final do código e coincide com o Estado Inicial da Figura [*]. 

% -------------------------------------------------------------
%   PREDICADOS UTILITARIOS PARA A BUSCA (PROBLEMA DAS FICHAS)
% -------------------------------------------------------------

concatenadas([], L, L) :-
  !.
concatenadas([X|C1], L2, [X|C3]) :-
  concatenadas(C1, L2, C3).

pertence_a(X, [X|_]) :-
  !.
pertence_a(X, [_|C]) :-
  pertence_a(X, C).

trajetoria_impressa([ r(raiz,Raiz) ]) :-
  write('Estado Inicial: '),
  write(Raiz),
  write('. \n'),
  !.
trajetoria_impressa([ r(Operacao,Nodo) | Resto ]) :-
  trajetoria_impressa(Resto),
  write(Operacao),
  write(' para obter o estado: '),
  write(Nodo),
  write('. \n').

transformado([v, A, B, C, D], operacao(deslisa), [A, v, B, C, D]).
transformado([A, v, B, C, D], operacao(deslisa), [v, A, B, C, D]).
transformado([A, v, B, C, D], operacao(deslisa), [A, B, v, C, D]).
transformado([A, B, v, C, D], operacao(deslisa), [A, v, B, C, D]).
transformado([A, B, v, C, D], operacao(deslisa), [A, B, C, v, D]).
transformado([A, B, C, v, D], operacao(deslisa), [A, B, v, C, D]).
transformado([A, B, C, v, D], operacao(deslisa), [A, B, C, D, v]).
transformado([A, B, C, D, v], operacao(deslisa), [A, B, C, v, D]).
transformado([v, A, B, C, D], operacao(salta), [B, A, v, C, D]).
transformado([A, v, B, C, D], operacao(salta), [A, C, B, v, D]).
transformado([A, B, v, C, D], operacao(salta), [v, B, A, C, D]).
transformado([A, B, v, C, D], operacao(salta), [A, B, D, C, v]).
transformado([A, B, C, v, D], operacao(salta), [A, v, C, B, D]).
transformado([A, B, C, D, v], operacao(salta), [A, B, v, D, C]).

e_estado_final([v, o, *, *, o]).
e_estado_final([o, v, *, *, o]).
e_estado_final([o, *, v, *, o]).
e_estado_final([o, *, *, v, o]).
e_estado_final([o, *, *, o, v]).

trajetoria_expandida([r(Ramo,Nodo) | Resto], [r(Op,Filho), r(Ramo,Nodo) | Resto]) :-
  transformado(Nodo, operacao(Op), Filho),
  not(produz_ciclo(Filho, [r(Ramo,Nodo) | Resto])).

produz_ciclo(Estado, Trajetoria) :-
  pertence_a(r(_,Estado), Trajetoria).

adjacentes(Trajetoria, Adjacentes) :-
  findall(Ti, trajetoria_expandida(Trajetoria, Ti), Adjacentes),
  !.
adjacentes( _ , [] ).

possui_estado_final([ r(_,Nodo) | _ ]) :-
  e_estado_final(Nodo).



% -------------------------------------------------------------
%                   BUSCA EM AMPLITUDE
% -------------------------------------------------------------

solucao_computada_em_amplitude([ Solucao | _ ], Solucao) :-
  possui_estado_final(Solucao),
  !.
solucao_computada_em_amplitude([ Trajetoria | Fila ], Solucao) :-
  adjacentes(Trajetoria, Lista_de_Trajetorias_Expandidas),
  concatenadas(Fila, Lista_de_Trajetorias_Expandidas, Fila_Expandida),
  solucao_computada_em_amplitude(Fila_Expandida, Solucao).

% *** Exemplo de Estado Inicial: [o, o, v, *, *]

solucao_da_busca_em_amplitude_a_partir_do(Estado_Inicial) :-
  solucao_computada_em_amplitude([ [ r(raiz,Estado_Inicial) ] ], Trajetoria),
  trajetoria_impressa(Trajetoria).

Para ilustrar a aplicação do predicado solucao_da_busca_em_amplitude_a_partir_do basta compilar seu código e executar a seguinte consulta: 

   ?- solucao_da_busca_em_amplitude_a_partir_do([o, o, v, *, *]).
   Estado Inicial: [o, o, v, *, *].
   deslisa para obter o estado: [o, v, o, *, *].
   salta para obter o estado: [o, *, o, v, *].
   deslisa para obter o estado: [o, *, v, o, *].
   salta para obter o estado: [o, *, *, o, v].
   yes

Busca em Profundidade

Na busca em profundidade, as trajetórias recém produzidas são incluídas em uma $ Pilha$ e não em uma fila. Na ávore de busca genericamente apresentada na Figura [*], o Estado Final $ n$ pode ser encontrado efetuando-se a busca em profundidade. Suponha que as seguintes trajetórias estejam na $ Pilha$ para serem examinadas ao final do primeiro ciclo de busca: 

          Pilha = [ [ r(1,c), r(raiz,b) ],
                    [ r(2,d), r(raiz,b) ],
                    [ r(3,e), r(raiz,b) ] ]

Retirando-se a trajetória do topo da $ Pilha$, verifica-se que ela não inclui o Estado Final. Empilha-se então as trajetórias extandidas com os filhos do nodo $ c$, as quais deixam a $ Pilha$ no seguinte estado: 

      NovaPilha = [ [ r(4,g), r(1,c), r(raiz,b) ],
                    [ r(5,h), r(1,c), r(raiz,b) ],
                    [ r(6,i), r(1,c), r(raiz,b) ],
                    [ r(2,d), r(raiz,b) ],
                    [ r(3,e), r(raiz,b) ] ]

Como a trajetória do topo de $ Pilha$ não inclui o Estado Final e não pode ser expandida, a $ Pilha$ fica no seguinte estado: 

          Pilha = [ [ r(5,h), r(1,c), r(raiz,b) ],
                    [ r(6,i), r(1,c), r(raiz,b) ],
                    [ r(2,d), r(raiz,b) ],
                    [ r(3,e), r(raiz,b) ] ]

Agora, apesar da trajetória do topo de $ Pilha$ não incluir o Estado Final, uma de suas formas expandidas possui. No final do processo de busca, a $ Pilha$ está assim: 

          Pilha = [ [ r(9,n),  r(5,h), r(1,c), r(raiz,b) ],
                    [ r(10,m), r(5,h), r(1,c), r(raiz,b) ],
                    [ r(6,i), r(1,c), r(raiz,b) ],
                    [ r(2,d), r(raiz,b) ],
                    [ r(3,e), r(raiz,b) ] ]

Uma das variações de implementação de programa em Prolog que é capaz de realizar a busca em profundidade mais completa, adotando a eliminação de trajetórias que possuem estados repetidos, está listado abaixo. Note que os predicados utilitários são exatamente os mesmos definidos no programa que implementa a buca em amplitude (por isso não foram repetidos aqui). 

% -------------------------------------------------------------
% BUSCA EM PROFUNDIDADE (COM PILHA EXPLICITA DE TRAJETORIAS)
% -------------------------------------------------------------

solucao_computada_em_profundidade([ Solucao | _ ], Solucao) :-
  possui_estado_final(Solucao),
  !.
solucao_computada_em_profundidade([ Trajetoria | Pilha ], Solucao) :-
  adjacentes(Trajetoria, Lista_de_Trajetorias_Expandidas),
  concatenadas(Lista_de_Trajetorias_Expandidas, Pilha, Pilha_Expandida),
  solucao_computada_em_profundidade(Pilha_Expandida, Solucao).

% *** Exemplo de Estado Inicial: [o, o, v, *, *]

solucao_da_busca_em_profundidade_a_partir_do(Estado_Inicial) :-
  solucao_computada_em_profundidade([ [ r(raiz,Estado_Inicial) ] ], Trajetoria),
  trajetoria_impressa(Trajetoria).

Para ilustrar a aplicação do predicado solucao_da_busca_em_profundidade_a_partir_do basta compilar seu código e executar a seguinte consulta: 

   ?- solucao_da_busca_em_profundidade_a_partir_do([o, o, v, *, *]).
   Estado Inicial: [o, o, v, *, *].
   deslisa para obter o estado: [o, v, o, *, *].
   salta para obter o estado: [o, *, o, v, *].
   deslisa para obter o estado: [o, *, v, o, *].
   deslisa para obter o estado: [o, v, *, o, *].
   deslisa para obter o estado: [v, o, *, o, *].
   salta para obter o estado: [*, o, v, o, *].
   deslisa para obter o estado: [*, v, o, o, *].
   salta para obter o estado: [*, o, o, v, *].
   deslisa para obter o estado: [*, o, o, *, v].
   salta para obter o estado: [*, o, v, *, o].
   deslisa para obter o estado: [*, v, o, *, o].
   deslisa para obter o estado: [v, *, o, *, o].
   salta para obter o estado: [o, *, v, *, o].
   yes

Note os seguites pontos:

Uma segunda maneira de implementação da busca em profundidade está listada no programa em Prolog que segue. Note que ele não manipula explicitamente nenhuma $ Pilha$. 

% ----------------------------------------------------------------
% BUSCA EM PROFUNDIDADE (SEM A PILHA DE TRAJETORIAS)
% ----------------------------------------------------------------

solucao_computada_em_profundidade(Solucao, Solucao) :-
  possui_estado_final(Solucao),
  !.
solucao_computada_em_profundidade(Trajetoria, Solucao) :-
  trajetoria_expandida(Trajetoria, T2),
  solucao_computada_em_profundidade(T2, Solucao).

% *** Exemplo de Estado Inicial: [o, o, v, *, *]

solucao_da_busca_em_profundidade_sem_pilha_a_partir_do(Estado_Inicial) :-
  solucao_computada_em_profundidade([ r(raiz,Estado_Inicial) ], Trajetoria),
  trajetoria_impressa(Trajetoria).

Observe duas coisas importantes:

Uma terceira variação de implementação da busca em profundidade ainda pode ser atingida por meio do uso explícito do predicado $ fail$. Ele irá forçar a produção de todos os estados diretamente atingíveis a partir do estado atual (ou estado corrente).

Métodos de Busca Heurística

Os métodos de busca heurística fazem uso de conhecimento específico sobre o domínio do problema para guiar o processo de busca.

Muitos dos referidos métodos procuram atribuir uma nota a cada nodo da árvore de busca para representar uma estimativa (ou função heurística) do custo de transformação do Estado Atual no Estado Final.

Os conceitos básicos que são tipicamente necessários ao entendimento estão apresentados a seguir.

Algoritmo $ A^*$

O Algoritmo $ A^*$ adota como base de orientação da busca a estimativa de transformação do Estado Inicial ($ E_i$) até o no Estado Final ($ E_f$), passando pelo Estado Atual ($ E_a$). Tal estimativa pode ser expressa pela seguinte fórmula:

\fbox{\Large $f(E_a) = g(E_a) + h(E_a)$}

Nesta fórmula, temos os seguintes detalhes:

O processo de busca executado por meio do algoritmo $ A^*$ reorganiza, a cada ciclo, as trajetórias da Lista de Prioridades de modo que aquelas com menor $ f(E_a)$ venham para a frente e sejam investigadas primeiro.

Figura: Mapa com ligações entre cidades e suas distâncias euclidianas
\begin{figure}\centerfig{mapa_coordenadas_cidades.eps}[63]\end{figure}

Um exemplo concreto de aplicação do $ A^*$ se destina a encontrar um caminho que leva, por exemplo, da cidade $ b$ à cidade $ s$ no mapa da Figura [*]. Sobre o mapa, pode-se dizer que:

Suponha que a investigação da máquina entre $ b$ e $ s$ atinja a cidade $ d$. Pode-se dizer então que:

O programa em Prolog abaixo realiza a busca $ A^*$ pela trajetória mínima entre duas cidades. Algumas de suas características são: 

% -------------------------------------------------------------
%  PREDICADOS UTILITARIOS (PROBLEMA DO CAMINHO ENTRE 2 CIDADES)
% -------------------------------------------------------------

pertence_a(X, [X|_]) :-
  !.
pertence_a(X, [_|C]) :-
  pertence_a(X, C).

trajetoria_impressa(t(F,G,T)) :-
  trajetoria_impressa_1(T).

trajetoria_impressa_1([ r(raiz,Raiz) ]) :-
  write('Estado Inicial: '),
  write(Raiz),
  write('. \n'),
  !.
trajetoria_impressa_1([ r(Operacao,Nodo) | Resto ]) :-
  trajetoria_impressa_1(Resto),
  write(Operacao),
  write(' a cidade: '),
  write(Nodo),
  write('. \n').

ligada_a(a,b). ligada_a(b,m).
ligada_a(m,f). ligada_a(f,q).
ligada_a(q,p). ligada_a(p,n).
ligada_a(p,s). ligada_a(b,c).
ligada_a(c,d). ligada_a(d,q).
ligada_a(d,n). ligada_a(d,g).
ligada_a(n,h). ligada_a(n,s).
ligada_a(h,g).

coord(a,  2, 4) :- !.  coord(b,  5, 6) :- !.
coord(c,  4, 2) :- !.  coord(d,  7, 4) :- !.
coord(f,  7, 8) :- !.  coord(g,  8, 2) :- !.
coord(h, 10, 1) :- !.  coord(m,  9, 6) :- !.
coord(n, 11, 3) :- !.  coord(p, 12, 6) :- !.
coord(q, 11, 7) :- !.  coord(s, 13, 2).


inserida(T, [], [T]).
inserida(t(F1,G1,Ramos1), [ t(F2,G2,Ramos2) | Resto ],
                          [ t(F1,G1,Ramos1), t(F2,G2,Ramos2) | Resto ]) :-
  F1 < F2,
  !.
inserida(t(F1,G1,Ramos1), [ t(F2,G2,Ramos2) | Resto ],
                          [ t(F2,G2,Ramos2) | Resto2 ]) :-
  inserida(t(F1,G1,Ramos1), Resto, Resto2).


inseridas_as_trajetorias([], Fila, Fila).
inseridas_as_trajetorias([T|C], Fila, Fila3) :-
  inserida(T,Fila, Fila2),
  inseridas_as_trajetorias(C, Fila2, Fila3).

trajetoria_expandida(t(F,  G,  [r(Ramo,     Nodo)              | Resto]),
                     t(F1, G1, [r(vai_para, Filho), r(Ramo,Nodo) | Resto])) :-
  ligada_a(Nodo, Filho),
  not(produz_ciclo(Filho, [r(Ramo,Nodo) | Resto])),
  funcao_h(Filho, H1),
  custo(Nodo, Filho, Custo),
  G1 is G  + Custo,
  F1 is G1 + H1.

produz_ciclo(Estado, Trajetoria) :-
  pertence_a(r(_,Estado), Trajetoria).

custo(Nodo, Filho, Custo) :-
  coord(Nodo,  XN, YN),
  coord(Filho, XF, YF),
  X is (XN-XF)*(XN-XF) + (YN-YF)*(YN-YF),
  prolog_eval(sqrt(X),Custo),
  !.

funcao_h(Ea, H) :-
  e_estado_final(Ef),
  coord(Ef, XEf, YEf),
  coord(Ea, XEa, YEa),
  X is (XEa-XEf)*(XEa-XEf) + (YEa-YEf)*(YEa-YEf),
  prolog_eval(sqrt(X),H),
  !.

adjacentes(X, Y, Z) :-
  findall(X, Y, Z),
  !.
adjacentes(_ , _ , [] ).

e_estado_final(s).

possui_estado_final(t(_,_,[r(_,Nodo)|_])) :-
  e_estado_final(Nodo).

% -------------------------------------------------------------
%              BUSCA HEURISTICA PELO  A*
% -------------------------------------------------------------

solucao_computada_por_A_estrela([ Solucao | _ ], Solucao) :-
  possui_estado_final(Solucao),
  !.
solucao_computada_por_A_estrela([ Trajetoria | Fila ], Solucao) :-
  adjacentes(T2, trajetoria_expandida(Trajetoria, T2), Lista_de_Trajetorias_Expandidas),
  inseridas_as_trajetorias(Lista_de_Trajetorias_Expandidas, Fila, Fila_Expandida),
  solucao_computada_por_A_estrela(Fila_Expandida, Solucao).

% *** Exemplo de Estado Inicial: b

solucao_da_busca_por_A_estrela_a_partir_do(Estado_Inicial) :-
  funcao_h(Estado_Inicial, H),
  solucao_computada_por_A_estrela([ t(H,0,[r(raiz,Estado_Inicial)]) ], Trajetoria),
  trajetoria_impressa(Trajetoria).

Para ilustrar a aplicação do predicado solucao_da_busca_por_A_estrela_a_partir_do basta compilar seu código e executar a seguinte consulta: 

   ?- solucao_da_busca_por_A_estrela_a_partir_do(b).
   Estado Inicial: b.
   vai_para a cidade: c.
   vai_para a cidade: d.
   vai_para a cidade: n.
   vai_para a cidade: s.
   yes

Note os seguintes pontos:

Algoritmo $ IDA^*$

O nome $ IDA^*$ significa Iterative Deepening $ A^*$. Para descrever melhor os seus conceitos básicos, além de conhecer o $ A^*$, é preciso abordar os seguintes elementos:

A busca de altura fixa é capaz de evitar até mesmo as deficiências da busca em profundidade (que em geral acha soluções muito longas). Note os aspectos abaixo.

O aumento iterativo da busca, combinado com a busca de altura fixa inclui as seguintes características:

O conceito de contorno de custo do espaço de busca é dado por um valor-limite para custo. Isso resulta na possibilidade de se manter a expansão de trajetórias cujos valores de $ f$ estão comprendidos dentro do valor-limite. Note agora os seguintes itens.

Exercício: Implemente a solução para o problema dos Ladrilhos Deslizantes ($ 8-Puzzle$) por meio do algoritmo $ IDA^*$.

Algoritmo $ SMA^*$

O nome $ SMA^*$ significa Simplified Memory-Bouded $ A^*$. Para descrever melhor os seus conceitos básicos, além de conhecer o $ A^*$, é preciso abordar os seguintes elementos:

Algoritmo de Busca Gulosa (Greedy - Best-first)

O de busca pela Melhor Escolha é assim conhecido por ser uma variação da busca em profundidade re-orientada apenas pelo menor valor da função heuríistica $ h$ aplicada aos descendentes do $ E_a$ (estado atual). Em outras palavras, o algoritmo é guiado apenas pela estimativa de menor distância do $ E_a$ ao $ E_f$. Suas características são:

Busca por Satisfação de Restrições

O de busca por Satisfação de Restrições é assim conhecido por ser mais uma variação da busca em profundidade, porém, re-orientada tipicamente por parâmetros de natureza meta-heuríistica. Suas características são:

As principais meta-heuíisticas utilizadas por este algoritmo são duas.

Sobre este documento ...

This document was generated using the LaTeX2HTML translator Version 2008 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 abh2.tex

The translation was initiated by Alexandre I. Direne on 2010-10-27

next_inactive up previous
Alexandre I. Direne 2010-10-27