Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement furthest nodes with shortest path #108

Open
sraaphorst opened this issue Jun 24, 2018 · 0 comments
Open

Implement furthest nodes with shortest path #108

sraaphorst opened this issue Jun 24, 2018 · 0 comments
Labels
enhancement New feature or request shared Code common to all libraries

Comments

@sraaphorst
Copy link
Owner

sraaphorst commented 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 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.

@sraaphorst sraaphorst changed the title Implement furthest nodes apart Implement furthest nodes with shortest path Jun 24, 2018
@sraaphorst sraaphorst added enhancement New feature or request shared Code common to all libraries labels Jun 25, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request shared Code common to all libraries
Projects
None yet
Development

No branches or pull requests

1 participant