I am working on an algorithm for what seems like a very simple problem, but I cannot find an efficient algorithm for it. The problem is this: I have a list of numbers (0-50) and an initial location, and you need to visit each of them while minimizing the distance traveled. Some pairs of places require me to go to another first (so to visit 29, I must first dial 26). However, I cannot figure out how to do this, simply without generating each option. Any ideas?
For example, we have the following
startLocation=25;
targetPairs=[[1,5],[7,12],[22,23]]
visitLocations=[4,6,8,2]
this means that we must visit 1 to 5, 7 to 12 and 22 to 23. We also need to visit places 4,6,8 and 2. One option to start is to go too 1 (distance 24), then go to 4 (distance 3 total 27), then go to 5 (distance 1 total 28), then we can go to 6 (distance 1 total 29) or for a complete set (7 (30), 8 (31), 12 ( 35), 22 (45), 23 (46)).
Logically, the limit of the number of places we should visit is 50 pairs and 50 places.
source
share