walk through all vertices in a non-hamiltonian, unweighted, undirected graph
I would like to find a heuristic or algorithm to solve a Travelling Sales Person-like problem with some key differences:
-The graph is unweighted. (so the cost of walking from any one vertex to a connected vertex is 1)
-I want to go through each vertex at least once, rather than exactly once.
-There are dead ends in the graph which we will have to backtrack from.
The graph would look something like this:
Currently, I am going along a random route, saving my history in a stack until I reach a vertex not connected to any un-travelled vertex - then I backtrack to the most recent unexplored branch and explore that. I repeat this until there are no vertices left to explore - I can walk the graph using this method in 2n steps, where n is the number of vertices. I feel there must be a better way - I would appreciate any help or pointers to materials I should research!
Your problem is actually general definition of a TSP. Your current approach can be very bigger than 2n you can go through a long path and then come back to some unvisited vertex which is connected to the first vertex of a path, which causes an arbitrary big gap between an optimum and your approach.
If you looking for a good heuristic then nearest neighbor is a good approach. First of all find shortest path between each two vertex and create a new graph G' such that weight of each edge uv is the length of a shortest path between this two vertices in G. Afterward run nearest neighbor algorithm in newly created graph.
Another approach is using Christofides algorithm. Finding a spanning tree of your graph and then create an eulerian tour based on this spanning tree. This one is always at most 3/2 x optimum, so you can use combination of this and nearest neighbor algorithm to get a good result.
By the way almost all well known TSP heuristics are applicable for your problem, best known that I know and I think you can find an implementation of that in the web is tour merging algorithm due to Cook and Seymour which is incredibly accurate but not very fast or easy to implement. (If you didn't find the implementation you can ask authors of the paper to bring an implementation).