Fatemeh Bahrani
Author
Like admissibility, being monotonic also helps to find an optimal path to the state it selects for expansion.
24-puzzle could be defined as well. (Size of the board is 5×5 instead of 3×3 and it has the same rules for moving.)
In general, admissible heuristic functions represent the cost of exact solutions to simplified or relaxed versions of the original problem (Pearl, 1984). For example, in a sliding tile puzzle (like 8-puzzle), to move a tile from position x to position y, x and y must be adjacent, and position y must be empty. By ignoring the empty constraint, we get a simplified problem where any tile can move to any adjacent position. We can solve any instance of this new problem optimally by moving each tile along the shortest path to its goal position, counting the number of moves made. The cost of such a solution is exactly the Manhattan distance from the initial state to the goal state. Since we removed a constraint on the moves, any solution to the original problem is also a solution to the simplified problem, and the cost of an optimal solution to the simplified problem is a lower bound on the cost of an optimal solution to the original problem. Thus, any heuristic derived in this way is admissible.
Pattern databases are for exploratory estimation of storing state-to-target distances in state space. Their effectiveness depends on the choice of basic patterns. If it is possible to divide the subsets into separate subsets so that each operator only affects the subsets in one subset, then we can have a more acceptable exploration performance. We used this method to improve performance in 15-puzzles with a coefficient of more than 2000 and to find optimal solutions for 50 random samples of 24-puzzles.
How do we combine the “h” s of the separated subset of state space?
− MAX: Which has diminishing.
− ADD: In this case, the limitation is removed and it is admissible.
Using a Pattern Database helps us solve many problems, but it is flawed in very large cases and is not scalable.
Why does summation result in an admissible heuristic in that case?
Proof:
Manhattan Dist. is a trivial example of a disjoint DBs, where each group contains only a single tile. As a general rule, when partitioning the tiles, we want to group tiles that are near each other in the goal state, since these tiles will interact the most with one another. Using this method, the 15-puzzle problem is solved 2000 times and the 24-puzzle problem is 12 million times faster