Home Ask Login Register

Developers Planet

Your answer is one click away!

adit-39 February 2016

A Class-Based Shortest Path Algorithm

Given n classes of locations that may each contain a minimum of 1 location of the form (x,y) in each class, how can I find a path that contains one such (x,y) from every class such that this path is the one with the shortest possible distance from among all choices.

For example:
Class A: [(1,1), (10,1)]
Class B: [(20,1), (2,2), (1,15)]
Class C: [(4,4)]
Class D: [(8,8), (5,5), (3,3)]

The solution would be (1,1) -> (2,2) -> (3,3) -> (4,4).

I do understand that this is possible by appliying the shortest path algorithm and computing the cost for every combination, but that will not be computationally feasible as the number of possible solutions multiplicatively increases with the number of classes and the locations in each class (In the above example, 2 * 3 * 1 * 3 possible paths).


Juan Lopes February 2016

You can reduce the Hamiltonian Path in a Euclidean space to this problem. You just have to make each class hold a single point.

Using this, you can easily prove your problem is in NP-hard, i.e., no solution will be much better than backtracking.

Post Status

Asked in February 2016
Viewed 2,908 times
Voted 14
Answered 1 times


Leave an answer

Quote of the day: live life