miniblog.

← Back to all posts
Nov 28, 2023 at 07:36
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.
algorithm - What heuristic functions can I use for a graph based (non-grid) A*? - Stack Overflow
algorithm - What heuristic functions can I use for a graph based (non-grid) A*? - Stack Overflow

Related Posts

Jul 4, 2022 at 00:05
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:
difftastic/src/diff/dijkstra.rs at 3b9474d9fe360a4122d63efbecda2ac7b3b36d30 · Wilfred/difftastic
difftastic/src/diff/dijkstra.rs at 3b9474d9fe360a4122d63efbecda2ac7b3b36d30 · Wilfred/difftastic
a structural diff that understands syntax 🟥🟩. Contribute to Wilfred/difftastic development by creating an account on GitHub.
Jul 4, 2021 at 17:06
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
Jan 24, 2021 at 03:33
1
Why don't browsers use history or Alexa rank to highlight trustworthy sites? Gmail already warns me if I haven't emailed a person/domain before. This seems like a viable heuristic against phishing sites.