Эвристика коммивояжера во времени NlogN

Перепрофилировав общий алгоритм машинного обучения, мы можем получить быстрое решение заведомо сложной проблемы.

Какой алгоритм?

Мы можем использовать кластеризацию KMeans для рекурсивного разделения наших точек. Если K = 4, мы начинаем с квадрата, который делит все точки на четыре квадранта. Затем каждую вершину можно разделить на четыре кластера, и мы найдем кратчайший путь, который объединяет эти четыре кластера в существующий квадрат. Процесс повторяется до тех пор, пока кластеры не сойдутся в самих точках. Алгоритм KMeans равен O (N), и он повторяется в среднем logK (N) раз.

Стоит ли эта эвристика?

Я провел несколько тестов с файлами из базы данных TSP Университета Ватерлоо, и этот алгоритм предлагал решения, которые часто находились в пределах 20 процентов от предполагаемой минимальной границы.

Однако вместо того, чтобы занимать часы или дни, каждое решение решалось менее чем за 5 минут. Время, необходимое для завершения каждой из этих стран, показано на следующей диаграмме:

Этот алгоритм не сравнивался с другими алгоритмами NlogN (предложения приветствуются); однако его сравнивают с алгоритмом наименьшей вставки (SI), который требует времени N². При выполнении 1000 тестов на случайных узлах при N = 100 рекурсивная кластеризация лучше, чем SI, более чем в 59% случаев, несмотря на то, что SI занимает значительно больше времени.

Мое тестирование можно найти в этом блокноте Jupyter.

Программная реализация

Вот ссылка на код на GitHub, и вот три высокоуровневые функции, которые предлагает программа:

import recursive_clustering as rc
# Create 100 random points and draw solution with K = 4
rc.solve_random(N=100, K=4)
# Given a numpy array, draw the solution
rc.solve_array(all_nodes, K=4)
# given a two-column CSV of X and Y, draw the solution
rc.solve_file('testFiles/usa115475.csv', K=5, draw=False)

Все эти функции возвращают словарь, длину обхода и время ожидания. Словарь имеет следующую структуру:

path_d = {
     ID0: {
          'center': [X, Y],
          'connections': [ID#, ID#],
          'subnodes': [[x, y]....[x ,y]],
          'hasBeenSplit': True
     },
     ID1: ...
}

Этот словарь содержит все кластеры и их подузлы. Если вы хотите получить доступ только к последним узлам, вы должны искать только ключи, subnodes список которых имеет длину один или не был разделен. Или вы можете перейти к последнему идентификатору и проследить связи по кругу. Предложения по улучшению реализации приветствуются.

Какое значение K мне следует использовать?

Алгоритм рассматривает все возможные перестановки K, когда он интегрирует новые кластеры K в существующую форму. Имея это в виду, больший K может очень быстро стать медленнее, чем N². Для точек от 1000 до 10000, K = 5, кажется, предлагает кратчайший путь. K = 5 также постоянно быстрее, чем все другие значения K, вероятно, потому, что его 120 перестановок перевешиваются более быстрой сходимостью.

Можем ли мы сделать это лучше?

Разработка какой-либо статистической модели для поиска оптимального значения K с учетом количества подузлов может быть простой и стоящей областью исследований в будущем. В настоящее время K статичен на протяжении всего процесса; однако моя интуиция подсказывает мне, что изменение K в зависимости от его подузлов уменьшит длину обхода и время выполнения.

Вдобавок, хотя я еще не проводил никаких тестов, этот алгоритм теоретически будет работать за время NlogK (N) и на многомерном TSP.

Вопросы? Вы нашли ошибки? Свяжитесь со мной и узнайте больше о проектах на моем сайте.

Эвристика коммивояжера во времени NlogN