- 0
Interesting Challenge
-
Recently Browsing 0 members
- No registered users viewing this page.
-
Similar Content
-
Self-replicating worm malware infects exposed Redis data store used for live streaming
By Ishtiaqe Hanif,
- 1 reply
- 3 views
-
ISRG to begin making Apache HTTP Server more secure
By zikalify,
- isrg
- internet security research group
- (and 8 more)
- 1 reply
- 432 views
-
- 13 replies
- 715 views
-
- 27 replies
- 1,195 views
-
- 8 answers
- 4,079 views
-
Question
simplezz
So recently I came across an interesting puzzle. Having never done any pathfinding before, I knocked up a tentative solution. I based it on Dijkstra's algorithm. Though I soon realised that it was insufficient for the puzzle's search space parameters.
Unless I'm misunderstanding it, it (Dijkstra's) appears to radiate out from the source based on the smallest distance aggregate of the current vertex and its descendants (adjacents). That didn't seem to fit with this particular puzzle due to the fact that the distance between nodes in the graph is constant (1). I tweaked it somewhat by calculating the distance to the target instead. This means that descendants have a sense of direction.
I'm not sure how effective it would be at processing larger graphs, but it does currently solve the examples provided. I'm also interested in how it can be improved. The wiki seems to suggest that a fibonacci heap might decrease its runtime cost. Does anyone have any experience or insight they might be willing to share regarding efficiencies and whether or not Dijkstra's is right for this particular problem.
Link to comment
Share on other sites
6 answers to this question
Recommended Posts