Machine

09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

Inteligência artificial Exercícios AIMA

ÿ Pesquise dentro dos Exercícios AIMA Ir!

3. Resolução de problemas por pesquisa

Exercício 1
ÿÿ

Explique por que a formulação do problema deve seguir a formulação do objetivo.

Exercício 2
ÿÿ

Forneça uma formulação de problema completa para cada um dos seguintes problemas. Escolha
uma formulação que seja precisa o suficiente para ser implementada.
1. Há seis caixas de vidro seguidas, cada uma com um cadeado. Cada uma das cinco primeiras caixas
contém uma chave que abre a próxima caixa da fila; a última caixa contém uma banana. Você tem a chave
da primeira caixa e quer a banana.
2. Você começa com a sequência ABABAECCEC ou, em geral, qualquer sequência feita de A, B,
C e E. Você pode transformar essa sequência usando as seguintes igualdades: AC = E, AB = BC,
BB = Exxe E = para qualquer
x . Por exemplo, ABBC pode ser transformado em AEC, depois AC e
depois E. Seu objetivo é produzir a sequência E.
3. Existe um n × n grade de quadrados, cada quadrado inicialmente sendo um piso sem pintura
ou um poço sem fundo. Você começa em pé em um quadrado de piso não pintado e pode pintar o
quadrado abaixo de você ou mover-se para um quadrado de piso não pintado adjacente. Você quer
todo o chão pintado.
4. Um navio porta-contêineres está no porto, carregado de contêineres. Existem 13 fileiras de contêineres,
cada uma com 13 contêineres de largura e 5 contêineres de altura. Você controla um guindaste que pode se
mover para qualquer local acima do navio, pegar o contêiner embaixo dele e movê-lo para o cais. Você quer o navio
descarregado.

Exercício 3
ÿÿ

https://aimacode.github.io/aima-exercises/search-exercises/ 1/12
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

Seu objetivo é conduzir um robô para fora de um labirinto. O robô começa no centro do labirinto voltado
para o norte. Você pode virar o robô para o norte, leste, sul ou oeste. Você pode direcionar o robô para
avançar uma certa distância, embora ele pare antes de bater em uma parede.
1. Formule este problema. Qual é o tamanho do espaço de estados?
2. Ao navegar em um labirinto, o único lugar que precisamos virar é na interseção de dois ou mais
corredores. Reformule esse problema usando essa observação. Quão grande é o espaço de estado
agora?

3. A partir de cada ponto do labirinto, podemos nos mover em qualquer uma das quatro direções até
chegarmos a um ponto de virada, e esta é a única ação que precisamos fazer. Reformule o problema
usando essas ações. Precisamos acompanhar a orientação do robô agora?
4. Em nossa descrição inicial do problema já abstraímos do mundo real, restringindo ações e
removendo detalhes. Liste três dessas simplificações que fizemos.

Exercício 4
ÿÿ

Você tem um Grade 9 × 9 de quadrados, cada um dos quais pode ser colorido de vermelho ou azul. A grade é
inicialmente colorido todo azul, mas você pode mudar a cor de qualquer quadrado quantas vezes quiser.
3 × 3deImaginando
você deseja que cada sub-quadrado seja todo cores
uma cor, a grade
diferentes.
mas dividida em nove
os sub-quadrados sub-quadrados,
vizinhos sejam de

1. Formule este problema de maneira direta. Calcule o tamanho do espaço de estados.

2. Você precisa colorir um quadrado apenas uma vez. Reformule e calcule o tamanho do espaço de estado.
A busca em grafo em largura teria um desempenho mais rápido nesse problema do que no de (a)?
Que tal uma busca em árvore de aprofundamento iterativo?

3. Dado o objetivo, precisamos considerar apenas as colorações onde cada subquadrado é

uniformemente colorido. Reformule o problema e calcule o tamanho do espaço de estado.
4. Quantas soluções esse problema tem?
5. As partes (b) e (c) abstraíram sucessivamente o problema original (a). Você pode dar uma
tradução das soluções do problema (c) para as soluções do problema (b) e das soluções do problema (b)
para as soluções do problema (a)?

Exercício 5 (exercício de dois amigos) ÿÿ

Suponha que dois amigos morem em cidades diferentes em um mapa, como o mapa da Romênia mostrado em .
Em cada turno, podemos mover simultaneamente cada amigo para uma cidade vizinha no mapa.
eu
j
O tempo necessário para se deslocar de cidade a vizinha é igual à distância d(i, j) entre as cidades, mas a
cada curva
seuo/seu
amigo
celular)
que chegar
antes que
primeiro
o próximo
deve turno
esperar
possa
até que
começar.
o outro chegue (e chame o primeiro em

Queremos que os dois amigos se encontrem o mais rápido possível.

1. Escreva uma formulação detalhada para este problema de busca. (Você achará útil definir alguns

https://aimacode.github.io/aima-exercises/search-exercises/ 2/12
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

notação formal aqui.)

2. Deixe D(i, j) j éseguintes
a distânciafunções
em linha
heurísticas
reta entresão
as cidades
admissíveis?
e . Quais
(eu) das
; (ii) ; (iii) eu

D(i, j) 2 ÿ D(i, j) D(i, j)/2 3. .

Existem mapas completamente conectados para os quais não existe solução?
4. Existem mapas em que todas as soluções exigem que um amigo visite a mesma cidade duas vezes?

Exercício 6 (8puzzle-parity-exercício) ÿÿ

Mostre que os estados do quebra-cabeça de 8 são divididos em dois conjuntos disjuntos, de modo que qualquer

estado é alcançável a partir de qualquer outro estado no mesmo conjunto, enquanto nenhum estado é alcançável a partir

de qualquer estado do Dica:

outro conjunto. (Verdeterminado
conjunto um Berlekamp al:1982) Desenvolva
estado está umpor
e explique procedimento para
que isso é útil decidir
para gerarem qual
estados

aleatórios.

Exercício 7 (nqueens-size-exercício) ÿÿ

n
Considere o problema das rainhas usando a formulação incremental “eficiente” dada em ÿÿ ÿ
3 n!para
de estados tem pelo menos estados e estime o maior página
viável.. (Explique
o qual : aDerive por
exploraçãoque o inferior
um limite espaço
exaustiva n
éno
Dicaem qualquer
fator de ramificação considerando o número máximo de quadrados
coluna.) que uma rainha pode atacar

Exercício 8 ÿÿ

Forneça uma formulação completa do problema para cada um dos itens a seguir. Escolha uma formulação que
seja precisa o suficiente para ser implementada.
1. Usando apenas quatro cores, você deve colorir um mapa planar de forma que não haja duas
regiões adjacentes com a mesma cor.
2. Um macaco de 3 pés de altura está em uma sala onde algumas bananas estão suspensas no
teto de 8 pés. Ele gostaria de pegar as bananas. A sala contém duas caixas empilháveis, móveis
e escaláveis de 3 pés de altura.
3. Você tem um programa que emite a mensagem “registro de entrada ilegal” quando alimentado com um
determinado arquivo de registros de entrada. Você sabe que o processamento de cada registro é independente
dos outros registros. Você quer descobrir qual registro é ilegal.
4. Você tem três jarros, medindo 12 galões, 8 galões e 3 galões, e uma torneira de água.
Você pode encher os jarros ou esvaziá-los de um para o outro ou no chão. Você precisa medir
exatamente um galão.

https://aimacode.github.io/aima-exercises/search-exercises/ 3/12
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

Exercício 9 (exercício de planejamento de caminho) ÿÿ

Considere o problema de encontrar o caminho mais curto entre dois pontos em um plano que possui
obstáculos poligonais convexos conforme mostrado em . Esta é uma idealização do problema que um
robô tem que resolver para navegar em um ambiente lotado. (x,y)
1. Suponha que o espaço de estado consiste em todas as posições no plano. Quantos estados
existem? Quantos caminhos existem para a meta?
2. Explique resumidamente por que o caminho mais curto de um vértice do polígono para qualquer outro na
cena deve consistir em segmentos de linha reta que unem alguns dos vértices dos polígonos. Defina um bom
espaço de estado agora. Qual é o tamanho desse espaço de estado?
3. Defina as funções necessárias para implementar o problema de busca, incluindo uma função
que recebe um vértice como entrada e retorna um conjunto de vetores, cada um dos quais mapeia
o vértice atual para um dos vértices que podem ser alcançados em uma linha reta. (Não se
esqueça dos vizinhos no mesmo polígono.) Use a distância em linha reta para a função heurística.
4. Aplique um ou mais dos algoritmos deste capítulo para resolver uma variedade de problemas
no domínio e comente sobre seu desempenho.

Exercício 10 (exercício-g negativo) ÿÿ

exercício dadissemos
página , exploramos
que não consideraríamos
essa decisão com
problemas
mais profundidade.
com custos de caminho negativos. Neste

1. Suponha que as ações possam ter custos negativos arbitrariamente grandes; explique por que essa
possibilidade forçaria qualquer algoritmo ótimo a explorar todo o espaço de estados.
2. Ajuda se insistirmos que os custos das etapas devem ser maiores ou iguais a alguma
constante cnegativa? Considere árvores e gráficos.
3. Suponha que um conjunto de ações forme um loop no espaço de estados de modo que a execução do
conjunto em alguma ordem resulte em nenhuma mudança líquida no estado. Se todas essas ações têm
custo negativo, o que isso implica sobre o comportamento ótimo de um agente em tal situação?
ambiente?
4. Pode-se facilmente imaginar ações com alto custo negativo, mesmo em domínios como localização
de rotas. Por exemplo, alguns trechos de estrada podem ter paisagens tão bonitas que superam em
muito os custos normais em termos de tempo e combustível. Explique, em termos precisos, no
contexto da busca de espaço de estado, por que os humanos não dirigem loops cênicos indefinidamente
e explique como definir o espaço de estado e as ações para encontrar rotas de modo que agentes
artificiais também possam evitar loops.
5. Você consegue pensar em um domínio real no qual os custos das etapas sejam tais que causem loops?

Exercício 11 (mc-problema) ÿÿ

https://aimacode.github.io/aima-exercises/search-exercises/ 4/12
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

O problema geralmente é declarado da seguinte maneira. Três missionários e três canibais

estão de um lado do rio, junto com um barco que pode levar uma ou duas pessoas. Encontre
uma maneira de levar todos para o outro lado sem nunca deixar um grupo de missionários em
um lugar superado pelos canibais naquele lugar. Este problema é famoso em IA porque foi o
tema do primeiro artigo que abordou a formulação de problemas do ponto de vista analítico
Amarel:1968.
1. Formule o problema com precisão, fazendo apenas as distinções necessárias para garantir uma
solução válida. Desenhe um diagrama do espaço de estados completo.
2. Implemente e resolva o problema de forma otimizada usando um algoritmo de busca apropriado. É uma boa
ideia verificar se há estados repetidos?
3. Por que você acha que as pessoas têm dificuldade em resolver esse quebra-cabeça, visto que o espaço de
estado é tão simples?

Exercício 12
ÿÿ

Defina com suas próprias palavras os seguintes termos: estado, espaço de estado, árvore de busca, nó de
busca, objetivo, ação, modelo de transição e fator de ramificação.

Exercício 13
ÿÿ

Qual é a diferença entre um estado mundial, uma descrição de estado e um nó de pesquisa? Por que
essa distinção é útil?

Exercício 14
ÿÿ

Uma ação como realmente consiste em uma longa sequência de ações mais refinadas:
ligar o carro, soltar o freio, acelerar, etc. Ter ações compostas desse tipo reduz o número
de etapas em uma sequência de solução, reduzindo assim a busca tempo.
Suponha que levemos isso ao extremo lógico, fazendo ações supercompostas de todas as
sequências possíveis de ações. Em seguida, cada instância do problema é resolvida por uma
única ação supercomposta, como . Explique como a pesquisa funcionaria nessa formulação. Esta
é uma abordagem prática para acelerar a resolução de problemas?

Exercício 15
ÿÿ

https://aimacode.github.io/aima-exercises/search-exercises/ 5/12
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

Um espaço de estados finito sempre leva a uma árvore de busca finita? Que tal um espaço de estado finito
que é uma árvore? Você pode ser mais preciso sobre quais tipos de espaços de estado sempre levam a
árvores de busca finitas? (Adaptado de , 1996.)

Exercício 16 (exercício de propriedade de separação de gráficos) ÿÿ

Prove que satisfaz a propriedade de separação de grafos ilustrada Dica: Comece mostrando
em . (que a propriedade mantém no início, mostre que, se ela é válida antes de uma iteração
do algoritmo, ela é mantida depois.) Descreva um algoritmo de pesquisa que viola a propriedade.

Exercício 17
ÿÿ

Quais das alternativas a seguir são verdadeiras e quais são falsas? Explique suas respostas.
1. A pesquisa em profundidade sempre expande pelo menos tantos nós quanto uma pesquisa com um
heurística admissível.
2. h(n) = 0 é uma heurística admissível para o quebra-cabeça de 8.

3. A não tem utilidade em robótica porque percepções, estados e ações são contínuos.
4. A busca em largura é completa mesmo se custos de etapa zero forem permitidos.
5. Suponha que uma torre pode se mover em um tabuleiro de xadrez qualquer número de casas em
linha reta, vertical ou horizontalmente, mas não pode pular outras peças. A distância de Manhattan é
uma heurística admissível para o problema de mover a torre do quadrado A para o quadrado B no
menor número de movimentos.

Exercício 18
ÿÿ

k tem dois
Considere um espaço de estado onde o estado inicial é o número 1 e cada estado
sucessores: números e 2k 2k + 1 .
1. Desenhe a parte do espaço de estado para os estados 1 a 15.
2. Suponha que o estado objetivo seja 11. Liste a ordem na qual os nós serão visitados para busca em
largura, busca limitada em profundidade com limite 3 e busca iterativa em aprofundamento.
3. Até que ponto a pesquisa bidirecional funcionaria nesse problema? Qual é o fator de ramificação
em cada direção da busca bidirecional?

4. A resposta para (c) sugere uma reformulação do problema que permitiria que você resolvesse
o problema de ir do estado 1 para um determinado estado objetivo quase sem busca? k 2k 2k +
1 5. Chame
encontrar um algoritmo que forneça a ação
a solução para que
essevai da esquerda
problema e a ação
semdireita.
nenhuma que
Você vai para a
pode
pesquisa?

https://aimacode.github.io/aima-exercises/search-exercises/ 6/12
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

Exercício 19 (exercício brio)

ÿÿ

Um conjunto ferroviário básico de madeira contém as peças mostradas em . A tarefa é conectar

essas peças em uma ferrovia que não tenha trilhos sobrepostos e sem pontas soltas onde um trem poderia
correr para o chão.

1. Suponha que as peças se encaixem na exatamente sem folga. Forneça uma formulação precisa de
tarefa como um problema de busca.
2. Identifique um algoritmo de busca desinformada adequado para esta tarefa e explique sua escolha.
3. Explique por que remover qualquer uma das peças do “garfo” torna o problema insolúvel.
4. Forneça um limite superior para o tamanho total do espaço de estados definido por sua formulação.
( Dica
: pense no fatoro de
ignorando ramificação
problema máximo
de peças para o processo
sobrepostas desoltas.
e pontas construção e na
Comece profundidade
fingindo máxima,
que cada peça é
única.)

Exercício 20
ÿÿ

Implemente duas versões da função para o quebra-cabeça de 8: uma que copia e edita a estrutura de
s
dados para o nó pai e outra que modifica o estado pai diretamente (desfazendo as modificações conforme
necessário). Escreva versões de pesquisa em profundidade de aprofundamento iterativo que use essas
funções e compare seu desempenho.

Exercício 21 (exercício de alongamento iterativo) ÿÿ

Na página, mencionamos
pesquisa. A ideia
a pesquisa
é usar limites
de alongamento
crescentes iterativo,
no custo um
do caminho.
análogo iterativo
Se for gerado
de custo
umuniforme
nó
cujo custo de caminho exceda o limite atual, ele é imediatamente descartado. Para cada nova iteração,
o limite é definido como o menor custo de caminho de qualquer nó descartado na iteração anterior.

1. Mostre que esse algoritmo é ótimo para custos gerais de

caminho. b da solução
, profundidade
2. Considere uma árvore uniforme com fator de ramificação d e custos de etapa unitária.

Quantas iterações o alongamento iterativo exigirá? [ÿ, 1]

3. Agora, considere os custos da etapa extraídos do intervalo , onde . Como
0<ÿ<1

contínuo, muitas iterações são necessárias no pior caso?

4. Implemente o algoritmo e aplique-o a instâncias dos problemas do quebra-cabeça de 8 e do
caixeiro-viajante. Compare o desempenho do algoritmo com o da pesquisa de custo uniforme e
comente seus resultados.

https://aimacode.github.io/aima-exercises/search-exercises/ 12/07
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

Exercício 22
ÿÿ

Descreva um espaço de estado no qual a busca de aprofundamento iterativo tem um desempenho muito pior
2
O(n)
do que a busca em profundidade (por exemplo, O(n) vs. ).

Exercício 23
ÿÿ

Escreva um programa que receba como entrada dois URLs de páginas da Web e encontre um caminho de
links de um para o outro. O que é uma estratégia de busca apropriada? A pesquisa bidirecional é uma boa ideia?
Um mecanismo de busca poderia ser usado para implementar uma função predecessora?

Exercício 24 (exercício de busca a vácuo) ÿÿ

Considere o problema do mundo do vácuo definido em .

1. Qual dos algoritmos definidos neste capítulo seria apropriado para este problema?
O algoritmo deve usar pesquisa em árvore ou pesquisa em
escolhido para calcular uma sequência ideal de ações para gráfico?
um mundo 3 ×cujo
3 2.estado
Apliqueinicial
o algoritmo
tenha
sujeira nos três quadrados superiores e o agente no centro.
3. Construa um agente de busca para o mundo do vácuo e avalie seu desempenho em um conjunto de 3 ×
3 mundos com probabilidade de 0,2 de sujeira em cada quadrado. Inclua o custo da pesquisa, bem como

custo do caminho na medida de desempenho, usando uma taxa de câmbio razoável.

4. Compare seu melhor agente de busca com um simples agente de reflexo aleatório que
suga se houver sujeira e se move aleatoriamente.
5. Considere o que aconteceria se o mundo fosse ampliado para . Como o n × n
o desempenho do agente de busca e do agente de reflexo variando comn ?

Exercício 25 (exercício de pesquisa de casos especiais) ÿÿ

Prove cada uma das seguintes afirmações ou dê um contra-exemplo: 1.

A busca em largura é um caso especial de busca de custo uniforme.
2. A busca em profundidade é um caso especial de busca na melhor árvore.
3. A busca de custo uniforme é um caso especial de busca A.

Exercício 26 ÿÿ

https://aimacode.github.io/aima-exercises/search-exercises/ 8/12
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

Compare o desempenho de A e RBFS em um conjunto de problemas gerados aleatoriamente nos domínios de

8 quebra-cabeças (com distância de Manhattan) e TSP (com MST - consulte Recursos). Discuta seus resultados.
O que acontece com o desempenho de RBFS quando um pequeno número aleatório é adicionado aos
valores heurísticos no domínio de 8 quebra-cabeças?

Exercício 27
ÿÿ

Trace a operação de uma busca aplicada ao problema de chegar a Bucareste de Lugoj

usando a heurística de distância em linha reta. Ou seja, mostre a sequência de nós que
o algoritmo irá considerar e a pontuação f, g e h para cada nó.

Exercício 28
ÿÿ

Às vezes, não há uma boa função de avaliação para um problema, mas há um bom método de
comparação: uma maneira de saber se um nó é melhor que outro sem atribuir valores numéricos a
nenhum deles. Mostre que isso é suficiente para fazer uma pesquisa do melhor primeiro. Existe um analógico
de A para esta configuração?

Exercício 29 (exercício-falha) ÿÿ

Crie um espaço de estado no qual A using retorna uma solução subótima com h(n) função
um que é admissível, mas inconsistente.

Exercício 30
ÿÿ

Heurísticas precisas não reduzem necessariamente o tempo de busca no pior caso. Dada qualquer
h(n) ÿ hprofundidade
(n)| ÿ O(log(n))ddmas
, defina um problema
expande todos os de
nósbusca com um nó objetivo
de profundidade escreva
em uma
profundidade
heurísticaeh \* |
funcionar de tal forma que \* Aÿ
menor que d.

Exercício 31
ÿÿ

https://aimacode.github.io/aima-exercises/search-exercises/ 12/09
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

O algoritmo de caminho heurístico Pohl:1977 é uma busca do melhor primeiro em que a função de avaliação
é c está completo? Para quais valores hw =
. Para que valores de isto
f(n) = (2 ÿ w)g(n) + wh(n)
=1w=2e? 0 é ótimo, assumindo que é admissível? Que tipo de pesquisa isso realiza
para w ,

Exercício 32
ÿÿ

Considere a versão ilimitada da grade 2D regular mostrada em . O estado inicial está na origem, (0,0), e
o estado final está em (x, y) .

1. Qual é o fator de ramificação nestebespaço de estado?

2. Qual
3. Quantos
é o número
estados máximo
distintosde
existem
nós expandidos
em profundidade
pela busca
(para
em em
largura?
)? árvore
kk > 0

4. Qual é o número máximo de nós expandidos pela busca em largura do grafo? h = |u ÿ x| + |v ÿ y|

5. É uma heurística
por umaadmissível
pesquisapara um estado em ?
h 6. Quantos nós são expandidos de gráfico usando (u,v) ? Explicar.

7. Permanece
h admissível se alguns links forem removidos?
h
8. Permanece admissível se alguns links forem adicionados entre estados não adjacentes?

Exercício 33
ÿÿ

n linha superior, mas na ordem inversa;

(1, 1) (n,
então
deve
1) veículos
oterminar
veículo que.(ou
veículos
ocupam
em seja,
começa
Em
devem apasso
quadrados
cadaser
emlinha 1)inferior)
movidos
(i,através
de + de
(ntempo,
ÿpara
ide 1, um n × n
i acada
n) grade. o
um dos veículos pode se mover um quadrado para cima, para baixo, para a esquerda ou para a direita, ou
ficar parado; mas se um veículo
pular sobre
permanecer
ele. Dois
parado,
veículos
outro
nãoveículo
podemadjacente n de um) pode
ocupar o (mas não mais

mesmo quadrado.

1. Calcule o tamanho do espaço de estados em função de . n

2. Calcule o fator de ramificação em função de . (xi, yi) hi 3.n
admissível não trivial para o (n ÿ i + Suponha
1, n) número
ao
euque
seu
de
o veículo
local
movimentos
deesteja
destino,
necessários
emassumindo
; escrevapara
uma
quechegar
heurística
nenhum outro
veículo esteja no grid.

4. Quais das seguintes heurísticas são admissíveis para o problema de mover todos os veículosn para seus
destinos? Explicar. oi
1. ÿn i=1 .
2. max{h1,…, hn} .
3. min{h1,…, hn} .

https://aimacode.github.io/aima-exercises/search-exercises/ 10/12
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

Exercício 34
ÿÿ

cavalos das casas iniciais para o golkk s1,…, sk k Considere o problema de mover
quadrados g1,…, gk , em um tabuleiro de xadrez ilimitado, sujeito à regra de que não há dois cavalos
podem pousar no mesmo quadrado ao mesmo tempo. Cada ação consiste em mover os cima para
k

cavaleiros simultaneamente. Gostaríamos de completar a manobra no menor número de

ações.

k 1. Qual é o fator de ramificação máximo neste espaço de estado, expresso como uma função de ?
2. Suponha oi
que seja uma heurística admissível para o problema de mover o cavalo para o gol eu
kimono

por si só. Quais das seguintes heurísticas são admissíveis para okproblema -knight? Daqueles,
Qual é o melhor?
1.min{h1,…, hk} .
2. máx{h1,…, hk} ÿk .
3. i=1 oi .
3. Repita (b) para o caso em que você pode mover apenas um cavalo por vez.

Exercício 35
ÿÿ

Vimos na página que a heurística da distância em linha reta desvia a busca gananciosa do melhor
primeiro para o problema de ir de Iasi para Fagaras. No entanto, a heurística é perfeita no problema
oposto: ir de Fagaras para Iasi. Existem problemas para os quais a heurística é enganosa em ambas
as direções?

Exercício 36
ÿÿ

Invente uma função heurística para o quebra-cabeça de 8 que às vezes superestima e mostre
como ela pode levar a uma solução abaixo do ideal em um problema específico. (Você pode usar
h
um computador para ajudar, se quiser.) c , Um
Prove que if nunca superestima em mais
uso huma solução
deretorna um
cujo custo excede o da solução ótima em não mais que . c

Exercício 37 (exercício-heurístico-consistente)
ÿÿ

Prove que se uma heurística é consistente, ela deve ser admissível. Construir um admissível
heurística que não é consistente.

https://aimacode.github.io/aima-exercises/search-exercises/ 11/12
Machine
09/03/23, 22:18 Translated by Google Exercícios de Pesquisa · Exercícios AIMA

Exercício 38 (tsp-mst-exercício) ÿÿ

O problema do caixeiro-viajante (TSP) pode ser resolvido com a heurística da árvore geradora
mínima (MST), que estima o custo de completar um passeio, dado que um passeio parcial já foi
construído. O custo MST de um conjunto de cidades é a menor soma dos custos de enlace de
qualquer árvore que conecte todas as cidades.
1. Mostre como essa heurística pode ser derivada de uma versão relaxada do TSP.

2. Mostre que a heurística MST domina a distância em linha reta.

3. Escreva um gerador de problemas para instâncias do TSP onde as cidades são representadas por
pontos aleatórios no quadrado unitário.
4. Encontre um algoritmo eficiente na literatura para construir o MST e use-o com uma
busca de grafo para resolver instâncias do TSP.

Exercício 39 (Gaschnig-h-exercício) ÿÿ

A na página definimos o relaxamento

, para o quadrado B se Bdo quebra-cabeça
estiver em branco.deA 8solução
em queexata
uma deste
peça pode se mover
problema doaquadrado
define heurística
h1 de Gaschnig Gaschnig:1979. Explique por que a heurística de Gaschnig é pelo menos tão precisa quanto
(ladrilhos
mal posicionados) e mostre casos em que é mais precisa do que ambos e h2 (distância de Manhattan).
Explique como calcular a heurística de Gaschnig de forma eficiente. h1

Exercício 40
ÿÿ

Demos duas heurísticas simples para o quebra-cabeça de 8: distância de Manhattan e peças mal colocadas.
Várias heurísticas na literatura pretendem melhorar isso - veja, por exemplo, Nilsson:1971,
Mostow+Prieditis:1989, e Hansson+al:1992. Teste essas afirmações implementando a
heurística e comparando o desempenho dos algoritmos resultantes.

https://aimacode.github.io/aima-exercises/search-exercises/ 12/12