Busca no espaço de estados (parte I) - IME-USPslago/pl-10.pdf · Idéia básica A idéia básica da busca no espaço de estados é considerar a existência de um agente cujas ações

Busca no espaço de estados (parte I)

Prof. Dr. Silvio do Lago Pereira

Departamento de Tecnologia da Informação

Faculdade de Tecnologia de São Paulo

Idéia básica

A idéia básica da busca no espaço de estadosA idéia básica da busca no espaço de estados

é considerar a existência de um agente cujas ações modificam o estado do mundo.é considerar a existência de um agente cujas ações modificam o estado do mundo.

Suposições clássicas:

o mundo muda apenas quando o agente executa uma ação

não há incerteza acerca dos efeitos das ações do agente

a meta do agente é alcançar um determinado estado final

Prof. Dr. Silvio do Lago Pereira – DTI / FATEC-SP 2

Exemplo 1. Mundo do aspirador simplificado [Russel & Norvig, 2004]Exemplo 1. Mundo do aspirador simplificado [Russel & Norvig, 2004]

a meta do agente é alcançar um determinado estado final

Ações do agente:

• entrar1

• entrar2

• aspirar

1111 2222

Espaço de estados

entrar1entrar1entrar1entrar1


aspiraraspiraraspiraraspirar

Um espaço de estados é um grafo definido por:Um espaço de estados é um grafo definido por:

um conjunto de estados (todos os possíveis estados em que o mundo pode estar)

um conjunto de ações (todas as ações que o agente é capaz de executar).

um conjunto de estados (todos os possíveis estados em que o mundo pode estar)

um conjunto de ações (todas as ações que o agente é capaz de executar).












Problema de busca


Um problema de busca em um determinado espaço de estados é definido por:Um problema de busca em um determinado espaço de estados é definido por:

um estado inicial (indicando o estado corrente do mundo do agente)

um conjunto de estados finais ou estados metas (indicando a meta do agente)

um estado inicial (indicando o estado corrente do mundo do agente)

um conjunto de estados finais ou estados metas (indicando a meta do agente)



estados metas












estado inicial

estados metas

Solução


A solução para um problema de busca éA solução para um problema de busca é

uma sequência de ações (ou plano) que, quando executada pelo agente, transforma o estado inicial em um estado metauma sequência de ações (ou plano) que, quando executada pelo agente, transforma o estado inicial em um estado meta















estado inicial




Representação de estados

Estados são representados por estruturasEstados são representados por estruturas

cujos componentes denotam suas propriedades ou características particularescujos componentes denotam suas propriedades ou características particulares

No mundo do aspirador, há três características que distinguem os possíveis estados

do mundo. Assim, podemos representar estes estados por estruturas da forma

[X,Y,Z][X,Y,Z][X,Y,Z][X,Y,Z], onde:

∈ { , } indica se o agente está na sala 1 ou 2


XXXX∈ {1,2} indica se o agente está na sala 1 ou 2

YYYY∈ {l,s} indica se a primeira sala está limpa ou suja

ZZZZ∈ {l,s} indica se a segunda sala está limpa ou suja

Exemplo 2. Representação do estado inicial e dos estados metasExemplo 2. Representação do estado inicial e dos estados metas

inicialinicialinicialinicial([1,s,s]).([1,s,s]).([1,s,s]).([1,s,s]).

metametametameta([_,l,l]).([_,l,l]).([_,l,l]).([_,l,l]).

inicialinicialinicialinicial([1,s,s]).([1,s,s]).([1,s,s]).([1,s,s]).

metametametameta([_,l,l]).([_,l,l]).([_,l,l]).([_,l,l]).

Representação de ações

Ações são representadas por regras da formaAções são representadas por regras da forma

ação(ação(ação(ação(αααα,e,e,e,e1111,e,e,e,e2222) :) :) :) :---- ββββ....

onde:

αααα é o identificador da ação

eeee1111 é o estado em que o mundo se encontra antes da execução da ação ααααeeee2222 é o estado em que o mundo fica após a execução da ação αααα

ββββ é uma especificação das precondições e/ou efeitos da ação αααα

ação(ação(ação(ação(αααα,e,e,e,e1111,e,e,e,e2222) :) :) :) :---- ββββ....

onde:

αααα é o identificador da ação

eeee1111 é o estado em que o mundo se encontra antes da execução da ação ααααeeee2222 é o estado em que o mundo fica após a execução da ação αααα

ββββ é uma especificação das precondições e/ou efeitos da ação αααα


ββββ é uma especificação das precondições e/ou efeitos da ação ααααββββ é uma especificação das precondições e/ou efeitos da ação αααα

Exemplo 3. Representação da ação aspiraraspiraraspiraraspirar no mundo do aspiradorExemplo 3. Representação da ação aspiraraspiraraspiraraspirar no mundo do aspirador

ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :----X1=1, Y1=s, X1=1, Y1=s, X1=1, Y1=s, X1=1, Y1=s, % precondições% precondições% precondições% precondiçõesX2=1, Y2=l, Z2=Z1. X2=1, Y2=l, Z2=Z1. X2=1, Y2=l, Z2=Z1. X2=1, Y2=l, Z2=Z1. % efeitos% efeitos% efeitos% efeitos

ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :----X1=2, Z1=s, X1=2, Z1=s, X1=2, Z1=s, X1=2, Z1=s, % precondições% precondições% precondições% precondiçõesX2=2, Y2=Y1, Z2=l. X2=2, Y2=Y1, Z2=l. X2=2, Y2=Y1, Z2=l. X2=2, Y2=Y1, Z2=l. % efeitos% efeitos% efeitos% efeitos

ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :----X1=1, Y1=s, X1=1, Y1=s, X1=1, Y1=s, X1=1, Y1=s, % precondições% precondições% precondições% precondiçõesX2=1, Y2=l, Z2=Z1. X2=1, Y2=l, Z2=Z1. X2=1, Y2=l, Z2=Z1. X2=1, Y2=l, Z2=Z1. % efeitos% efeitos% efeitos% efeitos

ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :,[X1,Y1,Z1],[X2,Y2,Z2]) :----X1=2, Z1=s, X1=2, Z1=s, X1=2, Z1=s, X1=2, Z1=s, % precondições% precondições% precondições% precondiçõesX2=2, Y2=Y1, Z2=l. X2=2, Y2=Y1, Z2=l. X2=2, Y2=Y1, Z2=l. X2=2, Y2=Y1, Z2=l. % efeitos% efeitos% efeitos% efeitos

Representação de ações

Representação implícita de precondições e efeitosRepresentação implícita de precondições e efeitos

Precondições e efeitos especificados por meio de condições que envolvem apenas teste de

igualdade e unificação podem ser representados de maneira implícita

Precondições e efeitos especificados por meio de condições que envolvem apenas teste de

igualdade e unificação podem ser representados de maneira implícita

Exemplo 4. Representação completa das ações para o mundo do aspiradorExemplo 4. Representação completa das ações para o mundo do aspirador

ação(ação(ação(ação(entrar1entrar1entrar1entrar1,[,[,[,[2222,Y,Z],[,Y,Z],[,Y,Z],[,Y,Z],[1111,Y,Z]). ,Y,Z]). ,Y,Z]). ,Y,Z]).

ação(ação(ação(ação(entrar2entrar2entrar2entrar2,[,[,[,[1111,Y,Z],[,Y,Z],[,Y,Z],[,Y,Z],[2222,Y,Z]).,Y,Z]).,Y,Z]).,Y,Z]).

ação(ação(ação(ação(entrar1entrar1entrar1entrar1,[,[,[,[2222,Y,Z],[,Y,Z],[,Y,Z],[,Y,Z],[1111,Y,Z]). ,Y,Z]). ,Y,Z]). ,Y,Z]).




ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[1,,[1,,[1,,[1,ssss,Z],[1,,Z],[1,,Z],[1,,Z],[1,llll,Z]). ,Z]). ,Z]). ,Z]).

ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[2,Y,,[2,Y,,[2,Y,,[2,Y,ssss],[2,Y,],[2,Y,],[2,Y,],[2,Y,llll]).]).]).]).


ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[1,,[1,,[1,,[1,ssss,Z],[1,,Z],[1,,Z],[1,,Z],[1,llll,Z]). ,Z]). ,Z]). ,Z]).

ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[2,Y,,[2,Y,,[2,Y,,[2,Y,ssss],[2,Y,],[2,Y,],[2,Y,],[2,Y,llll]).]).]).]).

Exercício 1. Transição de estado por meio da execução de uma açãoExercício 1. Transição de estado por meio da execução de uma ação

Digite as cláusulas do Exemplo 4 e faça as consultas a seguir:????---- ação(entrar1,E,S).ação(entrar1,E,S).ação(entrar1,E,S).ação(entrar1,E,S).????---- ação(entrar2,E,S).ação(entrar2,E,S).ação(entrar2,E,S).ação(entrar2,E,S).????---- ação(aspirar,E,S).ação(aspirar,E,S).ação(aspirar,E,S).ação(aspirar,E,S).

Digite as cláusulas do Exemplo 4 e faça as consultas a seguir:????---- ação(entrar1,E,S).ação(entrar1,E,S).ação(entrar1,E,S).ação(entrar1,E,S).????---- ação(entrar2,E,S).ação(entrar2,E,S).ação(entrar2,E,S).ação(entrar2,E,S).????---- ação(aspirar,E,S).ação(aspirar,E,S).ação(aspirar,E,S).ação(aspirar,E,S).

Ações aplicáveis

Uma ação A é aplicável a um estado EUma ação A é aplicável a um estado E

se as suas precondições são satisfeitas neste estadose as suas precondições são satisfeitas neste estado

Exemplo 5. Ações aplicáveis ao estado [2,l,s][2,l,s][2,l,s][2,l,s]Exemplo 5. Ações aplicáveis ao estado [2,l,s][2,l,s][2,l,s][2,l,s]

????---- findall(findall(findall(findall(AAAA, , , , ação(ação(ação(ação(AAAA,[2,l,s],_),[2,l,s],_),[2,l,s],_),[2,l,s],_), R). , R). , R). , R).

R = [entrar1, aspirar]R = [entrar1, aspirar]R = [entrar1, aspirar]R = [entrar1, aspirar]

????---- findall(findall(findall(findall(AAAA, , , , ação(ação(ação(ação(AAAA,[2,l,s],_),[2,l,s],_),[2,l,s],_),[2,l,s],_), R). , R). , R). , R).

R = [entrar1, aspirar]R = [entrar1, aspirar]R = [entrar1, aspirar]R = [entrar1, aspirar]


yes yes yes yes yes yes yes yes

Exercício 2. Ações aplicáveisExercício 2. Ações aplicáveis

Encontre todas as ações aplicáveis a cada um dos estados a seguir:

[1,l,l][1,l,l][1,l,l][1,l,l]

[1,l,s][1,l,s][1,l,s][1,l,s]

[1,s,l][1,s,l][1,s,l][1,s,l]

[1,s,s][1,s,s][1,s,s][1,s,s]

Encontre todas as ações aplicáveis a cada um dos estados a seguir:

[1,l,l][1,l,l][1,l,l][1,l,l]

[1,l,s][1,l,s][1,l,s][1,l,s]

[1,s,l][1,s,l][1,s,l][1,s,l]

[1,s,s][1,s,s][1,s,s][1,s,s]

Estados sucessores

Os estados sucessores de um estado EOs estados sucessores de um estado E

são aqueles que podem ser diretamente alcançados por uma ação aplicável ao estado Esão aqueles que podem ser diretamente alcançados por uma ação aplicável ao estado E

Exemplo 6. Sucessores do estado [2,l,s][2,l,s][2,l,s][2,l,s]Exemplo 6. Sucessores do estado [2,l,s][2,l,s][2,l,s][2,l,s]

????---- findall(findall(findall(findall(EEEE, , , , ação(_,[2,l,s],ação(_,[2,l,s],ação(_,[2,l,s],ação(_,[2,l,s],EEEE)))), R). , R). , R). , R).

R = [[1, l, s], [2, l, l]]R = [[1, l, s], [2, l, l]]R = [[1, l, s], [2, l, l]]R = [[1, l, s], [2, l, l]]

????---- findall(findall(findall(findall(EEEE, , , , ação(_,[2,l,s],ação(_,[2,l,s],ação(_,[2,l,s],ação(_,[2,l,s],EEEE)))), R). , R). , R). , R).

R = [[1, l, s], [2, l, l]]R = [[1, l, s], [2, l, l]]R = [[1, l, s], [2, l, l]]R = [[1, l, s], [2, l, l]]


yes yes yes yes yes yes yes yes

Exercício 3. Expansão de uma folha (ou geração de sucessores da folha)Exercício 3. Expansão de uma folha (ou geração de sucessores da folha)

Expanda as folhas a seguir:

[1,l,l][1,l,l][1,l,l][1,l,l]

[1,l,s][1,l,s][1,l,s][1,l,s]

[1,s,l][1,s,l][1,s,l][1,s,l]

[1,s,s][1,s,s][1,s,s][1,s,s]

Expanda as folhas a seguir:

[1,l,l][1,l,l][1,l,l][1,l,l]

[1,l,s][1,l,s][1,l,s][1,l,s]

[1,s,l][1,s,l][1,s,l][1,s,l]

[1,s,s][1,s,s][1,s,s][1,s,s]

Árvore de busca

Uma árvore de buscaUma árvore de busca

é o desdobramento (infinito) de um espaço de estados, a partir de um estado inicial particularé o desdobramento (infinito) de um espaço de estados, a partir de um estado inicial particular

[1,s,s][1,s,s][1,s,s][1,s,s]


[2,s,s][2,s,s][2,s,s][2,s,s] [1,l,s][1,l,s][1,l,s][1,l,s]



[2,s,l][2,s,l][2,s,l][2,s,l][1,s,s][1,s,s][1,s,s][1,s,s] [2,l,s][2,l,s][2,l,s][2,l,s]

[1,s,l][1,s,l][1,s,l][1,s,l][1,l,s][1,l,s][1,l,s][1,l,s] [1,l,s][1,l,s][1,l,s][1,l,s][2,s,s][2,s,s][2,s,s][2,s,s] [2,l,l][2,l,l][2,l,l][2,l,l]

[1,l,l][1,l,l][1,l,l][1,l,l][2,l,s][2,l,s][2,l,s][2,l,s] [2,l,s][2,l,s][2,l,s][2,l,s][1,s,s][1,s,s][1,s,s][1,s,s] [1,l,l][1,l,l][1,l,l][1,l,l]

entrar1entrar1entrar1entrar1 aspiraraspiraraspiraraspirar entrar2entrar2entrar2entrar2

entrar1entrar1entrar1entrar1entrar2entrar2entrar2entrar2 aspiraraspiraraspiraraspirar entrar1entrar1entrar1entrar1 aspiraraspiraraspiraraspirar

aspiraraspiraraspiraraspirarentrar2entrar2entrar2entrar2 entrar2entrar2entrar2entrar2 entrar1entrar1entrar1entrar1

[2,s,l][2,s,l][2,s,l][2,s,l]

entrar1entrar1entrar1entrar1 aspiraraspiraraspiraraspirar

............ ............ ............ ............ ............ ............

Estratégias de busca

Uma estratégia de buscaUma estratégia de busca

especifica em que ordem devemos visitar os nós da árvore de busca para achar uma soluçãoespecifica em que ordem devemos visitar os nós da árvore de busca para achar uma solução

As principais estratégias de busca podem ser divididas em dois grupos:

busca não-informada: as estratégias neste grupo não dispõem de informação que

possibilite a escolha do nó mais promissor para ser visitado em cada instante.

busca aleatória


busca aleatória

busca em largura

busca em profundidade

• busca informada: as estratégias neste grupo dispõem de informação que

possibilitam a escolha do nó mais promissor para ser visitado em cada instante.

busca pelo menor custo

busca pela melhor estimativa

busca ótima (A*)

Busca não-informada

busca aleatória

busca em largura

busca em profundidade

Busca aleatória

Na busca aleatóriaNa busca aleatória

a escolha das folhas a serem expandidas é feita aleatoriamentea escolha das folhas a serem expandidas é feita aleatoriamente

[1,s,s][1,s,s][1,s,s][1,s,s][1,s,s][1,s,s][1,s,s][1,s,s]



Solução: [entrar2,aspirar,entrar1,aspirar]Solução: [entrar2,aspirar,entrar1,aspirar]Solução: [entrar2,aspirar,entrar1,aspirar]Solução: [entrar2,aspirar,entrar1,aspirar]

[1,l,s][1,l,s][1,l,s][1,l,s][2,s,s][2,s,s][2,s,s][2,s,s][2,s,s][2,s,s][2,s,s][2,s,s]

[1,s,s][1,s,s][1,s,s][1,s,s]


[2,s,l][2,s,l][2,s,l][2,s,l][2,s,l][2,s,l][2,s,l][2,s,l]


[1,s,l][1,s,l][1,s,l][1,s,l][1,s,l][1,s,l][1,s,l][1,s,l]

[1,l,l][1,l,l][1,l,l][1,l,l]


[1,l,l][1,l,l][1,l,l][1,l,l]

Busca aleatória

Exemplo 7. Embaralhamento de conjunto de elementosExemplo 7. Embaralhamento de conjunto de elementos

embaralhaembaralhaembaralhaembaralha(0,F,F) :(0,F,F) :(0,F,F) :(0,F,F) :---- !!!!....

embaralhaembaralhaembaralhaembaralha(L,F,[(L,F,[(L,F,[(L,F,[X|NFX|NFX|NFX|NF]) :]) :]) :]) :----

N N N N is randomis randomis randomis random(L), (L), (L), (L),

nth0nth0nth0nth0(N,F,X), (N,F,X), (N,F,X), (N,F,X),

deletedeletedeletedelete(F,X,R), (F,X,R), (F,X,R), (F,X,R),


embaralhaembaralhaembaralhaembaralha(L,F,[(L,F,[(L,F,[(L,F,[X|NFX|NFX|NFX|NF]) :]) :]) :]) :----




Para garantir uma escolha aleatória, devemos embaralhar as folhas antes de fazer a escolha



M M M M isisisis LLLL----1, 1, 1, 1,

embaralha(M,R,NF), embaralha(M,R,NF), embaralha(M,R,NF), embaralha(M,R,NF), !!!!....




Exercício 4. Escolha aleatória de uma folha a ser visitadaExercício 4. Escolha aleatória de uma folha a ser visitada

Faça as consultas a seguir e analise os resultados:

????---- embaralha(4, [a,b,c,d], embaralha(4, [a,b,c,d], embaralha(4, [a,b,c,d], embaralha(4, [a,b,c,d], RRRR).).).).

????---- embaralha(4, [a,b,c,d], [embaralha(4, [a,b,c,d], [embaralha(4, [a,b,c,d], [embaralha(4, [a,b,c,d], [EEEE|_|_|_|_]).]).]).]).

????---- embaralha(3, [[1,s,s], [1,l,l], [1,l,s]], [embaralha(3, [[1,s,s], [1,l,l], [1,l,s]], [embaralha(3, [[1,s,s], [1,l,l], [1,l,s]], [embaralha(3, [[1,s,s], [1,l,l], [1,l,s]], [EEEE|_|_|_|_]).]).]).]).

Faça as consultas a seguir e analise os resultados:

????---- embaralha(4, [a,b,c,d], embaralha(4, [a,b,c,d], embaralha(4, [a,b,c,d], embaralha(4, [a,b,c,d], RRRR).).).).

????---- embaralha(4, [a,b,c,d], [embaralha(4, [a,b,c,d], [embaralha(4, [a,b,c,d], [embaralha(4, [a,b,c,d], [EEEE|_|_|_|_]).]).]).]).

????---- embaralha(3, [[1,s,s], [1,l,l], [1,l,s]], [embaralha(3, [[1,s,s], [1,l,l], [1,l,s]], [embaralha(3, [[1,s,s], [1,l,l], [1,l,s]], [embaralha(3, [[1,s,s], [1,l,l], [1,l,s]], [EEEE|_|_|_|_]).]).]).]).

Busca aleatória

Exemplo 8. Expansão de folha com extensão de caminhoExemplo 8. Expansão de folha com extensão de caminho

Quando a folha escolhida para ser expandida é reconhecida como estado meta, o

caminho que leva até ela deve ser devolvido como solução do problema de busca.

Assim, para facilitar a obtenção da solução de um problema de busca, juntamente

com cada folha EEEE guardamos o caminho CCCC que leva até ela.

Particularmente, no caso da folha correspondente ao estado inicial, este caminho é

representado por uma lista vazia.


Exemplo 8. Expansão de folha com extensão de caminhoExemplo 8. Expansão de folha com extensão de caminho

????---- E:C = [2,l,s]:[entrar2,aspirar], E:C = [2,l,s]:[entrar2,aspirar], E:C = [2,l,s]:[entrar2,aspirar], E:C = [2,l,s]:[entrar2,aspirar],

findallfindallfindallfindall((((NNNN:[:[:[:[A|CA|CA|CA|C],],],],ação(A,E,ação(A,E,ação(A,E,ação(A,E,NNNN)))),S).,S).,S).,S).

E = [2,l,s]E = [2,l,s]E = [2,l,s]E = [2,l,s]

C = [entrar2,aspirar]C = [entrar2,aspirar]C = [entrar2,aspirar]C = [entrar2,aspirar]

S = [[1,l,s]:[entrar1,entrar2,aspirar], S = [[1,l,s]:[entrar1,entrar2,aspirar], S = [[1,l,s]:[entrar1,entrar2,aspirar], S = [[1,l,s]:[entrar1,entrar2,aspirar],

[2,l,l]:[aspirar,entrar2,aspirar]][2,l,l]:[aspirar,entrar2,aspirar]][2,l,l]:[aspirar,entrar2,aspirar]][2,l,l]:[aspirar,entrar2,aspirar]]

yesyesyesyes

????---- E:C = [2,l,s]:[entrar2,aspirar], E:C = [2,l,s]:[entrar2,aspirar], E:C = [2,l,s]:[entrar2,aspirar], E:C = [2,l,s]:[entrar2,aspirar],

findallfindallfindallfindall((((NNNN:[:[:[:[A|CA|CA|CA|C],],],],ação(A,E,ação(A,E,ação(A,E,ação(A,E,NNNN)))),S).,S).,S).,S).

E = [2,l,s]E = [2,l,s]E = [2,l,s]E = [2,l,s]

C = [entrar2,aspirar]C = [entrar2,aspirar]C = [entrar2,aspirar]C = [entrar2,aspirar]

S = [[1,l,s]:[entrar1,entrar2,aspirar], S = [[1,l,s]:[entrar1,entrar2,aspirar], S = [[1,l,s]:[entrar1,entrar2,aspirar], S = [[1,l,s]:[entrar1,entrar2,aspirar],

[2,l,l]:[aspirar,entrar2,aspirar]][2,l,l]:[aspirar,entrar2,aspirar]][2,l,l]:[aspirar,entrar2,aspirar]][2,l,l]:[aspirar,entrar2,aspirar]]

yesyesyesyes

Busca aleatória

Exercício 5. Expansão de nó folha com extensão de caminhoExercício 5. Expansão de nó folha com extensão de caminho

Mostre como expandir os nós folhas a seguir:

[1,s,s]:[][1,s,s]:[][1,s,s]:[][1,s,s]:[]

[2,s,s]:[entrar2,entrar1,entrar2][2,s,s]:[entrar2,entrar1,entrar2][2,s,s]:[entrar2,entrar1,entrar2][2,s,s]:[entrar2,entrar1,entrar2]

Mostre como expandir os nós folhas a seguir:

[1,s,s]:[][1,s,s]:[][1,s,s]:[][1,s,s]:[]

[2,s,s]:[entrar2,entrar1,entrar2][2,s,s]:[entrar2,entrar1,entrar2][2,s,s]:[entrar2,entrar1,entrar2][2,s,s]:[entrar2,entrar1,entrar2]

Exercício 6. Expansão de nó folha escolhido aleatoriamenteExercício 6. Expansão de nó folha escolhido aleatoriamente


Exercício 6. Expansão de nó folha escolhido aleatoriamenteExercício 6. Expansão de nó folha escolhido aleatoriamente

Mostre como expandir um nó folha escolhido aleatoriamente na lista a seguir:

L = L = L = L = [[[[[1,s,s]:[entrar1,entrar2][1,s,s]:[entrar1,entrar2][1,s,s]:[entrar1,entrar2][1,s,s]:[entrar1,entrar2], , , ,

[1,l,l]:[entrar1,aspirar,entrar2][1,l,l]:[entrar1,aspirar,entrar2][1,l,l]:[entrar1,aspirar,entrar2][1,l,l]:[entrar1,aspirar,entrar2], , , ,

[1,l,s]:[aspirar][1,l,s]:[aspirar][1,l,s]:[aspirar][1,l,s]:[aspirar]]]]]

Mostre como expandir um nó folha escolhido aleatoriamente na lista a seguir:

L = L = L = L = [[[[[1,s,s]:[entrar1,entrar2][1,s,s]:[entrar1,entrar2][1,s,s]:[entrar1,entrar2][1,s,s]:[entrar1,entrar2], , , ,

[1,l,l]:[entrar1,aspirar,entrar2][1,l,l]:[entrar1,aspirar,entrar2][1,l,l]:[entrar1,aspirar,entrar2][1,l,l]:[entrar1,aspirar,entrar2], , , ,

[1,l,s]:[aspirar][1,l,s]:[aspirar][1,l,s]:[aspirar][1,l,s]:[aspirar]]]]]

Busca aleatória com ciclos

Exemplo 9. Implementação de busca aleatória com ciclosExemplo 9. Implementação de busca aleatória com ciclos

busca_aleatória_ccbusca_aleatória_ccbusca_aleatória_ccbusca_aleatória_cc ::::----

inicial(E),inicial(E),inicial(E),inicial(E),

busca_aleatória_cc([E:[]],P),busca_aleatória_cc([E:[]],P),busca_aleatória_cc([E:[]],P),busca_aleatória_cc([E:[]],P),

formatformatformatformat('~nPlano: ~w~n~n',[P]).('~nPlano: ~w~n~n',[P]).('~nPlano: ~w~n~n',[P]).('~nPlano: ~w~n~n',[P]).

busca_aleatória_ccbusca_aleatória_ccbusca_aleatória_ccbusca_aleatória_cc([E:C|_],P) :([E:C|_],P) :([E:C|_],P) :([E:C|_],P) :----

meta(E), meta(E), meta(E), meta(E), !!!!,,,,

busca_aleatória_ccbusca_aleatória_ccbusca_aleatória_ccbusca_aleatória_cc ::::----


busca_aleatória_cc([E:[]],P),busca_aleatória_cc([E:[]],P),busca_aleatória_cc([E:[]],P),busca_aleatória_cc([E:[]],P),

formatformatformatformat('~nPlano: ~w~n~n',[P]).('~nPlano: ~w~n~n',[P]).('~nPlano: ~w~n~n',[P]).('~nPlano: ~w~n~n',[P]).

busca_aleatória_ccbusca_aleatória_ccbusca_aleatória_ccbusca_aleatória_cc([E:C|_],P) :([E:C|_],P) :([E:C|_],P) :([E:C|_],P) :----




reversereversereversereverse(C,P).(C,P).(C,P).(C,P).

busca_aleatória_ccbusca_aleatória_ccbusca_aleatória_ccbusca_aleatória_cc([E:C|F],P) :([E:C|F],P) :([E:C|F],P) :([E:C|F],P) :----

sucessores(E:C,S),sucessores(E:C,S),sucessores(E:C,S),sucessores(E:C,S),

insereAleatoriamente(S,F,NF),insereAleatoriamente(S,F,NF),insereAleatoriamente(S,F,NF),insereAleatoriamente(S,F,NF),

busca_aleatória_cc(NF,P).busca_aleatória_cc(NF,P).busca_aleatória_cc(NF,P).busca_aleatória_cc(NF,P).



busca_aleatória_ccbusca_aleatória_ccbusca_aleatória_ccbusca_aleatória_cc([E:C|F],P) :([E:C|F],P) :([E:C|F],P) :([E:C|F],P) :----

sucessores(E:C,S),sucessores(E:C,S),sucessores(E:C,S),sucessores(E:C,S),

insereAleatoriamente(S,F,NF),insereAleatoriamente(S,F,NF),insereAleatoriamente(S,F,NF),insereAleatoriamente(S,F,NF),

busca_aleatória_cc(NF,P).busca_aleatória_cc(NF,P).busca_aleatória_cc(NF,P).busca_aleatória_cc(NF,P).

Inserindo aleatoriamente e removendo do início, garantimos uma escolha de folha aleatória


Exemplo 9. Implementação de busca aleatória com ciclos (continuação)Exemplo 9. Implementação de busca aleatória com ciclos (continuação)

sucessoressucessoressucessoressucessores(E:C,S) :(E:C,S) :(E:C,S) :(E:C,S) :----

findallfindallfindallfindall(N:[A|C],ação(A,E,N),S).(N:[A|C],ação(A,E,N),S).(N:[A|C],ação(A,E,N),S).(N:[A|C],ação(A,E,N),S).

insereAleatoriamenteinsereAleatoriamenteinsereAleatoriamenteinsereAleatoriamente(S,F,NF) :(S,F,NF) :(S,F,NF) :(S,F,NF) :----

appendappendappendappend(S,F,R), (S,F,R), (S,F,R), (S,F,R),

lengthlengthlengthlength(R,L), (R,L), (R,L), (R,L),

embaralha(L,R,NF), embaralha(L,R,NF), embaralha(L,R,NF), embaralha(L,R,NF), !!!!....

sucessoressucessoressucessoressucessores(E:C,S) :(E:C,S) :(E:C,S) :(E:C,S) :----

findallfindallfindallfindall(N:[A|C],ação(A,E,N),S).(N:[A|C],ação(A,E,N),S).(N:[A|C],ação(A,E,N),S).(N:[A|C],ação(A,E,N),S).








embaralhaembaralhaembaralhaembaralha(L,F,[X|NF]) :(L,F,[X|NF]) :(L,F,[X|NF]) :(L,F,[X|NF]) :----















Exercício 7. Teste de busca aleatória com ciclosExercício 7. Teste de busca aleatória com ciclos

Certifique-se de que a definição do problema de busca a seguir esteja compilada:

inicial([1,s,s]).inicial([1,s,s]).inicial([1,s,s]).inicial([1,s,s]).

meta([_,l,l]).meta([_,l,l]).meta([_,l,l]).meta([_,l,l]).

ação(ação(ação(ação(entrar1entrar1entrar1entrar1,[,[,[,[2222,Y,Z],[,Y,Z],[,Y,Z],[,Y,Z],[1111,Y,Z]). ,Y,Z]). ,Y,Z]). ,Y,Z]). ação(ação(ação(ação(entrar2entrar2entrar2entrar2,[,[,[,[1111,Y,Z],[,Y,Z],[,Y,Z],[,Y,Z],[2222,Y,Z]).,Y,Z]).,Y,Z]).,Y,Z]).

Certifique-se de que a definição do problema de busca a seguir esteja compilada:

inicial([1,s,s]).inicial([1,s,s]).inicial([1,s,s]).inicial([1,s,s]).

meta([_,l,l]).meta([_,l,l]).meta([_,l,l]).meta([_,l,l]).

ação(ação(ação(ação(entrar1entrar1entrar1entrar1,[,[,[,[2222,Y,Z],[,Y,Z],[,Y,Z],[,Y,Z],[1111,Y,Z]). ,Y,Z]). ,Y,Z]). ,Y,Z]). ação(ação(ação(ação(entrar2entrar2entrar2entrar2,[,[,[,[1111,Y,Z],[,Y,Z],[,Y,Z],[,Y,Z],[2222,Y,Z]).,Y,Z]).,Y,Z]).,Y,Z]).


ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[1,,[1,,[1,,[1,ssss,Z],[1,,Z],[1,,Z],[1,,Z],[1,llll,Z]). ,Z]). ,Z]). ,Z]). ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[2,Y,,[2,Y,,[2,Y,,[2,Y,ssss],[2,Y,],[2,Y,],[2,Y,],[2,Y,llll]).]).]).]).

Em seguida, verifique que o comportamento do predicado busca_aleatória_ccbusca_aleatória_ccbusca_aleatória_ccbusca_aleatória_cc

é realmente aleatório, repetindo a consulta a seguir diversas vezes:

????---- busca_aleatória_ccbusca_aleatória_ccbusca_aleatória_ccbusca_aleatória_cc....

ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[1,,[1,,[1,,[1,ssss,Z],[1,,Z],[1,,Z],[1,,Z],[1,llll,Z]). ,Z]). ,Z]). ,Z]). ação(ação(ação(ação(aspiraraspiraraspiraraspirar,[2,Y,,[2,Y,,[2,Y,,[2,Y,ssss],[2,Y,],[2,Y,],[2,Y,],[2,Y,llll]).]).]).]).

Em seguida, verifique que o comportamento do predicado busca_aleatória_ccbusca_aleatória_ccbusca_aleatória_ccbusca_aleatória_cc

é realmente aleatório, repetindo a consulta a seguir diversas vezes:

????---- busca_aleatória_ccbusca_aleatória_ccbusca_aleatória_ccbusca_aleatória_cc....

Busca aleatória sem ciclos

Exemplo 10. Busca aleatória sem ciclosExemplo 10. Busca aleatória sem ciclos

busca_aleatóriabusca_aleatóriabusca_aleatóriabusca_aleatória ::::----


busca_aleatóriabusca_aleatóriabusca_aleatóriabusca_aleatória([E:[]],([E:[]],([E:[]],([E:[]],[][][][],P),,P),,P),,P),

formatformatformatformat('('('('~nPlano~nPlano~nPlano~nPlano: ~: ~: ~: ~w~n~nw~n~nw~n~nw~n~n',[P]).',[P]).',[P]).',[P]).

busca_aleatóriabusca_aleatóriabusca_aleatóriabusca_aleatória([E:([E:([E:([E:C|_C|_C|_C|_],],],],____,P) :,P) :,P) :,P) :----


busca_aleatóriabusca_aleatóriabusca_aleatóriabusca_aleatória ::::----


busca_aleatóriabusca_aleatóriabusca_aleatóriabusca_aleatória([E:[]],([E:[]],([E:[]],([E:[]],[][][][],P),,P),,P),,P),

formatformatformatformat('('('('~nPlano~nPlano~nPlano~nPlano: ~: ~: ~: ~w~n~nw~n~nw~n~nw~n~n',[P]).',[P]).',[P]).',[P]).

busca_aleatóriabusca_aleatóriabusca_aleatóriabusca_aleatória([E:([E:([E:([E:C|_C|_C|_C|_],],],],____,P) :,P) :,P) :,P) :----





busca_aleatóriabusca_aleatóriabusca_aleatóriabusca_aleatória([E:([E:([E:([E:C|FC|FC|FC|F],],],],VVVV,P) :,P) :,P) :,P) :----

sucessores(E:C,sucessores(E:C,sucessores(E:C,sucessores(E:C,VVVV,S),,S),,S),,S),

insereAleatoriamenteinsereAleatoriamenteinsereAleatoriamenteinsereAleatoriamente(S,F,NF),(S,F,NF),(S,F,NF),(S,F,NF),

unionunionunionunion([E],([E],([E],([E],VVVV,NV),,NV),,NV),,NV),

busca_aleatóriabusca_aleatóriabusca_aleatóriabusca_aleatória(NF,(NF,(NF,(NF,NVNVNVNV,P).,P).,P).,P).



busca_aleatóriabusca_aleatóriabusca_aleatóriabusca_aleatória([E:([E:([E:([E:C|FC|FC|FC|F],],],],VVVV,P) :,P) :,P) :,P) :----

sucessores(E:C,sucessores(E:C,sucessores(E:C,sucessores(E:C,VVVV,S),,S),,S),,S),

insereAleatoriamenteinsereAleatoriamenteinsereAleatoriamenteinsereAleatoriamente(S,F,NF),(S,F,NF),(S,F,NF),(S,F,NF),

unionunionunionunion([E],([E],([E],([E],VVVV,NV),,NV),,NV),,NV),

busca_aleatóriabusca_aleatóriabusca_aleatóriabusca_aleatória(NF,(NF,(NF,(NF,NVNVNVNV,P).,P).,P).,P).

Guardando os estados já visitados, podemos evitar que a busca entre em ciclos


Exemplo 10. Busca aleatória sem ciclos (continuação)Exemplo 10. Busca aleatória sem ciclos (continuação)

sucessoressucessoressucessoressucessores(E:C,(E:C,(E:C,(E:C,VVVV,S) :,S) :,S) :,S) :----

findall(N:[A|C],(ação(A,E,N),findall(N:[A|C],(ação(A,E,N),findall(N:[A|C],(ação(A,E,N),findall(N:[A|C],(ação(A,E,N),notnotnotnot((((membermembermembermember(N,(N,(N,(N,VVVV))),S).))),S).))),S).))),S).





sucessoressucessoressucessoressucessores(E:C,(E:C,(E:C,(E:C,VVVV,S) :,S) :,S) :,S) :----

findall(N:[A|C],(ação(A,E,N),findall(N:[A|C],(ação(A,E,N),findall(N:[A|C],(ação(A,E,N),findall(N:[A|C],(ação(A,E,N),notnotnotnot((((membermembermembermember(N,(N,(N,(N,VVVV))),S).))),S).))),S).))),S).























Exercício 8. Teste de busca aleatória sem ciclosExercício 8. Teste de busca aleatória sem ciclos

Verifique a diferença entre busca aleatória sem e com detecção de ciclos, analisando

as respostas obtidas com as consultas a seguir (repita as buscas várias vezes) :

????---- busca_aleatória_cc.busca_aleatória_cc.busca_aleatória_cc.busca_aleatória_cc.

????---- busca_aleatória.busca_aleatória.busca_aleatória.busca_aleatória.

Verifique a diferença entre busca aleatória sem e com detecção de ciclos, analisando

as respostas obtidas com as consultas a seguir (repita as buscas várias vezes) :

????---- busca_aleatória_cc.busca_aleatória_cc.busca_aleatória_cc.busca_aleatória_cc.

????---- busca_aleatória.busca_aleatória.busca_aleatória.busca_aleatória.


Exercício 9. Diferença entre busca com e sem ciclosExercício 9. Diferença entre busca com e sem ciclos

Qual a diferença fundamental entre as duas estratégias quando o problema de busca

em questão não tem solução como, por exemplo, no caso a seguir?

inicial([1,l,l]).inicial([1,l,l]).inicial([1,l,l]).inicial([1,l,l]).

meta([2,s,s]).meta([2,s,s]).meta([2,s,s]).meta([2,s,s]).

Qual a diferença fundamental entre as duas estratégias quando o problema de busca

em questão não tem solução como, por exemplo, no caso a seguir?

inicial([1,l,l]).inicial([1,l,l]).inicial([1,l,l]).inicial([1,l,l]).

meta([2,s,s]).meta([2,s,s]).meta([2,s,s]).meta([2,s,s]).

Daqui por diante, vamos considerar apenas buscas sem ciclos.

Busca em largura

Na busca em larguraNa busca em largura

a escolha das folhas a serem expandidas é feita de acordo a política FIFO (First-In/First-Out)a escolha das folhas a serem expandidas é feita de acordo a política FIFO (First-In/First-Out)




Solução: [aspirar,entrar2,aspirar]Solução: [aspirar,entrar2,aspirar]Solução: [aspirar,entrar2,aspirar]Solução: [aspirar,entrar2,aspirar]

[2,s,s][2,s,s][2,s,s][2,s,s] [1,l,s][1,l,s][1,l,s][1,l,s][2,s,s][2,s,s][2,s,s][2,s,s]

[2,s,l][2,s,l][2,s,l][2,s,l]


[1,s,l][1,s,l][1,s,l][1,s,l]


[2,s,l][2,s,l][2,s,l][2,s,l]

[1,l,l][1,l,l][1,l,l][1,l,l]


[1,s,l][1,s,l][1,s,l][1,s,l]

[1,l,s][1,l,s][1,l,s][1,l,s]

[2,l,s][2,l,s][2,l,s][2,l,s]


[2,l,s][2,l,s][2,l,s][2,l,s]

[2,l,l][2,l,l][2,l,l][2,l,l]


[2,l,l][2,l,l][2,l,l][2,l,l]

Busca em largura

3333

1111

2222 4444

A busca em larguraA busca em largura

garante encontrar uma solução com número de passos mínimo (i.e., uma solução mais curta)garante encontrar uma solução com número de passos mínimo (i.e., uma solução mais curta)

Não são soluções!


33332222 4444

66665555 99997777 8888

Não são soluções mais curtas!Solução com mínimo de passos

Busca em largura

Exemplo 11. Implementação de busca em larguraExemplo 11. Implementação de busca em largura

busca_largurabusca_largurabusca_largurabusca_largura ::::----


busca_largura([E:[]],[],P),busca_largura([E:[]],[],P),busca_largura([E:[]],[],P),busca_largura([E:[]],[],P),

formatformatformatformat('~nPlano: ~w',[P]).('~nPlano: ~w',[P]).('~nPlano: ~w',[P]).('~nPlano: ~w',[P]).

busca_largurabusca_largurabusca_largurabusca_largura([E:C|_],_,P) :([E:C|_],_,P) :([E:C|_],_,P) :([E:C|_],_,P) :----


busca_largurabusca_largurabusca_largurabusca_largura ::::----


busca_largura([E:[]],[],P),busca_largura([E:[]],[],P),busca_largura([E:[]],[],P),busca_largura([E:[]],[],P),


busca_largurabusca_largurabusca_largurabusca_largura([E:C|_],_,P) :([E:C|_],_,P) :([E:C|_],_,P) :([E:C|_],_,P) :----





busca_largurabusca_largurabusca_largurabusca_largura([E:C|F],V,P) :([E:C|F],V,P) :([E:C|F],V,P) :([E:C|F],V,P) :----

sucessores(E:C,V,S),sucessores(E:C,V,S),sucessores(E:C,V,S),sucessores(E:C,V,S),

insereNoFinalinsereNoFinalinsereNoFinalinsereNoFinal(S,F,NF),(S,F,NF),(S,F,NF),(S,F,NF),

unionunionunionunion([E],V,NV),([E],V,NV),([E],V,NV),([E],V,NV),

busca_largura(NF,NV,P).busca_largura(NF,NV,P).busca_largura(NF,NV,P).busca_largura(NF,NV,P).



busca_largurabusca_largurabusca_largurabusca_largura([E:C|F],V,P) :([E:C|F],V,P) :([E:C|F],V,P) :([E:C|F],V,P) :----


insereNoFinalinsereNoFinalinsereNoFinalinsereNoFinal(S,F,NF),(S,F,NF),(S,F,NF),(S,F,NF),


busca_largura(NF,NV,P).busca_largura(NF,NV,P).busca_largura(NF,NV,P).busca_largura(NF,NV,P).

Inserindo sempre no final e removendo do início, garantimos a política de fila (FIFO)

Busca em largura

Exemplo 11. Implementação de busca em largura (continuação)Exemplo 11. Implementação de busca em largura (continuação)

sucessores(E:C,V,S) :sucessores(E:C,V,S) :sucessores(E:C,V,S) :sucessores(E:C,V,S) :----

findallfindallfindallfindall(N:[A|C],(N:[A|C],(N:[A|C],(N:[A|C],

(ação(A,E,N), (ação(A,E,N), (ação(A,E,N), (ação(A,E,N),

notnotnotnot((((membermembermembermember(N,V))),S).(N,V))),S).(N,V))),S).(N,V))),S).

insereNoFinal(S,F,NF) :insereNoFinal(S,F,NF) :insereNoFinal(S,F,NF) :insereNoFinal(S,F,NF) :----

appendappendappendappend(F,S,NF), (F,S,NF), (F,S,NF), (F,S,NF), !!!!....





insereNoFinal(S,F,NF) :insereNoFinal(S,F,NF) :insereNoFinal(S,F,NF) :insereNoFinal(S,F,NF) :----

appendappendappendappend(F,S,NF), (F,S,NF), (F,S,NF), (F,S,NF), !!!!....


appendappendappendappend(F,S,NF), (F,S,NF), (F,S,NF), (F,S,NF), !!!!....appendappendappendappend(F,S,NF), (F,S,NF), (F,S,NF), (F,S,NF), !!!!....

Exercício 10. Teste de busca em larguraExercício 10. Teste de busca em largura

Resolva o problema do mundo do aspirador usando busca em larguraResolva o problema do mundo do aspirador usando busca em largura

Busca em profundidade

Na busca em profundidadeNa busca em profundidade

a escolha das folhas a serem expandidas é feita de acordo a política LIFO (Last-In/First-Out)a escolha das folhas a serem expandidas é feita de acordo a política LIFO (Last-In/First-Out)



[2,s,s][2,s,s][2,s,s][2,s,s] [1,l,s][1,l,s][1,l,s][1,l,s]


[2,s,s][2,s,s][2,s,s][2,s,s]


Solução: [entrar2,aspirar,entrar1,aspirar]Solução: [entrar2,aspirar,entrar1,aspirar]Solução: [entrar2,aspirar,entrar1,aspirar]Solução: [entrar2,aspirar,entrar1,aspirar]

[2,s,s][2,s,s][2,s,s][2,s,s] [1,l,s][1,l,s][1,l,s][1,l,s][2,s,s][2,s,s][2,s,s][2,s,s]

[2,s,l][2,s,l][2,s,l][2,s,l]


[1,s,l][1,s,l][1,s,l][1,s,l]


[2,s,l][2,s,l][2,s,l][2,s,l]

[1,l,l][1,l,l][1,l,l][1,l,l]


[1,s,l][1,s,l][1,s,l][1,s,l]

[1,l,l][1,l,l][1,l,l][1,l,l]


1111

2222

A busca em profundidadeA busca em profundidade

pode ser mais eficiente em alguns casos, mas não garante encontrar uma solução mais curtapode ser mais eficiente em alguns casos, mas não garante encontrar uma solução mais curta


2222

66663333 7777

888855554444 9999

Solução encontrada Solução mais curta


Exemplo 11. Implementação de busca em profundidadeExemplo 11. Implementação de busca em profundidade

busca_profundidadebusca_profundidadebusca_profundidadebusca_profundidade ::::----


busca_profundidadebusca_profundidadebusca_profundidadebusca_profundidade([E:[]],[],P),([E:[]],[],P),([E:[]],[],P),([E:[]],[],P),

formatformatformatformat('('('('~nPlano~nPlano~nPlano~nPlano: ~w',[P]).: ~w',[P]).: ~w',[P]).: ~w',[P]).

busca_profundidadebusca_profundidadebusca_profundidadebusca_profundidade([E:([E:([E:([E:C|_C|_C|_C|_],_,P) :],_,P) :],_,P) :],_,P) :----


busca_profundidadebusca_profundidadebusca_profundidadebusca_profundidade ::::----


busca_profundidadebusca_profundidadebusca_profundidadebusca_profundidade([E:[]],[],P),([E:[]],[],P),([E:[]],[],P),([E:[]],[],P),

formatformatformatformat('('('('~nPlano~nPlano~nPlano~nPlano: ~w',[P]).: ~w',[P]).: ~w',[P]).: ~w',[P]).

busca_profundidadebusca_profundidadebusca_profundidadebusca_profundidade([E:([E:([E:([E:C|_C|_C|_C|_],_,P) :],_,P) :],_,P) :],_,P) :----





busca_profundidadebusca_profundidadebusca_profundidadebusca_profundidade([E:([E:([E:([E:C|FC|FC|FC|F],V,P) :],V,P) :],V,P) :],V,P) :----


insereNoInícioinsereNoInícioinsereNoInícioinsereNoInício(S,F,NF),(S,F,NF),(S,F,NF),(S,F,NF),


busca_profundidadebusca_profundidadebusca_profundidadebusca_profundidade(NF,NV,P).(NF,NV,P).(NF,NV,P).(NF,NV,P).



busca_profundidadebusca_profundidadebusca_profundidadebusca_profundidade([E:([E:([E:([E:C|FC|FC|FC|F],V,P) :],V,P) :],V,P) :],V,P) :----


insereNoInícioinsereNoInícioinsereNoInícioinsereNoInício(S,F,NF),(S,F,NF),(S,F,NF),(S,F,NF),


busca_profundidadebusca_profundidadebusca_profundidadebusca_profundidade(NF,NV,P).(NF,NV,P).(NF,NV,P).(NF,NV,P).

Restringindo as inserções e remoções ao início, garantimos a política de pilha (LIFO)


Exemplo 11. Implementação de busca em profundidade (continuação)Exemplo 11. Implementação de busca em profundidade (continuação)





insereNoInício(S,F,NF) :insereNoInício(S,F,NF) :insereNoInício(S,F,NF) :insereNoInício(S,F,NF) :----

appendappendappendappend(S,F,NF), (S,F,NF), (S,F,NF), (S,F,NF), !!!!....





insereNoInício(S,F,NF) :insereNoInício(S,F,NF) :insereNoInício(S,F,NF) :insereNoInício(S,F,NF) :----

appendappendappendappend(S,F,NF), (S,F,NF), (S,F,NF), (S,F,NF), !!!!....


appendappendappendappend(S,F,NF), (S,F,NF), (S,F,NF), (S,F,NF), !!!!....appendappendappendappend(S,F,NF), (S,F,NF), (S,F,NF), (S,F,NF), !!!!....

Exercício 11. Teste de busca em profundidadeExercício 11. Teste de busca em profundidade

Resolva o problema do mundo do aspirador usando busca em profundidadeResolva o problema do mundo do aspirador usando busca em profundidade

Algoritmo de busca não-informada generalizado

Exemplo 12. Implementação de busca não-informada generalizadoExemplo 12. Implementação de busca não-informada generalizado

busca_nibusca_nibusca_nibusca_ni((((TTTT):):):):----


busca_ni(busca_ni(busca_ni(busca_ni(TTTT,[E:[]],[],P),,[E:[]],[],P),,[E:[]],[],P),,[E:[]],[],P),

tipo(tipo(tipo(tipo(TTTT,B),,B),,B),,B),

formatformatformatformat('~nBusca: ~w',[B]),('~nBusca: ~w',[B]),('~nBusca: ~w',[B]),('~nBusca: ~w',[B]),


busca_nibusca_nibusca_nibusca_ni((((TTTT):):):):----


busca_ni(busca_ni(busca_ni(busca_ni(TTTT,[E:[]],[],P),,[E:[]],[],P),,[E:[]],[],P),,[E:[]],[],P),

tipo(tipo(tipo(tipo(TTTT,B),,B),,B),,B),

formatformatformatformat('~nBusca: ~w',[B]),('~nBusca: ~w',[B]),('~nBusca: ~w',[B]),('~nBusca: ~w',[B]),




busca_nibusca_nibusca_nibusca_ni(_,[E:C|_],_,P) :(_,[E:C|_],_,P) :(_,[E:C|_],_,P) :(_,[E:C|_],_,P) :----



busca_nibusca_nibusca_nibusca_ni((((TTTT,[E:C|F],V,P) :,[E:C|F],V,P) :,[E:C|F],V,P) :,[E:C|F],V,P) :----


insereinsereinsereinsere((((TTTT,S,F,NF),,S,F,NF),,S,F,NF),,S,F,NF),


busca_ni(busca_ni(busca_ni(busca_ni(TTTT,NF,NV,P).,NF,NV,P).,NF,NV,P).,NF,NV,P).


busca_nibusca_nibusca_nibusca_ni(_,[E:C|_],_,P) :(_,[E:C|_],_,P) :(_,[E:C|_],_,P) :(_,[E:C|_],_,P) :----



busca_nibusca_nibusca_nibusca_ni((((TTTT,[E:C|F],V,P) :,[E:C|F],V,P) :,[E:C|F],V,P) :,[E:C|F],V,P) :----


insereinsereinsereinsere((((TTTT,S,F,NF),,S,F,NF),,S,F,NF),,S,F,NF),


busca_ni(busca_ni(busca_ni(busca_ni(TTTT,NF,NV,P).,NF,NV,P).,NF,NV,P).,NF,NV,P).


Exemplo 12. Implementação de busca não-informada generalizado (continuação)Exemplo 12. Implementação de busca não-informada generalizado (continuação)


findallfindallfindallfindall(N:[A|C], (ação(A,E,N), (N:[A|C], (ação(A,E,N), (N:[A|C], (ação(A,E,N), (N:[A|C], (ação(A,E,N), notnotnotnot((((membermembermembermember(N,V))),S).(N,V))),S).(N,V))),S).(N,V))),S).

insereinsereinsereinsere((((1111,S,F,NF) :,S,F,NF) :,S,F,NF) :,S,F,NF) :---- appendappendappendappend(S,F,R), (S,F,R), (S,F,R), (S,F,R),

lengthlengthlengthlength(R,L), embaralha(L,R,NF), (R,L), embaralha(L,R,NF), (R,L), embaralha(L,R,NF), (R,L), embaralha(L,R,NF), !!!!....

insereinsereinsereinsere((((2222,S,F,NF) :,S,F,NF) :,S,F,NF) :,S,F,NF) :---- appendappendappendappend(F,S,NF), (F,S,NF), (F,S,NF), (F,S,NF), !!!!....

insereinsereinsereinsere((((3333,S,F,NF) :,S,F,NF) :,S,F,NF) :,S,F,NF) :---- appendappendappendappend(S,F,NF), (S,F,NF), (S,F,NF), (S,F,NF), !!!!....


findallfindallfindallfindall(N:[A|C], (ação(A,E,N), (N:[A|C], (ação(A,E,N), (N:[A|C], (ação(A,E,N), (N:[A|C], (ação(A,E,N), notnotnotnot((((membermembermembermember(N,V))),S).(N,V))),S).(N,V))),S).(N,V))),S).

insereinsereinsereinsere((((1111,S,F,NF) :,S,F,NF) :,S,F,NF) :,S,F,NF) :---- appendappendappendappend(S,F,R), (S,F,R), (S,F,R), (S,F,R),

lengthlengthlengthlength(R,L), embaralha(L,R,NF), (R,L), embaralha(L,R,NF), (R,L), embaralha(L,R,NF), (R,L), embaralha(L,R,NF), !!!!....

insereinsereinsereinsere((((2222,S,F,NF) :,S,F,NF) :,S,F,NF) :,S,F,NF) :---- appendappendappendappend(F,S,NF), (F,S,NF), (F,S,NF), (F,S,NF), !!!!....






N N N N is randomis randomis randomis random(L), (L), (L), (L), nth0nth0nth0nth0(N,F,X), (N,F,X), (N,F,X), (N,F,X),

deletedeletedeletedelete(F,X,R), M (F,X,R), M (F,X,R), M (F,X,R), M isisisis LLLL----1, 1, 1, 1,


tipotipotipotipo((((1111,aleatória).,aleatória).,aleatória).,aleatória).

tipotipotipotipo((((2222,largura).,largura).,largura).,largura).

tipotipotipotipo((((3333,profundidade).,profundidade).,profundidade).,profundidade).




N N N N is randomis randomis randomis random(L), (L), (L), (L), nth0nth0nth0nth0(N,F,X), (N,F,X), (N,F,X), (N,F,X),

deletedeletedeletedelete(F,X,R), M (F,X,R), M (F,X,R), M (F,X,R), M isisisis LLLL----1, 1, 1, 1,


tipotipotipotipo((((1111,aleatória).,aleatória).,aleatória).,aleatória).

tipotipotipotipo((((2222,largura).,largura).,largura).,largura).

tipotipotipotipo((((3333,profundidade).,profundidade).,profundidade).,profundidade).


Exercício 12. Teste do algoritmo de busca não-informada generalizadoExercício 12. Teste do algoritmo de busca não-informada generalizado

Resolva o problema do mundo do aspirador usando as consultas a seguir:

????---- busca_ni(1).busca_ni(1).busca_ni(1).busca_ni(1).



Resolva o problema do mundo do aspirador usando as consultas a seguir:




Exercício 13. Mundo do aspirador – versão 2Exercício 13. Mundo do aspirador – versão 2


Exercício 13. Mundo do aspirador – versão 2Exercício 13. Mundo do aspirador – versão 2

Considere uma versão do mundo do aspirador em que há três

salas. Nesta versão, um estado do mundo pode ser representado

por uma estrutura da forma [P,S[P,S[P,S[P,S1111,S,S,S,S2222,S,S,S,S3333]]]], onde PPPP∈{1111, 2222, 3333}

indica a posição do agente, e SSSSiiii∈{ssss, llll} indica a situação da

sala iiii. Com base nesta nova configuração, defina as ações

entrar1entrar1entrar1entrar1, entrar2entrar2entrar2entrar2, entrar3entrar3entrar3entrar3 e aspiraraspiraraspiraraspirar. Em seguida, use o

algoritmo de busca generalizado para encontrar soluções para o

problema com estado inicial [2,s,l,s][2,s,l,s][2,s,l,s][2,s,l,s] e meta [1,l,l,l][1,l,l,l][1,l,l,l][1,l,l,l].

Considere uma versão do mundo do aspirador em que há três

salas. Nesta versão, um estado do mundo pode ser representado

por uma estrutura da forma [P,S[P,S[P,S[P,S1111,S,S,S,S2222,S,S,S,S3333]]]], onde PPPP∈{1111, 2222, 3333}

indica a posição do agente, e SSSSiiii∈{ssss, llll} indica a situação da

sala iiii. Com base nesta nova configuração, defina as ações

entrar1entrar1entrar1entrar1, entrar2entrar2entrar2entrar2, entrar3entrar3entrar3entrar3 e aspiraraspiraraspiraraspirar. Em seguida, use o

algoritmo de busca generalizado para encontrar soluções para o

problema com estado inicial [2,s,l,s][2,s,l,s][2,s,l,s][2,s,l,s] e meta [1,l,l,l][1,l,l,l][1,l,l,l][1,l,l,l].

1 2 3

1 2 3


Exercício 14. Problema do fazendeiroExercício 14. Problema do fazendeiro

Um fazendeiro precisa atravessar um rio levando um lobo, uma ovelha e um repolho.

Para isto, ele dispõe de um pequeno bote com capacidade para levar apenas ele

mesmo e mais uma de suas cargas. Ele poderia cruzar o rio quantas vezes fossem

necessárias para transportar seus pertences; porém, na sua ausência, a ovelha pode

comer o repolho e o lobo pode comer a ovelha. Encontre uma sequência de passos

que possibilite o fazendeiro atravessar o rio sem perder nenhum de seus pertences.

Um fazendeiro precisa atravessar um rio levando um lobo, uma ovelha e um repolho.

Para isto, ele dispõe de um pequeno bote com capacidade para levar apenas ele

mesmo e mais uma de suas cargas. Ele poderia cruzar o rio quantas vezes fossem

necessárias para transportar seus pertences; porém, na sua ausência, a ovelha pode

comer o repolho e o lobo pode comer a ovelha. Encontre uma sequência de passos

que possibilite o fazendeiro atravessar o rio sem perder nenhum de seus pertences.


que possibilite o fazendeiro atravessar o rio sem perder nenhum de seus pertences.que possibilite o fazendeiro atravessar o rio sem perder nenhum de seus pertences.

% estado indica margem do rio em que se encontra cada elemento% estado indica margem do rio em que se encontra cada elemento% estado indica margem do rio em que se encontra cada elemento% estado indica margem do rio em que se encontra cada elemento

inicialinicialinicialinicial([e,e,e,e]).([e,e,e,e]).([e,e,e,e]).([e,e,e,e]).

metametametameta([d,d,d,d]).([d,d,d,d]).([d,d,d,d]).([d,d,d,d]).

açãoaçãoaçãoação((((vaivaivaivai, [e,L,O,R],[d,L,O,R]), [e,L,O,R],[d,L,O,R]), [e,L,O,R],[d,L,O,R]), [e,L,O,R],[d,L,O,R]) ::::---- LLLL\\\\=O, O=O, O=O, O=O, O\\\\=R.=R.=R.=R.

açãoaçãoaçãoação((((levaLobolevaLobolevaLobolevaLobo, [e,e,O,R],[d,d,O,R]), [e,e,O,R],[d,d,O,R]), [e,e,O,R],[d,d,O,R]), [e,e,O,R],[d,d,O,R]) ::::---- OOOO\\\\=R.=R.=R.=R.

açãoaçãoaçãoação((((levaOvelhalevaOvelhalevaOvelhalevaOvelha, [e,L,e,R],[d,L,d,R])., [e,L,e,R],[d,L,d,R])., [e,L,e,R],[d,L,d,R])., [e,L,e,R],[d,L,d,R]).

açãoaçãoaçãoação((((levaRepolholevaRepolholevaRepolholevaRepolho,[e,L,O,e],[d,L,O,d]),[e,L,O,e],[d,L,O,d]),[e,L,O,e],[d,L,O,d]),[e,L,O,e],[d,L,O,d]) ::::---- LLLL\\\\=O.=O.=O.=O.

............

% estado indica margem do rio em que se encontra cada elemento% estado indica margem do rio em que se encontra cada elemento% estado indica margem do rio em que se encontra cada elemento% estado indica margem do rio em que se encontra cada elemento

inicialinicialinicialinicial([e,e,e,e]).([e,e,e,e]).([e,e,e,e]).([e,e,e,e]).

metametametameta([d,d,d,d]).([d,d,d,d]).([d,d,d,d]).([d,d,d,d]).

açãoaçãoaçãoação((((vaivaivaivai, [e,L,O,R],[d,L,O,R]), [e,L,O,R],[d,L,O,R]), [e,L,O,R],[d,L,O,R]), [e,L,O,R],[d,L,O,R]) ::::---- LLLL\\\\=O, O=O, O=O, O=O, O\\\\=R.=R.=R.=R.

açãoaçãoaçãoação((((levaLobolevaLobolevaLobolevaLobo, [e,e,O,R],[d,d,O,R]), [e,e,O,R],[d,d,O,R]), [e,e,O,R],[d,d,O,R]), [e,e,O,R],[d,d,O,R]) ::::---- OOOO\\\\=R.=R.=R.=R.

açãoaçãoaçãoação((((levaOvelhalevaOvelhalevaOvelhalevaOvelha, [e,L,e,R],[d,L,d,R])., [e,L,e,R],[d,L,d,R])., [e,L,e,R],[d,L,d,R])., [e,L,e,R],[d,L,d,R]).

açãoaçãoaçãoação((((levaRepolholevaRepolholevaRepolholevaRepolho,[e,L,O,e],[d,L,O,d]),[e,L,O,e],[d,L,O,d]),[e,L,O,e],[d,L,O,d]),[e,L,O,e],[d,L,O,d]) ::::---- LLLL\\\\=O.=O.=O.=O.

............


Exercício 15. Problema dos jarrosExercício 15. Problema dos jarros

Há dois jarros com capacidades de 3 e 4 litros, respectivamente. Nenhum dos jarros

contém qualquer medida ou escala, de modo que só se pode ter certeza a respeito do

conteúdo exato de um jarro enchendo-o completamente.

Sabendo-se que podemos encherencherencherencher ou esvaziaresvaziaresvaziaresvaziar um jarro, bem como despejardespejardespejardespejar água

de um jarro em outro (sem perda de água), encontre uma sequência de passos cuja

execução possa garantir que o jarro de 4 litros ficará com exatamente 2 litros de água.

Há dois jarros com capacidades de 3 e 4 litros, respectivamente. Nenhum dos jarros

contém qualquer medida ou escala, de modo que só se pode ter certeza a respeito do

conteúdo exato de um jarro enchendo-o completamente.

Sabendo-se que podemos encherencherencherencher ou esvaziaresvaziaresvaziaresvaziar um jarro, bem como despejardespejardespejardespejar água

de um jarro em outro (sem perda de água), encontre uma sequência de passos cuja

execução possa garantir que o jarro de 4 litros ficará com exatamente 2 litros de água.


execução possa garantir que o jarro de 4 litros ficará com exatamente 2 litros de água.execução possa garantir que o jarro de 4 litros ficará com exatamente 2 litros de água.

inicialinicialinicialinicial([0,0]).([0,0]).([0,0]).([0,0]).

metametametameta([_,2]).([_,2]).([_,2]).([_,2]).

açãoaçãoaçãoação((((encher1encher1encher1encher1, [A,B],[3,B]), [A,B],[3,B]), [A,B],[3,B]), [A,B],[3,B]) ::::---- A<3.A<3.A<3.A<3.

açãoaçãoaçãoação((((esvaziar1esvaziar1esvaziar1esvaziar1, [A,B],[0,B]), [A,B],[0,B]), [A,B],[0,B]), [A,B],[0,B]) ::::---- A>0.A>0.A>0.A>0.

açãoaçãoaçãoação((((despejar1em2despejar1em2despejar1em2despejar1em2,[A,B],[0,S]),[A,B],[0,S]),[A,B],[0,S]),[A,B],[0,S]) ::::---- A>0,A>0,A>0,A>0, B<4,B<4,B<4,B<4, SSSS isisisis A+B,A+B,A+B,A+B, S=<4.S=<4.S=<4.S=<4.

açãoaçãoaçãoação((((despejar1em2despejar1em2despejar1em2despejar1em2,[A,B],[R,4]),[A,B],[R,4]),[A,B],[R,4]),[A,B],[R,4]) ::::---- A>0,A>0,A>0,A>0, B<4,B<4,B<4,B<4, SSSS isisisis A+B,A+B,A+B,A+B, S>4,S>4,S>4,S>4, RRRR isisisis SSSS----4.4.4.4.

............

inicialinicialinicialinicial([0,0]).([0,0]).([0,0]).([0,0]).

metametametameta([_,2]).([_,2]).([_,2]).([_,2]).

açãoaçãoaçãoação((((encher1encher1encher1encher1, [A,B],[3,B]), [A,B],[3,B]), [A,B],[3,B]), [A,B],[3,B]) ::::---- A<3.A<3.A<3.A<3.

açãoaçãoaçãoação((((esvaziar1esvaziar1esvaziar1esvaziar1, [A,B],[0,B]), [A,B],[0,B]), [A,B],[0,B]), [A,B],[0,B]) ::::---- A>0.A>0.A>0.A>0.

açãoaçãoaçãoação((((despejar1em2despejar1em2despejar1em2despejar1em2,[A,B],[0,S]),[A,B],[0,S]),[A,B],[0,S]),[A,B],[0,S]) ::::---- A>0,A>0,A>0,A>0, B<4,B<4,B<4,B<4, SSSS isisisis A+B,A+B,A+B,A+B, S=<4.S=<4.S=<4.S=<4.

açãoaçãoaçãoação((((despejar1em2despejar1em2despejar1em2despejar1em2,[A,B],[R,4]),[A,B],[R,4]),[A,B],[R,4]),[A,B],[R,4]) ::::---- A>0,A>0,A>0,A>0, B<4,B<4,B<4,B<4, SSSS isisisis A+B,A+B,A+B,A+B, S>4,S>4,S>4,S>4, RRRR isisisis SSSS----4.4.4.4.

............


Exercício 16. Problema das Torres de HanóiExercício 16. Problema das Torres de Hanói

A seguir temos a especificação do problema das Torres de Hanói, com 3 discos.

Use o algoritmo de busca generalizada para encontrar soluções para este problema e,

em seguida, modifique e teste a especificação para um problema com:

1 disco

2 discos

4 discos

A seguir temos a especificação do problema das Torres de Hanói, com 3 discos.

Use o algoritmo de busca generalizada para encontrar soluções para este problema e,

em seguida, modifique e teste a especificação para um problema com:

1 disco

2 discos

4 discos


4 discos4 discos

inicialinicialinicialinicial([[1,2,3], [], []]).([[1,2,3], [], []]).([[1,2,3], [], []]).([[1,2,3], [], []]).

metametametameta([[], [], [1,2,3]]).([[], [], [1,2,3]]).([[], [], [1,2,3]]).([[], [], [1,2,3]]).

açãoaçãoaçãoação((((m12m12m12m12, [[X|A],B,C], [A,[X|B],C]) :, [[X|A],B,C], [A,[X|B],C]) :, [[X|A],B,C], [A,[X|B],C]) :, [[X|A],B,C], [A,[X|B],C]) :---- B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).

açãoaçãoaçãoação((((m13m13m13m13, [[X|A],B,C], [A,B,[X|C]]) :, [[X|A],B,C], [A,B,[X|C]]) :, [[X|A],B,C], [A,B,[X|C]]) :, [[X|A],B,C], [A,B,[X|C]]) :---- C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).

açãoaçãoaçãoação((((m21m21m21m21, [A,[X|B],C], [[X|A],B,C]) :, [A,[X|B],C], [[X|A],B,C]) :, [A,[X|B],C], [[X|A],B,C]) :, [A,[X|B],C], [[X|A],B,C]) :---- A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).

açãoaçãoaçãoação((((m23m23m23m23, [A,[X|B],C], [A,B,[X|C]]) :, [A,[X|B],C], [A,B,[X|C]]) :, [A,[X|B],C], [A,B,[X|C]]) :, [A,[X|B],C], [A,B,[X|C]]) :---- C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).

açãoaçãoaçãoação((((m31m31m31m31, [A,B,[X|C]], [[X|A],B,C]) :, [A,B,[X|C]], [[X|A],B,C]) :, [A,B,[X|C]], [[X|A],B,C]) :, [A,B,[X|C]], [[X|A],B,C]) :---- A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).

açãoaçãoaçãoação((((m32m32m32m32, [A,B,[X|C]], [A,[X|B],C]) :, [A,B,[X|C]], [A,[X|B],C]) :, [A,B,[X|C]], [A,[X|B],C]) :, [A,B,[X|C]], [A,[X|B],C]) :---- B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).

inicialinicialinicialinicial([[1,2,3], [], []]).([[1,2,3], [], []]).([[1,2,3], [], []]).([[1,2,3], [], []]).

metametametameta([[], [], [1,2,3]]).([[], [], [1,2,3]]).([[], [], [1,2,3]]).([[], [], [1,2,3]]).

açãoaçãoaçãoação((((m12m12m12m12, [[X|A],B,C], [A,[X|B],C]) :, [[X|A],B,C], [A,[X|B],C]) :, [[X|A],B,C], [A,[X|B],C]) :, [[X|A],B,C], [A,[X|B],C]) :---- B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).

açãoaçãoaçãoação((((m13m13m13m13, [[X|A],B,C], [A,B,[X|C]]) :, [[X|A],B,C], [A,B,[X|C]]) :, [[X|A],B,C], [A,B,[X|C]]) :, [[X|A],B,C], [A,B,[X|C]]) :---- C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).

açãoaçãoaçãoação((((m21m21m21m21, [A,[X|B],C], [[X|A],B,C]) :, [A,[X|B],C], [[X|A],B,C]) :, [A,[X|B],C], [[X|A],B,C]) :, [A,[X|B],C], [[X|A],B,C]) :---- A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).

açãoaçãoaçãoação((((m23m23m23m23, [A,[X|B],C], [A,B,[X|C]]) :, [A,[X|B],C], [A,B,[X|C]]) :, [A,[X|B],C], [A,B,[X|C]]) :, [A,[X|B],C], [A,B,[X|C]]) :---- C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).C=[] ; (C=[Y|_], X<Y).

açãoaçãoaçãoação((((m31m31m31m31, [A,B,[X|C]], [[X|A],B,C]) :, [A,B,[X|C]], [[X|A],B,C]) :, [A,B,[X|C]], [[X|A],B,C]) :, [A,B,[X|C]], [[X|A],B,C]) :---- A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).A=[] ; (A=[Y|_], X<Y).

açãoaçãoaçãoação((((m32m32m32m32, [A,B,[X|C]], [A,[X|B],C]) :, [A,B,[X|C]], [A,[X|B],C]) :, [A,B,[X|C]], [A,[X|B],C]) :, [A,B,[X|C]], [A,[X|B],C]) :---- B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).B=[] ; (B=[Y|_], X<Y).

Continua...

Documents

Busca no espaço de estados (parte I) - IME-USPslago/pl-10.pdf · Idéia básica A idéia básica da busca no espaço de estados é considerar a existência de um agente cujas ações