Hold forth on these... I am especially interested in seeing blog comments from 471 students..
First a diversion: Check out the following mail from earlier years on the history of n-puzzle problems and how these grabbed popular imagination at one time..
http://rakaposhi.eas.asu.edu/f06-cse471-mailarchive/msg00023.html
Now the thinking-cap questions
0. Should h*(n) be zero for *all* goal nodes or only optimal goal nodes?
1. We argued that computing the optimal cost for getting each tile into its position and summing the distances will not give an admissible heuristic. However, Manhattan distance is doing the same thing--except in an abstract space. How come it is admissible?
1.1*****ADDED NEW (By EDITING BLOG POST)**********
[INTERACTIONS and Heuristics]
The reason we said we can't just add up true costs of putting individual tiles in the right position
is that the tiles have interactions. There are really *two* kinds of interactions
Positive interactions--getting one tile to its position makes it easier to get another tile to its position
Negative interactions--getting one tile to its position makes it *harder* to get another tile to its position.
How do positive and negative interactions affect the informedness and admissibility of the heuristics that *ignore* them?
2. The pattern we considered in the class was left and bottom edges. If instead we considerd the two diagonals of the goal position, will the resulting pattern database heuristic make sense?
3. Suppose there is a new 24-puzzle competition. You are all supposed to use the same hardware (computer memory etc) to solve
test instances optimally. Whoever solves the problem in the shortest time gets a prize (a "platinum-coated 24-puzzle, suitable for framing").
Before the competition starts however, everyone is given about 3 hours of time on the computer for any pre-computation. You want to use the pattern database heuristics, but you know that you don't quite have all the time needed to compute the pattern heuristic for all the possible states in the three hours. Is there any way you can use the precomputation time gainfully?
4. In the problem above, suppose for each team, they allowed two computers during pre-computation time. This obviously suggests the idea that you can compute two different pattern databases (say the left and bottom edges in one, and the right and top edges in the other). Can you imagine a way of using both the databases to improve search further?
--------------
Subscribe to:
Post Comments (Atom)
3 comments:
0. All goal nodes. h* is the shortest path to any goal node.
1. Manhattan distance is admissible because for each tile you must move it at least its Manhattan distance to get to a goal state, and you may only move one tile, one step per move. Hence sum(tiles, steps) <= moves required.
1.1 Positive interaction between, say, two tiles, makes the cost of getting both tiles into position less than the sum of the cost of getting the individual tiles into position, by themselves. This means adding the individual costs gives you an answer higher than the true cost--the heuristic becomes higher than H*, inadmissible. The informedness of the heuristic becomes irrelevant when it becomes inadmissible.
Negative interactions generally decrease informedness but leave admissibility alone.
2. I can't think of any reason why a diagonal database would not make sense, but I'll check my notes and come back to this.
3. Precompute some patterns at random and when solving the puzzle, if you recognize a pattern, use the pregenerated heuristic; otherwise use something suitable (Manhattan?).
4. Let pattern_a be its heuristic if found in the first database and pattern_b be its heuristic if found in the second database. Let pattern_c be a suitable alternate heuristic. If either database does contain a match for the current position, set its heuristic value to 0. Use max(pattern_a, pattern_b, pattern_c) for h().
0 yes h* is the shortest distnace to get to the goal node , so should be o
1. It is admissible because in because in practicality u have to move at least the Manhattan distance to reach the goal state, so Manhattan distance is admissible.
1.1 for positive interactions, the cost of getting to the goal position for let say 2 tiles will be less (which will be h*) as compared to their individual cost, so this will be inadmissible as when the individual cost is calculated it over shoot the range and hence inadmissible
negative interactions will be admissible but less informed.
2. yah it will sense as there will be then a bigger database to look(8 nodes) for but there may also be a trade of no of more computation needed as there will be then 8 nodes or places instead of 7 in bottom and left patterns
3 May be i will take a pattern of few no. of nodes let say 4 to 5 and develop pattern data base for that , this way i ll be somewhat closer to get to the goal state, this is wont serve the purpose by any means but i may get closer towards the goal ( in either way i m not getting it solved in 3 hrs)
4. I can go for left and bottom edge on one PC and top and left edge on other pc , this way i can get more informed heuristics for the nodes that are common to both.
All of Gavin's answers are on the mark.
(regarding "diagonal" pattern, any pattern is fine.. all we are saying is that the cost of getting to a goal state is greater than equal to the cost of getting to any partial pattern of the goal state.
Rao
Post a Comment