Author 
Message 
Fettpet
Joined: 03 Sep 2012 Posts: 4


Maybe to slow 

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


Thu Mar 28, 2013 11:34 pm 


Redford
Joined: 04 Jul 2009 Posts: 41 Location: Poland 



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 ), 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)
_________________


Fri Mar 29, 2013 4:23 pm 


Fettpet
Joined: 03 Sep 2012 Posts: 4




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.
mfg
Fettpet
P.S. My Heuristics function is O(n).


Fri Oct 10, 2014 2:07 pm 


Hippo
Joined: 01 Feb 2014 Posts: 333 Location: Praha 5 

Re: Maybe to slow 



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.)


Thu Jun 18, 2015 2:27 pm 


