Путешествующий продавец - приблизительное программное обеспечение онлайн?

Question

Кто-нибудь из вас знает решение для создания даже посредственного решения проблемы коммивояжера. У меня есть 3 человека, которые хотели посетить 31 пункт назначения... Я не знаю, как подойти к этому?

Спасибо всем -

Максим

Answer 1

Я полагаю, что вы можете попробовать жадный подход, выбрав произвольную точку для начала (если начальная точка не указана), а затем на каждом шаге вы перемещаетесь к ближайшей точке к вашей текущей точке. Предполагая, что расстояние между точками можно рассчитать за постоянное время, вы можете найти путь за O(n^2) времени.

Чтобы уточнить, следующий псевдокод должен помочь (я давно не писал такого рода вещи, поэтому я надеюсь, что это достаточно ясно)

Name: GreedyPath(C, p)
Input: C - a non-empty collection of points to visit
       p - a starting point in C
Output: S - a sequence of points covering C
Algorithm:
  Remove p from C
  If C is empty
    Return the sequence containing only p
  Else
    Let p1 be the closest point to p in C
    Let S = GreedyPath(C, p1)
    Append p to the start of S
    Return S

Очевидно, что трудоемкая часть находит ближайшую точку к p каждый раз, но для n Очки это должно только потребовать n(n-1)/2 Расчет расстояния (если я не ошибаюсь).

Answer 2

Есть несколько вариантов, включая: Ближайший сосед, Кристофидес и Лин-Керниган.

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