Пример коммивояжера с известным глобальным оптимумом
Я сделал имитационный алгоритм в Python для проблемы коммивояжера. Однако все данные тестирования (список расстояний между городами) я встретился, испытывают недостаток в информации лучшего решения, таким образом, я не могу знать, как близко к глобальному оптимуму мой алгоритм добирается.
Кто-либо знает, где я могу найти некоторые tsp данные тестирования (предпочтительно в матричной форме, но что-нибудь хорошо) с известным лучшим решением?
2 ответа
Вы гуглили?
http://www.tsp.gatech.edu/data/index.html
На этой странице представлено несколько тестовых примеров, из которых 16 имеют оптимальное решение.
Возможно, вы сможете сгенерировать свои собственные тестовые данные?
Это определенно не будет всесторонним тестированием, но может помощь. Примечание: ниже приведен гамильтонов путь, и если вы ищете циклы, что-то подобное будет работать.
Вы можете сделать следующее:
Допустим, вам дан неориентированный граф G с n узлами.
Теперь вы создаете взвешенный граф G ', устанавливая вес ребер в G равным 1 и добавляя ребра, не входящие в G, и давая им случайный вес> 1, т. Е. G' является полным графом с весами присваивается всем его краям.
Теперь, если вы запустите действительный алгоритм TSP на G 'и он сгенерирует путь размера n-1, тогда G будет иметь гамильтонов путь. В противном случае G не имеет гамильтонова пути.
Итак, теперь вы можете использовать графы, которые вы знаете , которые имеют / не имеют гамильтоновы пути (например, Hypercube имеет гамильтоновы пути) и генерировать тестовые данные для вашего алгоритма TSP.
На этой странице есть некоторые достаточные условия, которые могут оказаться полезными при создании графов с гамильтоновыми путями: http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html
I предположим, вам не составит труда найти данные на графах с гамильтоновыми путями или без них.
Надеюсь, это поможет. Удачи!