Где найти набор сложных задач коммивояжёра (с известными решениями/приближениями)?

Я хочу попробовать свои силы в поиске эвристик/аппроксимаций для решения задачи коммивояжёра, и для этого я ищу несколько «жестких» экземпляров TSP (вместе с их наиболее известными решениями), чтобы попытаться решить их и посмотреть, насколько хорошо я могу сделать.

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

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


algorithm language-agnostic traveling-salesman np-hard np-complete
person user541686    schedule 09.03.2013    source источник

Ответы (3)


arrow_upward
3
arrow_downward

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

Если вы не можете их найти, как насчет случайного создания набора узлов вместе с путем, соединяющим их, сохраняя длину пути как «минимальную» (убедившись, что самое длинное соединение между двумя узлами никогда не > X), а затем добавляя кучу других путей, чтобы убедиться, что все они> X?

Таким образом (если я что-то не упустил) у вас есть набор подключенных узлов "настолько сложный, насколько вы хотите" и с самого начала знаете фактический кратчайший путь соединения...

Дополнение: если вы действительно хотите сравнить свои инструменты с существующими, вам нужно запустить их на сгенерированных проблемах. Бесплатный и доступный (но я не знаю, насколько "эффективным" он может быть) является Библиотека TSP для R.

В Википедии есть список других бесплатных программных пакетов для этого.

Возможно, вы могли бы создать другой вопрос SE с вопросом, как получить другие инструменты TSP.

person p.marino    schedule 09.03.2013
comment
Что ж, проблема не только в их генерации — проблема в том, как мне узнать, насколько хорошо я справляюсь по сравнению с сегодняшними хорошими решателями TSP? Все это могло бы сказать мне, как я справляюсь с оптимальным решением, которого у меня нет надежды достичь, учитывая достаточно сложный граф, а не насколько хорошо я справляюсь по сравнению с существующими инструментами. - person user541686; 09.03.2013
comment
Что касается вашего редактирования: я надеюсь избежать накладных расходов (загрузка и установка целых наборов инструментов только для решения пары проблем TSP и т. д.)... поэтому я действительно предпочитаю искать существующие проблемы/решения, а не тратить много времени генерирую их самостоятельно, а затем нахожу решения для них. - person user541686; 09.03.2013
comment
+1 ссылка на GATech выглядит интересно, посмотрю; благодаря. - person user541686; 09.03.2013

arrow_upward
1
arrow_downward

Сайт шлюза TSP кажется каноническим сайтом для информации TSP.

Вот список доступных наборов данных: http://www.tsp.gatech.edu/data/index.html

Оптимальное решение доступно для некоторых наборов данных с более чем 10 000 городов. Доступны наборы данных по более чем 1 000 000 городов.

person Geoffrey De Smet    schedule 10.03.2013

arrow_upward
0
arrow_downward

Существует известный алгоритм поиска оптимального решения TSP — он называется перебором.

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

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

Единственный реальный способ, с помощью которого вы сможете сравнить свой алгоритм с другими, — это реализовать другие алгоритмы, а затем ставить свои и их те же самые сложные задачи (и, как определили другие, легко сделать, по крайней мере, некоторые типы сложных задач). ). Реализация этих существующих алгоритмов может предложить способы улучшения вашего. http://en.wikipedia.org/wiki/Travelling_salesman_problem содержит множество алгоритмов, и по крайней мере пара выглядит очень легко кодируемой. Почему бы не реализовать их в качестве первого эталона для вашего алгоритма?

person Peter Webb    schedule 09.03.2013