Реализация PTAS для евклидова TSP?

Question

Я готов реализовать алгоритм для решения 2-dimensional Euclidian version of the Traveling Salesman Problem наиболее эффективным способом (т. Е. Наиболее точный результат + наименьшее время). Во время моих исследований я нашел множество алгоритмов, но Arora's 1998 paper и его presentation поразили меня, возможно, лучшие для этой цели. Существуют и другие варианты решения, использующие ту же идею, что и одна из них: Schultes в 2004 году. Проблема в том, что это невероятно сложно (если не невозможно) для ее реализации, и я не нашел записей о тех, кто когда-либо делал это доступным способом даже несмотря на то, что прошло почти 20 лет с момента опубликования этой статьи.

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

Answer 1

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

Помимо сложностей, «практическая проблема с PTAS заключается в том, что показатель степени полинома может резко возрастать по мере сжимаемости ε, например, если время выполнения равно O (n (1/ε)!)». Это приводит к еще более жестким требованиям, таким как EPTAS и FPTAS, хотя я не считаю, что TSP в настоящее время имеет решения по этим более строгим требованиям. Поэтому имейте в виду, что решение PTAS не обязательно устраняет широкую изменчивость по мере изменения параметра аппроксимации.

Самая подходящая бумага, которую я нашел для вашего сообщения, - An Empirical Analysis of Approximation Algorithms for Euclidean TSP.

Новаторская полиномиальной аппроксимации схемы (СПТ) для евклидовой TSP был дан Санджив Арора. На сегодняшний день нет данных , которые могут быть реализованы, чтобы быть практически полезными. В свете , мы предлагаем реализацию евклидова TSP, которая составляет , на основе существенных шагов PTAS Arora и добавляет эвристику , чтобы улучшить время работы.

Авторы не предоставляют ссылку на их реализацию на С ++, но вы можете попробовать отправить их по электронной почте. Более важным аспектом их работы является количественное сравнение их подхода, основанного на Ароре, и 4 других конкурентных алгоритма, предоставляемых в решателе Concorde. В их документе делается заключение:

Экспериментальные результаты показывают, что ПТАС Arora практически осуществима. Таблица I и Таблица II показывают, что, несмотря на ее хорошую производительность, кажется, что наш подход должен быть улучшен, чтобы генерировать более приблизительные решения . В большинстве случаев значительные теоретические результаты теряются в связи с принятием решений. Мы считаем, что качество решений связано с аспектами реализации, связанными с структурами данных, и необходимостью давать больше подсказок о том, какие порталы должны использоваться в туре .

Если вы прочтете их статью подробно, вы увидите, что они приняли различные решения и оптимизационные решения, многие из которых, вероятно, являются субоптимальными и/или не строго обоснованными. Прочтите результаты для себя, но мне кажется, что их алгоритм ПТАС завершил в 0,25x до 1,0x время других алгоритмов в среднем, но результаты иногда были значительно хуже.Мне кажется, что самый большой риск здесь - это «решения по внедрению» и эвристики, которые могут потребоваться для проб и ошибок в надежде на то, что они действительно реализуют эти неуловимые преимущества в производительности.