CSC 361: Tutorial 3

Heuristic Search

Exercise 1: (Greedy Search)

Solve the following 8-puzzle problem using Greedy search algorithm as search strategy and h1() as heuristic:

-h1(n): the number of misplaced tiles for the current node n

Exercise 2: (A*)

•Solve the following 8-puzzle problem using A* search algorithm as search strategy and the following function f(n) as heuristic: f(n)=g(n)+h(n)

–h(n):the number of misplaced tiles

–g(n):the number of steps from the initial state

Exercise 3: (A*)

•Solve the following 8-puzzle problem using A* search algorithm as search strategy and the following function f(n) as evaluation function: f(n)=g(n)+h(n)

–h(n):the Manhattan Distance

–g(n):the number of steps from the initial state

Exercise 4: (Greedy Search, A*, and Maze Traversal)

•Consider the following problem.

•Give a formulation for this problem.

•Solve this problem using greedy Search and A* with Manhattan Distance as heuristic function.

Exercise 5: (A* and Maze Traversal)

•Consider the following problem: Maze Traversal

-Where A3 is the Starting node and E2 the End node.

•Give a formulation for this problem.

•The problem is to get from square A3 to the square E2, one step at a time, avoiding obstacles. Solve this problem using A* algorithm with Manhattan distance as heuristic. The operators are to be used in this order: go-left, go-right and go-down. Each operator costs 1.

•Solve this problem using IDA*.

Exercise 6: (Greedy Best first search, A*)

-Consider the following Map:

Distance between citiesh(): SLD heuristic

Questions

  1. Is h() admissible? Explain.
  2. We wish to move from Hannover to Munchen. Find the shortest path using:
  1. Gready search with SLD as heuristic.
  2. A* algorithm.

Exercise 7: (IDA*)

•Solve the following 8-puzzle problem using IDA* search algorithm as search strategy and the following function f(n) as evaluation function: f(n)=g(n)+h(n)

–h(n):the number of misplaced tiles

–g(n):the number of steps from the initial state

Exercise 8: (BFS, DFS, A*)

Given the following graph where S is the starting node and G is the goal node. Numbers related to arcs between nodes indicate step costs.

  1. Trace Graph-Search algorithm using BFS and DFS strategies. In each case, show the order in which nodes are added to the fringe as well as the generated tree and the solution path. Leftmost nodes are added before rightmost ones. Indicate if found solutions are optimal.

To check for repeated states, use the following simple strategy: Do not add a state as a leaf if that state is on the path from the root to the current node.

  1. Given the heuristic function h for which values are given in table below:

Node n / S / A / D / B / E / F / G
h (n) / 9 / 7 / 10 / 5 / 3 / 2 / 0
  1. Is h() admissible? Why.
  1. Solve this problem using A*. Show values of the evaluation function as well as the state of the fringe and the solution path.

Exercise 9: (UCS, Greedy Search, A*)

Consider the following graph with start state S and goal state Z. The numbers on the arcs indicate the cost of traversing that arc.

(a) Solve this problem using uniform-cost search, assuming nodes are considered in alphabetical order.

(b) Same as (a), but using the greedy search with the following heuristic functions:

(c) Same as (a), but using the A* search with the following heuristic functions: