CODEWITHSUNDEEP
algorithmscheduling
Thijser
Thijser

Reputation: 2633

1D travelingsalesman with constraint

I'm working on a algorithm for what seems like a very easy problem but I cannot find an efficient algorithm for it. The problem is as following: I have a list of numbers (0-50) and a start location and have to visit each of these while minimalising the total distance travelled. Some pairs of locations require me to visit the other one first (so to visit 29 I must first pick something up on 26). However I cannot quite seem to figure out how to do this without just generating every 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 have to visit 1 before 5, 7 before 12 and 22 before 23. We also have to visit the location 4,6,8 and 2. One option to get started is to go too 1(distance 24) then go to 4 (distance 3 total 27) then go to 5 (distance 1 total 28) we can then go on to 6 (distance 1 total 29) or for the full set (7(30),8(31),12(35),22(45),23(46)).

Logically the limit for the number of locations we have to visit is 50 pairs and 50 locations.

Upvotes: 4

Views: 98

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51226

The problem can be solved by the following potentially exponential-time algorithm, and if it's NP-hard (as I suspect) then you won't be able to do much better (where by "much", I mean find an algorithm with polynomial time complexity -- it may well be possible to reduce the base of the exponential-time algorithm).

Basically, do a best-first search in a state space in which each state consists of two things: a current position, and a set of already-visited locations. (It's unfortunately not sufficient to simply track the number of already-visited cities.) We always have at most the following 2 moves from each point in this state space:

  1. Move left to the nearest visitable location
  2. Move right to the nearest visitable location

That's because there is always an optimal solution in which each location is visited the first time we move to or past it after it has become visitable. Here, "visitable" means that all a location's predecessors (including predecessors of predecessors, etc.) have already been visited.

Any state in which all locations have already been visited is a goal state. Using best-first search (implementable with a priority queue, or in this case, simply a size-50 array would do), the first such state found will correspond to an optimal solution. This algorithm will take time exponential in the number of locations that need to be visited.

This search can be sped up by using the A* algorithm -- that is, by using some admissible heuristics to determine a lower bound on the distance remaining from a given state. It should be fairly easy to come up with something reasonable here -- e.g. let x be the leftmost unvisited location and y the rightmost, then if our current position z is between them, it will require at least min(2(z-x) + y-z, z-x + 2(y-z)) to visit both of them from z. (If instead z is to the left or to the right of all unvisited cities, it will take at least y-z, or at least z-x, respectively.) Taking predecessors into consideration could improve the bounds considerably.

Upvotes: 1

Related Questions