Page 1 of 1

Maybe to slow

Posted: Thu Mar 28, 2013 11:34 pm
by Fettpet
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 :wink:

Posted: Fri Mar 29, 2013 4:23 pm
by Redford
Hi!
I haven't attempted this game yet, but your implementation of A* sounds wrong ;)
I haven't used A* (I always use Dijkstra, so, don't trust me :D), 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)

Posted: Fri Oct 10, 2014 2:07 pm
by Fettpet
Hallo,

Ok after long time I have a solution (Ok I didn't work for more than one year). My Problem was in CreateNewWorld Function (Copy the complete World and move a worm). I return the world by value not by address. So it create the world more than 1 times (altogether 4 times). After that chance I can create 25000 vertices per second. For now that is enough, because my Ram is full after 5 seconds. :oops:

mfg
Fettpet
P.S. My Heuristics function is O(n). ;)

Re: Maybe to slow

Posted: Thu Jun 18, 2015 2:27 pm
by Hippo
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 :wink:
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.)