Блог

Я знаю, как найти пару непересекающихся путей с минимальной суммой длин (алгоритм Сурбалле). У меня также есть формулировка ILP, которая решает следующую задачу, которая обобщает мою проблему: учитывая две вершины u и v в графе G, из всех непересекающихся пар путей, соединяющих u и v в G, найдите пару с минимальной длиной более длинного пути в паре. (Конечно, эта проблема может быть переформулирована для групп из более чем двух непересекающихся путей).

У кого-нибудь есть идея для эффективного (многочлена?) алгоритм решения любой из этих задач (проблема в названии или обобщенная проблема?)

Спасибо!

Я думаю, что это проблема NP, потому что я мог бы свести проблему с рюкзаком к этому, и согласно этой статье проблема с рюкзаком является NP-полной. действительно, задача о рюкзаке имеет алгоритм псевдополиномиального времени в значении размера рюкзака, но он не имеет алгоритма полиномиального времени в размере входных данных.

сведение проблемы с рюкзаком к указанной вами проблеме:

-спецификация моей проблемы с рюкзаком:

1- предположим, у вас есть два рюкзака, оба из которых имеют размер c.

2- у вас есть n элементов с объемами v1, v2, .. vn.

3- вы хотите переместить все эти n предметов в свои рюкзаки.

-сведение этой проблемы с рюкзаком к вашей проблеме:

1- создайте граф с (n 1) вершинами.

2- вершина i соединена с вершиной (i 1) с помощью двух ребер. один со стоимостью vi (объем i-го элемента) и один со стоимостью ноль.

3- вы хотите найти два реберных непересекающихся пути из вершины 1 в вершину (n 1) с верхней границей, равной размеру рюкзака.

итак, если бы вы могли решить свою задачу в полиноме, проблема с рюкзаком решается в полиноме, и вы доказали P = NP. : D

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