## COSC 6368 (Dr. Eick) in Fall 2004 Assignment1: Heuristic Search Second Draft

Assigned: 9/15/04
Due: 10/5/04 in class; problem 5 is due 10/16/04, 11p using electronic submission; submit your report and other material to Yan Wang prior to the deadline! Submit a hardcopy of your report and other materials in the class on Tu., October 19, 2004.
Approximate Problem Weights: 1:** 2:** 3:** 4:* 5:********** 6:*

### Problem 1 --- State-Space Search Representation

In the water-jug puzzle we are given a 3 liter jug, named Three, and a 4 liter jug, named Four. Initially, Three and Four are empty. A jug can be filled from a tap T, and, we can discard the water from either jug into a drain, D. Water may also be poured from one jug into another. There are no other measuring devices. We want to find a set of operations that will leave precisely two liters of water in Four.

(a) Formulate this problem as a state-space search problem Give a precise definition of a state, the start state, the goal state or goal condition, and the operators. Operators should be specified as "schemas" that indicate for a given state, when the operator is legal (i.e., a set of constraints on when the operator can be applied to an arbitrary state) and the description of the successor state after the operator is applied. In other words, each operator should be specified in a way that it would easily implemented in a program to solve this problem.

(b) Show the State Space
Draw the complete state-space graph that includes all nodes (and legal directed arcs connecting these nodes) for this problem. Inside each node show the state description, and label each arc with its associated operator. Highlight a path that gives a solution to the problem.

### Problem 2 --- Using various search techniques

Assume that you have the following search graph, where S is the start node and G1 and G2 are goal nodes. Arcs are labeled with the cost of traversing them and the estimated cost to a goal is reported inside nodes.

(i) For each of the search strategies listed below, (a) indicate which goal state is reached if any, (b) list, in order, the states expanded, and (c) show the final contents of the OPEN and CLOSED lists. (Recall that a state is expanded when it is removed from the OPEN list.) When all else is equal, nodes should be expanded in alphabetical order.

2. depth-first
3. best-first (using f = h)
4. A* (using f = g + h)
5. RBFS (using f=g+h) --- due to the fact that RBFS is a recursive algorithm give the search tree as your answer for RBFS!
6. SMA* (using f=g+h and limiting the open-list to just 3 elements)

#### General Pseudocode for Searching

The following is the basic outline of the search strategy used for breadth-first, depth-first, and best-first search algorithms.

OPEN   = { startNode } // Nodes under consideration.
CLOSED = { }           // Nodes we're done with.

while OPEN is not empty
{
remove an item from OPEN based on search strategy used
- call it X

if goalState?(X) return the solution found

otherwise // Expand node X.
{
2) generate the immediate neighbors (ie, children of X)
3) eliminate those children already in OPEN or CLOSED
4) add REMAINING children to OPEN
}
}
return FAILURE  // Failed if OPEN exhausted without a goal being found.
The following is the basic outline of the search strategy used for the A* and SMA* search algorithms.

OPEN   = { startNode } // Nodes under consideration.
CLOSED = { }           // Nodes we're done with.

while OPEN is not empty
{
remove an item from OPEN based on search strategy used
- call it X

if goalState?(X) return the solution found

otherwise // Expand node X.
{
2) generate the immediate neighbors (ie, children of X)
3) add all children to OPEN
}
}
return FAILURE  // Failed if OPEN exhausted without a goal being found.

Remark: RBFS is a recursive algorithm and does not use open- and close-lists in the way the other five algorithm do.

### Problem 3 --- Compare RBFS and A*

Compare RBFS and A*. What are the main differences between the two algorithms? What are the weaknesses of each algorithm? Illustrate your claims by giving a particular example run of the particular algorithm that shows its weakness, if feasible.

### Problem 4: A* Termination

Algorithm A* does not terminate until a goal node is selected for expansion. However, a path to a goal node might be reached long before that node is selected for expansion. Why not terminating as soon as the goal node is found? Illustrate your answer with an example!

### Problem 5: Using Various Search Techniques to Solve the Travelling Salesman Problem (TSP)

(a) Devise a steepest decent hill climbing algorithm to solve TSP. Explain your approach!
(b) Outline an "informed", depth-first, backtracking-style approach to solve TSP. Propose, heuristics, if helpful to enhance the performance of the algorithm. Explain your approach!
(c) Either outline how evolutionary computing could be used to solve TSP or propose a third algorithm on your own to solve TSP. Either explain the proposed EC-approach or the "third" algorithm you propose.
(d) Implement 2 of the algorithms you proposed in steps a-c.
(e) Evaluate the performance of the two algorithm using a Benchmark of TSP-problems involving 3 different distance functions.
(f) Enhance the two algorithms based on the running of the benchmark, if feasible.
(g) Rerun the modified algorithms for the benchmark.
(f) Write a 4-6 page report that summarizes your solutions and results with respect to problems a-g. Also submit the source code of your program (no documentation required) and be prepared to demo the two programs you wrote.

### Problem 6: Questions concerning Adversarial Search

(a) Assume alpha/beta search is applied to a game tree, such as the one in Fig. 6.2 of our textbook using the following 2 versions v1 and v2:
(v1) enumerating leaf nodes from left to right
(v2) enumerating leaf nodes from right to left
Will versions v1 and v2 always select the same move, if there is a single best move? Will version v1 and v2 always have the same runtime? Give reasons for your answers!

(b) Most game-playing programs do not save search results from one move to the next. Instead, they usually start completely over whenever it is the machine's turn to move. Why?