Draw the search space expanded for a lowest-cost-first

Assignment Help Computer Engineering

Reference no: EM132117290

This question investigates using graph searching to design video presentations. Suppose there exists a database of video segments, together with their length in seconds and the topics covered, set up as follows:

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]

Suppose we represent a node as a pair:

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. Assume that none of the segments in Segs cover any of the topics in To_Cover.

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. [Part of this exercise is to think about the exact structure of these neighbors.]

For example, given the aforementioned database of segments, the neighbors of the node <[welcome,robots],[]>, assuming that welcome was selected, are <[], [seg2]> and <[robots], [seg0]>.

Thus, each arc adds exactly one segment but can cover 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 MustCover. The starting node is , and 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]. Suppose the algorithm always select 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. Please indicate the order of node expansion in the search tree.

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

Reference no: EM132117290

Questions Cloud

Describe the format and contents of rules used : Describe the format and contents of rules used by a typical enterprise firewall.

Discuss the effects on the computing practices : One key Intellectual Property(IP) issue is plagiarism. Discuss briefly its ethical consequences and effects on the computing practices.

Write a return statement to complete the function definition : Function double takes a number and returns twice its value. Write a return statement to complete the function definition.

Create a css code snippet : Create a CSS code snippet that demonstrates the more efficient method that uses a pseudo-class selector and in the comments on that code describe the method.

Draw the search space expanded for a lowest-cost-first : Give a non-trivial heuristic function h that is an underestimate of the real cost. [Note thath(n)=0 for all n is the trivial heuristic function.]

How to create a class rectangle with double attributes : Write a function called main() in the same file to test your Rectangle class . It should prompt the user to enter a length and width of a rectangle.

How a semaphore could be used to implement such a server : Question from OS Sometimes servers wish to limit the number of active connections they have open at any one time.

What is enabled to create incremental backups : What command is used in a backup script to prevent other users from writing to a table while the script is running?

What are the search engines : The development of expert systems is often described as a tedious process. What activities does it typically include?

User Account

All Pages