search

KeRNeLith / QuikGraph

Generic Graph Data Structures and Algorithms for .NET
https://kernelith.github.io/QuikGraph/
Microsoft Public License
453 stars 65 forks source link

Shortest Path Early Termination and Edge Filtering #62

Open BenBohannon opened 2 years ago

BenBohannon commented 2 years ago

Is your feature request related to a problem? Please describe. I'm creating a Unity game as a hobby, and am looking to use this library for pathfinding.

  1. For very large graphs, we want to calculate only the single best shortest path without visiting every vertex for improved performance. (e.g. A-star algorithm)
  2. There are constraints on movement which could be used to limit the search space (optimizing performance) (e.g. Dijkstra's algorithm)

Describe the solution you'd like

  1. Add an option/constructor argument for early termination. If set to True, the priority queue is cleared upon finding the target so that BFS will artificially finish its FlushVisitQueue
  2. Expose the BFS outEdgesFilter to the shortestPath algorithms, so that it can be used to filter the search space based on max cost/vertex distance/whatever the user desires.

Describe alternatives you've considered

  1. Subscribing to the FinishVertex event, canceling the algorithm upon finding the target, and catching the abort exception.
  2. Using FilteredVertexListGraph to limit the search space (but it isn't able to filter dynamically based on cost/distance).

Additional context I'm not familiar with many of the other shortestPath algorithms, so I don't know if these solutions are applicable beyond Astar and Dijkstras.

KeRNeLith commented 2 years ago

Hello @BenBohannon,

I imagine you're in a case you've specified a root vertex (source) which is then given to the BFS algorithm, and also have implicitly a destination (target) to reach, right? If yes I imagine that would be something more for an algorithm based on RootedSearchAlgorithmBase<,> which defines a target vertex.

BTW to have the best path to a vertex you may require to explore the full graph which can lead to path reduction (especially with weighted graphs). If we early stop the A algorithm can we really call it A then? It would more be a search of the first path to a given vertex regardless of its efficience (best fit). What are your thoughts about that? Indeed given a vertex the A* will gather the distances to other vertices you're not trying "to go" which is more a side effect of the algorithm because it may be needed to define the path to the real target.

BenBohannon commented 2 years ago

Yes, that is the case that I'm using A* for.

But I would disagree with using RootedSearchAlgorithmBase because early termination is only available for some optimized search algorithms like A. DFS can't take advantage of it without accepting suboptimal paths, and it doesn't make a whole lot of sense for Dijkstra's to have early termination. I would normally expect A to have early termination without the option of disabling it, since that "goal-oriented heuristic optimization" is the whole purpose of using A*.

With regards to early stopping: as long as your heuristic is a "consistent" heuristic, you'll be guaranteed to find the optimal path with A. I don't think it would be unreasonable to put the onus of ensuring your heuristic is consistent on the user of the A algorithm. Otherwise, the current A* implementation is nearly the same as running Dijkstra's performance-wise.

Kemsekov commented 1 year ago

Dijkstra algorithm can be performed in parallel

This is not a particular solution to early termination, but it would help to improve performance.