Visit all nodes in a graph with least repeat visit

问题:

I have a tile based map where several tiles are walls and others are walkable. the walkable tiles make up a graph I would like to use in path planning. My question is are their any good algorithms for finding a path which visits every node in the graph, minimising repeat visits?

For example:

map example http://img220.imageshack.us/img220/3488/mapq.png

If the bottom yellow tile is the starting point, the best path to visit all tiles with least repeats is:

path example http://img222.imageshack.us/img222/7773/mapd.png

There are two repeat visits in this path. A worse path would be to take a left at the first junction, then backtrack over three already visited tiles.

I don't care about the end node but the start node is important.

Thanks.

Edit:

I added pictures to my question but cannot see them when viewing it. here they are:

http://img220.imageshack.us/img220/3488/mapq.png

http://img222.imageshack.us/img222/7773/mapd.png

Additionally, in the graphs I need this for there will never be a situation where min repeats = 0. That is, to step on every tile in the map the player must cross his own path at least once.

回答1:

Your wording is bad -- it allows a reduction to an NP-complete problem. If you could minimize repeat visits, then could you push them to 0 and then you would have a Hamiltonian Cycle. Which is solvable, but hard.

回答2:

This sounds like it could be mapped onto the traveling salesman problem ... and so likely ends up being NP complete and no efficient deterministic algorithm is known.

Finding a path is fairly straight forward -- find a (or the minimum) spanning subtree and then do a depth/breadth-first traversal. Finding the optimal route is the really difficult bit.

You could use one of the dynamic optimization techniques to try and converge on a fairly good solution.

Unless there is some attribute of the minimum spanning subtree that could be used to generate the best path ... but I don't remember enough graph theory for that.