Today I learnt that A* doesn't work for an arbitrary non-planar graph, you need additional structure:
https://stackoverflow.com/q/26568552/509706
This matches my experience with difftastic so far. The graph is non-planar and my best heuristic only matches Dijkstra perf in typical cases.
miniblog.
Related Posts
3
I've been impressed with code written by Fable in my testing:
Difftastic: found small optimisations in a hot loop I'd already profiled extensively. Helped me prototype Dijkstra to A* too (hard to find a good heuristic).
Garden: Found some real bugs in my simplistic typechecker.
I've started playing again with A* search instead of Dijkstra for difftastic. So far it's only saved me visiting 3% of graph nodes, which is negligible.
A* works best when you have a good heuristic, but finding a good heuristic is hard. Currently:
Snorkel is a project that encourages you to build heuristic functions to train a ML model on. It's a clever alternative to manually labelling data.
https://www.snorkel.org/use-cases/01-spam-tutorial