Universidade
de São Paulo
Instituto de Ciências Matemáticas e de Computação Departamento de Ciências da Computação e Estatística Primeiro Semestre de 1999 |
SCE
5774 - Introdução à Inteligência Artificial
Profa.: Sandra Maria Aluísio sandra@icmsc.sc.usp.br |
Carlos A. Estombelo Montesco
cestombe@icmsc.sc.usp.br
Pastor W. Gonzales Taco pastor@sc.usp.br |
Os algoritmos de busca bidirecional tem o potencial de serem os
mais eficientes quando comparados a suas contrapartes os algoritmos unidirecionais.
Na verdade isto pode ser considerado quando o tamanho da árvore
de busca é tomado como um indicador do custo computacional envolvido,
isto é quanto maior a arvore mais nós podem ser expandidos
e maior será o esforço de busca. Desde que a arvore tenha
uma tendência de incremento exponencial como seus incrementos em
profundidade, este será usualmente o caso no qual a soma das longitudes
dos dois pequenos arvores de busca (a busca bidirecional de forward
e backward) é menor que o tamanho da arvore de busca em largura
da busca unidirecional. Além disso reduzindo o numero total de nós
expandindose sem igual, menores árvores de procura também
oferecem a vantagem de menor custo computational na escolha de menores
jogos de nodos abertos. Alguns trabalhos atestam à promessa de espaços
de procura menores usando algoritmos bidirecionais (Kwa, 1989). Outra motivação
é a substancial redução no tempo de funcionamento
pela implementação da busca bidirecional em paralelo. Porém,
isto não significa que seu algoritmo unidirecional rodará
mais rapidamente, isto dependerá do computacional overheads envolvido
no algoritmo bidirecional.
2.1 O Uso da Lógica na Resolução de Problemas
Segundo Nilson (1971), frequentemente a solução de um
problema qualquer requer a ajuda de uma análise lógica. Algumas
vezes as análises mostram que esses problemas são irresoluveis.
Por exemplo, no caso do 15 Puzzle, é possivel provar que
o estado inicial (Figura 1a) não pode
produzir a configuração da meta (Figura
1b) em função da configuração do estado
inicial.
|
|
Assim um completo tratamento de tecnicas de redução-problema, deverá incluir uma discussão de métodos mecánicos de busca de prova. Algums desses métodos usam estrategias de busca que são similares a os discutidos nas abordagens dos espaços-estados e da redução-problema.
Porém, muitos dos quebra-cabeça existentes considerados
como problemas reais requerem da análise de bom senso, podendo em
princípio possuir um formalismo lógico o qual permite resolve-los
através de técnicas de busca de prova.
A busca bidirecional é basicamente uma busca simultânea que começa no estado inicial e que retrocede a partir da meta, finalizando quando as ambas buscas se encontram em algum ponto intermédio (Figura 2.) No caso dos problemas cujo fator de ramificação é b em ambas as direções, a busca bidirecional pode ser muito útil (Russell & Norvig, 1996). Se em forma geral assumimos a existência de uma solução geral cuja profundidade é d, então a solução estará a O(2b^(d/2)) = O(b^(d/2)) passos, dado que nas buscas para adiante (top-down) e atras (bottom-up), somente percorresse a metade do trajeto. Podemos entender melhor esta situação através de um exemplo real: se b = 10 e d = 6, uma busca preferencial por largura produzirá 1 111, 111 (um milhão cento onze mil e cento onze) nós. Entretanto, uma busca bidirecional terá êxito quando cada uma das direções de busca está a uma profundidade 3, em cujo caso gerasse 2 222 (dois mil e duzentos vente e dos) nós. Na teoria isso é fabuloso, mas antes da possivle implantação do algoritmo, é necessário resolver várias situações as quais podem serem resumidas em:
3. Comparação das Diversas Estratégias de Busca
Na Tabela 1, a seguir comparam-se as seis estratégias de busca
em função dos critérios de avaliação.
Critérios de Avaliação | Preferente por Largura | Custo Uniforme | Preferente por Profundidade | Limitada em Profundidade | Profundização Iterativa | Bidirecional (quando aplicada) |
Tempo | b^d | b^d | b^m | b^l | b^d | b^(d/2) |
Espaço | b^d | b^d | bm | bl | bd | b^(d/2) |
É ótima? | Sim | Sim | Não | Não | Sim | Sim |
É completa? | Sim | Sim | Não | Sim, quando
l >= d |
Sim | Sim |
4. Resolução do Problema Bidirecional
As clausulas de Horn (um programa em PROLOG é descrito como uma série de definições lógicas, sendo que cada uma delas é uma cláusula horn) que descrevem uma típica resolução de problemas podem ser classificadas dentro de três tipos (Kowalski, 1979):
a) Procedimentos de propósito geral (incluem asserções) com a descrição do domínio do problema;As asserções de problemas específicos podem estar ausentes desde a descrição de uma tarefa dada. Mas quando estes estejam presentes podem ser úteis para combinar procuras "top-down" (desde o problema até sua resolução), com a procura "botom-up" (desde a hipótese ao problema). Porém, é importante em este caso evitar a procura "botom-up" das asserções, as quais são parte da descrição geral do domínio do problema. Essa restrição usa da procura "botom-up" combinado com a procura "top-dowm" que é uma característica do sistema do teorema da prova de Bledsoe (1971) apud. Kowalski (1979).
b) Asserções de problemas específicos, os que expressam a hipótese do problema a ser resolvido, e
c) A declaração do objetivo o qual expressa esse mesmo problema.
A maioria dos procedimentos de prova de "botom-up" não distingue entre os diferentes tipos de asserções. Como resultado estes geralmente conduzem a comportamentos de combinação explosiva, gerando asserções que seguem desde uma descrição geral do domínio do problema em adição, para asserções as quais seguem das suposições do problema particular em tratamento.
Um critério útil para combinar problemas específicos de procura "botom-up" com procura "top-dowm" é uma variação de uma proposta de Pohl (1972) apud. Kowalski (1979) para problemas de procura de rotas:
"Para todo passo escolher a direção de conclusão
que dá lugar ao ultimo numero de alternativas"
Na direção "top-dowm" o numero de alternativas é
um numero pequeno de procedimentos os quais se emparelham ao sub-objetivo
selecionado em um objetivo declarado. Na direção "butom-up",
esto é um pequeno numero de asserções as que podem
ser derivadas de uma asserção. O critério de Pohl
é mostrado na Figura 3, a seguir como o
problema de procura de rotas:
O numero seguinte de cada nó indica o numero dos nós sucessores.
O critério de Pohl seleciona a direção associada com
a geração do sucessor de N (Fig. 3b). Dada a previa formulação
do problema de procura de rotas, a procura de rotas bidirecional é
realizada pela combinação das procuras "top-dowm" e "bottom-up".
5. Uma Notação para Descrever a Solução doProblema Bidirecional
Para a distinção entre o "bottom-up" e "top-dowm", pode
ser usado o desenho de flechas para indicar a direção da
procura. Para cada par de átomos emparelhados na configuração
inicial de clausulas (das quais um é a condição e
o outro é a conclusão) uma flecha é dirigida de um
átomo ao outro.
Para a inferência top-dowm as flechas são dirigidas das
condições às conclusões. Para o problema dos
Grandparent, obtemos a seguinte representação:
Para a inferência botom-up, as flechas são dirigidas das
conclusões às condições, como mostrado a seguir:
A definição dos Grandparent pode também ser usada em uma combinação top-down, bottom-up, sendo que as diferentes combinações podem ser representadas usando números que indiquem a seqüência. Para simplificar mostraremos somente a notação associada com a definição dos Grandparent, onde a combinação de direções será:
a qual representa o algoritmo seguinte:
1)
esperar até x seja confirmado como parente de z, então
2)
encontrar um filho y de z, e finalmente
3)
confirmar que x é Grandparent de y.
A combinação indicada por:
representará o algoritmo seguinte:
1)
responder ao problema mostrando que x é o Grandparent
de y,
2)
esperando até x ser confirmado como padre de z, e
então
3)
tente mostrar que z é padre de y.
6. Problema do Jogo das Oito Fichas (8 Puzzle)
O jogo das oito fichas pertence à família dos blocos deslizáveis (Puzzles). Está classe geral é do tipo NP completa, sendo possível achar métodos de solução como os dos algoritmos de busca em profundidade, busca em largura, uma combinação de ambos, ou técnicas de busca como a busca bidirecional. Sendo que este tipo de jogos permite o teste de novos algoritmos em Inteligência Artificial.
O quebra-cabeça de 8 ou jogo das oito fichas, cujo exemplo mostra-se na Figura 4a, consiste em um tabuleiro quadrado com nove divisões, onde são colocadas oito fichas quadradas, numeradas de 1 a 8, e um espaço em vazio. A ficha adjacente ao espaço em vazio pode ser deslocada para aquele espaço. O objetivo é obter, a partir de uma posição inicial (configuração mostrada na Figura 4a), uma posição meta (configuração mostrada na Figura 4b), deslocando as peças até que elas atinjam o local desejado. Um estrategia importante é obtida ao descobrir que em lugar de usar operadores como "desliza a ficha 3 ao espaço vazio", é melhor utilizar operadores como "o espaço vazio pode trocar seu lugar com a ficha que está à esquerda", dado que existe menos operadores como o anterior. Isto nos permite chegar a seguinte formulação de condições básicas para resolução do problema:
|
|
A recuperabilidade de um problema tem papel importante na determinação
da complexidade da estrutura de controle necessária para a solução
do problema. Os problemas recuperáveis podem ser solucionados através
de uma estrutura de controle ligeiramente mais complicada, que às
vezes comete erros. O retrocesso será necessário para recuperar
estes erros, logo a estrutura de controle precisa ser implementada usando-se
uma pilha de cima para baixo, na qual as decisões são gravadas
caso precisem ser desfeitas mais tarde.
6.1 Raciocínio para Frente Versus Raciocínio para Trás
O objetivo de um procedimento de busca é descobrir um caminho através de um espaço de problema, a partir de uma configuração inicial até um estado-meta. Embora o PROLOG só busque a partir de um estado-meta, uma busca na verdade pode prosseguir em duas direções:
Considere o problema de resolver uma determinada instância do
quebra-cabeça de 8. As regras a serem usadas para solucionar o quebra-cabeça
podem ser escritas como mostra a Figura 4 Usando
essas regras, podemos tentar solucionar o quebra-cabeça mostrado
na Figura4. de uma destas duas maneiras:
Podemos também buscar tanto simultaneamente para frente a partir
do estado inicial quanto para trás a partir do objetivo até
que dois percursos se encomtrem em algum lugar no meio do caminho. Esta
estratégia é chamada de busca bidirecional. Ela parece
interessante se o número de nós em cada passo cresce exponencialmente
em relação ao número de passos que já foram
dados. Resultados empíricos (Pohl, 1971) sugerem que no caso de
buscas cegas, esta estratégia de dividir-e-conquistar é realmente
eficaz. A Figura 5, mostra porque a busca bidirecional
pode ser ineficaz. As duas buscas podem passar uma pela outra, resultando
em mais um trabalho do que teria sido necessário para uma delas,
por si só, terminar. Entretanto, se etapas isoladas para frente
e para trás forem cumpridas conforme especificado por um programa
cuidadosamente construído para explorar cada uma dessas situações
exatamente nas situações em que elas são mais lucrativas,
os resultados poderão ser mais encorajadores. Na verdade, muitas
aplicações de sucesso em IA foram elaborados usando-se uma
combinação do raciocínio para frente e para trás,
e a maioria dos ambientes de programação em IA fornece suporte
explícito para esse raciocínio híbrido.
Embora em princípio, o mesmo conjunto de regras possa ser usado tanto para o raciocínio para frente quanto para o raciocínio para trás, na prática ficou provado que é útil definir duas classes de regras, cada uma delas codificando um determinado tipo de conhecimento:
6.2 Combinar o Raciocínio para Frente e Para Trás
Ás vezes, certos aspectos de um problema são mais bem abordados via encadeamento para frente, e outros aspectos pelo encadeamento para trás. Consideresse um programa de diagnóstico médico com encadeamento para frente. Ele pode aceitar vinte e tantos fatos sobre a condição de um paciente, e depois encadear para frente, com base nesses fatos, para tentar deduzir a natureza e/ou a causa da doença. Agora suponha que, em um determinado ponto, o lado esquerdo de uma regra esteja quase satisfeito - digamos, nove entre dez de suas precondições foram satisfeitas. Pode valer a pena aplicar o raciocínio para trás de maneira direcionada para satisfacer a décima precondição em vez de esperar que o encadeamento para frente forneça o fato por acidente. Ou talvez a décima condição exija mais testes médicos. Nesse caso , o encadeamento para trás pode ser usado para consultar o usuário.
Saber se é possível ou não usar as mesmas regras
para o raciocínio para frente e para trás também depende
da forma das regras em si. Se tanto os lados esquerdos quanto os lados
direitos contêm apenas declarações, então o
encadeamento para frente pode casar as declarações no lado
esquerdo de uma regra e acrescentar à descrição do
estado a declaração do lado direito. Mas, se procedimentos
arbitrários forem permitidos nos lados direitos das regras, então
elas não serào reversíveis. algumas linguagens de
regras de produção permiten apenas regras reversíveis;
outras não. Quando regras irreversíveis são usadas,
então é preciso que haja um acordo sobre a direção
da busca no momento em que as regras forem escritas. Mas, conforme sugerimos,
isto e com frequencia um recurso útil, porque permite que o criador
da regra acrescente conhecimentos de controle às própias
regras.
Até aqui, descrevemos o proceso de uso de busca para solucionar problemas como sendo a aplicação de regras apropiadas a estados isolados de problemas, para gerar novos estados aos quais as regras podem então ser aplicadas, e assim por diante, até ser encontradas uma solução. Sugerimos que a busca inteligente deve envolver a escolha de regras que possam ser aplicadas em um determinado ponto, e que têm grande chance de levar a uma solução. Mas foi dito pouco sobre como extrair de un conjunto inteiro de regras aquelas que podem ser aplicadas em um determinado ponto. Esta operação requer algum tipo de casamento entre o estado atual e a precondição das regras. Como isto deve ser feito? A resposta a esta pergunta pode ser crucial para o sucesso de um sistema baseado em regras. Temos algumas propostar a seguir :
O resultado do processo de casamento é uma lista de regras cujos
antecedentes casaram com a descrição do estado atual, juntamente
com quaisquer ligações da variáveis geradas pelo mesmo
processo. É responsabilidade do método de busca decidir sobre
a ordem em que as regras serão aplicadas. Mas, ás vezes,
é útil incorporar parte da tomada de decisão ao processo
de casamento. Esta fase é então chamada de resolução
de conflitos. Neste caso do quebra-cabeça de 8 a abordagen usado
para o problema da resolução de conflitos em um sistema de
produção e Preferência Baseadas em Estados, quer dizer
os estados são comparados em cada nivel de exploração.
7. Algoritmo de Busca Bidirecional
Para execusão do programa da busca bidirecional recomenda-se aumentar a capacidade de memória ao trabalhar com LPA-PROLOG, digitando no ambiente DOS:
C:\...\pro386w /h16000
/* Busca em Profundidade
x Largura */
/* Definição
de Operadores Utilizados no Algoritmo, e Bases de Dados Dinâmicas
para a Contagem de Nós Expandidos eTempo de Execusão*/
:- op(35, xf, e_a_meta
).
:- op(35, xfx, atinge_a_meta).
:- op(35, xfx, transforma
).
:- op(30, xfx, em
).
:- op(35, xfx, nao_produz_circulos_em).
:- dynamic(countinicio/1).
:- dynamic(countmeta/1).
:- dynamic(tempo/1).
/********************************************************************/
/********************* Predicado
Principais *************************/
/*Resolva o Predicado Principal para Iniciar a Busca Bidirecional, Onde inicia as Bases de Dados Dinâmicas em Zero*/
resolva :- init_dynamic,
estado_inicial( Inicio
), Meta e_a_meta, /*Carrega o estado inicial e o estado meta
nas respectivas variaveis*/
busca_bidirectional(
[[ r(raiz, Inicio) ]], [[r(meta, Meta)]], SolucaoDeInicio, SolucaoDeMeta
), /*Inicia a Busca Bidirecional, interccalando os casamentos de busca*/
imprimatempo,
imprima( SolucaoDeInicio
), nl, nl,
imprima( SolucaoDeMeta
), nl.
/*Pergunta se tem a rota
de solução para cada iteração*/
busca_bidirectional( LLSolDeInicio,
LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ) :-
procura( LLSolDeInicio,
LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ).
/*Passa ao nível seguinte
gerando os filhos do nível pai, tanto para a busca da árvore
de inicio como da busca da árvore de meta*/
busca_bidirectional( [HeadIni|TailIni],
[HeadMeta|TailMeta], SolucaoDeInicio, SolucaoDeMeta) :-
ache_todos( ExtensaoAteUmFilhoIni,
estende_ate_filho( HeadIni, ExtensaoAteUmFilhoIni ), ExtensoesIni ),
soma_ini(ExtensoesIni),
/*Conteo dos nós expandidos desde o nó de inicio*/
ap( ExtensoesIni,
TailIni, ListaEstendidaIni ), /*Adiciona todos os nós filhos à
listapara a busca em profundidade*/
ache_todos( ExtensaoAteUmFilhoMeta,
estende_ate_filho( HeadMeta, ExtensaoAteUmFilhoMeta ), ExtensoesMeta ),
soma_meta(ExtensoesMeta),
/*Conteo dos nós expandidos desde o nó meta*/
ap( TailMeta, ExtensoesMeta,
ListaEstendidaMeta ), /*Adiciona todos os nós filhos para a busca
em largura*/
busca_bidirectional(
ListaEstendidaIni, ListaEstendidaMeta, SolucaoDeInicio, SolucaoDeMeta ).
/*Extende tudos os nós
filhos de um nó determinado*/
estende_ate_filho( [r(Ramo,N)|Trajetoria],
[r(Op,Filho), r(Ramo,N)|Trajetoria] ) :-
operacao( Op ) transforma
N em Filho,
not Filho nao_produz_circulos_em
Trajetoria.
/*Verifica que não
existam ciclos na rota*/
Estado nao_produz_circulos_em
Trajetoria :-
membro( r( Operacao,
Estado ), Trajetoria ).
/* Nesta Linha debe-se fazer
a comparação Bidirecional */
r( RamoIni, ML ) atinge_a_meta
r( RamoMeta, MP ):-
ML = MP.
/* nova comparação
*/
procura( LLSolDeInicio,
LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ) :-
procura2( LLSolDeInicio,
LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ).
procura( [_|LTailSolIni]
, LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ) :-
procura( LTailSolIni,
LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ).
/*Comparação
dos nós de inicio com os nós meta, em função
do tipo de busca bidirecional*/
procura2( [[ HeadIni|TailIni
] | _], [[ HeadMeta|TailMeta ] | _], SolucaoDeInicio, SolucaoDeMeta ) :-
HeadIni atinge_a_meta
HeadMeta,
SolucaoDeInicio =
[ HeadIni | TailIni ],
SolucaoDeMeta
= [ HeadMeta | TailMeta ], !.
procura2( LLSolDeInicio,
[_|LTailMeta], SolucaoDeInicio, SolucaoDeMeta ) :-
procura2( LLSolDeInicio
, LTailMeta, SolucaoDeInicio, SolucaoDeMeta ).
/*********************************************************************/
/***********************
Base de Conhecimentos ***********************/
operacao(esq) transforma
[A,*,C,D,E,F,H,I,J] em [*,A,C,D,E,F,H,I,J].
operacao(esq) transforma
[A,B,C,D,*,F,H,I,J] em [A,B,C,*,D,F,H,I,J].
operacao(esq) transforma
[A,B,C,D,E,F,H,*,J] em [A,B,C,D,E,F,*,H,J].
operacao(esq) transforma
[A,B,*,D,E,F,H,I,J] em [A,*,B,D,E,F,H,I,J].
operacao(esq) transforma
[A,B,C,D,E,*,H,I,J] em [A,B,C,D,*,E,H,I,J].
operacao(esq) transforma
[A,B,C,D,E,F,H,I,*] em [A,B,C,D,E,F,H,*,I].
operacao(cima) transforma
[A,B,C,*,E,F,H,I,J] em [*,B,C,A,E,F,H,I,J].
operacao(cima) transforma
[A,B,C,D,*,F,H,I,J] em [A,*,C,D,B,F,H,I,J].
operacao(cima) transforma
[A,B,C,D,E,*,H,I,J] em [A,B,*,D,E,C,H,I,J].
operacao(cima) transforma
[A,B,C,D,E,F,*,I,J] em [A,B,C,*,E,F,D,I,J].
operacao(cima) transforma
[A,B,C,D,E,F,H,*,J] em [A,B,C,D,*,F,H,E,J].
operacao(cima) transforma
[A,B,C,D,E,F,H,I,*] em [A,B,C,D,E,*,H,I,F].
operacao(dir) transforma
[A,*,C,D,E,F,H,I,J] em [A,C,*,D,E,F,H,I,J].
operacao(dir) transforma
[A,B,C,D,*,F,H,I,J] em [A,B,C,D,F,*,H,I,J].
operacao(dir) transforma
[A,B,C,D,E,F,H,*,J] em [A,B,C,D,E,F,H,J,*].
operacao(dir) transforma
[*,B,C,D,E,F,H,I,J] em [B,*,C,D,E,F,H,I,J].
operacao(dir) transforma
[A,B,C,*,E,F,H,I,J] em [A,B,C,E,*,F,H,I,J].
operacao(dir) transforma
[A,B,C,D,E,F,*,I,J] em [A,B,C,D,E,F,I,*,J].
operacao(baixo) transforma
[A,B,C,*,E,F,H,I,J] em [A,B,C,H,E,F,*,I,J].
operacao(baixo) transforma
[A,B,C,D,*,F,H,I,J] em [A,B,C,D,I,F,H,*,J].
operacao(baixo) transforma
[A,B,C,D,E,*,H,I,J] em [A,B,C,D,E,J,H,I,*].
operacao(baixo) transforma
[*,B,C,D,E,F,H,I,J] em [D,B,C,*,E,F,H,I,J].
operacao(baixo) transforma
[A,*,C,D,E,F,H,I,J] em [A,E,C,D,*,F,H,I,J].
operacao(baixo) transforma
[A,B,*,D,E,F,H,I,J] em [A,B,F,D,E,*,H,I,J].
/********************************************************************/
/************************
Testes ***********************/
/*Test A*/
estado_inicial([1,2,3,4,5,6,7,8,*]).
[3,*,1,2,5,6,4,7,8] e_a_meta.
/*Test B*/
/*
estado_inicial([1,2,3,4,5,6,7,8,*]).
[*,3,1,2,5,6,4,7,8] e_a_meta.
*/
/*Test C*/
/*
estado_inicial([1,2,3,4,5,6,7,8,*]).
[2,3,1,*,5,6,4,7,8] e_a_meta.
*/
/*Test D*/
/*
estado_inicial([1,2,3,4,5,6,7,8,*]).
[2,3,*,1,5,6,4,7,8] e_a_meta.
*/
/* Test E */
/*
estado_inicial([1,2,3,4,5,6,7,8,*]).
[1,2,3,5,*,6,4,7,8] e_a_meta.
*/
/********************************************************************/
/************************
Predicados de Ajuda ***********************/
init_dynamic :-
asserta(countinicio(0)),
asserta(countmeta(0)),
ticks(Tempo), asserta(tempo(Tempo)).
imprimatempo :- ticks(Tempo2),
retract(tempo(Tempo)),
write('***********
Resultados **********'),nl,nl,
write('O Tempo Rodado
em ticks :'),
Ticks is Tempo2 -
Tempo,
write(Ticks),nl,nl.
/*Contadores da expansão
dos nós de inicio e de meta*/
soma_ini([]):-!.
soma_ini([Head|Tail])
:- retract(countinicio(N)),
Tot is N + 1, asserta(countinicio(Tot)),
soma_ini(Tail),!.
soma_meta([]):-!.
soma_meta([Head|Tail]) :-
retract(countmeta(N)),
Tot is N + 1, asserta(countmeta(Tot)),
soma_meta(Tail),!.
/*Adiciona uma lista para
outra lista*/
ap([],X,X) :- !.
ap([X|Y],Z,[X|W]) :- ap(Y,
Z, W).
/*Verifica se um elemento
encontra-se dentro de uma lista*/
membro(X,[X|_]) :- !.
membro(X,[_|Y]) :- membro(X,Y).
ache_todos(X, Y, Z) :- findall(X,
Y, Z), !.
ache_todos(_, _, []).
imprima([r(raiz,Raiz)]) :-
!,
write('Estado Inicial(
Busca De Inicio - Profundidade) : '),
write(Raiz), write('.'),nl,
retract(countinicio(Nos)),
write('Nos Expandidos:'), write(Nos),nl.
imprima([r(meta,Meta)]) :-
!,
write('Estado Final
( Busca De Meta - Largura ) :
'),
write(Meta), write('.'),nl,
retract(countmeta(Nos)),
write('Nos Expandidos:'), write(Nos),nl.
imprima([r(Ramo,Nodo)|R])
:- imprima(R), nl,
write(Ramo), write('
e ,portanto, temos: '), nl,
tab(4),write(Nodo),
write('.').
8. Tipos de Busca Bidirecional Usando Largura e Profundidade
Foram definidas as seguintes combinações de busca, testadas para cada um dos tipos de 8-puzzle:
Em cada teste foi gerado, alem do estado meta, indicadores que possibilitem avaliar o comportamento de cada combinação de algoritmos mostradas acima (Tabelas 2, 3, 4, 5 e 6). Para isto obteve-se valores do tempo de execusão, medido em ticks do relogio do computador (como mostrado nas tabelas de cada tipo de Puzzle). Pode-se observar que alguns valores dos tempos estão indicados com ~ 0, significando que pela rapidez do processamento valor de saida do tempo é considerado como de valor zero, sem serlo na realidade. Por isto indicamos que as características do computador utilizado nos testes são os seguintes: Pentium II, MMX, Processador Intel Inside, Sistema Operativo Windows. Além disso obteve-se também valores dos números de Nós expandidos para cada árvore, do estado de inicio e do estado meta, assim como os Numeros de nós na rota que corresponde a solução do puzzle.
|
|
Largura x Largura | Largura x Profundidade | Profundidade x Largura | Profundidade x Profundidade | |
Tempo (ticks) | 14080 | 2560 | 256 | 512 |
Nós expandidos | 160 - 166 | 91 - 95 | 29 - 29 | 38 - 40 |
Numero de nós na rota | 8 - 7 | 7 - 62 | 15 - 4 | 18 - 21 |
|
|
Largura x Largura | Largura x Profundidade | Profundidade x Largura | Profundidade x Profundidade | |
Tempo (ticks) | 14336 | 33024 | ~ 0 | 256 |
Nós expandidos | 164 - 164 | 212 - 213 | 21 - 24 | 19 - 21 |
Numero de nós na rota | 8 - 8 | 8 - 54 | 12 - 4 | 11 - 5 |
|
|
Largura x Largura | Largura x Profundidade | Profundidade x Largura | Profundidade x Profundidade | |
Tempo (ticks) | 77312 | 3584 | 256 | 256 |
Nós expandidos | 297 - 271 | 99 - 106 | 35 - 34 | 19 - 20 |
Numero de nós na rota | 9 - 8 | 7 - 58 | 12 - 5 | 11 - 6 |
|
|
Largura x Largura | Largura x Profundidade | Profundidade x Largura | Profundidade x Profundidade | |
Tempo (ticks) | ~ 0 | 256 | ~ 0 | ~ 0 |
Nós expandidos | 7 - 7 | 34 - 31 | 13 - 16 | 5 - 5 |
Numero de nós na rota | 3 - 3 | 5 - 5 | 4 - 4 | 3 - 3 |
|
|
Largura x Largura | Largura x Profundidade | Profundidade x Largura | Profundidade x Profundidade | |
Tempo (ticks) | ~ 0 | ~ 0 | ~ 0 | ~ 0 |
Nós expandidos | 4 - 6 | 4 - 6 | 4 - 6 | 4 - 6 |
Numero de nós na rota | 2 - 2 | 2 - 2 | 2 - 2 | 2 - 2 |
8.6 Análise dos Resultados Experimentais
Os esperimentos foram conduzidos por comparação pelos
resultados obtidos em função dos nós expandidos em
cada tipo de busqueda bidirecional, e os nós de rota de casamento.
Em ambos os casos tomou-se em consideração o estado de busqueda
para frente desde o inicio, e os estado de busca para trás desde
a meta. Assim é possivel fazer uma comparação do tipo
de busca bidirecional nos diferentes tipos de puzzle, tratando-se de determinar
a variavilidade dos resultados.
Para o Tipode Puzzle C, como observado na Figura 8, podemos afirmar que em função do numero de nós expandidos, a combinação largura x largura gerou a maior quantidade de nós, a respeito das outras combinações, sendo esta combinação dependente da memória do computador. O caso oposto a isso é observado na combinação profundidade x profundidade, onde gerou-se o menor numero de nós expandidos. Isso não significa que esta ultima seja uma combinação ideal, pois pode acontecer que os espaços de busca sejam distantes um do outro, impossibilitando encontrar-se, gerando assim o pior caso de busca unidirecional em ambos os sentidos de busca.
Para o caso dos número de nós da rota, no Tipode
Puzzle C, podemos observar na seguinte Figura
9, este segue um comportamento muito similar ao produzido no Tipo
de Puzzle B .
8.7 Comparação Final dos Testes para os Diferentes Tipos de Puzzle
Para efeitos de um melhor entendimento foi gerada a seguinte Figura
10, onde são comparados os numeros de Nós expandidos
para cada Tipo de Puzzle, observamos que estes valores são
maiores no caso da combinação largura x largura ((inicio)Lar
--(meta)Lar). Além disso estes valores nos mostram a maior dificuldade
do Puzzle C, a respeito do Puzzle
D. Para todas os Puzzles na combinação profundidade
x profundicade ((inicio)Pro--(meta)Pro) o número de nós
expandidos foram poucos, sendo que isto não necesariamente seja
a melhor combinação, como explicado anteriormente
.
Bibliografia Referêncial: