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).

Answers


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

Search




Leave an answer