Fettpet wrote:Hi Hackers,
for this puzzle I use the A* algorithm. It is in level 30 very slow (needs much mininutes to solve). So I look why it needs so long. A problem could be, that it only can calculate 1300 vertices per Second. It sounds very less, but i have not enough evaluate it.
My Question is, has someone write a A* or dijkstra algorithm and can me say how much vertices per second his/her solution can calculate per Second.
P.S. I hope the forum isn´t deed
A* is bad idea (if it's queue (BFS) based), the implicit graph size grows exponencially with the search depth so you will "instantly" run out of memory.
Much better solution for searches of huge implicit graphs is IDA* (it's stack based (DFS) to slowly growing maximal depth).
I am afraid even IDA* would not be sufficient without further tricks, but l am almost sure space would not be the limiting factor (but time would).
I don't think quick "accurate" heuristics exists so the searched portion of the graph will still be huge.
My attempts are to find path combined from several subpaths found by using searches to smaller depth than would be required for full search. Of course making the heuristics as accurate as possible helps. (Currently I am thinking about solving puzzle with some worms removed as a heuristics lowerbound ... for levels with more worms.)
), but properly implemented Dijkstra should calculate over 1M vertices per second, and properly implemented A* should be faster than Dijkstra. Check whether your solution works in O(n lg n), not O(n^2). Maybe your "heuristic function" from A* is bad? Or you use wrong container for vertices? (e.g. in C++ you should use set/multiset/priority_queue)
