Оптимизация алгоритма - кратчайший путь между несколькими точками

Question

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

Пример: я в отпуске и нахожусь в определенном городе. Я еду ОДИН ПУТЬ, чтобы увидеть ЛЮБЫЕ четыре города, и я хочу проехать как можно меньше. Я не могу посещать один и тот же город более одного раза.

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

Как лучше всего искать кратчайший маршрут?

Answer 1

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

---

Для будущих опрошенных: Алгоритм Флойд-Варшалла и все подобные Флойду вариации здесь неприменимы.

Answer 2

Вообще вам следует строго плохие варианты ... Я думаю, что вы должны использовать некоторые варианты метода Branch_and_bound http://en.wikipedia.org/wiki/Branch_and_bound

Answer 3

Либо первый поиск, как сказал norheim.se, либо алгоритм Дейкстры также будет моим предложением.

Answer 4

Это очень распространенная ситуация в реальном времени, в которую может попасть каждый пользователь. Интерфейс пользователя карты Google дает вам путь в том же порядке, который вы добавляете в список адресатов. он не дает вам оптимального пути, хотя их собственный API карт Google обеспечивает решение.

Google Maps API предоставляет решение для этого. В запросе для определения пути необходимо указать флаг «optimizeWaypoints: true». Запрос будет выглядеть так.

var request = {
            origin: start,
            destination: end,
            waypoints: waypts,
            optimizeWaypoints: true,
            travelMode: google.maps.TravelMode.DRIVING
        };

и вы можете увидеть весь код утилиты в виде исходного кода, так как полная утилита разработана в javascript и HTML.

Надеюсь, это поможет.

Answer 5

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

Предположим, у вас уже есть двухточечный алгоритм кратчайшего пути - он имеет классические решения для различных видов графиков. Предположим, что все расстояния неотрицательны и d (A-> B-> C) = d (A-> B) + d (B-> C).

Основным является то, что путь начинается в S, проходит через один из промежуточных городов "abcd" и заканчивается E:

например. SabcdE, SacbdE и т.д ...

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

Тогда, учитывая начальную и конечную точку, есть 12 возможностей, привязанных к одному из abcd и для каждых двух возможностей для интерьера. Вы уже вычислили эти расстояния, поэтому вы добавляете расстояние от S до головы и от хвоста до E. Выберите минимум. Поэтому, предварительно рассчитав промежуточные расстояния для фиксированного набора внутренних городов, вам нужно выполнить 12 двухточечных задач кратчайшего пути для любой пары начальной и конечной точек.

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

Пример моей мысли: предположим, что все промежуточные расстояния между городами O (1). Без ограничения на графике, расстояние от S до любого промежуточного города может быть 1000, за исключением одного, равного 1. То же самое для хвоста. Таким образом, вы можете заставить первый город, который будет посещен, быть чем угодно. Теперь, пройдите на один слой вниз, возьмите первый город в качестве «начальной точки». Примените тот же аргумент: вы можете выбрать лучший путь для любого из следующих городов, манипулируя расстояниями на графике.

Так что, кажется, что сложность не может быть решена без дополнительных предположений.

Answer 6

Это звучит как коммивояжёр? Одним из решений является использование метода оптимизации, такого как эволюционный алгоритм. В настоящее время вы выполняете исчерпывающий поиск, который будет очень медленным и очень быстрым. Но я думаю, что это в значительной степени проблема коммивояжера, и она решалась в течение нескольких десятилетий, если не столетий, и существует несколько возможных способов атаки. Google твой друг.

Answer 7

Похоже, что края вашего графика двунаправленные. В этом случае вы ищете алгоритм Дейкстры .