-
Notifications
You must be signed in to change notification settings - Fork 69
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
RFE: bidirectional search #543
Comments
Hi Josh, I'm not sure the current API can readily support a bidirectional search. In addition to the points you've already mentioned (the
Incorporating advanced pathfinding techniques is something I'd love to see added to this crate. Bidirectional search and graph compression (with initial offline processing) are among those techniques. I would welcome such contributions, as I currently lack the resources to undertake them myself. I'll leave the issue open as a feature request to keep track of this. |
https://en.wikipedia.org/wiki/Bidirectional_search
It could be beneficial to some problems to search simultaneously from the start and end states to meet in the middle. The most general implementation would need to use separate successor and predecessor functions, but an undirected graph can use the same for both. I think at least BFS, Dijkstra, and A* (with separate heuristics) could support this.
I also wonder if there are any tricks to approximate bidirectional search with the existing API.
The text was updated successfully, but these errors were encountered: