Самая короткая общая траектория между множеством широты/долготы

У меня есть набор из 52 пар широты/долготы. Мне просто нужно найти кратчайший путь через все из них; не имеет значения, где точка зрения или конечная точка.Самая короткая общая траектория между множеством широты/долготы

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

Вы знаете какие-либо библиотеки или существующие сценарии/приложения, которые будут вычислять кратчайший путь таким образом? В коде/библиотеках предпочтительно использовать Python или Clojure, но это действительно не имеет значения.

Благодаря

источник

2009-11-01 Brian Gianforcaro

Если это замкнутый путь, это задача коммивояжера, и неоптимальный, но весьма эффективный способ ее решения заключается в использовании Simulated Annealing

источник

2009-11-01 02:12:35 Mathias

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

@ THC4k Я знаю, что это был не вопрос, но этот комментарий просто полностью позволил мне закончить мой код самым простым простейшим способом , У меня уже был TSP с закрытым путем. Благодаря! –

Разве это не Traveling Salesman Problem, и, следовательно, не существует эффективный способ решить эту проблему?

источник

2009-11-01 02:08:19

Это TSP без оговорок окончания, где вы начали, поэтому теоретически вы должны получить гораздо более короткое общее расстояние. –

Пик! TSP - это O (n!), Не так ли? У него только 52 пары = что-то вроде 8.07e + 67 возможностей, нет? : p – mpen

Нет эффективного способа найти решение _optimal_, возможно ... но есть _fairly good_ решения. –

В Python, обработка лучшего графиком библиотеки я был в состоянии положил руки networkx. Он поддерживает широкий спектр различных альгос для short path search.

Пойдите для этого. Это действительно полно и хорошо спроектировано.

источник

2009-11-01 07:43:09

Самая короткая общая траектория между множеством широты/долготы

ответ

Смежные вопросы