Informatyka i programowanieGranice obliczeń — problemy łatwe, trudne i niemożliwe

Euler jest łatwy, Hamilton może być bardzo trudny

Dwa klasyczne pytania o przejście przez graf brzmią niemal jak rodzeństwo. Ścieżka Eulera ma użyć każdej krawędzi dokładnie raz; ścieżka Hamiltona ma odwiedzić każdy wierzchołek dokładnie raz. Dla nieskierowanego grafu istnienie ścieżki Eulera można rozpoznać z prostych warunków stopni i spójności, a samą trasę znaleźć w czasie liniowym względem liczby krawędzi. Problem ścieżki Hamiltona jest NP-zupełny. Różnica pokazuje, że „odwiedzić wszystko po jednym razie” nie jest jedną klasą trudności: znaczenie ma to, czy pilnujemy lokalnych krawędzi, czy globalnego wyboru kolejności wierzchołków.

Mosty Królewca i lokalne stopnie

Problem Eulera wyrósł z pytania o przejście przez wszystkie mosty Królewca dokładnie raz. W nieskierowanym grafie, po pominięciu izolowanych wierzchołków, trasa Eulera istnieje wtedy, gdy graf jest spójny i ma zero albo dwa wierzchołki nieparzystego stopnia — zero dla cyklu, dwa dla otwartej ścieżki. To zaskakująco lokalne kryterium: stopnie wierzchołków i spójność wystarczają do rozstrzygnięcia istnienia trasy.

Hierholzer składa cykle

Algorytm Hierholzera buduje trasę, idąc nieużywanymi krawędziami, a następnie wplatając kolejne cykle w już znalezioną część. Przy odpowiedniej reprezentacji grafu każda krawędź jest przetwarzana stałą liczbę razy, więc algorytm może działać liniowo względem liczby krawędzi. To przykład sytuacji, w której warunek „każda krawędź raz” ma strukturę pozwalającą na bardzo wydajne rozwiązanie.

Hamilton wymaga globalnej kolejności

Ścieżka Hamiltona pyta o odwiedzenie każdego wierzchołka dokładnie raz. Tutaj lokalne stopnie nie wystarczają. Wierzchołek może mieć wiele możliwych wejść i wyjść, ale wybór jednego połączenia może dopiero dużo później odciąć część grafu. Decyzje są globalnie powiązane. Problem decyzyjny Hamiltonian Path należy do klasycznych problemów NP-zupełnych, więc wielomianowy algorytm dla dowolnych grafów oznaczałby P=NP.

Dlaczego podobieństwo nazw myli

W obu zadaniach otrzymujemy graf i szukamy jednej trasy. W obu występuje słowo „dokładnie raz”. Ale obiektem kontrolowanym raz są krawędzie, a raz wierzchołki. To wystarcza, by pojawiła się przepaść złożoności. Przykład jest dobrym ostrzeżeniem przed ocenianiem trudności na podstawie powierzchownego podobieństwa opisu problemów.

Granice są precyzyjne, nie intuicyjne

Teoria złożoności często odkrywa takie sąsiadujące przypadki: niewielka zmiana warunków usuwa strukturę umożliwiającą prosty algorytm albo przeciwnie — ją wprowadza. Dlatego przy optymalizacji sieci, tras czy harmonogramów trzeba bardzo dokładnie ustalać, co właściwie ma zostać użyte raz i jakie powtórzenia są dozwolone. Drobny zapis w specyfikacji może decydować o klasie problemu.

Co algorytm „widzi” lokalnie

W problemie Eulera każdy krok zużywa krawędź, a parzystość stopni mówi, czy po wejściu do wierzchołka zwykle pozostaje możliwość wyjścia. Ta lokalna księgowość jest na tyle silna, że można skonstruować trasę przechodząc każdą krawędź raz w czasie Θ(E+V). W problemie Hamiltona lokalna informacja o stopniu wierzchołka nie mówi, czy wybranie jednej z wielu sąsiednich krawędzi nie odetnie kilka kroków później całej części grafu. Z tego powodu dwa zadania różnią się nie tylko znanym czasem działania algorytmów, ale rodzajem informacji potrzebnej do podejmowania bezpiecznych decyzji. Euler ma silne lokalne kryterium; Hamilton wymaga kontroli globalnej struktury odwiedzin.

Historia nazw nie tłumaczy różnicy złożoności

Eulerowskie i hamiltonowskie trasy powstały w różnych kontekstach historycznych, ale dzisiejszy kontrast nie wynika z wieku problemów ani z tego, że jednemu poświęcono więcej badań. Istotna jest matematyczna struktura warunków. Dla Eulera parzystość stopni i spójność dają pełne kryterium oraz konstrukcję. Dla Hamiltona nie znamy analogicznego lokalnego testu działającego dla wszystkich grafów, a problem jest NP-zupełny.

#Euler#grafy#Hamilton#Hierholzer#NP-zupełność
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki