Once we have identified a bottleneck, we can use it in conjunction with other search algorithms. For instance, rather than running heuristic search on the full maze, we can use heuristic search to get Pinocchio to the gap in the wall, and then run a second heuristic search from the gap to the end. This will do at least as well as the original heuristic search, and usually better.
It won’t literally do “at least as well as the original heuristic”, I’m pretty sure. You could construct a maze where going in the direction of the bottleneck leads you into a longer path than going into the direction of the end. It’ll of course do better in expectation.
This is great. Just one nitpick
It won’t literally do “at least as well as the original heuristic”, I’m pretty sure. You could construct a maze where going in the direction of the bottleneck leads you into a longer path than going into the direction of the end. It’ll of course do better in expectation.
Yeah, on reflection that’s right, I didn’t think it through properly.