Задача нахождения гамильтоновой схемы для задачи TSP

Question

Привет Я работаю над проектом, который должен решить проблему TSP. Здесь мне нужно то, как я могу найти гамильтоновы схемы в графе. На самом деле я знаю, как это сделать в реальном мире. Но в реализации и исходном коде я не знаю, как это можно сделать. Я прочитал статьи в Интернете, в которых используются некоторые вложенные циклы, но я не понял, для чего каждый из них делает и как проходит вся история. Я был бы признателен, если кто-то может помочь мне в этом. И приведите простой пример того, как это реализовать. Мне не нужна рабочая модель. Просто предположим, что у нас есть массив вершин и массив путей (под путем я подразумеваю начальную и конечную вершины пути). Как мы можем решить эту проблему.

Answer 1

Одним из наиболее эффективных способов найти точное решение для TSP является использование алгоритма динамического программирования, который работает в O (n ^ 2 * 2 ^ n). Это довольно просто по сравнению с некоторыми альтернативами линейного программирования. Ищите «Динамическое программирование TSP», и вы наверняка найдете много примеров.

Есть более наивные подходы, такие как грубая сила, которые работают в O (n!). Если вы видели много циклов for (то есть: более двух), это скорее всего тот тип алгоритма, который вы видели раньше. Они выполнят работу (возможно, не в этой жизни, в зависимости от размера вашего графика).