search

jgrapht / jgrapht

Master repository for the JGraphT project
http://www.jgrapht.org
Eclipse Public License 2.0
2.59k stars 825 forks source link

A* Shortest Path with Inconsistent Heuristics #808

Open bbockman opened 5 years ago

bbockman commented 5 years ago

There are some desirable use cases for A* with inconsistent heuristics. The current implementation of the AStarShortestPath class is optimal for consistent heuristics, but does not support efficient search when inconsistent.

Currently when the heuristic is inconsistent and its magnitude grows with the size of the graph, the worst case running time is O(2^n). I would like to add an optimization that would bring this down to O(n^2). This bidirectional pathmax of order 1, (BPMX(1)) is discussed in the following paper: https://www.ijcai.org/Proceedings/09/Papers/111.pdf

The change is fairly minor, the heuristic at each step would be updated to its lowest allowable value. As stated in the paper BPMX(1) is essentially free in that it would not change the asymptotic running time of the original algorithm other than increasing its constant slightly (very slightly!). Because of this my original idea would be to simply augment the current class with this update step.

However Joris mentioned creating a new subclass for this problem. This would prevent any impact to the original class, but the subclass would be dependent on the implementation of its parent. The parent is currently fashioned with all protected methods and fields, so I'm not sure if this implies a contract to keep the relationship between its methods consistent over time.

The final option would be to simply create a standalone class. This removes any inner-dependency but also unnecessary code duplication.

What are your thoughts. Is this a useful thing for me to implement? If so, what approach would you suggest. Thanks for your time!

d-michail commented 5 years ago

I agree with Joris. Best to start with a subclass in order to exactly see how much of the old code is relevant or not. We can change some methods to being protected if you need to use them.

After having a first version as a subclass we would be much better suited to check if any additional refactoring is relevant.

bbockman commented 5 years ago

Thanks for the input! I can put together a pull request with the subclass.

One additional note. The current performance test class DijkstrasShortestPathPerformanceTest does not include any inconsistent heuristic based tests. The only heuristic generator I see currently available in the code base is the ALTAdmissibleHeuristic. I could create another class for generating good inconsistent heuristics for particular classes of problems, however I feel the data available in the research papers is much stronger than anything I would be able to produce in a reasonable amount of time.

Would it be reasonable to simply use the research data to support any performance benefit claims? I can certainly use the current performance test to show the lack of degradation given a consistent heuristic. If this is helpful, it would be relatively simple.

bbockman commented 5 years ago

I think I can actually make a reasonable inconsistent heuristic generator out of the ALTAdmissibleHeuristic class without much trouble by having it use a random landmark for each source node instead of the maximum. I certainly wouldn't say it's a good inconsistent heuristic, but if you want some data this is an option. I still think the research results are more valuable for coming to conclusions regarding performance for this particular use case however.

bbockman commented 5 years ago

Pull request submitted. I went ahead and created that utility class for generating inconsistent heuristics. I also made a super minor bug fix to the current A* implementations which were preventing them from working with inconsistent heuristics!