Проблемът за най-дългия път

Проблемът за най-дългия пъте проблемът за намиране на прост път с максимална дължина в даден график. Пътят се нарича прост, ако няма повтарящи се върхове. Дължината на пътя може да бъде измерена или чрез броя на ръбовете, или (в случай на претеглени графики) чрез сумата от теглата на неговите ръбове. За разлика от проблема с най-краткия път, който може да бъде решен за полиномиално време върху графики без цикли с отрицателно тегло, проблемът с най-дългия път е NP-труден и не може да бъде решен за полиномиално време за произволни графики, освен ако P = NP. Известна е и по-голяма трудност, което показва, че проблемът е труден за приблизително определяне. Въпреки това, проблемът се решава в линейно време върху насочени ациклични графики, които имат важни приложения в проблеми с критичния път в проблеми с графика.

Съдържание

NP-твърдостта на непретегления проблем за намиране на най-дългия път може да бъде показана чрез редуциране на проблема до намиране на хамилтонов път [en] — графикGима хамилтонов път тогава и само ако най-дългият път в него има дължинаn− 1, къдетоnе броят на върховете на графикаG. Тъй като проблемът за намиране на хамилтонов път е NP-пълен, тази редукция показва, че проблемът за намиране на най-дългия път в разрешимия случай също е NP-пълен. В този проблем за разрешимост входът е графикатаGи числотоk. Очаквайте да, акоGсъдържа път сkили повече дъги, илинев противен случай [1] .

Ако проблемът за намиране на най-дългия път може да бъде решен за полиномиално време, той може да се използва за решаване на този проблем с разрешимостта чрез намиране на най-дългия път и сравняване на дължината на получения път с числотоk. Така че задачата за намиране на най-дългия път еNP-твърд. Той не е NP-пълен, защото не е проблем за разрешимост [2] .

В претеглени пълни графи с неотрицателни тегла на ръбове проблемът за намиране на претегления най-дълъг път е същият проблем като проблема на пътуващия търговец, тъй като най-дългият път винаги включва всички върхове на този проблем [3] .

Най-дългият път A между два дадени върхаsиtв претегления графGе същият като най-късия път в графика −G, получен отGчрез заместване на всички тегла с тегла с противоположен знак. Така, ако най-краткият път може да бъде намерен в −G, тогава най-дългият път също може да бъде намерен вG[4] .

За повечето графики тази трансформация е безполезна, тъй като създава цикли с отрицателна дължина в −G. Но акоGе насочен ацикличен график, не е възможно да се създаде отрицателен цикъл и най-дългият път вGможе да бъде намерен в линейно време чрез прилагане на алгоритъм за най-кратък път в −G(също насочен ацикличен график), който работи в линейно време [4] . Например, за всеки връхvв насочен ацикличен граф, дължината на най-дългия път, завършващ наv, може да бъде получена чрез изпълнение на следните стъпки:

Когато това е направено, най-дългият път в цялата графика може да се получи, като се започне от върхаvс най-голямата записана стойност и се работи назад, като се избере входящата дъга, чийто начален връх има най-голяма стойност.

Методът на критичния път за планиране на набор от дейности използва изграждането на насочен ацикличен граф, в който върховете представляват възловите събития на проекта, а дъгите представляват дейностите, които трябва да бъдат завършени преди възела.събития и след това. На всяка дъга се присвоява тежест, равна на очакваното време за завършване на работата. В такава графика най-дългият път от първото възлово събитие до последното е критичният път, който определя общото време за завършване на проекта [4] .

Най-дългият път на насочени ациклични графи може да се използва и за послойно чертане на графи [en] — поставяме всеки връхvна насочения ацикличен графGна нивото, чийто номер съответства на дължината на най-дългия път, завършващ наv. В резултат на това получаваме подреждането на върховете по нива, при което броят на нивата ще бъде минимален [5] .

Bjorklund, Hasfeldt и Kanna пишат, че проблемът за намиране на най-дългия път в непретеглен неориентиран граф е „известен със своята трудност при разбирането на трудността му при приближаване“ [6] . Най-известният полиномиален алгоритъм за приближение по време на изпълнение дава само много слабо приближение, n / exp ⁡ ( Ω ( log ⁡ n ) ) >))> [7]. За всеки 0>"> ϵ > 0 0> 0>" данни- > невъзможно е да се определи приблизително най-дългия път с коефициент по-малък от 2 ( log ⁡ n ) 1 − ϵ >> , освен ако NP принадлежи към квазиполиномиални детерминирани времеви проблеми. Съществува обаче голяма празнина между този резултат за приближаване и известните алгоритми за приближение за този проблем [8] .

В случай на непретеглени, но насочени графики, има добре известни резултати за силна апроксимация. За всеки 0>"> ϵ > 0 0> 0>" данни- > проблемът не може да бъде апроксимиран в рамките на n 1 − ϵ > , освен ако P = NP и, при силни теоретични допускания, проблемът не може да бъде приблизително определен в рамките на n / log 2 + ϵ ⁡ n n>gt; [6]. Може да се използва техникацветно кодиран [en], за да намерите път с дължина на log, ако съществува, но тази техника дава само фактор на приближение O (n / log ⁡ n) [9] .

Проблемът за намиране на най-дългия път е фиксирано-параметрично разрешим [en], ако е параметризиран от дължината на пътя. Например проблемът може да бъде решен във време, което е линейно по отношение на размера на входната графика (но в експоненциално време по дължината на пътя) с алгоритъм, който предприема следните стъпки:

Извършваме първо търсене в дълбочина на графиката. Нека d е дълбочината на полученото дърво за търсене в дълбочина.
Ние използваме пътищата от корена до листата на дървото за търсене в дълбочина в реда, в който са търсени по време на търсенето, за разлика от разлагането на пътя на графиката с ширина на пътя d .
Използвайте динамично програмиране на това разлагане на пътя, за да намерите най-дългия път в O ( d ! 2 d n ) n)> , където n е броят на върховете на графа.

Тъй като изходният път е поне d дълъг, времето за работа също ще бъде ограничено до O ( ℓ ! 2 ℓ n ) n)> , където ℓ е дължината на най-дългия път [10] . Използвайки цветно кодиране, зависимостта от дължината на пътя може да бъде намалена до една експоненциална [11] [12] [13] . Подобна техника на динамично програмиране показва, че проблемът с най-дългия път също е разрешим с фиксирани параметри в ширината на дървото на графиката.

За графики с ограничена ширина на клика проблемът с най-дългия път може да бъде решен за полиномиално време с помощта на алгоритъм за динамично програмиране. Степента на полинома обаче зависи от ширината на клика на графиката, така че тези алгоритми не могат да бъдат решавани с фиксиран параметър. Проблемът за намиране на най-дългия път, параметризиран отширината на кликите е трудна за класа на параметризирана сложност [en] W [ 1 ] , което означава, че едва ли има алгоритъм с фиксирани параметри [14] .

Проблемът с най-дългия път може да бъде решен за полиномиално време върху допълненията на графиките на сравнимостта [15] . Може също да се реши за полиномиално време на всеки клас графики с ограничена ширина на дървото или ограничена ширина на клика, като например наследени от разстояние графики. Въпреки това, проблемът е NP-труден, дори ако се ограничим до разделени графики, кръгови графики или равнинни графики [16] .