hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Maybe to slow

 
Reply to topic    hacker.org Forum Index » Tapeworm View previous topic
View next topic
Maybe to slow
Author Message
Fettpet



Joined: 03 Sep 2012
Posts: 3

Post Maybe to slow Reply with quote
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
Thu Mar 28, 2013 11:34 pm View user's profile Send private message
Redford



Joined: 04 Jul 2009
Posts: 41
Location: Poland

Post Reply with quote
Hi!
I haven't attempted this game yet, but your implementation of A* sounds wrong Wink
I haven't used A* (I always use Dijkstra, so, don't trust me Very Happy), 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 View user's profile Send private message Visit poster's website
Fettpet



Joined: 03 Sep 2012
Posts: 3

Post Reply with quote
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. Embarassed

mfg
Fettpet
P.S. My Heuristics function is O(n). Wink
Fri Oct 10, 2014 2:07 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 332
Location: Praha 5

Post Re: Maybe to slow Reply with quote
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.)
Thu Jun 18, 2015 2:27 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Tapeworm All times are GMT
Page 1 of 1

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.