Qu 1

a) Using the hill climbing search approach, find the best path for the tree described below. Use 'a' as starting point. Show your workings.

b) Perform the A* algorithm on the following figure. Explicitly write down the queue at each step.

c) The vertices in the graph below denote neighbouring cities and their distances (in kilometres) are indicated on each edge. Suppose you live in city A. You want to plan a trip that visits each city only once that starts and ends at home. For example, the trip ABDCEA (meaning you go from city A to B, then to D, etc) is one such path that would take you 17 kilometres to follow. Your goal is to choose a path that minimizes the time spent traveling. Formulate the state space and draw a tree diagram of the complete state space.

[10] [4] d) a [0] b) k [0] i [6] k [0]