2. h (n), h,(n), hz (n), and h_(n) are four heuristic estimates to the distance from node n to the nearest goal node. It is known that hi(n). h (n), and hz (n) are admissible heuristics, but he(n) is not known to be admissible. We define other heuristics as combinations of the given heuristics: h (n) + h (n) + h (n) 3 h(n) + h_(n) +h3(n) + h (n) he(n) = 4 h (n) = hi(n) +h2(n) +h3(n) hg(n) = max{hi(n), h2(n)} hg(n) = min{hi(n), hz(n)} ho(n) = max{h3(n), h4(n)} hi(n) = min{hz(n), h4(n)} (1). If these heuristics are uesd by A*, in which cases are we guaranteed to find the optimal solution? (Circle the ones you would like to choose) Answer: h1/h2/h3/h4/hs/ h / h /hg/h/ho/hui (2). With no additional information about h1, h2, h3, h4, give a formula that produces a heuristic h that you consider to be better than h1, h2,...,hu1 when used by A* algorithm. Answer: Circle at least one of the following statements: a. I am unable to find a solution that would be a guaranteed improvement. The best heuristic in (1) is b. My solution improves over the heuristics in (1), in terms of MEMORY. In all other aspects my solution is at least as good as the heuristics in (1). c. My solution improves over the heuristics in (1), in terms of SPEED. In all other aspects my solution is at least as good as the heuristics in (1). d. My solution improves over the heuristics in (1), in terms of GUARANTEED OPTIMAL SOLUTION. In all other aspects my solution is at least as good as the heuristics in (1). e. My solution improves over the heuristics in (1). in terms of QUALITY OF SOLUTION. (I expect it to find a better solution.) In all other aspects my solution is at least as good as the heuristics in (1). 2. h (n), h,(n), hz (n), and h_(n) are four heuristic estimates to the distance from node n to the nearest goal node. It is known that hi(n). h (n), and hz (n) are admissible heuristics, but he(n) is not known to be admissible. We define other heuristics as combinations of the given heuristics: h (n) + h (n) + h (n) 3 h(n) + h_(n) +h3(n) + h (n) he(n) = 4 h (n) = hi(n) +h2(n) +h3(n) hg(n) = max{hi(n), h2(n)} hg(n) = min{hi(n), hz(n)} ho(n) = max{h3(n), h4(n)} hi(n) = min{hz(n), h4(n)} (1). If these heuristics are uesd by A*, in which cases are we guaranteed to find the optimal solution? (Circle the ones you would like to choose) Answer: h1/h2/h3/h4/hs/ h / h /hg/h/ho/hui (2). With no additional information about h1, h2, h3, h4, give a formula that produces a heuristic h that you consider to be better than h1, h2,...,hu1 when used by A* algorithm. Answer: Circle at least one of the following statements: a. I am unable to find a solution that would be a guaranteed improvement. The best heuristic in (1) is b. My solution improves over the heuristics in (1), in terms of MEMORY. In all other aspects my solution is at least as good as the heuristics in (1). c. My solution improves over the heuristics in (1), in terms of SPEED. In all other aspects my solution is at least as good as the heuristics in (1). d. My solution improves over the heuristics in (1), in terms of GUARANTEED OPTIMAL SOLUTION. In all other aspects my solution is at least as good as the heuristics in (1). e. My solution improves over the heuristics in (1). in terms of QUALITY OF SOLUTION. (I expect it to find a better solution.) In all other aspects my solution is at least as good as the heuristics in (1)
