Closed ltratt closed 6 years ago
Looks good apart from that really hard to read method call astar_bag
which has arguments that spread over a hundred lines.
Agreed, it's hard to use astar_bag
neatly but, I think, this is as good as it gets :/
Alright. That's fair enough. I thought the closures could maybe be put into variables so one can at least see what's passed over to astar_bag
. But if that doesn't make sense then I'm fine with this.
Alright merged.
This is the first part of a new error recovery algorithm (titled, for the time being, KimYi+). When one has an incorrect output such as:
it will, unlike the normal KimYi algorithm, show you all possible minimal repairs:
[In other words, "normal" KimYi will find just one of the PLUSPLUS / MINUSMINUS repairs; KimYi+ finds both.]
This is far from perfect: at the moment, one can end up with repairs which, from a human perspective are duplicates (though they're not duplicates if you understand the algorithm); and the implementation isn't particularly fast (it can take a couple of seconds to find a complex repair). However, fixing these things in this PR would just make things more complex.
Note that the first commit is, theoretically, not related to the second; but in practise it is. In essence, it's a change which I couldn't find to have any impact on KimYi, but which definitely has an impact on KimYi+. Some of the tests in the second commit rely on the first commit being present. [This PR also relies on the changes of https://github.com/samueltardieu/pathfinding/pull/51 -- but one can take those as a given.]