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