Ищем алгоритм эффективного маршрута

Я хочу написать приложение, которое поможет, скажем, коммивояжеру/музыканту спланировать свой тур.

Так что речь идет о создании эффективного маршрута.

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

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

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

Я посмотрел на A *, но, похоже, это только начальная и конечная точки.

Любые идеи приветствуются

Благодарность

Алекс


algorithm graph-algorithm
person bergin    schedule 30.07.2014    source источник
comment
Вы загуглили Traveling Salesman и просмотрели en.wikipedia.org/wiki/Travelling_salesman_problem?   -  person wckd    schedule 30.07.2014
comment
слышал об этом, не был уверен, касается ли это моей проблемы или нет   -  person bergin    schedule 30.07.2014
comment
Это касается именно того вопроса, который вы задаете. Если вам не нужна дополнительная информация об API для сбора данных о различных поездках/проживании/других факторах, влияющих на эффективность, по пути. В этом случае это не вопрос алгоритма.   -  person mfa    schedule 30.07.2014
comment
Нет, это определенно это вопрос об алгоритмах, решающих TSP. Данные о ребрах - это позже, когда у меня будет рабочая реализация подходящего алгоритма, который решает TSP, но мое подозрение на данный момент состоит в том, что доступные алгоритмы - это лучшие попытки, а не точные решения, поскольку его NP сложно - немного беспокоясь об этом, прежде чем я даже начал!   -  person bergin    schedule 31.07.2014

Ответы (3)


arrow_upward
3
arrow_downward

Как писали другие авторы, это задача коммивояжера. Для планировщика вашего музыкального тура вам потребуются оба: (i) алгоритм, вычисляющий путь с наименьшей стоимостью из одного места в другое [через физическую сеть], И (ii) алгоритм, вычисляющий наилучшую последовательность мест с учетом вашего начального и конечного местоположения. и дополнительные ограничения, такие как временные окна.

(i) может быть решена, например, с помощью Дейкстры, А*, иерархий сжатия

(ii) может быть решена с помощью Held-Karp, Branch and Bound/Cut [точно] и Lin-Kernighan или любой другой (мета)эвристики, которая также применяется для решения задач маршрутизации транспортных средств (VRP) [эвристически]

Однако эффективная реализация этих алгоритмов не вопрос дней. Таким образом, я бы рекомендовал вам использовать существующее программное обеспечение. Для (i) идеальным выбором будет GraphHopper, а для (ii) вы можете попробовать jsprit. Оба написаны на Java и имеют открытый исходный код.

person Stefan Schröder    schedule 04.08.2014

arrow_upward
1
arrow_downward

TSP (задача коммивояжера) — это то, что вам нужно, вам просто нужно настроить функцию стоимости так, чтобы она не зависела исключительно от расстояния. Скорее всего, вы захотите перевести расстояние в фактическое значение в долларах, которое учитывает стоимость поездки, а также время в пути.

Было бы неплохо иметь ползунок, чтобы смещать расчет либо в сторону времени в пути, либо в сторону стоимости поездки (время — деньги и все такое). Хотя неясно, насколько это будет полезно, учитывая, насколько интенсивными вычислениями обычно является оптимизация экземпляра TSP.

person Nuclearman    schedule 30.07.2014

arrow_upward
1
arrow_downward

Как уже упоминалось, это случай задачи коммивояжера (TSP). Обратите внимание, что TSP можно решить с помощью алгоритма грубой силы, когда n, количество городов, не слишком велико. Музыкант может захотеть посетить только 15 городов или меньше, поэтому вы все равно можете найти лучший путь с помощью перебора. Вам просто нужно рассчитать вес между разными городами (расстояние и другие факторы), а затем проверить все возможности, чтобы найти наилучшие возможные маршруты. Если городов больше 20, оптимальное решение все равно можно найти, но нужен алгоритм получше, чем прямой перебор.

person Ari    schedule 31.07.2014