Given a square grid (undirected graph), is there any way to find a path which will visit as much as possible vertices.
each vertex can be visit only once. It means that the path will be Hamilton tour if exist, or be a longest path.
The graph has some walls. Wall is a vertex has no edge connect to neighbors.
I has a solution (in mind), but it's very similar to find all path and chose the first one has most vertices visited.
Find a path will visit all neighbors from given start vertex to the end (no way can go).
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.
analysis and choose the longest path (has most vertices).
I found similar problem, cannot understand what does @Juho mean:
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.
I don't have enough reputation to add a comment there.
my solution get performance trouble, I guess. Any suggestion?
This is more of a Hamiltonian Path problem. It's NP-complete so you'll need to do an exhaustive search. Get your brute-force on. I can only suggest that it is possible to use threading to alleviate your performance problem; divide up your starting vertices evenly amongst your available threads. Terminate in the event that you find a Hamiltonian Path, else the longest path wins.
The algorithm itself is just going to have to find all possible paths. I there is possibly a heuristic to stop bothering with a path that seems to be getting bad results but that will mean the solution may not always be correct.