Commit Graph

6 Commits (main)

Author SHA1 Message Date
magical 910da239c0 new A* optimization: worst-case pruning
i'm not sure if this has been described in the literature exactly but it
is similar to existing branch-and-bound techniques.

it doesn't speed up the search directly (the number of visited nodes is
the same) but it does cut the queue length down by an order of magnitude
and shave a couple seconds off of day 16, presumably due to reduced memory
pressure or something.
2022-12-17 20:15:25 -08:00
magical e9ada04aa9 lib/astar: report final queue length 2022-12-17 19:29:26 -08:00
magical e1fb37d229 lib/astar: handle inconsistent heuristics better
before pruning a node we've already visited, we need to check if it has
a better cost.
2022-12-17 19:27:28 -08:00
magical 2e18e87a95 lib/astar: fix return value for failed search 2022-12-17 15:22:18 -08:00
magical a54304686d day 16 python alternate solution (astar) 2022-12-17 13:20:20 -08:00
magical f2fc82c55f add astar module and alternate solution for day 12 2022-12-12 12:55:37 -08:00