question archive Problem 3: You are given a game which has the following rules: You have a single token x, and it can move, I Two squares right which has to follow with 1 square up or down (ex: if the token {x} in {2,3} goes to right1 it should also either go to {4,2} or {4
Problem 3: You are given a game which has the following rules: You have a single token x, and it can move, I Two squares right which has to follow with 1 square up or down (ex: if the token {x} in {2,3} goes to right1 it should also either go to {4,2} or {4
Subject:Computer SciencePrice:3.86 Bought8
Problem 3: You are given a game which has the following rules: You have a single token x, and it can move, I Two squares right which has to follow with 1 square up or down (ex: if the token {x} in {2,3} goes to right1 it should also either go to {4,2} or {4.4" I Two squares left which has to follow with 1 square up or down I Two squares up which has to follow with 1 square right or left I Two squares down which has to follow with 1 square right or left 23455 D III...- 1 III...- 2 III...- 3 I-?-I-I 4 III...- 5 III...- 6 III...- a} Provide an admissible heuristic, means it should be admissible tor a given any start state to any goal state {example below]. Please provide your heuristic like a formula and then explain the formula if it is needed with an example mm more than 2 sentences] (it) points} {in the example the ?rst gn'd is a start state and the second grid is a goal state)| b} Independent than the above problem. Assume that for anv game, the actual cost from start state to the goal state is 51:}. You have two admissible heuristics which h1 have an estimate 4t] and h2 has an estimate 3t]. 1|.r'li'hich one of the two admissible heuristic would you choose to use in your algorithm for a better solution? Explain the reason in two sentences {answer with no explanation will not get any point} (10 points]
Purchase A New Answer
Custom new solution created by our subject matter experts
GET A QUOTE
Answer Preview
Question (a) Provide an admissible heuristic, means it should be admissible for a given any start state to any goal state (example below). Please provide your heuristic like a formula and then explain the formula if it is needed with an example (not more than 2 sentences) (10 points)
Answer to Q(a): The movements can be depicted as
The dotted lines represent the straight line distances between the Start and the End states. This straight line distance can be used as the Admissible Heuristic, because the straight line distance will be shortest possible distance between any two points in 2D space and thus this distance will never have a tendency to overestimate the heuristic cost.
The heuristic function, the straight line distance between start point p with xy-coordinates (p1,p2) and the end point q with xy-coordinates (q1,q2) can be represented as
Answer Question (b): Given that the actual cost is 50. Also given that h1 estimated cost as 40 and h2 as 30. The efficiency criteria for an admissible heuristic function (both h1 and h2 are admissible here) is that the heuristic function must estimate a value which must as close as possible to the actual cost so that the search will directly converge to the solution with minimum possible steps. By going this criteria I would select h1 as it is more closer the actual cost and hence results much less exploration of nodes as compared to a search using h2.
Please see the attached file for the complete solution
