![]() ![]() Adding the number of remaining food pellets made it tighter without losing consistency. So for instance your first heuristic is great for one pellet, but not for multiple. So when I'm trying to find consistent heuristics, I usually do what you did: start with a basic computation, then add factors that are missing while still staying consistent. I'd like to know: how many nodes did you have to expand with this heuristic? Tighter Heuristic So your best consistent heuristic thus far is "Manhattan distance to closet food" + (total number of food pellets) - 1. Your last heuristic ("Manhattan distance to furthest food + Manhattan distance from furthest food to its closet food") is also inconsistent for the same reason: again, picture walking in a straight line to the last pellet results in eating all the remaining food. if walking in a straight line to farthest food eats up all the food, then you will over-estimate the cost). Your 3rd heuristic "adding to any of those amount of food left" is consistent for the first heuristic but NOT the second (e.g. Your first two heuristics: "Manhattan distance to closet food" and "Manhattan distance to furthest food" are definitely consistent. Reviewing your (sometimes inconsistent) heuristics So they are definitely guiding us to A* search with a consistent heuristic that is more clever than Manhattan distance. The fact that "If your heuristic is inconsistent, you will receive no credit". ![]() So A* search with Manhattan distance as the consistent heuristic is our basis. The note "Make sure to complete Question 4 before working on Question 7, because Question 7 builds upon your answer for Question 4.".However, I am basing my approach on the following: Ok, so this is not a complete answer, since I have not implemented it, and so I do not know how it performs.
0 Comments
Leave a Reply. |