This question investigates using graph searching to design video presentations. Consider a database of video segments, together with their length in seconds and the topics covered:

Segment Length Topics Covered seg0 10 [welcome]

seg1 30 [skiing, views]

seg2 50 [welcome, artificial intelligence, robots]

seg3 40 [graphics, dragons]

seg4 50 [skiing, robots]

In the search graph, a node is a pair

To Cover, Segs where Segs is a list of segments that must be in the presentation, and To Cover is a list of topics that also must be covered.

The neighbors of a node are obtained by first selecting a topic from To Cover.

There is a neighbor for each segment that covers the selected topic. The remaining topics are the topics not covered by the segment added. [Part of this exercise is to think about the exact structure of these neighbors.] Assume that the leftmost topic is selected at each step.
Given the above database, the neighbors of the node [welcome,robots], [] , when welcome is selected, are [], [seg2] and [robots], [seg0] .
Thus, each arc adds exactly one segment but can cover (and so remove) one or more topics. Suppose that the cost of the arc is equal to the time of the segment added.
The goal is to design a presentation that covers all of the topics in the list MustCover. The starting node is MustCover, [] . The goal nodes are of the form [], Presentation . The cost of the path from a start node to a goal node is the time of the presentation. Thus, an optimal presentation is a shortest presentation that covers all of the topics in MustCover.

(a) Suppose that the goal is to cover the topics [welcome,skiing,robots] and the algorithm always selects the leftmost topic to find the neighbors for each node. Draw the search space expanded for a lowest-cost-first search until the first solution is found. This should show all nodes expanded, which node is a goal node, and the frontier when the goal was found.

(b) Give a non-trivial heuristic function h that is admissible. [Note that h(n) = 0 for all n is the trivial heuristic function.] Does it satisfy the monotone restriction for a heuristic function?

(c) Does the topic selected affect the result found? Why or why not?