Lista Inteligência artificial Tatiane Nogueira Rios prova 1 problemas por meio de busca

Prévia do material em texto

Universidade Federal da Bahia
Departamento de Ciência da Computação
Inteligência Artificial
Resolução de problemas por meio de busca
Profª.: Tatiane Nogueira Rios
Estagiária: Elidiane Pereira
Monitora: Renata Antunes da Costa
Este documento reúne vários exercícios, e suas respectivas
respostas, selecionados de diversos pesquisadores da
comunidade de inteligência artificial no Brasil e no exterior, cujo
conteúdo está disponível na web. Os enunciados e respostas
fornecidos, portanto, apesar de terem sido revisados pela
professora, monitora e estagiária, podem gerar dúvidas ou serem
de assuntos não vistos em sala de aula. Sendo assim, espera-se
que os alunos de Inteligência Artificial sejam capazes de resolver
os exercícios, bem como desenvolver a autocrítica comparando as
respostas obtidas na resolução das questões com as respostas
fornecidas pelos autores das questões.
Qualquer dúvida/sugestão, por gentileza entrar em contato:
tatiane.nogueira@ufba.br.
Resolução de problemas por meio de busca
Questão 1
Descreva o estado inicial, o estado objetivo, a função sucessor e a função de custo para
os problemas (Escolha uma formulação que seja precisa o bastante para ser
implementada):
a) Você tem um programa que lhe dá a mensagem “Registro de entrada ilegal” quando
lhe é fornecido um certo arquivo de entrada. Você sabe que o processamento de cada
registro é independente dos outros. Você quer descobrir que registro é ilegal.
Estado Inicial: O primeiro registro a ser avaliado
Função sucessor: O próximo arquivo a ser avaliado
Função custo: O custo de ler cada arquivo.
Estado objetivo: Descobrir que o arquivo avaliado é ilegal.
b) Você tem três jarros, medindo 12 litros, 8 litros e 3 litros e uma fonte de água. Você
pode encher ou esvaziar os jarros de um para o outro ou no chão. Você quer medir
exatamente um litro.
Estado Inicial: 3 jarros com capacidade de 12, 8 e 3 litros respectivamente e uma fonte.
Função sucessor: a troca de água de um vazo para o outro, ou despejo de água no
chão.
Função custo: o custo de cada ação.
Estado objetivo: ficar com apenas um litro dentro de um dos vazos.
Questão 2
As definições a seguir representam, respectivamente, os métodos de busca:
(1) A estratégia de busca guarda a soma do custo de cada caminho e procura, a cada
passo, o caminho que implicará na menor soma.
(2) A estratégia de busca utiliza uma estimativa do custo do caminho até o nó destino,
calculando o caminho de menor custo ou que implicará na menor soma.
(3) A estratégia de busca é visitar o nó com menor custo vinculado ao percurso.
A. (1) Busca Ordenada - (2) Busca Simples - (3) Busca pelo vizinho mais próximo
B. (1) Busca Simples - (2) Busca Completa - (3) Busca pelo vizinho mais próximo
C. (1) Busca Heurística - (2) Busca pelo vizinho mais próximo - (3) Busca Ordenada
D. (1) Busca Ordenada - (2) Busca Heurística - (3) Busca pelo vizinho mais próximo
D
Questão 3
Uma pessoa deseja atravessar o labirinto abaixo. Porém, ela não tem qualquer
2
Resolução de problemas por meio de busca
informação sobre o labirinto que a ajude a tomar uma decisão que a leve a saída de
forma mais eficiente. Mesmo sem ter qualquer informação sobre o labirinto, ela sabe
que pode usar uma técnica de busca não informada para atravessá-lo chamada de
busca em profundidade. Para isso basta ela seguir a seguinte regra ao tentar atravessar
o labirinto:
Escolher um lado do muro, direito ou esquerda, e sempre percorrer o labirinto
seguindo o lado muro escolhido como referência. Com base nessa informação, se
usarmos o lado direito do muro como referência qual a árvore de busca em
profundidade que pode ser gerada do labirinto abaixo?
Legenda: IN = entrada do labirinto OUT = saída do labirinto A, B, C, D, E, F, G, H, I, J, K, L,
M, N = vértices
Resposta
Questão 4
Considere as seguintes afirmações sobre resolução de problemas em IA.
I. A* é um conhecido algoritmo de busca heurística.
3
Resolução de problemas por meio de busca
II. O Minimax é um dos principais algoritmos para jogos de dois jogadores, como o
xadrez. III. Busca em espaço de estados é uma das formas de resolução de problemas
em IA. Assinale a alternativa correta
A. Apenas II e III estão corretas
B. Apenas I e III estão corretas
C. Apenas III está correta
D. I, II e III estão corretas
D
Questão 5
Analise as seguintes afirmativas:
I. A estratégia de busca em largura encontra a solução ótima quando todos os
operadores de mudança de estado têm o mesmo custo.
II. A estratégia de busca em profundidade sempre expande um menor número de nós
que a estratégia de busca em largura, quando aplicadas ao mesmo problema.
III. A estratégia de busca heurística encontra sempre a solução de menor custo.
IV. A estratégia de busca heurística expande um número de nós em geral menor que o
algoritmo de busca em largura, mas não garante encontrar a solução ótima.
V. O algoritmo de busca heurística que utiliza uma função heurística admissível
encontra a solução ótima.
A esse respeito, pode-se concluir que: Escolha a alternativa correta:
A. Apenas a afirmativa V é correta.
B. Apenas as afirmativas I e IV são corretas.
C. Apenas as afirmativas II e V são corretas.
D. Apenas as afirmativas I, IV e V são corretas.
D
Questão 6
Com relação às técnicas de buscas usadas em inteligência artificial, considere as
afirmativas a seguir:
I. Um algoritmo genético é uma busca de subida de encosta (Hill Climbing) estocástica
em que é mantida uma grande população de estados. Novos estados são gerados por
mutação e por crossover, que combina pares de estados da população.
II. A busca em largura, em profundidade e de custo uniforme são casos especiais de
busca pela melhor escolha (Best First).
III. A busca A* expande nós com valor mínimo para f(n) = g(n) + h(n). A* é completa e
ótima, desde que se possa garantir que h(n) seja admissível.
4
Resolução de problemas por meio de busca
Assinale a alternativa correta.
A. Somente as afirmativas I e II são corretas
B. Somente as afirmativas I e III são corretas
C. Somente a afirmativa II é correta
D. As afirmativas I, II e III são corretas
D
Questão 7
Sabendo-se que cada vértice representa uma localidade e deseja-se, partindo-se da
localidade A chegar à localidade J. Determine todos os possíveis caminhos através da
busca ordenada, informando seus respectivos custos. Destaque ao final qual o melhor
caminho, isto é, o de menor custo.
ABDFHJ = 8+5+7+10+9 = 39
ABFHJ = 8+10+10+9 = 37
AGHJ = 20+6+9 = 35
AGIJ = 20+7 +3 = 30
ACEIJ = 10+12+4+3 = 29 <-[Melhor caminho]
ACEJ = 10+12+9 = 31
Questão 8
Give the name of the algorithm which results from
a Local beam search with k = 1
b Local beam search with one initial state and no limit on the number of states
retained
5
Resolução de problemas por meio de busca
c Simulated annealing with T = ∞ at all times
a Hill climbing
b Breadth first search
c Random walk through the search space
Questão 9
Considere o espaço de busca a seguir. Cada nó é rotulado por uma letra. Cada nó
objetivo é representado por um círculo duplo. Existe uma heurística estimada para
cada dado nó (indicada por um valor ao lado do nó). Arcos representam os operadores
e seus custos associados.
Para cada um dos algoritmos a seguir, liste os nós visitados na ordem em que eles são
examinados, começando pelo nó A. No caso de escolhas equivalentes entre diferentes
nodos, prefira o nodo mais próximo da raiz, seguido pelo nodo mais à esquerda na
árvore.
a) Algoritmo de Busca em Largura;
Buscando I: A – B – C – D – E – F – G – H – I
Buscando K: A – B – C – D – E – F – G – H – I – J – K
b) Algoritmo de Busca em Profundidade;
Buscando I: D – H – I
Buscando K: D – H – I – E – B – F – J – K
c) Algoritmo de Busca Gulosa;
Buscando I: A – B – E – I
Buscando K: A – B – E – I – H – D – C – G – K
d) Algoritmo A*.
Buscando I: A – B – E – I
Buscando K: A – B – E – I – H – D – C – G – K
6
Resolução de problemas por meio de busca
Questão 10
Consider the following graph where each state has the objective value or measure of
quality ofstates given in Table 1. We can perform an action which would take us from
one state to another. Action identifiers are denoted on the edges between nodes. The
goal is to perform a sequence of actions that would maximize the objective function.
Assume A is the initial state.
If you were to perform hill-climbing, what would be the final state you would reach?
If were to perform hill-climbing we would get stuck in a local optimum: The solution
is in node E with objective value 9 and sequence of transitions: <a,b,c>
Questão 11
Considere o seguinte mapa (fora de escala)
7
Resolução de problemas por meio de busca
Usando o algoritmo A* determine uma rota de A até R, usando as seguintes funções de
custo g(n) = a distância entre cada cidade (mostrada no mapa) e h(n) = a distância em
linha reta entre duas cidades. Estas distâncias são dadas na tabela abaixo.
Em sua resposta forneça o seguinte:
1. A árvore de busca que é produzida, mostrando a função de custo em cada nó.
2. Defina a ordem em que os nós serão expandidos.
3. Defina a rota que será tomada e o custo total.
Distância em linha reta até R
Resposta
8
Resolução de problemas por meio de busca
Ordem da expansão dos nós: ABCDEILMFOPR
Rota: ACIMOR
Custo total: 270
Questão 12
For all the questions below assume:
● All search algorithms are graph search (as opposed to tree search).
● is the cost to go from node i to node j.𝑐
𝑖𝑗
> 0 
● There is only one goal node (as opposed to a set of goal nodes).
● All ties are broken alphabetically.
● Assume heuristics are consistent.
Definition: Two search algorithms are defined to be equivalent if and only if they
expand the same nodes in the same order and return the same path.
In this question we study what happens if we run uniform cost search with action costs
that are potentially different from the search problem's actual action costs .𝑑
𝑖𝑗
𝑐
𝑖𝑗
Concretely, we will study how this might, or might not, result in running uniform cost
search (with these new choices of action costs) being equivalent to another search
algorithm.
a) Mark all choices for costs that make running Uniform Cost Search𝑑
𝑖𝑗
 
algorithm with these costs equivalent to running Breadth-First Search.𝑑
𝑖𝑗
o 𝑑
𝑖𝑗
= 0
● 𝑑
𝑖𝑗
= α, α > 0
o 𝑑
𝑖𝑗
= α, α < 0
● 𝑑
𝑖𝑗
= 1 
o 𝑑
𝑖𝑗
=− 1
o None of the above
Beadth First search expands the node at the shallowest depth first. Assigning a
constant positive weight to all edges allows to weigh the nodes by their depth in the
search tree.
b) Mark all choices for costs that make running Uniform Cost Search𝑑
𝑖𝑗
algorithm with these costs equivalent to running Depth-First Search.𝑑
𝑖𝑗
9
Resolução de problemas por meio de busca
o 𝑑
𝑖𝑗
= 0
o 𝑑
𝑖𝑗
= α, α > 0
● 𝑑
𝑖𝑗
= α, α < 0
o 𝑑
𝑖𝑗
= 1
● 𝑑
𝑖𝑗
=− 1
o None of the above
Depth First search expands the nodes which were most recently added to the fringe
first. Asssigning a constant negative weight to all edges essentially allows to reduce the
value of the most recently nodes by that constant, making them the nodes with the
minimum value in the fringe when using uniform cost search.
c) Mark all choices for costs that make running Uniform Cost Search algorithm𝑑
𝑖𝑗
with these costs equivalent to running Uniform Cost Search with the𝑑
𝑖𝑗
original costs .𝑐
𝑖𝑗
o 𝑑
𝑖𝑗
= 𝑐
𝑖𝑗
2
o 𝑑
𝑖𝑗
= 1𝑐
𝑖𝑗
● 𝑑
𝑖𝑗
= α 𝑐
𝑖𝑗
, α > 0
o 𝑑
𝑖𝑗
= 𝑐
𝑖𝑗
+ α, α > 0
o 𝑑
𝑖𝑗
= α𝑐
𝑖𝑗
+ β, α > 0, β > 0
o None of the above
Uniform cost search expands the node with the lowest cost-so-far = on the fringe.
𝑖𝑗
∑ 𝑐
𝑖𝑗
Hence, the relative ordering between two nodes is determined by the value of =
𝑖𝑗
∑ 𝑐
𝑖𝑗
for a given node. Amongst the above given choices, only for , can weα 𝑐
𝑖𝑗
 α > 0
conclude,
𝑖𝑗 ∈ 𝑝𝑎𝑡ℎ(𝑛)
 
∑ 𝑑
𝑖𝑗
≥ 
𝑖𝑗 ∈ 𝑝𝑎𝑡ℎ(𝑚)
∑ 𝑑
𝑖𝑗
↔ 
𝑖𝑗 ∈ 𝑝𝑎𝑡ℎ(𝑛)
∑ 𝑐
𝑖𝑗
≥ 
𝑖𝑗 ∈ 𝑝𝑎𝑡ℎ(𝑚)
∑ 𝑐
𝑖𝑗
, 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑛𝑜𝑑𝑒𝑠 𝑛 𝑎𝑛𝑑 𝑚. 
10
Resolução de problemas por meio de busca
d) Let h(n) be the value of the heuristic function at node n.
i) Mark all choices for costs dij that make running Uniform Cost Search
algorithm with these costs dij equivalent to running Greedy Search with the
original costs cij and heuristic function h.
o 𝑑
𝑖𝑗
= ℎ(𝑖) − ℎ(𝑗)
● 𝑑
𝑖𝑗
= ℎ(𝑗) − ℎ(𝑖)
o 𝑑
𝑖𝑗
= α ℎ(𝑖), α > 0
o 𝑑
𝑖𝑗
= α ℎ(𝑗), α > 0
o 𝑑
𝑖𝑗
= 𝑐
𝑖𝑗
+ ℎ(𝑗) + ℎ(𝑖) 
o None of the above
Greedy search expands the node with the lowest heuristic function value h(n).
then the cost of a node n on the fringe when running𝐼𝑓 𝑑
𝑖𝑗
= ℎ(𝑗) − ℎ(𝑖), 
uniform-cost search will be As is a common
𝑖𝑗
∑ 𝑑
𝑖𝑗 
= ℎ(𝑛) − ℎ(𝑠𝑡𝑎𝑟𝑡). ℎ(𝑠𝑡𝑎𝑟𝑡)
constant subtracted from the cost of all nodes on the fringe, the the relative ordering of
the nodes on the fringe is still determined by h(n), i.e. their heuristic values.
(ii) Mark all choices for costs dij that make running Uniform Cost Search
algorithm with these costs dij equivalent to running A* Search with the original
costs cij and heuristic function h.
o 𝑑
𝑖𝑗
= α ℎ(𝑖), α > 0
o 𝑑
𝑖𝑗
= α ℎ(𝑗), α > 0
o 𝑑
𝑖𝑗
= 𝑐
𝑖𝑗
+ ℎ(𝑖) 
● 𝑑
𝑖𝑗
= 𝑐
𝑖𝑗
+ ℎ(𝑗)
o 𝑑
𝑖𝑗
= 𝑐
𝑖𝑗
+ ℎ(𝑖) − ℎ(𝑗) 
o 𝑑
𝑖𝑗
= 𝑐
𝑖𝑗
+ ℎ(𝑗) − ℎ(𝑖) 
o None of the above
11
Resolução de problemas por meio de busca
A∗ search expands the node with the lowest value, where f is𝑓(𝑛) + ℎ(𝑛) (𝑛) = 
𝑖𝑗
∑ 𝑐
𝑖𝑗
the cost-so-far and h is the heuristic value. If , then the cost𝑑
𝑖𝑗
 = 𝑐
𝑖𝑗
+ ℎ(𝑗) − ℎ(𝑖)
of a node n on the fringe when running uniform-cost search will be =
. As is a
𝑖𝑗
∑ 𝑑
𝑖𝑗
= 
𝑖𝑗
∑ 𝑐
𝑖𝑗 
+ ℎ(𝑛) − ℎ(𝑠𝑡𝑎𝑟𝑡) = 𝑓(𝑛) + ℎ(𝑛) − ℎ(𝑠𝑡𝑎𝑟𝑡) ℎ(𝑠𝑡𝑎𝑟𝑡)
common constant subtracted from the cost of all nodes on the fringe, the relative
ordering of the nodes on the fringe is still determined by 𝑓(𝑛) + ℎ(𝑛).
Questão 13
After running A* graph search and finding an optimal path from start to goal, the cost
of one of the edges, , in the graph changes. Rather than re-running the entire𝑋→𝑌
search, you want to find a more efficient way of finding the optimal path for this new
search problem.
You have access to the fringe, the closed set and the search tree as they were at the
completion of the initial search. In addition, you have a closed node map that maps a
state, s from the closed set to a list of nodes in the search tree ending in s which were
not expanded because s was already in the closed set.
For example, after running A* search with the null heuristic on the following graph, the
data structures would be as follows:
Fringe: {}
Closed Node Map: {A:[ ], B:[ ], C:[ ], D:[(A-C-D, 6)]}
Closed Set: {A, B, C, D}
Search Tree: { A : : [(A-B, 1), (A-C, 4)],
A-B : [(A-B-D, 2)],
A-C : [ ],
A-B-D : [(A-B-D-G, 7)],
A-B-D-E : [ ]}
For a general graph, for each of the following scenarios, select the choice that finds
the correct optimal path and cost while expanding the fewest nodes. Note that if you
select the choice, you must fill in the change, and if you select the last choice, you 4𝑡ℎ
must describe the set of nodes to add to the fringe.
12
Resolução de problemas por meio de busca
In the answer choices below, if an option states some nodes will be added to the
fringe, this also implies that the final state of each node gets cleared out of the closed
set (indeed, otherwise it'd be rather useless to add something back into the fringe).
You may assume that there are no ties in terms of path costs.
Following is a set of eight choices you should use to answer the questions on the
following page.
i. The optimal path does not change, and the cost remains the same.
ii. The optimal path does not change, but the cost increases by n
iii. The optimal path does not change, but the cost decreases by n
iv. The optimal path does not change, but the cost changes
by_______________________
v. The optimal path for the new searchproblem can be found by adding the
subtree rooted at X that was expanded in the original search back onto the
fringe and re-starting the search.
vi. The optimal path for the new search problem can be found by adding the
subtree rooted at Y that was expanded in the original search back onto the
fringe and re-starting the search.
vii. The optimal path for the new search problem can be found by adding all nodes
for each state in the closed node map back onto the fringe and re-starting the
search.
viii. The optimal path for the new search problem can be found by adding some
other set of nodes back onto the fringe and re-starting the search. Describe the
set below.
a) Cost of is increased by , the edge is on the optimal path, and𝑋→𝑌 𝑛; 𝑛 > 0
was explored by the first search.
o i
o ii
o iii
o iv, Change:
o v
o vi
o vii
o viii, Describe the set below:
The combination of all the nodes from the closed node map for the final state of each
node in the subtree rooted at Y plus the node ending at Y that was expanded in the
initial search. This means that you are re-exploring every path that was originally
13
Resolução de problemas por meio de busca
closed off by a path that included the edge X → Y .
b) Cost of is decreased by , the edge is on the optimal path, and𝑋→𝑌 𝑛; 𝑛 > 0
was explored by the first search.
o i
o ii
● iii
o iv, Change:
o v
o vi
o vii
o viii, Describe the set below
The original optimal path’s cost decreases by n because X → Y is on the original optimal
path. The cost of any other path in the graph will decrease by at most n (either n or 0
depending on whether or not it includes X → Y ). Because the optimal path was already
cheaper than any other path, and decreased by at least as much as any other path, it
must still be cheaper than any other path.
c) Cost of is increased by , the edge is not on the optimal path,𝑋→ 𝑌 𝑛; 𝑛 > 0
and was explored by the first search.
● i
o ii
o iii
o iv, Change:
o v
o vi
o vii
o viii, Describe the set below
d) Cost of is decreased by , the edge is not on the optimal path,𝑋→ 𝑌 𝑛; 𝑛 > 0
and was explored by the first search.
o i
o ii
14
Resolução de problemas por meio de busca
o iii
o iv, Change:
o v
o vi
o vii
a. viii, Describe the set below
The combination of the previous goal node and the node ending at X that was
expanded in the initial search. There are two possible paths in this case. The first is the
original optimal path, which is considered by adding the previous goal node back onto
the fringe. The other option is the cheapest path that includes X → Y , because that is
the only cost that has changed. There is no guarantee that the node ending at Y , and
thus the subtree rooted at Y contains X → Y , so the subtree rooted at X must be added
in order to find the cheapest path through X → Y.
e) Cost of is increased by , the edge is not on the optimal path,𝑋→ 𝑌 𝑛; 𝑛 > 0
and was not explored by the first search.
● i
o ii
o iii
o iv, Change:
o v
o vi
o vii
o viii, Describe the set below:
This is the same as part (c).
f) Cost of is decreased by the edge is not on the optimal path,𝑋→ 𝑌 𝑛; 𝑛 > 0,
and was not explored by the first search.
● i
o ii
o iii
o iv, Change:
o v
15
Resolução de problemas por meio de busca
o vi
o vii
o viii, Describe the set below:
Assuming that the cost of X → Y remains positive, because the edge was never
explored, the cost of the path to X is already higher than the cost of the optimal path.
Thus, the cost of the path to Y through X can only be higher, so the optimal path
remains the same.
If you allow edge weights to be negative, it is necessary to find the optimal path to Y
through X separately. Because the edge was not explored, a node ending at X was
never expanded, so the negative edge would still never be seen unless the path was
found separately and added onto the fringe. In this case, adding this path and the
original goal path, similar to (d), would find the optimal path with the updated edge
cost.
Questão 14
If and are all admissible heuristics then which of the following are also𝑓(𝑠), 𝑔(𝑠) ℎ(𝑠)
guaranteed to be admissible heuristics:
o 𝑓(𝑠) + 𝑔(𝑠) + ℎ(𝑠)
● 𝑓(𝑠)/6 + 𝑔(𝑠)/3 + ℎ(𝑠)/2
● 𝑚𝑖𝑛 (𝑓(𝑠), 𝑔(𝑠), ℎ(𝑠)) 
● 𝑚𝑎𝑥(𝑓(𝑠), 𝑔(𝑠), ℎ(𝑠))
● 𝑓(𝑠)/3 + 𝑔(𝑠)/3 + ℎ(𝑠)/3 
o 𝑓(𝑠) * 𝑔(𝑠) * ℎ(𝑠)
● 𝑚𝑖𝑛(𝑓(𝑠), 𝑔(𝑠) + ℎ(𝑠)) 
o 𝑚𝑎𝑥(𝑓(𝑠), 𝑔(𝑠) + ℎ(𝑠)) 
In order to guarantee that a function of admissible heuristics is still admissible, the
expression must be less than or equal to the max of the heuristics. Sums and products
do not satisfy these, so bubbles 1, 6, and 8 all immediately fail. Bubbles 3, 4, and 7 all
work because the max of admissible heuristics is still admissible, as is the min of an
admissible heuristic and anything else. Bubble 5 is the average of the heuristics, so it
must be less than the max, and is thus admissible. Lastly, bubble 2 is a weighted
average, and is thus also less than the max, and is thus admissible.
16
Resolução de problemas por meio de busca
Questão 15
The optimal search algorithms we covered in CS188 find one optimal path (or return
failure). We will explore how to find the paths.𝑏𝑒𝑠𝑡 𝑘 (𝑤𝑖𝑡ℎ 𝑘 ≥ 1)
The following assumptions can be made regarding all the questions in this problem:
1. There are at least k paths from the start state to a goal state.
2. All edge costs are positive numbers (𝑐𝑜𝑠𝑡 > 0).
3. No ties occur.
Consider a modified implementation of the Uniform Cost Graph Search (UCS)
algorithm with the following basic modifications:
1. Maintain a list of successful paths to a goal state found so far. When a path from
the start state to a goal state is found (i.e., whenever a path ending in the goal
state is popped from the fringe), it is added to this list.
2. Exit the algorithm only if the length of the above list is k (success) or the fringe
is empty (failure).
For each of the additional modifications on the next page, mark whether or not it
would correctly give the top k unique least cost paths from the start state to a goal
state. If a modification does not work, select all of the below graphs where there exists
at least one set of edge weights and value for (subject to the constraint that there are𝑘
at least k paths through the graph) that would cause the algorithm to fail. Note that
some modifications may even lead to failure for 𝑘 = 1.
a) Everytime after a path is found, empty out the closed set.
o Will work correctly
o Will not work correct
Graphs for which this modification fails:
17
Resolução de problemas por meio de busca
o 1
● 4
●2
● 5
●3
o 6
Whenever two paths intersect prior to the goal state, there is at least one set of
weights such that this algorithm will fail for k > 1. This occurs in graphs 2, 3, 4, and 5
b) For each state , maintain a count count expand(s) of how many times a path𝑠
ending in state has been popped from the fringe. Only add a state s to the𝑠
closed set if count expand(s) = k.
● Will work correctly
o Will not work correctly
Graphs for which this modification fails:
o 1
o 4
o 2
o 5
o 3
o 6
The first k paths ending in a state are guaranteed to be the shortest k paths to that
state, because of how uniform cost search works. Further, it is guaranteed that any
path ending at a state, s, that is not one of the k shortest paths to s, cannot be part of
one of the overall k shortest paths. This means that any path that stops being expanded
because a state is on the closed set cannot be one of the overall k shortest paths.
c) Do not use a closed set.
● Will work correctly
o Will not work correctly
Graphs for which this modification fails:
o 1
18
Resolução de problemas por meio de busca
o 4
o 2
o 5
o 3
o 6
This is running tree search, which will consider every possible path through the graph in
order of increasing cost. Thus, it will find every path to the goal in order of increasing
cost, which will correctly return the k shortest paths given the basic modifications.
d) Do not use aclosed set and, every time after a path is found, change the edge
costs along that path by adding , where is a number that is at least as large 𝐶 𝐶
as the sum of the costs of all edges in the graph. Also for each path on the
fringe that contains i edges of the path that was just found, add to the𝑖 × 𝐶
cost associated with this path on the fringe.
o Will work correctly
o Will not work correctly
Graphs for which this modification fails:
o 1
● 4
● 2
o 5
o 3
o 6
This modification can fail on graphs in which only a strict subset of the paths share an
edge. This applies to graphs 2 and 4. Note that while some of the other graphs share
edges, because the edges are common to all paths, changing the value of those edges
does not change the order in which the paths are expanded, and thus does not cause
the search to fail.
e) Do not use a closed set and, for each state , maintain a of𝑠 𝑐𝑜𝑢𝑛𝑡 _𝑓𝑟𝑖𝑛𝑔𝑒(𝑠)
how many times a node ending in state s has been added to the fringe. Only
add a node ending in a state s to the fringe if 𝑐𝑜𝑢𝑛𝑡 𝑓𝑟𝑖𝑛𝑔𝑒(𝑠) < 𝑘.
o Will work correctly
o Will not work correctly
19
Resolução de problemas por meio de busca
Graphs for which this modification fails:
● 1
● 4
● 2
● 5
● 3
● 6
This modification can fail on any graph in which multiple paths intersect on any node,
including the goal, which is the case for all of the graphs provided.
f) No modification is made except for the Basic Modification described at the
beginning of this question.
o Will work correctly
o Will not work correctly
Graphs for which this modification fails:
o 1
● 4
● 2
● 5
● 3
o 6
This algorithm can fail on any graph that has paths intersecting on any node other then
the goal, similar to (a). This occurs in graphs 2, 3, 4, and 5.
Questão 16
20
Resolução de problemas por meio de busca
Consider the state space graph shown above. A is the start state and G is the goal state.
The costs for each edge are shown on the graph. Each edge can be traversed in both
directions. Note that the heuristic h1 is consistent but the heuristic h2 is not consistent.
a) Possible paths returned
For each of the following graph search strategies (do not answer for tree search),
mark which, if any, of the listed paths it could return. Note that for some search
strategies the specific path returned might depend on tie-breaking behavior. In any
such cases, make sure to mark all paths that could be returned under some
tie-breaking scheme.
Search Algorithm A-B-D-G A-C-D-G A-B-C-D-F-G
Depth first search x x x
Breadth first search x x
Uniform cost search x
A* search with heuristic ℎ
1
x
A* search with heuristic ℎ
2
x
The return paths depend on tie-breaking behaviors so any possible path has to be
marked. DFS can return any path. BFS will return all the shallowest paths, i.e. A-B-D-G
and A-C-D-G. A-B-C-D-F-G is the optimal path for this problem, so that UCS and A*
using consistent heuristic h1 will return that path. Although, h2 is not consistent, it will
also return this path.
b) Heuristic function properties
Suppose you are completing the new heuristic function h3 shown below. All the
values are fixed except ℎ
3
(𝐵).
Node A B C D E F G
ℎ
3
10 ? 9 7 1.5 4.5 0
For each of the following conditions, write the set of values that are possible for
For example, to denote all non-negative numbers, write [0, ∞], to denoteℎ
3
(𝐵).
the empty set, write ∅, and so on.
21
Resolução de problemas por meio de busca
i) What values of make admissible?ℎ
3
(𝐵). ℎ
3
 
To make h3 admissible, h3(B) has to be less than or equal to the actual optimal cost
from B to goal G, which is the cost of path B-C-D-F-G, i.e. 12. The answer is
0 ≤ ℎ3(𝐵) ≤ 12
ii) What values of make consistent? ℎ
3
(𝐵). ℎ
3
.
All the other nodes except node B satisfy the consistency conditions. The consistency
conditions that do involve the state B are: 
ℎ(𝐴)≤ 𝑐(𝐴, 𝐵) + ℎ(𝐵)
ℎ(𝐵)≤ 𝑐(𝐵, 𝐴) + ℎ(𝐴)
 ℎ(𝐶)≤ 𝑐(𝐶, 𝐵) + ℎ(𝐵)
ℎ(𝐵)≤ 𝑐(𝐵, 𝐶) + ℎ(𝐶)
ℎ(𝐷)≤ 𝑐(𝐷, 𝐵) + ℎ(𝐵)
ℎ(𝐵) ≤ 𝑐(𝐵, 𝐷) + ℎ(𝐷) 
Filling in the numbers shows this results in the condition: 9 ≤ ℎ
3
(𝐵) ≤ 10
iii) What values of will cause A* graph search to expand node A, then nodeℎ
3
(𝐵) 
C, then node B, then node D in order?
The A* search tree using heuristic h3 is on the right. In order to
make A* graph search expand node A, then node C, then node B,
suppose , we needℎ
3
(𝐵) = 𝑥
1 + 𝑥 > 13
5 + 𝑥 < 14 (𝑒𝑥𝑝𝑎𝑛𝑑 𝐵’ )𝑜𝑟 1 + 𝑥 < 14 (𝑒𝑥𝑝𝑎𝑛𝑑 𝐵)
𝑠𝑜 𝑤𝑒 𝑐𝑎𝑛 𝑔𝑒𝑡 12 < ℎ
3
(𝐵) < 13
Questão 17
The following parts consider a Pacman agent in a deterministic environment. A goal
state is reached when there are no remaining food pellets on the board. Pacman’s
available actions are {N, S, E, W}, but Pacman can not move into a wall. Whenever
22
Resolução de problemas por meio de busca
Pacman eats a food pellet he receives a reward .𝑜𝑓 + 1
Assume that pacman eats a food pellet as soon as he occupies the location of the food
pellet—i.e., the reward is received for the transition into the square with the food
pellet.
Consider the particular Pacman board states shown below. Throughout this problem
assume that for all states, s. Let the discount factor, γ = 1𝑉0(𝑠) = 0
a) What is the optimal value of state A, ?𝑉 * (𝐴)
1
b) What is the optimal value of state B, 𝑉 * (𝐵)?
1
The reason the answers are the same for both (b) and (a) is that there is no penalty for
existing. With a discount factor of 1, eating the food at any future step is just as
valuable as eating it on the next step. An optimal policy will definitely find the food, so
the optimal value of any state is always 1.
c) At what iteration, k, will ) first be non-zero?𝑉
𝑘
(𝐵
5
The value function at iteration k is equivalent to the maximum reward possible within k
steps of the state in question, B. Since the food pellet is exactly 5 steps away from
Pacman in state B, V_5 (B)= 1 and V_(k<5 ) (B)=0
d) How do the optimal q-state values of moving W and E from state A compare?
(choose one)
o 𝑄 * (𝐴, 𝑊) > 𝑄 * (𝐴, 𝐸)
o 𝑄 * (𝐴, 𝑊) < 𝑄 * (𝐴, 𝐸)
o 𝑄 * (𝐴, 𝑊) = 𝑄 * (𝐴, 𝐸)
23
Resolução de problemas por meio de busca
Once again, since γ = 1, the optimal value of every state is the same, since the optimal
policy will eventually eat the food.
e) If we use this MDP formulation, is the policy found guaranteed to produce the
shortest path from pacman’s starting position to the food pellet? If not, how
could you modify the MDP formulation to guarantee that the optimal policy
found will produce the shortest path from pacman’s starting position to the
food pellet?
No. The Q-values for going W est and East from state A are equal so there is no
preference given to the shortest path to the goal state. Adding a negative living reward
(example: -1 for every time step) will help differentiate between two paths of different
lengths. Setting γ < 1 will make rewards seen in the future worth less than those seen
right now, incentivizing Pacman to arrive at the goal as early as possible.
Questão 18
In this class you met A*, an algorithm for informed search guaranteed to return an
optimal solution when given an admissible heuristic. Often in practical applications it is
too expensive to find an optimal solution, so instead we search for good suboptimal
solutions.
Weighted A* is a variant of A* commonly used for suboptimal search. Weighted A* is
exactly the same as A* but where the f-value is computed differently:
, where is a parameter given to the algorithm. In𝑓(𝑛) = 𝑔(𝑛) + ε ℎ(𝑛) ε ≥ 1
general, the larger the value of ε, the faster the search is, and the higher cost of the
goal found.
Pseudocode for weighted A* tree search is given below. NOTE: The only differences
from the A* tree search pseudocode presented in the lectures are: (1) fringe is
assumed to be initialized with the start node before this function is called (this will be
important later), and (2) now Insert takes ε as a parameter soit can compute the
correct f-value of the node.
1: function Weighted-A*-Tree-Search(problem, fringe, ε)
2: loop do
3: if fringe is empty then return failure
4: node ← Remove-Front(fringe)
5: if Goal-Test(problem, State[node]) then return node
6: for child-node in child-nodes do
7: fringe ← Insert(child-node, fringe, ε)
a) We’ll first examine how weighted A* works on the following graph:
24
Resolução de problemas por meio de busca
Execute weighted A* on the above graph with ε = 2, completing the following
table. To save time, you can optionally just write the nodes added to the fringe,
with their g and f values.
node Goal? fringe
- - {𝑆 : 𝑔 = 0, 𝑓 = 16}
𝑆 No { }𝑆→𝐴: 𝑔 = 5, 𝑓 = 7; 𝑆→𝐵 : 𝑔 = 6, 𝑓 = 20
𝑆→𝐴 No { }𝑆→𝐴→𝐺1 : 𝑔 = 15, 𝑓 = 15; 𝑆→𝐵 : 𝑔 = 6, 𝑓 = 20
𝑆→𝐴→𝐺1 Yes -
b) After running weighted A* with weight ε ≥ 1 a goal node G is found, of cost
g(G). Let C ∗ be the optimal solution cost, and suppose the heuristic is
admissible. Select the strongest bound below that holds, and provide a proof.
● g(𝐺) ≤ ε 𝐶*
When weighted A* terminates, an ancestor n of the optimal goal G∗ is on the fringe. Since G was
expanded before n, we have As a result:𝑓(𝐺) ≤ 𝑓(𝑛).
𝑔(𝐺) = 𝑓(𝐺)≤ 𝑓(𝑛) = 𝑔(𝑛) + εℎ(𝑛)≤ ε (𝑔(𝑛) + ℎ(𝑛))≤ ε 𝐶*
If you’re confused about whether this all comes from, rembmer that 𝑓(𝑛) = 𝑔(𝑛) + εℎ(𝑛)
comes from the problem statement and the inequality is𝑔(𝑛) + εℎ(𝑛) ≤ ε(𝑔(𝑛) + ℎ(𝑛))
true by algebra.
Since we know that g(n) is non-negative, it must be true that
This is a common technique used when trying to𝑔(𝑛) + εℎ(𝑛) <= ε(𝑔(𝑛) + ℎ(𝑛)).
prove/find a bound.
25
Resolução de problemas por meio de busca
o 𝑔(𝐺)≤ 𝐶* + ε
o 𝑔(𝐺)≤ 𝐶* 2 ε 
o 𝑔(𝐺)≤ 2ε𝐶* 
o 𝑔(𝐺) ≤ ε2𝐶*
Proof: (Partial credit for reasonable proof sketches.)
c) Weighted A* includes a number of other algorithms as special cases. For each
of the following, name the corresponding algorithm.
i. ε = 1.
Algorithm: A*
ii. ε = 0
Algorithm: UCS
iii. ε → ∞ (i.e., as ε becomes arbitrarily large).
Algorithm: Greedy search
d) Here is the same graph again:
]
i. Execute weighted A* on the above graph with ε = 1, completing the
following table as in part (a):
node Goal? fringe
- - {𝑆 : 𝑔 = 0, 𝑓 = 8}
𝑆 No {S → A : g = 5, f = 6; S → B : g = 6, f = 13}
𝑆→𝐴 No {S → B : g = 6, f = 13; S → A → G1 : g = 15, f = 15}
26
Resolução de problemas por meio de busca
𝑆→𝐵 No {{S → B → C : g = 7, f = 8; S → A → G1 : g = 15, f = 15}
S → B → C No {S → B → C → D : g = 8, f = 10; S → B → C → G2 : g = 13, f = 13; S → A
→ G1 : g = 15, f = 15}
S → B → C → D No {S → B → C → D → G3 : g = 10, f = 10; S → B → C → G2 : g = 13, f = 13;
S → A → G1 : g = 15, f = 15}
S → B → C → D →
G3
3 Yes -
ii. You’ll notice that weighted A* with ε = 1 repeats computations
performed when run with ε = 2. Is there a way to reuse the
computations from the ε = 2 search by starting the ε = 1 search with a
different fringe? Let F denote the set that consists of both (i) all nodes
the fringe the ε = 2 search ended with, and (ii) the goal node G it
selected. Give a brief justification for your answer.
o Use F as new starting fringe
o Use F with goal G removed as new starting fringe
● Use F as new starting fringe, updating the f-values to account for
the new ε
o Use F with goal G removed as new starting fringe, updating the
f-values to account for the new ε
o Initialize the new starting fringe to all nodes visited in previous
search
o Initialize the new starting fringe to all nodes visited in previous
search, updating the f-values to account for the new ε
o It is not possible to reuse computations, initialize the new
starting fringe as usual Justification:
Justification:
We have to include G in the fringe as it might still be optimal (e.g. if it is the only
goal). We don’t have to update the g-values, but we do have the update the f-values
to reflect the new value of ε. With these modifications, it is valid to continue
searching as the state of the fringe is as if A* with the new ε was run, but with some
extraneous node expansions.
Here is the same graph again:
27
Resolução de problemas por meio de busca
iii. Now re-run the = 1 search for the above graph using the fringe you
selected in the previous question.
node Goal? fringe
- - {𝑆 → 𝐵 : 𝑔 = 6, 𝑓 = 13; 𝑆 → 𝐴 → 𝐺1 : 𝑔 = 15, 𝑓 = 15}
S → B No {𝑆 → 𝐵 → 𝐶 : 𝑔 = 7, 𝑓 = 8; 𝑆 → 𝐴 → 𝐺1 : 𝑔 = 15, 𝑓 = 15}
S → B → C No {S → B → C → D : g = 8, f = 10; S → B → C → G2 : g = 13, f = 13; S →
A → G1 : g = 15, f = 15}
S → B → C →
D
No {S → B → C → D → G3 : g = 10, f = 10; S → B → C → G2 : g = 13, f =
13; S → A → G1 : g = 15, f = 15}
S → B → C →
D → G3
Yes -
Questão 19
Consider the state space search problem shown to the
right. A is the start state and the shaded states are goals.
Arrows encode possible state transitions, and numbers by
the arrows represent action costs. Note that state
transitions are directed; for example, A → B is a valid
transition, but B → A is not. Numbers shown in diamonds
are heuristic values that estimate the optimal (minimal) cost from that node to a goal.
For each of the following search algorithms, write down the nodes that are removed
from fringe in the course of the search, as well as the final path returned. Because the
original problem graph is a tree, the tree and graph versions of these algorithms will do
the same thing, and you can use either version of the algorithms to compute your
answer.
Assume that the data structure implementations and successor state orderings are all
such that ties are broken alphabetically. For example, a partial plan S → X → A would
be expanded before S → X → B; similarly, S → A → Z would be expanded before S → B
→ A.
a) Depth-First Search (ignores costs)
Nodes removed from fringe:
28
Resolução de problemas por meio de busca
A, B, E, F
Path returned:
A, B, F
b) Breadth-First Search (ignores costs)
Nodes removed from fringe:
A, B, C, D
Path returned:
A, D
c) Uniform-Cost Search
Nodes removed from fringe:
A, C, B, G
Path returned:
A, C, G
d) Greedy Search
Nodes removed from fringe:
A, D
Path returned:
A, D
e) A* Search
Nodes Removed from fringe:
A, C, G
Path returned:
A, C, G
Questão 20
For the following questions, consider the search problem shown on the left. It has only
three states, and three directed edges. A is the start node and G is the goal node. To
the right, four different heuristic functions are defined, numbered I through IV.
h(A) h(B)
h(G)
I 4 1 0
II 5 4 0
III 4 3 0
IV 5 2 0
29
Resolução de problemas por meio de busca
a) Admissibility and Consistency For each heuristic function, circle whether it is
admissible and whether it is consistent with respect to the search problem
given above.
Admissible? Consistent?
I Yes No Yes No
II Yes No Yes No
III Yes No Yes No
I
V
Yes No Yes No
II is the only inadmissible heuristic, as it overestimates the cost from 𝐵: ℎ(𝐵) = 4,
when the actual cost to G is 3.
To check whether a heuristic is consistent, ensure that for all paths, h(N) − h(L) ≤ path(N
→ L), where N and L stand in for the actual nodes. In this problem, h(G) is always 0, so
making sure that the direct paths to the goal (A → G and B → G) are consistent is the
same as making sure that the heuristic is admissible. The path from A to B is a different
story.
Heuristic I is not consistent: h(A) − h(B) = 4 − 1 = 3 ≤ path(A → B) = 2.
Heuristic III is consistent: h(A) − h(B) = 4 − 3 = 1 ≤ 2
Heuristic IV is not consistent: h(A) − h(B) = 5 − 2 = 3 ≤2
b) Function Domination
Recall that domination has a specific meaning when talking about heuristic
functions.
Circle all true statements among the following.
1. Heuristic function III dominates IV.
2. Heuristic function IV dominates III.
3. Heuristic functions III and IV have no dominance relationship.
4. Heuristic function I dominates IV.
5.Heuristic function IV dominates I.
6. Heuristic functions I and IV have no dominance relationship.
For one heuristic to dominate another, all of its values must be greater than or equal to
the corresponding values of the other heuristic. Simply make sure that this is the case. If
it is not, the two heuristics have no dominance relationship.
30
Resolução de problemas por meio de busca
Questão 21
Search: Slugs You are once again tasked with planning ways to get various insects out of a
maze. This time, it’s slugs! As shown in the diagram below to the left, two slugs A and B
want to exit a maze via their own personal exits. In each time step, both slugs move,
though each can choose to either stay in place or move into an adjacent free square. The
slugs cannot move into a square that the other slug is moving into. In addition, the slugs
leave behind a sticky, poisonous substance and so they cannot move into any square that
either slug has ever been in. For example, if both slugs move right twice, the maze is as
shown in the diagram below to right, with the x squares unpassable to either slug.
You must pose a search problem that will get them to their exits in as few time steps as
possible. You may assume that the board is of size N by M; all answers should hold for a
general instance, not simply the instance shown above. (You do not need to generalize
beyond two slugs.)
a) How many states are there in a minimal representation of the space? Justify
with a brief description of the components of your state space.
2𝑀𝑁 (𝑀𝑁)2
The state includes a bit for each of the MN squares, indicating whether the square has
been visited (2MN possibilities). It also includes the locations of each slug (MN
possibilities for each of the two slugs).
b) What is the branching factor? Justify with a brief description of the successor
function.
5 × 5 = 25 for the first time step, 4 × 4 = 16 afterwards.
At the start state each slug has at most five possible next locations (North, South, East,
West, Stay). At all future time steps one of those options will certainly be blocked off by
the snail’s own trail left at the previous time step.
Only 4 possible next locations remain.
We accepted both 25 and 16 as correct answers.
c) Give a non-trivial admissible heuristic for this problem.
Max(maze distance of bug A to its exit, maze distance of bug B to its exit). Many other
correct answers are possible.
31
Resolução de problemas por meio de busca
Questão 22
As shown in the diagram on the left, two slugs A and B want to exit a maze via exits 𝐸
1
and . At each time step, each slug can either stay in place or move to an adjacent free𝐸
2
square. A slug cannot move into a square that the other slug is moving into. Either slug
may use either exit, but they cannot both use the same exit. When a slug moves, it
leaves behind a poisonous substance. The substance remains in the square for 2 time
steps; during this time, no slug can move into the poisonous square.
For example, if slugs A and B begin in the positions shown above on the left, and slug A
moves Down 3 steps while slug B moves Right three steps, then the world becomes as
shown above on the right, with ×’s marking the poisonous squares. Note that slug A
does have the option of moving Right from its current position, since the trail from B
will evaporate by the time it arrives.
You must pose a search problem that will get both slugs to the exits in as few time
steps as possible. Assume that the board is of size M by N. While all answers should
hold for a general board, not just the one shown above, you do not need to generalize
beyond two slugs, two exits, or two timesteps of decay for the slug trails.
a) How many states are there in a minimal representation of the space? Justify
with a brief description of the components of your state space.
 (𝑀𝑁)2 · 52
Our state space needs to encode the position of each slug (MN possibilities per slug, so
for both slugs) as well as the slug trails. Note that we only need to track the(𝑀𝑁)2
more recent of the two squares in each trail, since the second square will evaporate
before the next move and so has no effect on the available actions (this is a subtle
point, so we still gave full credit to solutions which tracked both squares). Given a slug’s
location, there are five possible locations for its trail (immediately North, East, South,
West of the slug, or directly underneath the slug if its most recent action was to stay in
place), so there are possibilities for the trails of the two slugs. Note that this52
representation is significantly more efficient than if we had specified the explicit
coordinates of each trail.
32
Resolução de problemas por meio de busca
b) Let d(x, y) denote Manhattan distance between x and and y. Consider three
heuristics, defined in terms of slug locations A and B and exit locations E1 and
E2. Remember that either slug can use either exit, but they must use different
exits.
Definition Explanation
ℎ
1
 = 𝑚𝑎𝑥
𝑠∈{𝐴,𝐵}
 𝑚𝑖𝑛(𝑑(𝑠, 𝐸
1
), 𝑑(𝑠, 𝐸
2
)) 
Return the maximum, over the two slugs, of
the distance from the slug to its closest exit.
ℎ
2
 = 𝑚𝑎𝑥 (𝑑(𝐴, 𝐸
1
), 𝑑(𝐵, 𝐸
2
))
Assign slug A to exit and B to ; then𝐸
1
𝐸
2
return the maximum distance from either
slug to its assigned exit.
ℎ
3
 = 𝑚𝑖𝑛
(𝑒,𝑒')∈{(𝐸
1
,𝐸
2
),(𝐸
2
,𝐸
1
)}
 𝑚𝑎𝑥(𝑑(𝐴, 𝑒), 𝑑(
Return the max distance from a slug to its
assigned exit, under the assignment of slugs
to distinct exits which minimizes this
quantity.
i) Which of these three heuristics are admissible? Fill in all that apply.
● ℎ
1
o ℎ
2
● ℎ
3
 
ii) For each pair of heuristics, fill in the circle which correctly describes
their dominance relationship. Note: dominance is defined regardless of
admissibility.
o dominatesℎ
1
 ℎ
2
 
● dominatesℎ
2
 ℎ
1
o =ℎ
1
ℎ
2
o none
o dominatesℎ
1
 ℎ
3
● ℎ
3
 𝑑𝑜𝑚𝑖𝑛𝑎𝑡𝑒𝑠 ℎ
1
o ℎ
1
 = ℎ
3
 
o none
33
Resolução de problemas por meio de busca
● dominatesℎ
2
ℎ
3
o dominates ℎ
3
ℎ
2
 
o ℎ
2
 = ℎ
3
 
o None
Questão 23
Answer the following questions about the search problem shown above. Break any ties
alphabetically. For the questions that ask for a path, please give your answers in the
form ‘S − A − D − G.’
a) What path would breadth-first graph search return for this search problem?
S – G
b) What path would uniform cost graph search return for this search problem?
S − A − C − G
c) What path would depth-first graph search return for this search problem?
S − A − B − D – G
d) What path would A* graph search, using a consistent heuristic, return for this
search problem?
S − A − C − G
e) Consider the heuristics for this problem shown in the table below.
State ℎ
1
ℎ
2
S 5 4
34
Resolução de problemas por meio de busca
A 3 2
B 6 6
C 2 1
D 3 3
G 0 0
i) Is admissible? Yes Noℎ
1
ii) Is consistent? Yes Noℎ
1
iii) Is admissible? Yes Noℎ
2
iv) Is consistent? Yes Noℎ
2
An admissible heuristic must underestimate or be equal to the true cost. A consistent
heuristic must satisfy for all paths and nodes N and L.ℎ(𝑁) − ℎ(𝐿) ≤ 𝑝𝑎𝑡ℎ(𝑁 → 𝐿)
h1 overestimates the cost S → G as 5 when it is 4, so it is inadmissible.
h1 is not consistent because is violated as 5 − 3 ≤ 1.ℎ(𝑆) − ℎ(𝐴) ≤ 𝑝𝑎𝑡ℎ(𝑆 → 𝐴)
h2 does not overestimate costs and is admissible.
h2 is not consistent because is violated as 4 − 2 ≤ 1.ℎ(𝑆) − ℎ(𝐴) ≤ 𝑝𝑎𝑡ℎ(𝑆 → 𝐴)
Questão 24
function A* Graph Search(problem)
fringe ← an empty priority queue
fringe ← Insert(Make-Node(Initial-State[problem]), fringe)
closed ← an empty set
Add Initial-State[problem] to closed
loop
if fringe is empty then
return failure
end if
node ← Remove-Front(fringe)
if Goal-Test(problem, State[node]) then
return node
end if
for successor in GetSuccessors(problem, State[node]) do
if successor not in closed then
Add successor to closed
fringe ← Insert(Make-Successor-Node(successor, node), fringe)
end if
end for
end loop
end function
The above implementation of A* graphsearch may be incorrect! In the list below circle
35
Resolução de problemas por meio de busca
all of the problems that
the bugs may cause when executing graph search and justify your answer. Note that
the fringe is a priority queue. Nodes are inserted into the fringe using the standard key
for A*, namely h is a consistent heuristic.𝑓 = 𝑔 + ℎ.
a) The GetSuccessors function could be called multiple times on the same state.
b) The algorithm is no longer complete.
c) The algorithm could return a suboptimal solution.
d) The implementation is incorrect, but none of the above problems will be caused.
e) The implementation is correct.
To receive any credit you must briefly justify your answer in space below.
The bug is the insertion of successor into closed at time of insertion of a node into the
fringe, rather than at
the time that node gets popped from the fringe. As a consequence of this bug, the first
path encountered to a
state will put that state in the closed list. This can cause suboptimality as we only have
the guarantee that a
state has been reached optimally once a node reaching it gets popped off the fringe.
a) is False as when a node that reaches a state s is placed in the fringe, that state s
is also put on the closed
list. This means never in the future can a node be placed on the fringe that ends
in that same state s, and hence the same state s can be the argument to
GetSuccessors at most once.
b) is False. A* tree search is complete. The difference is that the above algorithm
will cut off parts of the tree
search whenever it has placed a node on the fringe in the past that ends in the
same state. So compared
to tree search we only lose copies of subtrees that we are covering. Hence the
above algorithm is complete.
c) is True. See explanation at beginning of solution.
d) is False.
e) is False.
Questão 25
If a search problem has only a single goal state, it is common to perform bidirectional
search. In bidirectional search you build two search trees at the same time: the
“forward” search tree is the one we have always worked with in CS188, the “backward”
search tree is one that starts from the goal state, and calls a predecessor (rather than
successor) function to work its way back to the start state. Both searches use the same
36
Resolução de problemas por meio de busca
cost function for transitioning between two states. There will now also be a backward
heuristic, which for each state estimates the distance to the start state. Bidirectional
search can result in significant computational advantages: the size of the search tree built
grows exponentially with the depth of the search tree. If growing a tree from start and
goal to each other, these two trees could meet in the middle, and one ends up with a
computational complexity of just twice searching a tree of half the depth, which are very
significant savings.
Recall the pseudo-code for a standard A* graph search
function Graph-Search(problem)
forward-closed <-- empty set
forward-priority-queue <-- Insert(Make-Node(Start-State(problem)),
forward-priority-queue)
LOOP DO
IF forward-priority-queue is empty THEN return failure
IF forward-priority-queue is not empty THEN
node <-- pop(forward-priority-queue)
IF (State(node) == Goal-State(problem) ) THEN return node
IF State(node) is not in forward-closed THEN
add State(node) to forward-closed
forward-priority-queue <-- Insert-All(ExpandForward(node, problem),
forward-priority-queue)
END // LOOP
Now consider the following tentative pseudo-code for bidirectional A* search. We
assume a consistent forward heuristic, and a consistent backward heuristic.
Concatenation is a function that builds a plan that goes from start state to goal state by
combining a forward partial plan and a backward partial plan that end in the same
state.
function Bidirectional-Graph-Search(problem)
forward-closed <-- empty set
backward-closed <-- empty set
forward-priority-queue <-- Insert(Make-Node(Start-State(problem)),
forward-priority-queue)
backward-priority-queue <-- Insert(Make-Node(Goal-State(problem)),
backward-priority-queue)
LOOP DO
IF forward-priority-queue is empty AND backward-priority-queue is
empty THEN return failure
1 IF there exist a node n1 in forward-priority-queue and a node n2 in
backward priority queue ...
37
Resolução de problemas por meio de busca
1 such that State(n1) == State(n2) THEN
1 return Concatenation of n1 and n2
IF forward-priority-queue is not empty THEN
node <-- pop(forward-priority-queue)
IF ( State(node) == Goal-State(problem) ) THEN return node
2 IF ( State(node) is in backward-priority-queue ) THEN
2 return Concatenation of node and matching node in
backward-priority-queue
3 IF ( State(node) is in backward-closed ) THEN
3 return Concatenation of node and matching node in
backward-closed
IF State(node) is not in forward-closed THEN
add State(node) to forward-closed
forward-priority-queue <-- Insert-All(ExpandForward(node,
problem), forward-priority-queue)
IF backward-priority-queue is not empty THEN
node <-- pop(backward-priority-queue)
IF ( State(node) == Start-State(problem) ) THEN return node
4 IF ( State(node) is in forward-priority-queue ) THEN
4 return Concatenation of node and matching node in
forward-priority-queue
5 IF ( State(node) is in forward-closed ) THEN
5 return Concatenation of node and matching node in
forward-closed
IF State(node) is not in backward-closed THEN
add State(node) to backward-closed
backward-priority-queue <-- Insert-All(ExpandBackward(node,
problem), backward-priority-queue)
END // LOOP
a) The IF statements labeled 1, 2, 3, 4, 5 are modifications to try to connect both
search trees.
i) If cutting out all lines of code labeled 1, 2, 3, 4, or 5, will
Bidirectional-Graph-Search return an optimal solution? Briefly
justify your answer.
Yes. It will simply run two A∗ searches in parallel, without any interaction. One from
start to goal, and one from goal to start. Each one of them individually would return an
optimal solution, and in case of running them in parallel it will be whichever one
finishes first that will be returning an optimal solution.
38
Resolução de problemas por meio de busca
ii) If amongst the numbered lines of code we only retain 1, is
Bidirectional-Graph-Search guaranteed to be optimal? Briefly
justify your answer.
No. Consider the following example where it would not find the optimal solution: Have
a state space graph with states S, A, B, C, G, with edges and respective costs: S − A: 1; S
− B: 5, A − C: 1, C − G:1, B −G: 5. Assume the heuristic is zero everywhere. Enabling
code section 1 will result in finding the path S − B − G with cost 10, whereas the optimal
path is S − A − C − G with cost 2.
iii) If amongst the numbered lines of code we only retain 2, is
Bidirectional-Graph-Search guaranteed to be optimal? Briefly
justify your answer.
No. Consider the same example as in the previous subquestion. Enabling code section 2
will result in finding the path S − B − G, which is suboptimal.
iv) If amongst the numbered lines of code we only retain 3, is
Bidirectional-Graph-Search guaranteed to be optimal? Briefly
justify your answer.
No. Consider the following state space graph: states are S, A, G, edges and costs are S −
A: 4, A − G: 4, S − B: 3, B − C: 3, C − G: 3. Assume the heuristics are: A to G: 4; A to S: 4,
B to G: 3, B to S: 0, C to G: 0, C to S: 3. In the first iteration we will expand S and G on
their respective priority queues. In the second iteration we will expand S − B and G − C.
In the third iteration we will expand S − B − C and notice that C is on the backward
closed list, hence declare success for S − B − C − G, which is not optimal. Intuitively:
enabling code section 3 ensures that when success is declared in section 3 we have
found the shortest path between S and G that goes through the current State(node),
but we can only guarantee this plan to be optimal if none of the plans in the backward
priority queue has an f-cost lower than this just found path’scost. The extension that
would work would be to keep track of such found paths, but then only declare success
once the f costs in their respective queues have gone above their path cost. This was a
tricky question the way we set it up, and we decided to give full credit even if going
wrong on code sections 3 and 5.
v) If amongst the numbered lines of code we only retain 4, is
Bidirectional-Graph-Search guaranteed to be optimal? Briefly
justify your answer.
No. Consider the same example as in the question about code section 2. Enabling code
section 2 will result in finding the path S − B − G, which is suboptimal.
vi) If amongst the numbered lines of code we only retain 5, is
39
Resolução de problemas por meio de busca
Bidirectional-Graph-Search guaranteed to be optimal? Briefly
justify your answer.
No. Consider the following state space graph: states are S, A, B, G, edges and costs are
S − A: 3, A − G: 3, S − B: 4, B − G: 4. Assume the heuristics are: A to G: 3, A to S: 3, B to
G: 1, B to S: 1, S to G: 4, G to S: 4. Then in the first iteration S and G will be expanded. In
the second iteration S − B and G − B will be expanded, and in the expansion of G − B the
algorithm would declare success.
vii) Which numbered code section(s) should be retained to
maximally benefit from the bidirectional search and at the same
time retain optimality guarantees?
None can be retained while maintaining optimality guarantees. See explanation about
code section 3 for a hint at how you might be able to do better.
Questão 26
Consider the search graph shown below. S is the start state and G is the goal state. All
edges are bidirectional.
For each of the following search strategies, give the
path that would be returned, or write none if no
path will be returned. If there are any ties, assume
alphabetical tiebreaking (i.e., nodes for states earlier in the alphabet are expanded first
in the case of ties).
a) Depth-first graph search
S-B-E-F-G
b) Breadth-first graph search
S-C-G
c) Uniform cost graph search
S-B-E-G
40
Resolução de problemas por meio de busca
d) Greedy graph search
S-B-E-G
e) A* graph search
S-B-E-G
For the following question parts, all edges in the graphs discussed have cost
1.
f) Suppose that you are designing a heuristic h for the graph on the
right. You are told that h(F) = 0.5, but given no other information.
What ranges of values are possible for h(D) if the following
conditions must hold? Your answer should be a range, e.g.
. You may assume that h is nonnegative.2 ≤ ℎ(𝐷) < 10
i. h must be admissible
0 ≤ h(D) ≤ 3
The path to goal from D is 3
ii. h must be admissible and consistent
0 ≤ ℎ(𝐷) ≤ 2. 5 
In order for h(E) to be consistent, it must hold that , sinceℎ(𝐸) − ℎ(𝐹) ≤ 1
the path from E to F is of cost 1. Similarly, it must hold
𝑡ℎ𝑎𝑡 ℎ(𝐷) − ℎ(𝐹) = ℎ(𝐷) − 0. 5 ≤ 2, 𝑜𝑟 ℎ(𝐷) ≤ 2. 5.
g) Now suppose that , and all otherℎ(𝐹) = 0. 5, ℎ(𝐸) = 1. 1
heuristic values except h(B) are fixed to zero (as shown on the right).
For each of the following parts, indicate the range of values for h(B)
that yield an admissible heuristic AND result in the given expansion
ordering when using A* graph search. If the given ordering is
impossible with an admissible heuristic, write none. Break ties
alphabetically. Again, you may assume that h is nonnegative.
i. B expanded before E expanded before F
1.0 ≤ ℎ(𝐵) ≤ 1. 1
ii. E expanded before B expanded before F
1. 1 < ℎ(𝐵) ≤ 1. 5
41
Resolução de problemas por meio de busca
Questão 27
The following implementation of graph search may be incorrect. Circle all the problems
with the code.
function Graph-Search(problem, fringe)
closed ← an empty set,
fringe ← Insert(Make-Node(Initial-State[problem]), fringe)
loop
if fringe is empty then
return failure
end if
node ← Remove-Front(fringe)
if Goal-Test(problem,State[node]) then
return node
end if
add State[node] to closed
fringe ← InsertAll(Expand(node, problem), fringe)
end loop
end function
1. Nodes may be expanded twice.
2. The algorithm is no longer complete.
3. The algorithm could return an incorrect solution.
4. None of the above.
The stated algorithm is equivalent to tree search. In graph search, nodes added to the
“closed” list should not be expanded again. Since this algorithm does not do that, it can
get stuck in a loop and that is why it is not complete.
a) The following implementation of graph search may be incorrect. You may𝐴*
assume that the algorithm
is being run with a consistent heuristic. Circle all the problems with the code.
function A*-Search(problem, fringe)
closed ← an empty set
fringe ← Insert(Make-Node(Initial-State[problem]), fringe)
loop
if fringe is empty then
return failure
end if
node ← Remove-Front(fringe)
if State[node] is not in closed then
add State[node] to closed
42
Resolução de problemas por meio de busca
for successor in GetSuccessors(problem, State[node]) do
fringe ← Insert(Make-Node(successor), fringe)
if Goal-Test(problem,successor) then
return successor
end if
end for
end if
end loop
end function
1. Nodes may be expanded twice.
2. The algorithm is no longer complete.
3. The algorithm could return an incorrect solution.
4. None of the above.
The stated algorithm expands fewer nodes to find a goal, but it does not always find
the optimal goal in terms of cost. Note that “incorrect” means that it “not optimal”
here.
Questão 28
Consider the following state space graph where the directed arcs represent the legal
successors of a node. The cost of moving to a successor node is given by the number on
the arc. The value of a heuristic function, h, if computed at a state, is shown inside each
node. The start state is S and the goal is G.
When a node is expanded, assume its children are put in the Frontier set in
alphabetical order so that the child closest to the front of the alphabet is removed
before its other siblings (for all uninformed searches and for ties in informed searches).
For each of the search methods below, give (i) the sequence of nodes removed from
the Frontier (for expansion or before halting at the goal), and (ii) the solution path
found.
43
Resolução de problemas por meio de busca
a) Uniform-Cost graph search (i.e., use an Explored set)
Nodes removed: S B A D C E G
Solution: S B D G
b) Greedy Best-First tree search (i.e., no repeated state checking)
Nodes removed: S A G
Solution: S G
c) A* tree search (i.e., no repeated state checking)
Nodes removed: S A D B D G
Solution: S B D G
Questão 29
a) True or False: Depth-First search using iterative deepening can be made to
return the same solution as Breadth-First search.
True
b) True or False: In a finite search space containing no goal state, A* will always
explore all states.
True
c) True or False: The solution path found by Uniform-Cost search may change if we
add the same positive constant, c, to every arc cost.
True. For example, say there are 2 paths S → A → G and S → G where cost(S,A) = 1,
cost(A,G) = 1, and cost(S,G) = 3. So the optimal path is through A. If we now add 2 to
each cost, the optimal path goes directly from S to G and UCS will now find this new
path.
d) True or False: If h is a consistent heuristic, then h is also an admissible heuristic.
True. A heuristic is consistent iff for every node n and every successor n′ of n generated
by any action a, h(n) ≤ c(n, a, n′) + h(n′). One simple proof is by induction on the number
k of nodes on the shortest path to any goal from n. For k = 1, let n′ be the goal node;
then h(n) ≤ c(n, a, n′). For the inductive case, assume n′ is on the shortest path k steps
from the goal and that h(n′) is admissible by hypothesis; then h(n) ≤ c(n, a, n′) + h(n′) ≤
c(n, a, n′) + h∗(n′) = h∗(n) so h(n) at k + 1 steps from the goal is also admissible.
e) True or False: A* search will always expand fewer nodes than Uniform-Cost
search.
44
Resolução de problemas por meio de busca
False
f) Suppose you are using a Genetic Algorithm. Two individuals (i.e., candidate
solutions) in the currentgeneration are given by 8-digit sequences: 1 4 6 2 5 7 2
3 and 8 5 3 4 6 7 6 1.
i) What is the result of performing 1-point crossover with a
cross-point between the third and fourth digits?
1 4 6 4 6 7 6 1 and 8 5 3 2 5 7 2 3
ii) If there are n individuals in the current generation, how many
crossover operations are used to produce the next generation?
If there are n individuals in the current generation, then there should be n individuals in
every generation. Crossover takes two individuals from the current generation and
generates two children individuals in the next generation. Hence n/2 crossover
operations are used.
Questão 30
a) A* search can be made to perform a Breadth-First search by setting, for all
nodes, n, h(n) = ? and, for all arcs, arc cost = ?
h(n) = 0 (or any constant) and arc cost = 1 (or any constant)
b) Depth-First search (DFS) can be made to return the same solution as
Breadth-First search by augmenting DFS how?
Add iterative-deepening with increments of the depth bound by 1 at each iteration
in DFS.
c) To avoid maintaining an Explored set of already expanded nodes during A*
search with an admissible heuristic, h, what additional condition can be added
so as to guarantee finding an optimal solution while not maintaining an
Explored set? Name and define it.
Add the consistency (aka monotonicity) condition, which means h(n) ≤ c(n, n′) +
h(n′) where n is a node, n′ is a successor of n, and c(n, n′) is the cost of the action in
going from state n to state n′. In other words, a kind of triangle inequality condition
on arc costs and heuristic costs.
45
Resolução de problemas por meio de busca
d) Say we define an evaluation function for a heuristic search problem as
where g(n) is the cost of the best𝑓(𝑛) = (𝑤 * 𝑔(𝑛)) + ((1 – 𝑤) * ℎ(𝑛))
path found from the start state to state n, h(n) is an admissible heuristic
function that estimates the cost of a path from n to a goal state, and 0.0 ≤ w ≤
1.0. What search algorithm do you get when:
i) w = 0.0
Greedy Best-First search
ii) w = 0.5
A* algorithm
iii) w = 1.0
Uniform-Cost search
Questão 31
Consider A* search on the following grid, with initial state A and goal state G, and one
can move left, right, up, or down one step at a time (no wrapping around). The cost g is
the number of moves taken, and the heuristic h is the Manhattan distance to G.
At the moment that A* declares success, which states remain in OPEN?
a) ABDEG
b) ABDE
c) ABE
d) BE
e) none of the above
Questão 32
Say your search problem has a special structure: the state space form a chain
s1→s2→s3→⋯→sn, where s1 is the initial state and sn is the only goal. All states are
distinct, all edges have the same cost, and it is possible to compute the predecessor
function. Which search algorithm should you avoid: BFS, DFS, uniform cost search,
iterative deepening, or bidirectional search?
46
Resolução de problemas por meio de busca
All these algorithms can find the goal with similar space requirement (1 or 2). The
difference is in time complexity: all are O(n) except for iterative deepening, which is
O(n^2). We should avoid iterative deepening. This seems counterintuitive, but is caused
by the very small branching factor.
Questão 33
If h(s) and i(s) are both admissible heuristic functions, what values of p will guarantee
that is also an admissible heuristic function?
p has to be no bigger than 1. Otherwise, p*h(s) when h(s)=H is the true cost will not be
admissible. The same argument on i(s) leads to p no smaller than zero. Then, ph+(1p)i
<= pH+(1p)H=H. So, p in [0,1]. One can also use a convex combination argument.
Questão 34
List the states in the order of being examined by A* search. Show repeats if any.
A(0+1), {B(2+0,A), C(1+2,A)}
B(2+0,A) {C(1+2,A), D(3+1,B)}
C(1+2,A) {D(3+1,B), D’(2+1,C)}
D’(2+1,C) {D(3+1,B), G(5+0,D’)}
D(3+1,B) {G(5+0,D’), G(6+0,D)}
G(5+0,D’)
The states are A,B,C,D,D,G
Questão 35
Two friends live in different cities on a map. On each turn, we can simultaneously move
each friend to a neighboring city on the map or stay in the same city. The amount of
time needed to move from city i to neighbor j is equal to the road distance D(i,j)
between the cities. But on each turn the friend that arrives first must wait until the
other one arrives (and calls the first on her cellphone) before the next turn can begin.
We want the two friends to meet as quickly as possible.
a) Let S(i,j) be the straightline distance between cities i and j . Let one friend be at city i
and the other friend be at city k. Circle the heuristic functions below that are
admissible.
i. min ( max(D(i, ), D(k, ) )) {j in all cities} j j
No, it might be faster to go through an intermediate city.
ii. min (max (S(i, ), S(k, )) ) {j in all cities} j j yes, this is physics
47
Resolução de problemas por meio de busca
b) Are there completely connected maps for which no solution exists?
No, they can always meet
c) Are there maps in which all solutions require one friend to visit the same city twice?
No, he might as well stay in that city.
Questão 36
You have two jugs, measuring 3 gallons and 4 gallons, and a water faucet. You can fill
the jugs up or empty them out from one to another or onto the ground. You need to
measure out exactly 2 gallons.
a) Let state (a, b) mean the amount of water in the 3 and 4 gallon jugs,
respectively. Define all successors of this state.
(3, b); if a < 3
(a, 4); if b < 4
(0, b); if a > 0
(a, 0); if b > 0
(3, b − (3 − a) = a + b − 3); if a < 3 and a + b > 3
(a + b, 0); if a < 3 and b > 0 and a + b <= 3
The two above can be combined into (min(a + b,3), max(a + b − 3,0))
(a − (4 − b) = a + b − 4, 4); if b < 4 and a + b > 4
(0, a + b); if b < 4 and a > 0 and a + b <= 4
The two above can be combined into (max(a + b − 4,0), min(a + b,4))
b) Write down a solution path from (3, 4) to a goal state. You do not need to show
how you find this path.
(3, 4) − (3, 0) − (0,3) − (3,3) − (2,4) or
(3, 4) − (0, 4) − (3,1) − (0,1) − (1,0) − (1,4) − (3,2)
c) Let the cost of every edge be 1. Consider the function h(a, b) = |a − b|. Is h an
admissible heuristic? Justify your answer.
No. On many goal states this h is not zero. On the first solution path, (0,3) has
actual cost 2 (i.e. two steps away from goal) but h(0, 3) = 3 > 2 . Similarly, on the
2nd solution path, (1,4) has actual cost 1 but h(1,4) = 3 > 1.
Questão 37
Consider the following pathfinding problem. One can move from one small triangle to
another if they share a vertex (e.g., A can go to B and C). However, the goal G can only
be accessed from F. The number after th e letter is the heuristic
48
Resolução de problemas por meio de busca
function value for that state. The actual cost of each move is as follows:
● A move down one level (e.g. A→C or B→ E) costs 1
● A move sideways on the same level (e.g. C→B or E→ F ) costs 2
● A move up one level (e.g. B→ A or C→ A ) costs 3
a) Perform DepthFirst Search , starting from A, using pathchecking to avoid
repeated states if they occur on the path back to the root in the search tree.
Expand successors in alphabetical order. Show your search tree, and circle
states that are expanded. What is the cost of your solution path?
Cost=11
b) Perform A* Search, starting from A. Break ties alphabetically. Show the
expanded states and the priority queue contents at each step. What is the cost
of your solution path?
Expanded states
A(0+2)
C(1+1)
B(1+2)
F(2+1)
E(2+2)
D(2+3)
G(5+0)
priority queue
A(0+2)
B(1+2), C(1+1)
B(1+2) D(2+3), E(2+2),
D(2+3), E(2+2), F(2+1),
D(2+3), E(2+2), G(5+0),
D(2+3), G(5+0), H(3+3)
G(5+0), H(3+3)
H(3+3)
Path: ACFG, cost=5
49
Resolução de problemas por meio de busca
Questão 38
Consider the following search space where we want to find a path from the start state
S to the goal state G. The table shows three different heuristic functions h1, h2, and h3.
a) What solution path is found by Greedy Bestfirst search using h2? Break ties
alphabetically.
S, A, G
b) What solution path is found by UniformCost search?Break ties
alphabetically.
Sequence of nodes expanded: S, B, D, C, A, G
Solution path: S, B, C, G
c) Give the three solution paths found by algorithm A using each of the three
heuristic functions, respectively. Break ties alphabetically.
h0: This is the same as uniformcost search, so the answer is the same as (b).
That is, the solution path is: S, B, C, G
h1: S, B, C, G expanded; solution: S, B, C, G
h2: S, B, D, G expanded; solution: S, B, D, G
Questão 39
a) Consider the 8puzzle in which there is a 3 x 3 board with eight tiles numbered 1
through 8. The goal is to move the tiles from a start configuration to a goal
configuration, where a move consists of a horizontal or vertical move of a tile into an
adjacent position where there is no tile. Each move has cost 1.
(i) Is the heuristic function defined by admissible , where di is the
number 8 i=1 α1 1 di of vertical plus the number of horizontal moves of tile i from its
current position to its goal position assuming there are no other tiles on the board, and
0 ≤ ai ≤ 1 is a constant weight associated with tile i? Explain briefly why or why not.
Yes, it is admissible because each di is a lower bound on the number of moves to get
each tile to its goal position and the weights decrease those values.
(ii) Is the heuristic defined by h(n) = 8 – cost(n) admissible , where cost(n) is the
cost from start to node n? Explain briefly why or why not.
No, it is not admissible because, for example, if a start node configuration is only one
move away from the goal configuration, then h(start) = 8 – 0 = 8 but h*(start) = 1. Also,
50
Resolução de problemas por meio de busca
there are situations where h(n) could be negative for some nodes, which is not allowed.
b) Given two arbitrary admissible heuristics, h1 and h2, which composite heuristic is
better to use, max(h1, h2), (h1 + h2)/2, or min(h1, h2)? Explain briefly why.
Max(h1, h2) is best because it is admissible but greater than or equal to the other two
composite heuristics for all nodes.
Questão 40
Consider the search space below, where S is the start node and G1 and G2 are goal
nodes. Arcs are labeled with the value of a cost function; the number gives the cost of
traversing the arc. Above each node is the value of a heuristic function; the number
gives the estimate of the distance to the goal. Assume that uninformed search
algorithms always choose the left branch first when there is a choice. Assume that the
algorithms do not keep track of and recognize repeated states.
For each of the following search strategies
(a) indicate which goal state is reached first (if any) and
(b) list in order, all the states that are popped off the OPEN list.
Depth-first
(a) G2
(b) S, A, D, H, J, G2
Iterative Deepening
(a) G1
(b) S, A, B, C, S, A, D, H, H, B, H, G1
Breadth-first
(a) G1
51
Resolução de problemas por meio de busca
(b) S, A, B, C, D, H, H, G1
Greedy
(a) G2
(b) S, C, A, D, H, E, J, G2
A*
(a) G1
(b) S, A, C, D, E, H, B, G1
52