You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
In general, longest path is an NP-hard problem (except for trees, which our perfect graphs are).
However, we don't exactly want longest path: what we want is to find the maximum length shortest path, which can be done via a BFS at each node, keeping track of the pair of cells that are the furthest apart. Ultimately, these can be used for the start and the goal position to presumably make the maze more challenging.
This should be calculable in time O(w2h2) simply by starting at each cell, of which there are at most w * h, and running a BFS, which will take at most w * h steps.
By implementing BFS for each maze type, we will be able to do this easily, as well as find the connected components easily, and possibly have enough information to generalize solutions to AbstractMaze.
The text was updated successfully, but these errors were encountered:
sraaphorst
changed the title
Implement furthest nodes apart
Implement furthest nodes with shortest path
Jun 24, 2018
In general, longest path is an NP-hard problem (except for trees, which our perfect graphs are).
However, we don't exactly want longest path: what we want is to find the maximum length shortest path, which can be done via a BFS at each node, keeping track of the pair of cells that are the furthest apart. Ultimately, these can be used for the start and the goal position to presumably make the maze more challenging.
This should be calculable in time
O(w2h2)
simply by starting at each cell, of which there are at mostw * h
, and running a BFS, which will take at mostw * h
steps.By implementing BFS for each maze type, we will be able to do this easily, as well as find the connected components easily, and possibly have enough information to generalize solutions to
AbstractMaze
.The text was updated successfully, but these errors were encountered: