Решение TSP с использованием Neo4j

Question

Можно ли решить проблему с Traveler Salesman или Multi-TSP с помощью Neo4j?

Мне нужно найти оптимальный путь, который охватывает все узлы. Я попытался найти все возможные пути, а затем найти минимальное расстояние. Время выполнения увеличивается экспоненциально по мере увеличения количества узлов.

Answer 1

Проблема с продавцом - quintessential example of an NP-hard problem. Таким образом, время выполнения не увеличивается экспоненциально как, если бы это было так, это было бы многочленом. На самом деле, наверное, это хуже. :)

Эти алгоритмы по умолчанию не указаны в neo4j. Можете ли вы сделать их с помощью java и cypher? Да, конечно. Должны ли вы их делать? Практический совет, который я видел, состоит в том, что, как только вы доберетесь до 100 городов, это начинает непрактично делать это. Исследовательские системы с лучшими алгоритмами решают TSP для 30 000 - 50 000 городов прямо сейчас. Лично я бы не советовал пробовать его в двух порядках исследовательских систем прямо сейчас, если у вас нет большого количества аппаратных средств и вычислений, которые вы можете на него набросать (например, через что-то вроде арендованных EC2-вычислений).

С точки зрения алгоритмов существует Held-Karp algorithm, который является O (n^2 * 2^n). Уч. Wikipedia has other suggestions as well.

Итак, я думаю, с точки зрения теоретической информатики, да, это выполнимо, вам нужно написать его самостоятельно, алгоритм очень сложный (в том смысле, что требуется много времени для выполнения и быстрого роста). С практической точки зрения, это полностью выполнимо для менее чем 100 городов, и это будет чрезвычайно сложно и дорого, чтобы попробовать это с n> = 10 000 или около того.

См. Также this related stack overflow question.