Algorithm to cover all edges when starting node

Question

Working on a game algorithm, I am developing with a friend, and we are stuck. We currently have a cyclic undirected graph, and we are trying to find the fastest way from running node S, which covers each edge. We are not looking for a tour, and there may be repeated edges.

Any ideas on an algorithm or approximation? I am sure this problem is NP-hard, but I do not believe this TSP.

Answer 1

Route check

This is called a route check problem , and it has a polynomial solution.

The main idea (see the link for more details) is that it is easy to solve for the Euler path (where we meet each edge every time), but for some graphs, only the Euler path is possible.

In particular, the graph must be connected and have either 0 or 2 vertices of odd degree.

However, this can be generalized to other graphs by adding additional edges in the cheapest way, which will give a graph that has an Euler path. (Note that we added more edges so that we can move around the edges several times on the original graph.)

The way to choose the best way to add additional edges is the maximum matching problem, which can be solved in O (n ^ 3).

PS

By the way, I wrote a simple demo earlier ( link to the game ) for a planar problem with maximum resolution. The solution to this problem is based on the exact same route check :)

EDIT

I just noticed from the comments that in your particular case, your chart may be a tree.

If so, then I find the answer a lot simpler, since you just need to do DFS over the tree to find the shallow subtree first.

For example, suppose you have a tree with edges S-> A and S-> A-> B. S has two subtrees, and you should first visit A ​​because it is smaller.

The total edges visited will be equal to the number of edges visited in full DFS, minus the depth of the last leaf visited, so to minimize the total edges you want to maximize the depth of the last leaf and therefore visit the shallow subtree first.

Answer 2

This is similar to the Euler path . The main difference is that there may be blind spots, and you can modify the algorithm to suit your needs. Cropping dead spots is one option, or you can reduce the graph by several connected components.

Answer 3

DFS will work here. However, you should have a good rating function for an early branch branch. Otherwise, you will not be able to quickly solve this problem. You can refer to my discussion and implementation in Java here http://www.capacode.com/?p=650

Details of my evaluation function My first attempt is that the length of the current path plus the distance from U to G is not shorter than the minimum length (stored in the minLength variable) that we found, we will not visit U because it cannot lead to more short way.

In fact, the aforementioned rating function is ineffective because it only works when we are already visiting most cities. We need to more accurately calculate the minimum length in order to reach G with all the cities visited.

Suppose that s is a length from S to U, from U to visit G and go through all the cities, the length is at least s = s + Σ minDistance (K), where K is an undisclosed city and differs from U; minDistance (K) is the minimum distance from K to the unreviewed state. In principle, for each unforeseen condition, we assume that we can reach this city with the shortest edge. Note that these shortest edges may not contain a valid path. Then we will not visit U if s ≥ minLength.

With this rating function, my program can deal with a problem with 20 cities in 1 second. I also add another optimization to improve performance. Before starting the program, I use a greedy algorithm to get a good value for minLength. In particular, for each city we will visit the nearest city. The reason is that we have less minLength, we can crop more.