1D travelingsalesman с ограничением

Question

Я работаю над алгоритмом, который кажется очень простой проблемой, но я не могу найти для него эффективный алгоритм. Проблема заключается в следующем: У меня есть список чисел (0-50) и место начала и вам нужно посетить каждый из них, одновременно минимизируя пройденное пройденное расстояние. Некоторые пары мест требуют, чтобы я сначала побывал в другой (так, чтобы посетить 29, я должен сначала что-то набрать 26). Однако я не могу понять, как это сделать, просто не генерируя каждый вариант. Есть идеи?

Например, мы имеем следующую

startLocation=25; 
targetPairs=[[1,5],[7,12],[22,23]] 
visitLocations=[4,6,8,2] 

это означает, что мы должны посетить 1 до 5, 7 до 12 и 22, прежде чем 23. Мы также должны посетить расположение 4,6,8 и 2 Один из вариантов, который нужно начать, - это пойти слишком 1 (расстояние 24), затем перейдите к 4 (расстояние 3 всего 27), затем перейдите к 5 (расстояние 1 всего 28), тогда мы можем перейти на 6 (всего 1 всего 29) или для полного набора (7 (30), 8 (31), 12 (35), 22 (45), 23 (46)).

Логично ограничение количества мест, которые мы должны посетить, составляет 50 пар и 50 мест.

Answer 1

Проблема может быть решена с помощью следующего потенциально экспоненциального алгоритма, и если это NP-жесткий (как я подозреваю), то вы не сможете сделать намного лучше (где «много», I означает найти алгоритм с полиномиальной временной сложностью - вполне возможно уменьшить базу алгоритма экспоненциального времени).

В принципе, сделайте лучший поиск в пространстве состояний, в котором каждое состояние состоит из двух вещей: текущей позиции и набора уже посещенных мест. (Это, к сожалению, не достаточно просто отслеживать количество уже посещаемых городов.) У нас всегда есть в большинстве 2 следующих шагов от каждой точки в этом пространстве состояний:

1. Перемещение влево на ближайший посещаемых расположение
2. Переместить право на ближайших Visitable место

это потому, что всегда есть оптимальное решение, в котором каждое место посещается в первый раз, мы двигаемся в прошлое или это после того, как оно стало доступным для посещения. Здесь «visitable» означает, что все предшественники местоположения (включая предшественники предшественников и т. Д.) Уже были посещены.

Любое состояние, в котором все местоположения уже были посещены, является состоянием цели. Используя наилучший поиск (реализуемый с приоритетной очередью, или в этом случае просто массив размером 50), первое такое состояние будет соответствовать оптимальному решению. Этот алгоритм займет время экспоненциально в количестве мест, которые необходимо посетить.

Этот поиск можно ускорить с помощью алгоритма A *, то есть с помощью допустимых эвристик определить нижнюю границу расстояния, оставшегося от данного состояния. Здесь довольно легко придумать что-то разумное - например, пусть x - крайнее левое место, а y - самое правое, то, если наше текущее положение z находится между ними, для этого потребуется как минимум min (2 (zx) + yz, zx + 2 (yz)), чтобы посетить оба из них из z , (Если вместо z находится слева или справа от всех невидимых городов, это займет как минимум y-z, или, по крайней мере, z-x, соответственно.) Принимая во внимание предшественники, можно значительно улучшить границы.