ПРИМЕР ПЕРЕДАЧИ ПРЕДЛОЖЕНИЯ с известным глобальным оптимальным

Question

Я сделал мемотический алгоритм в Python для Проблема с продавцомАнкет Тем не менее, все тестовые данные (список расстояний между городами), с которыми я столкнулся, не хватает информации о лучшем решении, поэтому я не могу знать, насколько близко к глобальному оптимуму, мой алгоритм.

Кто -нибудь знает, где я могу найти некоторые тестовые данные TSP (предпочтительно в форме матрицы, но что -то хорошее) с известным лучшим решением?

Answer 1

Вы Google?

http://www.tsp.gatech.edu/data/index.html

Эта страница содержит несколько тестовых случаев, из которых 16 имеет оптимальное решение.

Answer 2

Возможно, вы можете генерировать свои собственные тестовые данные?

Это определенно не будет полным тестированием, но это может помочь. Примечание. Ниже приведено о гамильтонианском пути, и если вы ищете циклы, сработает что -то подобное.

Вы можете сделать следующее:

Скажем, вам дают неправомерный график G с N -узлами.

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

Теперь, если вы запускаете действительный алгоритм TSP на G ', и он генерирует путь размера N-1, то G имеет гамильтонианский путь. В противном случае G не имеет гамильтонианского пути.

Итак, теперь вы можете использовать графики, которые вы знать У этого нет гамильтонианских путей (например, например: Гиперкуб имеет гамильтонианские пути) и генерируйте тестовые данные для вашего алгоритма TSP.

Эта страница имеет достаточные условия, которые могут оказаться полезными при создании графиков, которые имеют гамильтонианские пути: http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html

Я полагаю, вам не будет трудно найти данные на графиках с/без гамильтонианских путей.

Надеюсь, поможет. Удачи!

Answer 3

TSPlib - это библиотека экземпляров образцов для TSP (и связанных с ними задач) из различных источников и различных типов.

http://comopt.ifi.uni-heidelberg.de/software/tsplib95/