Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.
left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Prévia do material em texto

DECSI - UFOP, CSI 457
Notas de Aula
Busca
Inteligência Arti�cial
Prof. Dr. Talles Henrique de Medeiros
Talles Medeiros
2020/1
Contents
Contents
1 Busca 3
1.1 Formulando o Problema de Busca . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Exemplos de Problemas de Busca . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Exemplo de viagem por Romênia . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Exemplo de Quebra Cabeça de 8 Peças . . . . . . . . . . . . . . . . . . 5
1.3 O que é um Espaço de Estados? . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Grafo de Espaço de Estados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Árvores de Busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.1 Procurando numa Árvore de Busca . . . . . . . . . . . . . . . . . . . . 8
1.6 A Busca em Profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6.1 As Propriedades da Busca em Profundidade . . . . . . . . . . . . . . . 10
1.7 A Busca em Largura (ou Amplitude) . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.1 As Propriedades da Busca em Largura . . . . . . . . . . . . . . . . . . 11
1.8 Busca em Profundidade Limitada . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.9 Busca de Custo Uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.9.1 As Propriedades da Busca de Custo Uniforme . . . . . . . . . . . . . . 14
1.10 Busca Bidirecional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.11 Busca de Aprofundamento Iterativo . . . . . . . . . . . . . . . . . . . . . . . . 15
1.12 Comparação entre as Estratégias de Busca . . . . . . . . . . . . . . . . . . . . 16
1.13 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.14 Notas Bibliográ�cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.15 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2
1 Busca
1 Busca
Os agentes inteligentes devem maximizar a sua medida de desempenho. Adotar um objetivo
a ser satisfeito ajudam a organizar o comportamento, restringindo as ações que ele precisa
considerar. A formulação de objetivos, baseada no estado atual e na medida de desempenho
é o primeiro passo para a resolução do problema. A formulação do problema corresponde
ao processo de decidir que ações e estados devem ser considerados. Para isso é preciso ter
informação sobre o ambiente para que o agente saiba quais as melhores ações possíveis é a
melhor. Veremos alguns algoritmos de buscam sem informação, que embora possam resolver
qualquer problema solucionável, nenhum deles pode fazê-lo de forma e�ciente. Já os algoritmos
de busca informada podem ter sucesso a partir de alguma orientação sobre a busca por uma
solução.
Os problemas são formulados por descrições matemáticas abstratas, que dão uma descrição
simpli�cada do mundo real. O processo de remover detalhes do problema real é dito abstração.
A habilidade de darmos um nível de abstração adequado o mundo real, permite-nos tratar
problemas de grande complexidade a ponto de conseguirmos encontrar soluções para nossos
modelos.
O processo de procura por uma sequência de ações que alcançam o objetivo é chamado de
busca. Um algoritmo de busca recebe uma formulação de um problema como entrada e retorna
uma solução na forma de uma sequência de ações.
1.1 Formulando o Problema de Busca
Um problema de busca consiste de um espaço de busca, contemplando a representação dos
possíveis estados do problema. Uma função sucessora (com ações e custos), indicando os estados
resultantes após uma ação. Um estado inicial e um estado alvo. Formalmente podemos de�nir
os componentes do problema:
• Estado Inicial: O estado inicial que o agente começa o problema.
• Ações: Uma descrição das ações disponíveis para o agente em um dado estado particular
B . Uma rotina AÇÕES(B) devolve um conjunto de ações que podem ser executadas em B .
• Modelo de Transição: Uma rotina RESULTADO(B, 0) devolve o estado que resulta exe-
cutar uma ação 0 em um estado B .
• Teste de Objetivo: Determina se um estado é um estado objetivo. Às vezes o teste é um
estado explícito, que precisa ser veri�cado. Outras vezes é um estado implícito, como
3
1 Busca
Figure 1.1: Problemas de Busca envolvem planejamento de ações a serem executadas para se
atingir um objetivo, de forma a maximizar o desempenho do agente.
o “xeque-mate” no xadrez, que veri�ca se nesse estado o rei está em uma condição de
ataque e não consegue escapar.
• Custo de Caminho: Uma função que atribui um custo ao caminho. A função de custo
deve re�etir a própria medida de desempenho. O custo do passo para executar uma ação
0 sobre o estado B e alcançar o estado B ′ é de�nido como 2 (B, 0, B ′)
A solução é uma sequência de ações que transformam o estado inicial para o estado objetivo.
A solução ótima tem o menor custo de caminho entre todas as soluções.
1.2 Exemplos de Problemas de Busca
1.2.1 Exemplo de viagem por Romênia
• Estados: O estado é dado pela cidade em que se encontra no momento.
• Estado Inicial: A cidade de origem da viagem.
• Ações: Viajar de uma cidade para outra vizinha.
• Modelo de Transição: As ações levem o viajante de uma cidade à outra por meio de
uma ação.
• Teste de Objetivo: Veri�car se o estado é a cidade de destino.
• Custo de Caminho: Cada passo tem o custo referente à distância física da estrada entre
as cidades vizinhas. Logo o custo do caminho é a soma dos custos dos passos de cada
ação executada até o estado atual.
4
1 Busca
Figure 1.2: Agente planejando ação.
Figure 1.3: Problemas de Busca são representados por modelos (abstrações) do mundo real, onde
alguns detalhes são removidos dessa representação.
1.2.2 Exemplo de �ebra Cabeça de 8 Peças
Este exemplo consiste em um tabuleiro 3x3 de 8 peças numeradas e um quadrado vazio. A peça
adjacente ao quadrado vazio pode ser deslizada para esse espaço. A formulação pode ser dada
por:
• Estados: Uma descrição de estado especí�ca uma con�guração do tabuleiro com a posição
de cada peça.
• Estado Inicial: Uma con�guração do tabuleiro qualquer.
• Ações: Mover o espaço vazio para cima, para baixo, para esquerda e para direita. Algumas
ações podem estar restritas dependendo de onde o espaço vazio estiver localizado.
• Modelo de Transição: Dado um estado e uma ação, ele devolve o estado resultante, ou
seja, a troca das peças envolvidas na ação.
• Teste de Objetivo: Veri�ca se as peças estão todas nas posições desejadas para o estado
objetivo.
• Custo de Caminho: Cada passo tem custo unitário. O custo do caminho é o número de
passos do caminho.
5
1 Busca
Figure 1.4: Viajando pela Romênia usando uma mapa com cidades e estradas que ligam estas
cidades.
Figure 1.5: Um exemplo típico de um quebra cabeça de 8 peças com seu estado inicial e um
estado objetivo.
Este quebra-cabeça de blocos deslizantes de 8 peças possui 9!/2 = 181.440 estados acessíveis.
O quebra-cabeça de 15 peças (4x4) possui 15!/2 = 1.307.674.368.000 estados, que podem ser
resolvidos facilmente por algum algoritmo de busca. Porém um quebra-cabeça de 25 peças (5x5)
tem cerca de 25!/2 = 1025 estados e já demandam muitas horas para serem resolvidos.
1.3 O que é um Espaço de Estados?
O estado do mundo inclui cada detalhe do ambiente. Em geral representado por estruturas,
onde cada componente denota um atributo do estado representado.
6
1 Busca
Figure 1.6: O ambiente do Pacman com vários pontos de comida, alguns fantasmas e as possibil-
idades de locais que o agente pode se mover por todo o ambiente.
1.1: ESPAÇO DE ESTADOS
Um espaço de estados pega somente os detalhes necessários para o planejamento (ab-
stração).
• Problema: Pacman deve comer todos os pontos.
– Estados: {.(x,y), pontos booleanos }.
7
1 Busca
– Ações: mover para cima, baixo, esquerda e direita.
– Sucessor (Modelo de Transição): atualiza localização e possibilidades de pontos
booleanos.
– Teste de objetivo:pontos todos em FALSE.
Como exemplo, veja um cenário de um jogo de Pacman com as seguintes con�gurações:
• Posições do Agente: 120.
• Contagem de Comidas (pontos): 30
• Posições do Fantasma: 12
• Ação do Agente: mover-se para cima, baixo, esquerda e direita.
O resultado é um número total de estados de�nido por: 120- (230)- (122)-4. O número de
estados por caminhamento: 120. O número de estados para todas comidas (pontos): 120- (230).
1.4 Grafo de Espaço de Estados
O grafo do espaço de estados é uma representação matemática do problema de busca onde os nós
são representações (abstrações) do mundo. Os ARCOS representam as funções sucessoras (ações)
que implementam a transição entre os estados. O TESTE DE OBJETIVO é uma con�guração
dos nós objetivo, podendo ser somente um estado.
No grafo do espaço de estados, cada estado só ocorre uma única vez!
Raramente podemos construir este grafo completo na memória, pois é muito grande. Porém é
uma ideia útil!
1.5 Árvores de Busca
Uma árvore de busca é uma estrutura do tipo ”Se-Então-Senão” com planos e suas respostas. O
estado inicial é o nó raiz. Os nós �lhos são os estados sucessores. Os nós exibem os estados,
mas correspondem a planos que alcançam esses estados. Para a grande maioria dos problemas
de busca, não podemos nunca construir a árvores de busca completa.
1.5.1 Procurando numa Árvore de Busca
O procedimento de busca em uma árvore parte da expansão de nós com seus potenciais planos
de ação. A �gura 1.8 apresenta 3 nós como possíveis ações a serem executadas. O gerenciamento
de uma lista de nós expansíveis (”borda” ) é responsável manter os planos de ação parciais em
consideração. Tenta-se expandir o menor número possível de nós quanto for possível.
8
1 Busca
Figure 1.7: Grafo de Estados para um ambiente do Pacman, exibindo os estados e seus sucessores
conectados por meio de arcos indicativos das transições após uma ação.
Figure 1.8: Procurando uma solução na árvore de busca representativa do problema do mapa da
Romênia.
O algoritmo básico de busca deve ser executado usando uma estratégia própria para visitação
de nós até encontrar uma solução ou falhar, partindo de um nó inicial.
1.2: BUSCA GERAL EM ÁRVORE
Importantes ideias para este algoritmo básico:
• Lista de Nós de Borda
• Expansão
• Estratégia de Expansão
9
1 Busca
Figure 1.9: Algoritmo Geral de Busca em Árvore, recebendo a estrutura do problema formulado
e o tipo de estratégia de busca e retornando uma solução ou falha.
1.6 A Busca em Profundidade
A estratégia de busca em profundidade, do inglês (Deep First Search - DFS), é baseada na expansão
dos nós mais profundos da árvore. Para isso a borda é gerenciada como uma estrutura do tipo
LIFO (Last in - First out). A busca prossegue até o nó mais profundo da árvore, onde não há
mais sucessores.
Figure 1.10: Grafo com Nós para Visitação, sendo S o nó inicial e G o nó objetivo.
1.6.1 As Propriedades da Busca em Profundidade
• Completa: Garantia de encontrar uma solução se existe.
• Ótima: Garantia de encontrar o caminho de custo mínimo.
• Complexidade de Tempo:
• Complexidade de Espaço:
• Grá�co da Busca na Árvore
– 1 é o fator de rami�cação
– < é a profundidade máxima
– soluções em várias profundidades
• Número de nós em toda a árvore: 1 + 1 + 12 + · + 1< = $ (1<)
10
1 Busca
Figure 1.11: Grá�co da exploração em profundidade de uma árvore de busca.
A �gura 1.11 mostra que a exploração dos nós da árvores durante a busca em profundidade
começa pelo nós mais à esquerda e vai aprofundando até não encontrar mais um sucessor. Só
então os próximos caminhos serão analisados pelo algoritmo.
• Quais nós expandir?
– A partir do lado esquerdo na árvore
– Poderia processar a árvore completa
– Se< é �nito, leva um tempo $ (1<)
• Quanto espaço a borda ocupa? Somente possui nós irmãos no caminho para a rais,
então ocupa $ (1<).
• É Completa? A profundidade< poderia ser in�nita, então é completa se prevenirmos
os ciclos.
• É Ótima? A busca não é ótima, ela encontra a solução mais à esquerda, independente-
mente da profundidade ou do custo.
1.7 A Busca em Largura (ou Amplitude)
A estratégia de busca em largura, do inglês Breadth First Search - BFS, é baseada na estratégia de
expansão do nó mais raso primeiro, de modo a analisar toda uma camada para somente depois
fazer a expansão dos nós da camada seguinte. A implementação dessa estratégia adota uma
estrutura do tipo FIFO (First-in First-out) para a Borda.
Usando o mesmo grafo da �gura 1.10 é possível representar visualmente a ordem de visitação
do procedimento de busca na �gura 1.13.
1.7.1 As Propriedades da Busca em Largura
• Quais nós expandir?
11
1 Busca
Figure 1.12: A árvore tem destacado em vermelho os caminhos que foram visitados pelo agentes
na busca do nó objetivo G. Como esperado, usando a busca em profundidade de�ne
um lado da árvore e explora até não encontrar mais sucessores à partir do primeiro
nó visitado à partir do início.
Figure 1.13: Visualizando o processo de visitação dos nós em uma busca em largura, percorrendo
todo um nível da árvore para somente depois visitar o nível inferior.
– Processa todos os nós acima da solução mais rasa
– Seja a profundidade de solução mais rasa, B
– A busca consome um tempo $ (1B)
• Quanto espaço a lista de expansíveis ocupa? Aproximadamente até a camada da
solução da rasa, então $ (1B).
• É Completa? Sim, se a camada B for �nita.
• É Ótima? A busca é ótima se e somente se os custos forem todos iguais.
1.8 Busca em Profundidade Limitada
A busca em profundidade limitada insere um limitador ; para que a busca não se perca em espaço
de estados in�nitos, de forma que o método trata os estados sucessores da profundidade ; como
12
1 Busca
Figure 1.14: A busca em largura analisa toda uma camada para depois ir para a camada imedi-
atamente abaixo. Encontrando uma solução na camada menos profunda da árvore
de busca.
inexistentes. Isso resolve o problema de busca in�nita, porém introduz uma incompleteza na
busca quando ; < 3 , ou seja, a profundidade da solução mais rasa é maior que o limite de�nido.
Na prática, infelizmente, nem sempre conhecemos um bom limite de profundidade antes de
resolvermos o problema. A busca pode ser �nalizada por duas condições: falha indicando
nenhuma solução; corte indicando nenhuma solução dentro do limite de profundidade.
1.9 Busca de Custo Uniforme
A busca de Custo Uniforme, do inglês (Uniform Cost Search - UCS), é baseada em uma estratégia
de expansão de nós por meio do custo do próximo nó a ser visitado, optando pelo nó de menor
custo.
A lista de caminhos expansíveis é uma lista com prioridade de custo cumulativa.
Figure 1.15: Exemplo de um grafo com custos para a transição entre os estados. Estes custos
permitiram ao algoritmo adotar uma estratégia que custo do caminho até o momento
para decidir qual caminho expandir.
Os métodos de busca em profundidade e largura encontram um caminho em termo de número
13
1 Busca
de ações, mas não o caminho de custo mínimo. O método de custo uniforme é um método
similar aos anteriores, mas que encontra o caminho de custo mínimo.
Figure 1.16: Contorno com os custos acumulados dos caminhos já analisados pelo método.
1.9.1 As Propriedades da Busca de Custo Uniforme
• Quais nós expandir?
– Processa todos os nós com custo inferior à solução de custo mínimo.
– Se a solução custa�∗ e os arcos custam pelo menos n , então a ”profundidade efetiva”
é aproximadamente
�∗
n
.
– Consome um tempo $ (1 (�∗/n) )
• Quanto espaço a lista de expansíveis ocupa? Aproximadamente até a camada da
solução, então $ (1 (�∗/n) ).
• É Completa? Assumindo que a melhor solução tem um custo �nito e um arco de custo
mínimo positivo, então ela é completa.
• É Ótima? Sim!
Figure 1.17: Propriedades da busca de custo mínimo ser completa e ótima.
14
1 Busca
A busca de Custo Uniforme explora os contornos de custo crescente, podendo ser uma busca
completa e ótima. O lado negativo é que a busca explora opções em cada direção. Nenhuma
informaçãosobre a localização do objetivo é usada.
1.10 Busca Bidirecional
A ideia desta busca é executar duas buscas simultâneas, sendo uma a partir do estado inicial
e outra a partir do estado objetivo, esperando que as duas buscam se encontrem no meio do
caminho. A motivação é que a complexidade de tempo 13/2 +13/2 é menor que 13 . Por exemplo,
sendo 1 = 2 e 3 = 6, tem-se:
13/2 + 13/2 < 13
26/2 + 26/2 < 26
8 + 8 < 32
(1.1)
A implementação desta estratégia de busca substituto teste de objetivo por uma veri�cação das
bordas das duas buscas, que cruzando-se, indica que uma solução foi encontrada.
A redução da complexidade de tempo da busca bidirecional é bastante atraente, mas a realização
da busca inversa nem sempre é algo trivial. Quando o estado objetivo é um estado explicitamente
citado há opção de mapear a busca para obter os estados predecessores a partir do objetivo
explicitamente citado. Porém há casos em que o estado objetivo é uma condição mais abstrata,
sem uma con�guração explicitamente de�nida. Neste caso, a busca bidirecional é mais complexa
de ser usada.
1.11 Busca de Aprofundamento Iterativo
Um estratégia usada com frequência em combinação com a busca em profundidade em árvore,
encontrando o melhor limite de profundidade. Do inglês, Iterative Deepening Search - IDS, o
limite é gradualmente incrementado até encontrar o objetivo, no limite 3 que contém a solução.
Basicamente, a busca de aprofundamento iterativo executa a estratégia em profundidade limitada
várias vezes, com os limites crescentes. Apesar de parecer um desperdício gerar os estados
várias vezes, a grande maioria dos nós estará sempre no nível mais profundo, se a árvore tiver
o mesmo (ou quase igual) fator de rami�cação. Pode-se, então, determinar o número de nós
gerados por:
# (��() = 31 + (3 − 1)12 + (3 − 2)13 + · + (1)13 = $ (13 ). (1.2)
Esta complexidade é exatamente a mesma da busca em profundidade. O exemplo a seguir mostra
a diferença no número de estados gerados, porém assintoticamente, a tendência é que o custo
extra gerado pelo IDS seja baixo para árvores cada vez maiores. Se 1 = 10 e 3 = 5, então:
15
1 Busca
# (��() = 50 + 400 + 3000 + 20000 + 100000 = 123450
# (��() = 10 + 100 + 1000 + 10000 + 100000 = 111100
(1.3)
1.12 Comparação entre as Estratégias de Busca
Os quatro critérios de�nidos para avaliação das estratégias de busca em árvore permitem uma
comparação.
Figure 1.18: A tabela permite que sejam comparadas as estratégias de busca quando avaliadas
as condições descritas em cada sessão descritiva da estratégia.
As anotações sobrescritas são: 0 completa se b é �nito; 1 completa se o custo do passo é ≥∈ para
∈ positivo; 2 ótima se os custos dos passos são todos idênticos; 3 se ambos os sentidos utilizam
busca em largura.
1.13 Resumo
• Todos esses algoritmos são os mesmos exceto pela estratégia de expansão da lista de
caminhos expansíveis.
– Conceitualmente, todas as listas são �las de prioridades (coleções de nós com priori-
dades anexadas).
– Praticamente, para busca em profundidade e largura, pode-se evitar a sobrecarga
log= de uma �la de prioridade real, usando pilhas e �las.
– Pode até codi�car uma implementação que usa um objeto de en�leiramento variável.
• As buscas operam sobre modelos do mundo
– O agente não testa todos os planos do mundo real!
– O planejamento é TUDO em uma simulação.
– Sua busca é somente tão boa quanto o seu modelo!
16
1 Busca
Figure 1.19: Um modelo é uma abstração da realidade. Nele temos somente parte do que nos
interessa e/ou somos capazes de controlar. Logo, seu modelo será sempre uma
representação limitada do problema real.
1.14 Notas Bibliográficas
Consulte o livro "Inteligência Arti�cial" de Stuart Russel e Peter Norvig, capítulo 03 (até 3.4
inclusive) para complementar sua leitura desta nota de aula. Pois ela foi baseada nesse capítulo.
1.15 Exercícios
1. Desenhe um grafo representado o espaço de estados do mundo do robô aspirador de pó,
contendo 3 salas linha [A - B - C]. Nesse grafo cada nó é um estado do mundo e cada arco
será uma transição entre dois estados. Os arcos devem ser direcionados. Considere que
cada estado é representado por uma estrutura na forma [-,., /,, ], onde - ∈ �, �,�
indica a sala do robô, . ∈ 0, 1 indica se a sala está suja, / ∈ 0, 1 indica se a sala está suja e
, ∈ 0, 1 indica se a sala está suja.
2. O problema dos Jarros consiste em 2 jarros com capacidades de 3 e 4L, respectivamente.
Nenhum dos jarros contém qualquer medida ou escala, de modo que só se pode saber o
conteúdo exato quando eles estão cheios. Sabendo que podemos encher ou esvaziar um
jarro, bem como transferir a água de um jarro para outro, determine uma sequência de
passos que deixe o jarro de 4L com exatamente 2L. OBS.: Represente os estados desse
problema com um par [-,. ], onde - ∈ 0, 1, 2, 3 representa o conteúdo do jarro 1 e
. ∈ 0, 1, 2, 3, 4 representa o conteúdo do jarro 2. O estado inicial é B> = [0, 0] e o objetivo
é � = [,2].
3. O problema do fazendeiro consiste no seguinte enunciado: um fazendeiro encontra-se
na margem esquerda de um rio, levando consigo um lobo, um repolho e uma ovelha. O
fazendeiro precisa chegar até a outra margem do rio com toda sua carga intacta. Para isso
ele possui um barco com capacidade para levar ele e mais uma carga junto. O problema é
que nunca podem ser deixados à sós o lobo e a ovelha, e a ovelha e o repolho em nenhuma
das margens. Determine uma sequência de passo para resolver este problema.
17
	Busca
	Formulando o Problema de Busca
	Exemplos de Problemas de Busca
	Exemplo de viagem por Romênia
	Exemplo de Quebra Cabeça de 8 Peças
	O que é um Espaço de Estados?
	Grafo de Espaço de Estados
	Árvores de Busca
	Procurando numa Árvore de Busca
	A Busca em Profundidade
	As Propriedades da Busca em Profundidade
	A Busca em Largura (ou Amplitude)
	As Propriedades da Busca em Largura
	Busca em Profundidade Limitada
	Busca de Custo Uniforme
	As Propriedades da Busca de Custo Uniforme
	Busca Bidirecional
	Busca de Aprofundamento Iterativo
	Comparação entre as Estratégias de Busca
	Resumo
	Notas Bibliográficas
	Exercícios

Mais conteúdos dessa disciplina