Вычислите кратчайший путь через продуктовый магазин

Ну, в основном это проблема коммивояжера, но с вашими требованиями вы довольно хорошо ограничиваете пространство поиска. Если местоположений не так много, вы можете попытаться вычислить все возможные варианты, но если это невозможно, вам нужно еще больше ограничить пространство поиска.

Вы можете ограничить время поиска, чтобы вы вернули кратчайший путь, который вы можете найти за 1 секунду, но он может быть не самым коротким из всех, но в любом случае довольно коротким.

Вы также можете применить Жадный алгоритм , чтобы найти следующее ближайшее ближайшее местоположение, затем, используя Отслеживание с возвратом , выберите следующее ближайшее ближайшее местоположение и т. Д.

Псевдокод для возможного решения:

def find_shortest_path(current_path, best_path):
  if time_limit()
    return

  if len(current_path) == NUM_LOCATIONS:
      # destionation reached
      if calc_len(current_path) < calc_len(best_path):
          best_path = current_path
      return

  # You need to sort the possible locations well to maximize your chances of finding the
  # the shortest solution
  sort(possible_locations)

  for location in possible_locations:
      find_shortest_path(current_path + location, best_path)

Похоже, рассмотрение этого вопроса как проблемы TSP усложняет задачу. Кто-то заметил, что продуктовые истории не так уж и сложны. В знакомых мне продуктовых магазинах (в США) не так уж и много разумных маршрутов. Особенно, если у вас есть заданная отправная точка. Я думаю, что хорошо продуманная эвристика, вероятно, поможет.

Например: я обычно начинаю с одного конца - если это большая поездка, я обязательно просматриваю замороженные продукты в последнюю очередь, но часто это не имеет значения, и я начинаю ближе всего к тому месту, где я захожу в магазин. Я обычно хожу по улице, идя по отдельным проходам только в том случае, если мне что-то нужно в этом. Как только вы войдете в проход, подберите все, что находится в нем. В некоторых проходах лучше перейти в один конец, схватить предмет и вернуться к исходной точке, а в других вы просто передадите весь проход - это функция последнего элемента, который вам нужен в этом проходе, и там, где вам нужно. быть следующим - как выбраться из прохода зависит от следующего необходимого элемента - он может включать или не включать возврат - но компьютер может легко вычислить кратчайший путь к следующим элементам.

Я согласен с полезными советами по другим проблемам, приведенным выше, но, возможно, будет работать менее общий алгоритм. И, вероятно, будет лучше работать с ограниченными ресурсами. Однако TSP сообщает нам, что вы не можете доказать, что это оптимальный подход, но я подозреваю, что в этом нет необходимости ...

Что ж, вы можете ограничить пространство поиска, используя информация о планировке магазина. Например, в типичном магазине (по крайней мере, здесь, в Германии) много полок, которые можно рассматривать как переулки. Между ними есть перпендикулярные полосы, которые соединяют полосы между полками. Теперь вы определяете перекрестки как узлы, а полосы как ребра в графе. По краям обозначены все предметы на полках этого участка переулка. Теперь даже для большого магазина этот график будет довольно маленьким. Теперь вам нужно будет найти кратчайший путь, который включает в себя все необходимые вам метки (элементы). Это должно быть возможно при использовании жадного подхода с обратным отслеживанием , который предложил Туомас Пелконен .

Это всего лишь идея, и я не знаю, действительно ли она работает, но, возможно, вы сможете ее взять отсюда.

Только поиск в ширину гарантирует, что вы не «пропустите» путь через магазин, что лучше, чем ваше текущее «лучшее» решение, но вам не нужно искать каждый узел на пути. Узлы, которые «очевидно» длиннее текущего «лучшего» решения, могут быть расширены позже.

Это означает, что вы подходите к проблеме как поиск «сначала дыхание», но изменяете расширение ваших узлов в зависимости от текущего пройденного расстояния. Некоторые ветви дерева поиска будут расширяться быстрее, чем другие, потому что им удастся посетить больше узлов за то же время.

Итак, если расширение узла на самом деле не в первую очередь, почему я продолжаю использовать это слово? Потому что после того, как вы действительно найдете решение, вы все равно должны расширить текущий набор «рассматриваемых узлов», пока каждый из этих путей поиска не превзойдет решение. Это позволяет избежать пропуска пути, который требует много времени на начальных этапах, но заканчивается быстрее, чем текущее решение, потому что последний этап быстро освещается.

Требование начального узла является фиктивным. Используя TSP, вы получите обзор, в котором вы сможете выбрать нужный начальный узел без изменения стоимости решения.

С счетчиками дело обстоит сложнее: вам нужно решить задачу на ориентированном графе с отсутствием некоторых дуг (или, что то же самое, где некоторые дуги имеют действительно высокую стоимость).

Начиная с полного ориентированного графа, вы должны изменить стоимость соответствующих дуг, чтобы:

1. запретить переход от элементов к начальному узлу
2. запретить переход от счетчиков к элементам
3. запретить движение от начального узла к счетчикам
4. позволяют переходить от счетчиков к начальному узлу с нулевой стоимостью (это необходимо только для закрытия пути)
5. после того, как нарисовал вещь, скажите мне, если я что-то пропустил :)

HTH