I have a graph with an arbitrary amount of edges and vertexes. Each vertex having an arbitrary amount of edges connecting to it but in practice the number is usually around 3 or 4 no less than one and no more than a dozen. I want to find the path that goes to as many vertexes and edges as possible without using any edge more than once.
In addition there are a few special cases that I would like to add but an algorithm that doesn't solve for these is fine:
- There are pairs of vertexes that are connected with multiple edges. I can traverse multiple of these edges but I cannot immediately return to the previous vertex I was at without first going to another vertex.
- There are some edges that are one way.
- Some vertexes will change the destination of edges connected to themselves depending on the edge you arrived from. In practice this is always a vertex with two edges that if arrived from one edge will change the other edge to return to the source of the first edge and if arrived from the other edge the first will not change. In theory it doesn't have to be though.
I know this problem cannot be solved in polynomial time and I have thought of ways to speed up the brute force method I am just wondering if anyone else has any ideas.