Mieszany problem chińskiego listonosza

Mieszany problem chińskiego listonosza (MCPP lub MCP) to poszukiwanie najkrótszego przejścia grafu ze zbiorem wierzchołków V, zbiorem nieskierowanych krawędzi E o dodatnich wagach wymiernych oraz zbiorem skierowanych łuków A o dodatnich wagach wymiernych, które obejmuje każdą krawędź lub łuk przynajmniej raz przy minimalnych kosztach. Problem został udowodniony jako NP-zupełny przez Papadimitriou . Mieszany problem chińskiego listonosza często pojawia się w przypadku problemów z trasowaniem łuku takich jak odśnieżanie, gdzie niektóre ulice są zbyt wąskie, aby można je było przejechać w obu kierunkach, podczas gdy inne ulice są dwukierunkowe i można je odśnieżać w obu kierunkach. Łatwo jest sprawdzić, czy wykres mieszany ma wycieczkę listonosza dowolnej wielkości, sprawdzając, czy wykres jest silnie spójny. Problem jest NP-trudny, jeśli ograniczymy trasę listonosza do przechodzenia przez każdy łuk dokładnie raz lub jeśli ograniczymy ją do przechodzenia przez każdą krawędź dokładnie raz, jak udowodnił Zaragoza Martinez.

Definicja matematyczna

Definicja matematyczna to:

Wejście: silnie połączony, mieszany wykres dla każdego ${\ Displaystyle G = (V, E, A)}$ kosztem do $\ Displaystyle c (e) \ geq 0}$ krawędź ${\ Displaystyle e \ podzbiór E \ kubek A}$ i maksymalny koszt ${\ Displaystyle c_ {max}}$ .

Pytanie: czy istnieje (ukierunkowana) trasa, która przechodzi przez każdą krawędź w $}$ każdy łuk w przynajmniej raz i ma koszt co najwyżej $displaystyle c_ {max$$}$ ?

Złożoność obliczeniowa

Główna trudność w rozwiązaniu problemu mieszanego chińskiego listonosza polega na wyborze orientacji dla (nieukierunkowanych) krawędzi, gdy mamy napięty budżet na naszą wycieczkę i możemy sobie pozwolić tylko na jednokrotne przejście przez każdą krawędź. Następnie musimy zorientować krawędzie i dodać kilka kolejnych łuków, aby uzyskać skierowany graf Eulera, to znaczy, aby każdy wierzchołek był zrównoważony. Jeśli istnieje wiele krawędzi incydentnych z jednym wierzchołkiem, określenie prawidłowej orientacji każdej krawędzi nie jest łatwym zadaniem. Matematyk Papadimitriou przeanalizował ten problem z większą liczbą ograniczeń; „MIESZANY CHIŃSKI POSTMAN jest NP-zupełny, nawet jeśli graf wejściowy jest płaski, każdy wierzchołek ma co najwyżej trzy stopnie, a każda krawędź i łuk kosztują jeden”.

Graf Eulera

Proces sprawdzania, czy graf mieszany jest eulerowski, jest ważny przy tworzeniu algorytmu do rozwiązania problemu mieszanego chińskiego listonosza. Stopnie mieszanego wykresu G muszą być równe, aby mieć cykl Eulera, ale to nie wystarczy.

Przybliżenie

Fakt, że mieszany chiński listonosz jest NP-trudny, doprowadził do poszukiwania algorytmów czasu wielomianowego, które zbliżają optymalne rozwiązanie do rozsądnego progu. Frederickson opracował metodę ze współczynnikiem 3/2, którą można zastosować do grafów planarnych, a Raghavachari i Veerasamy znaleźli metodę, która nie musi być planarna. Jednak czas wielomianowy nie może znaleźć kosztu martwego punktu, czasu potrzebnego pługowi śnieżnemu na dotarcie do ulic, które będzie orał, lub zamiatarki ulicznej, aby dotrzeć do ulic, które będzie zamiatać.

Definicja formalna

$zestawem$ uwagę silnie połączony wykres mieszany $i$$i$ \ , łuków ${$$\ Displaystyle A}$ kosztem ${\ Displaystyle e \ in E \ cup A}$ każdego $polega na$ wycieczki o minimalnych kosztach przechodzącej przez każde raz

biorąc pod uwagę ${\ Displaystyle S \ podzbiór V}$ , ${\ Displaystyle \ delta ^ {+} (S) =\{(i,j)\in A:i\in S,j\in V\ukośnik odwrotny S\}}$ , ${\ Displaystyle \ delta ^ {-} (S) = \ {(i, j) \ w A: i \ w V \ ukośnik odwrotny S, j \ w S \} }$ , ${\ Displaystyle \ delta (S)}$ oznacza zbiór krawędzi z dokładnie jednym punktem $S$ i ${\ Displaystyle \ delta ^ {\ gwiazda} = \ delta (S) \ kubek \ delta ^ {+} (S) \ kubek \ delta ^ {-}}$ . Biorąc pod $uwagę$ wierzchołek ( ) oznacza liczbę łuków wprowadzić $i}$$,$$d_ {i } ^ {+}} (stopnie$ { ) to liczba łuków wychodzących ${\$ (stopień) to liczba łączy incydentnych z $textstyle i$ } ${\ Displaystyle ja}$ . Zauważ, że ${\ Displaystyle d_ {i} = | \ delta ^ {\ gwiazda} (\ {{i} \}) |}$ . Wykres mieszany $jeśli$ się jeśli jego wierzchołki mają parzysty stopień $i$$} ^ {+}}$ dla każdego wierzchołka mówi się, że jest zrównoważony, jeśli, biorąc pod uwagę dowolny podzbiór S $\ displaystyle S}$$,$ między liczbą $skierowanych$ od do ${\ Displaystyle |\ delta ^ {+} (S) |}$ i liczba łuków skierowanych od ${\ Displaystyle V \ ukośnik odwrotny S}$${\ Displaystyle |\ delta ^ {-} (S) |}$ S $\ Displaystyle S}$ | $V \ backslash S$ nie jest większa niż liczba niekierowanych krawędzi łączących i $Displaystyle$ } ${\ Displaystyle | \ delta (S) |}$ .

Dobrze znany jest fakt, że graf mieszany $równy$$wtedy$ i tylko wtedy, gdy jest i zrównoważony. Zauważ, że jeśli $parzyste i symetryczne, to G jest również zrównoważone$ i eulerowskie). $.$ jeśli $jest parzysta$ można rozwiązać dokładnie w czasie

Nawet algorytm MCPP

1. $pod uwagę$ parzysty i silnie połączony wykres mieszany $}$ zbiorem łuków otrzymanych losowo przypisanie kierunku krawędziom w $.$ przy tych samych kosztach Oblicz ${\ Displaystyle s_ {i} = d_ {j} ^ {-} -d_ {i} ^ {+}}$ dla każdego wierzchołka ja na grafie skierowanym ${\ Displaystyle (V, A \ cup A_ {1})}$ . Wierzchołek z $ja$${\ Displaystyle s_ {i}> 0 (s_ {i}<0)}$ za źródło (ujście) z popytem na podaż ${\ Displaystyle s_ {i} (-s_ {i})}$ . Zauważ, że jak ${\ Displaystyle G}$ to wykres parzysty, wszystkie dostawy i zapotrzebowania są liczbami parzystymi (zero jest uważane za liczbę parzystą).
2. Niech będzie zbiorem łuków w kierunku przeciwnym do tych w ${2}$$}$ odpowiednich krawędzi, i niech $}$$\ displaystyle A_$$zerowym$ będzie zbiorem łuków równoległych do koszcie.
3. Aby spełnić wymagania $wierzchołków$ , rozwiąż problem przepływu minimalnych kosztów na grafie $kubek A_ {1} \ kubek A_ {2} \ kubek A_ {3})}$${\ Displaystyle (V, A$ , w którym każdy łuk w ${\ Displaystyle A \ kubek A_ {1} \ kubek A_ {2}}$ ma nieskończona pojemność i każdy łuk w ${\ displaystyle A_ {3}}$ ma pojemność 2. Niech ${\ displaystyle x_ {ij}}$ będzie optymalnym przepływem.
4. Dla każdego łuku ${\ Displaystyle (i, j)}$ w ${\ Displaystyle A_ {3}}$ wykonaj: Jeśli ${\ Displaystyle x_ {ij} = 2}$ , to zorientuj odpowiednia krawędź w $i}$ do $ja$ kierunek , od do $do$$\ displaystyle j}$$\$ { , przypisany do powiązanej krawędzi w kroku 1 był „błędny”); jeśli ${\ Displaystyle x_ {ij} = 0}$$”$ to ustaw odpowiednią krawędź w sol od $)$ w tym przypadku orientacja w kroku 1 była „właściwa "). Zwróć uwagę $jest$$niemożliwy , ponieważ wszystkie wartości$ przypadek przez łuki parzystymi
5. Zwiększyć $A \ kubek A_ {1} \ kubek A_ {2}$ dodając kopie ${$ łuku w $ZA$ . Otrzymany wykres jest parzysty i symetryczny.

Algorytmy heurystyczne

Gdy graf mieszany nie jest parzysty i nie wszystkie węzły mają parzysty stopień, graf można przekształcić w graf parzysty.

• Niech $_$ _ _ _ Znajdź węzły nieparzystych stopni, ignorując kierunki łuku i uzyskaj dopasowanie przy minimalnym koszcie. $_ } }$ wykres .
• Wykres jest parzysty, ale nie jest symetryczny, a graf mieszany eulerowski jest parzysty i symetryczny. Rozwiąż problem przepływu minimalnych kosztów w celu uzyskania symetrycznego wykresu, który może nie być równy $'}$$G$ .
• Ostatni krok polega na $wyrównaniu$ . Oznacz nieparzyste węzły stopni . ${\ Displaystyle V_ {O}}$ . Znajdź cykle, które naprzemiennie $występują$ między liniami w zbiorze łuków $O$$styl wyświetlania V_{O}}$ zbiorze krawędzi , w punktach w ${$ . Łuki w ${\ Displaystyle A''\ backslash A}$ należy traktować jako krawędzie nieukierunkowane, a nie skierowane łuki.

Algorytm genetyczny

Artykuł opublikowany przez Hua Jiang et. Al opracował algorytm genetyczny, aby rozwiązać mieszany problem chińskiego listonosza, operując na populacji. Algorytm działał dobrze w porównaniu z innymi algorytmami aproksymacyjnymi dla MCPP.

Zobacz też

• Problem z prowadzeniem łuku pojemnościowego