Hi there Im работает над проектом, который должен решить проблему TSP. То, что мне нужно, это то, что я могу найти гамильтоновские схемы на графике. На самом деле я знаю, как это сделать в реальном мире. Но в реализации и в исходном коде я не знаю, как это можно сделать. Я читал статьи в Интернете, которые используют некоторые вложенные циклы, но я не понял, что каждый из них делает и как происходит вся история. Я бы оценил, может ли кто-нибудь помочь мне в этом. И дайте мне простой пример того, как это реализовать. Мне не нужна рабочая модель. Предположим, что у нас есть массив вершин и массив путей (по пути я подразумеваю начальную и конечную вершины пути). Как мы можем решить эту проблему.Проблема в поиске гамильтоновой схемы для задачи TSP
0
A
ответ
1
Одним из наиболее эффективных способов нахождения точного решения TSP является использование алгоритма динамического программирования, который работает в O (n^2 * 2^n). Это довольно просто по сравнению с некоторыми альтернативами линейного программирования. Найдите «динамическое программирование TSP», и вы наверняка найдете много примеров.
Есть более наивные подходы, такие как грубая сила, которая работает в O (n!). Если вы видели много циклов для циклов (т. Е. Более двух), это, скорее всего, тот тип алгоритма, который вы видели раньше. Они сделают работу (возможно, не в этой жизни, в зависимости от размера вашего графика).
Я не уверен, что понимаю, что вы хотите, но чтобы решить TSP самым быстрым способом, вам нужно объединить различные алгоритмы, такие как: ближайший сосед, 2-opt, 3-opt, ant algorithm, ... Проблема заключается в том, лучше комбинировать их, чем программировать. – Pietro 2010-12-16 13:21:32
Нет моей проблемы не найти быстрый способ, это просто о ее реализации. Я имею в виду, по каким шагам я могу найти цикл на графике? Затем я хочу сравнить циклы и посмотреть, какой из них посещает все узлы, а затем я хочу найти минимальный тур. Я знаю, что это не хороший алгоритм, но я хочу реализовать именно это. И я не знаю, как алгоритм программирования для нахождения цикла в графе. – user435245 2010-12-16 13:25:45