how to find a path visit as much as possible vertices? <p>Given a square grid (undirected graph), is there any way to find a path which will visit as much as possible vertices.</p> <p>each vertex can be visit only once. It means that the path will be Hamilton tour if exist, or be a longest path.</p> <p>The graph has some walls. Wall is a vertex has no edge connect to neighbors.</p> <p>I has a solution (in mind), but it's very similar to find all path and chose the first one has most vertices visited.</p> <blockquote> <ol> <li><p>Find a path will visit all neighbors from given start vertex to the end (no way can go).</p></li> <li><p>look back to the current path until the starting vertex, if there is any vertex has neighbors outside of the current path, process like step 1 from the found vertex and its new neighbors.</p></li> <li><p>analysis and choose the longest path (has most vertices).</p></li> </ol> </blockquote> <p>I found <a href="http://cs.stackexchange.com/questions/14390/find-a-simple-path-visiting-all-marked-vertices">similar problem</a>, cannot understand what does @Juho mean: </p> <blockquote> <p>Choose a successor si to top(S), and try to find a path si−1⇝si avoiding vertices in F. If a path is found, insert the vertices on the path si−1⇝si to F.</p> </blockquote> <p>I don't have enough reputation to add a comment there.</p> <p>my solution get performance trouble, I guess. Any suggestion?</p>