2
$\begingroup$

I did a project in a class using A* search to solve an 8-puzzle. But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles. I’m not sure whether something like A* search could still work or not. I have trouble fathoming how a heuristic might be designed. Are their other shortest path algorithms or search algorithms that are better suited for this kind of problem?

$\endgroup$

2 Answers 2

1
$\begingroup$

If you have multiple goal nodes and a consistent (or admissible) heuristic to each of them, taking the minimum of them will be still be a consistent (or admissible) heuristic.

Aside from that, there is nothing in A* that prevents you from having multiple goal nodes. The algorithm works fine unchanged.


[Edit] Another heuristic for your problem specifically: for each tile, compute the distance to the nearest valid goal-space, then take the sum over all tiles as the heuristic.

With $n$ spaces, $n-1$ tiles, and $g$ goals, this can be done in $O(n)$ time during the pathfinding by pre-computing the distance to the nearest goal, for each tile, using eg. BFS. This will require $O(n^2)$ space and $O(gn^2)$ time (by searching backwards from each goal).

$\endgroup$
2
  • $\begingroup$ Is there anything that might be better suited for a situation with millions of goal states, other than computing that same number of heuristic scores? The puzzle I’m working with have a lot of identical pieces which are interchangeable in the solved state. The best heuristic I’ve come up with for a single solved state is already kind of complicated and slows down the program a lot. $\endgroup$ Jul 30, 2020 at 21:55
  • $\begingroup$ @ConorHenry: See edit $\endgroup$ Jul 30, 2020 at 22:37
0
$\begingroup$

Yup! You can use A* in that situation. Possibly the simplest method is to run A* once per goal node. Another plausible approach is to consider all of the 'solved' states as a single goal node. Then the heuristic function $h(\cdot)$ is an estimate of the distance from the current node to the goal node, i.e., from the current node to any solved state. Thus, modifications to the heuristic function will be required. One way to modify it is to estimate the distance to each of the possible solved states, and take $h(\cdot)$ to be the smallest of those estimates.

$\endgroup$
4
  • $\begingroup$ What would you suggest if the number of “goals” is 24,192,000? I’m working with a puzzle that has a lot of interchangeable pieces. I’m a little dumbfounded at how to design a heuristic for it. Is there another type of algorithm that might be better suited than A*? $\endgroup$ Jul 30, 2020 at 20:19
  • $\begingroup$ I think you are oversimplifying the modification to the heuristic function a bit. The heuristic functions commonly used for the 8-puzzle are quite involved (to prove correct), and definitely assume there is only 1 solved state. Simply re-running that heuristic for each solved state and taking the minimum might lead to overestimation if you're not very careful that the rules of the game aren't fundamentally changed by adding more final positions, invalidating some assumption of your heuristic. $\endgroup$
    – orlp
    Jul 30, 2020 at 20:19
  • $\begingroup$ @orlp, Thanks for the feedback. I'm not sure I understand the concern. It's easy to prove that the minimum of such heuristic functions can never lead to overestimation (assuming each individual one doesn't overestimate the distance to its corresponding goal). $\endgroup$
    – D.W.
    Jul 30, 2020 at 21:59
  • $\begingroup$ @ConorHenry, that's a separate question. That's an issue with the selection of heuristic function - in your question you ask about whether A* can be used. The details of how to pick a heuristic function are usually very specific to the particular task you've solving. I suggest asking a separate question about how to choose a heuristic function for your particular situation. $\endgroup$
    – D.W.
    Jul 30, 2020 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.