Переупорядочивание полосок бумаги для формирования оригинального документа обычно рассматривается как проблема коммивояжера, где расстояние между узлами - полосами - является своего рода мерой подобия. Я наткнулся на пару статей ( 1 и 2 ), которые рассматривают проблему как проблему назначения, сопоставляя левую сторону одной полосы с правой стороной следующей, и используйте венгерский алгоритм для его оптимизации. Мне кажется, что это потенциально может привести к проблеме петель, например
A (R) -> B (L)
B (R) -> C (L)
C (R) -> A (L)
D (R) -> E (L)
E (R) -> F (L)
F (R) -> D (L)
AB C и DEF сформировали две отдельные цепочки, поэтому их невозможно собрать в полный документ. Есть ли способ предотвратить это?
Я не могу понять, как они, по-видимому, превратили проблему NP в проблему P.