У меня есть полный взвешенный граф с 1000 узлами, и мне нужно найти максимально длинный гамильтонов путь в графе (точнее, последовательность узлов).Я должен уместиться в 5 секунд (для Java), ограничение памяти достаточно велико.Поиск самого длинного гамильтонова пути мало чем отличается от поиска решения для TSP (коммивояжера).Конечно, об оптимальном решении не может быть и речи, поэтому я ищу хорошую эвристику.Моим лучшим решением на данный момент является использование алгоритма Nearest Neighbor, который прост в реализации и выполняется за полиномиальное время (занимает ~ 0,7 секунды для графа 1000 узлов).Это немного далеко от оптимального решения.Поэтому я ищу лучшую эвристику, которая все еще работает относительно быстро.Я вижу упомянутый поиск Табу, Имитация отжига, Муравьиная колония, Генетика, Ветвление и связывание, алгоритмы на основе MST и другие.Проблема в том, что их реализация не совсем тривиальна, трудно найти их временную сложность, чтобы решить, что может уместиться в 5 секунд.лимит времени;например, запустить в полиномиальное время.Для некоторых алгоритмов, таких как Christofides ', я вижу, что сложность составляет O (V ^ 4), где V - число вершин, что, по-видимому, делает невозможным подгонку.
Я сталкивался с решением Bitonic Tour, обычноиспользуется для нахождения кратчайшего гамильтонова пути в евклидовых графах, но, похоже, тоже подходит для нахождения самой длинной траектории в неевклидовых графах:
public static void minCostTour(int[][] graph) {
int n = graph.length;
int[][] dp = new int[n][n];
dp[0][1] = graph[0][1];
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++)
if (i == (j - 1) && i != 0) {
dp[i][j] = dp[0][j-1] + graph[0][j];
for (int k = 1; k <= j - 2; k++)
if ((dp[k][j-1] + graph[k][j] < dp[i][j])) {
dp[i][j] = dp[k][j-1] + graph[k][j];
}
} else if (i != 0 || j != 1) {
dp[i][j] = dp[i][j-1] + graph[j-1][j];
}
}
System.out.println("Optimal Tour Cost: " + (dp[n-2][n-1] + graph[n-2][n-1]));
}
Стандартный алгоритм включает начальную сортировку координат, которую я пропустил, поскольку, по-видимому, нет координат для сортировки (график неевклидов).Это решение динамического программирования работает в O (V ^ 2), так что это может быть хорошо.Проблема в том, что он выводит длину пути гамильтониана, и мне нужна последовательность узлов.Я не могу понять, как восстановить путь из приведенного выше алгоритма (если это вообще возможно).
Версия TL DR: Можно ли использовать приведенный выше алгоритм Bitonic Tour для нахождения последовательностиузлов на самом длинном гамильтоновом пути в полном весовом графе?Если нет, можете ли вы порекомендовать алгоритм с аналогичной (полиномиальной) временной сложностью для этой задачи?