CSCI 4511W Midterm: CS 4511 UMN Midterm 1 s08
Document Summary
You are given an instance of the traveling salesperson problem (tsp). A salesperson has to visit a group of cities, visiting each only once and getting back to the starting city. The objective is to minimize the total distance traveled. Explain brie y your answer. in each city h(n) Is this heuristics: suppose you use the above heuristics in a greedy best- rst search algo- rithm. Nodes that have the same f (. ) value are ordered arbitrarily. You are given a state-space search problem, i. e. you are given the initial state, the operators, and a goal state. You come up with your own heuristics, apply a*, and produce an optimal solution: what property should your heuristics satisfy to guarantee the solution is optimal, is the optimal solution unique? if yes, explain why. If not, describe what could cause nding multiple solutions. Turn to the next page for more questions: 20 points.
