CS 311 – Artificial Intelligence (Fall 2015)
Handout 1
Q1)

2

F

E
2

4

B

D

6

3
4

A

H

4
5

3

C

G

3

22

3

K

21
3

I

J

Consider the graph above (not drawn to scale).
Given the heuristic values for the distance to city F: h(A) = 5

h(B) = 3

h(C) = 6

h(D) = 3

h(E) = 2

h(F) = 0

h(G) = 7

h(H) = 8

h(I) = 29

h(J) = 9

h(K) = 8

Draw the search trees resulting from
i) BFS can be performed on the graph ii) DFS iii) Uniform Cost iv) A* search on the graph with start node A.
Q2) Consider the problem of finding a path in the grid shown below from the position s to the position
g. A piece can move on the grid horizontally and vertically, one square at a time. No step may be made into a forbidden shaded area.

1. On the grid, number the nodes in the order in which they are removed from the frontier in a depth-first search from s to g, given that the order of the operators you will test is: up, left, right, then down. Assume there is a cycle check.
2. Number the nodes in order in which they are taken off the frontier for an A* search for the same graph. Manhattan distance should be used as the heuristic function. The Manhattan distance between two points is the distance in the x-direction plus the distance in the y-direction. It corresponds to the distance traveled along city streets arranged in a grid. For example, the
Manhattan distance between g and s is 4. What is the path that is found?
3. Based on this experience, discuss which of the two algorithms is best suited for this problem.
4. Suppose that the graph extended infinitely in all directions. That is, there is no boundary, but s, g, and the forbidden area are in the same relative positions to each other. Which method would no longer find a path? Which would be the best method, and why?
Q3)
1. How can A* be modified to perform like Breadth-First Search?
2. Depth-First search (DFS) can be made to return the same solution as Breadth-First search by augmenting DFS how?
3. Say we define an evaluation function for a heuristic search problem as f(n) = (w ∗ g(n)) + ((1 – w) ∗ h(n)) where g(n) is the cost of the best 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 ii) w = 0.5 iii) w = 1.0
Q4) There are 3 discs with different diameters. We can slide these discs onto 3 perpendicular rods. It's important that if there is a disc under another one then it must be bigger in diameter. We denote the rods with “P”, “Q” and “R”, respectively. The discs are denoted by “1”, “2” and “3”, respectively, in ascending order of diameter. The initial state of discs can be seen in the figure below:

We can slide a disc onto another rod if the disc
• is on the top of its current rod, and
• the discs on the goal rod will be in ascending order by size after the replacing.
Our goal is to move all the discs to rod R.
i) Draw a state space representation of the given problem. ii) Generate search space and find the goal using BFS, and DFS. iii) Suggest a heuristic to solve this problem using A*. Note the value of the heuristic should be 0 at the goal state.
Q5) We have 3 jugs of capacities 3, 5, and 8 litres, respectively. There is no scale on the jugs, so it's only their capacities that we certainly know. Initially, the 8-litre jug is full of water, the other two are empty. We can pour water from one jug to another, and the goal is to have exactly 4 litres of water in any of the jugs. The amount of water in the other two jugs at the end is irrelevant.
There is no scale on the jugs and we don't have any other tools that would help.
Suggest a graph based representation for the problem, and apply BFS, DFS and A* to solve the above problem.