Алгоритм гамильтоновых путей и социальный граф

Question

У меня есть случайный неориентированный социальный граф.

Я хочу найти гамильтонов путь, если это возможно.Или, если невозможно (или невозможно узнать, если возможно, за полиномиальное время) ряд путей.В этой «серии путей» (где все N узлов используются ровно один раз) я хочу минимизировать количество путей и максимизировать среднюю длину путей.(Так что нет тривиального решения N путей одного узла).

Я уже сгенерировал матрицу смежности для узлов и ребер.

Есть предложения?Указатели в правильном направлении?Я понимаю, что это потребует эвристики из-за NP-полной (?) Природы проблемы, и я в порядке с «достаточно хорошим» ответом.Также я хотел бы сделать это на Java.

Спасибо!

Answer 1

Англуин и Валиант дали эвристику почти линейного времени, которая почти всегда работает в достаточно плотном случайном графе Эрдоша-Реньи.Это описано Уилфом, на странице 121 .Вероятно, ваш случайный граф - , а не Erdos-Renyi, но эвристика может работать в любом случае (когда он "терпит неудачу", он все же дает вам (надеюсь) длинный путь; жадно выбирайте этот путь и снова запускайте AV).

Answer 2

Если я правильно истолковываю ваш вопрос, то, что вы запрашиваете, все еще является NP-сложным, поскольку лучшим решением проблемы «нескольких путей» будет гамильтонов путь, и известно, что определение того, существует ли он, NP-трудной. Более того, даже если вы гарантируете, что гамильтонова траектория не существует, решение этой проблемы все равно может быть NP-трудным, поскольку я мог бы дать вам график с одним отключенным узлом, плавающим в пространстве, для которого лучшим решением является тривиальный путь, содержащий этот узел и гамильтонов путь в оставшемся графе. В результате, если P = NP, для вашей задачи не будет алгоритма полиномиального времени.

Надеюсь, это поможет, и извините за отрицательный результат!

Answer 3

Используйте генетический алгоритм (без кроссовера), где каждый индивидуум представляет собой перестановку узлов.Это дает вам «серию путей» в каждом поколении, развивая минимальное количество путей (1) и максимальное среднее значение.длина (N).

Answer 4

Как вы поняли, нет точного решения за полиномиальное время. Вы можете попробовать несколько случайных методов поиска, хотя. Моя рекомендация, начните с генетического алгоритма и попробуйте поиск по табу.