4

My problem is related to the "shortest path" problem, however it's slightly different in that I don't want to draw one path but to draw all paths without repeating any routes (as much as is possible). I'm trying to work out what this geometric problem is called (if it has been covered at all) in order to find an algorithm to work with.

Say there are 6 points in a network that are attached via a web of 10 edges (non-weighted). I must make a route starting form any one single point and move down every edge in any order but without repeating any of these edges. When I find myself in a position where there are no possible new edges forward I can either take one of the previously travelled edges back or I can go "off-road" directly to a new point, however these are considered "lost time". What I want is to find an algorithm (or even the name of this geometric problem) that will minimise "lost time" As I attempt to move down all routes.

An easier way to explain might be a printer that draws out all of these paths: while the printers pen is down (i.e. drawing) we are not wasting energy, however as the printers pen will not repeat any drawn lines it may have to move between points with the pen up, which we consider as wasted energy. I want to minimise energy waste.

Can anyone help point me in the right direction?

1

You need to do a perfect, minimum weight matching, done using the blossom algorithm

Find all points in your network with an odd number of edges. From these you find the distance (lost time) to all other such points. This is the input to the blossom algorithm. Once you have the perfect matching, the "lost time" edges can be added to the network and you have a network with all points having an even number of edges.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.