Blandade kinesiska brevbärarproblem

Det blandade kinesiska brevbärarproblemet (MCPP eller MCP) är sökandet efter den kortaste genomgången av en graf med en uppsättning hörn V, en uppsättning oriktade kanter E med positiva rationella vikter och en uppsättning riktade bågar A med positiva rationella vikter som täcker varje kant eller båge minst en gång till minimal kostnad. Problemet har visat sig vara NP-komplett av Papadimitriou . Det blandade kinesiska brevbärarproblemet uppstår ofta i bågdirigeringsproblem som snöplogning, där vissa gator är för smala för att korsa i båda riktningarna medan andra gator är dubbelriktade och kan plogas i båda riktningarna. Det är lätt att kontrollera om en blandad graf har en brevbärartur av någon storlek genom att verifiera om grafen är starkt kopplad. Problemet är NP-svårt om vi begränsar brevbärarturen till att korsa varje båge exakt en gång eller om vi begränsar den till att korsa varje kant exakt en gång, vilket bevisats av Zaragoza Martinez.

Matematisk definition

Den matematiska definitionen är:

Ingång: En starkt sammankopplad, blandad graf $G=(V,E,A)$ med kostnad $c(e)\geq 0$ för varje edge $e\subset E\cup A$ och en maximal kostnad $c_{max}$ .

Fråga: finns det en (riktad) tur som korsar varje kant i $E$ och varje båge i $A$ minst en gång och har kostat högst $c_{max}$ ?

Beräkningskomplexitet

Den största svårigheten med att lösa det blandade kinesiska brevbärarproblemet ligger i att välja orienteringar för de (oriktade) kanterna när vi får en knapp budget för vår turné och bara har råd att korsa varje kant en gång. Vi måste sedan orientera kanterna och lägga till ytterligare några bågar för att få en riktad Eulerisk graf, det vill säga för att göra varje vertex balanserad. Om det finns flera kanter som faller på en vertex är det inte en lätt uppgift att bestämma den korrekta orienteringen av varje kant. Matematikern Papadimitriou analyserade detta problem med fler restriktioner; "MIXED CHINESE POSTMAN är NP-komplett, även om ingångsgrafen är plan, har varje vertex högst tre grader, och varje kant och båge har kostat en."

Eulerisk graf

Processen att kontrollera om en blandad graf är Eulerian är viktig för att skapa en algoritm för att lösa problemet med blandade kinesiska brevbärare. Graderna för en blandad graf G måste vara jämn för att ha en Eulerisk cykel, men detta är inte tillräckligt.

Approximation

Det faktum att den blandade kinesiska brevbäraren är NP-hård har lett till sökandet efter polynomtidsalgoritmer som närmar sig den optimala lösningen till rimlig tröskel. Frederickson utvecklade en metod med en faktor på 3/2 som kunde appliceras på plana grafer, och Raghavachari och Veerasamy hittade en metod som inte behöver vara plan. Däremot kan polynomtiden inte hitta kostnaden för deadheading, den tid det tar för en snöplog att nå gatorna den kommer att ploga eller en gatusopare att nå de gator som den kommer att sopa.

Formell definition

Givet en starkt sammankopplad blandad graf $G=(V,E,A)$ med en vertexuppsättning $V$ , och kantmängd $E$ , en båguppsättning $A$ och en icke-negativ kostnad $c_{e}$ för varje $e\in E\cup A$ , MCPP består av att hitta en minimikostnad tur genom varje länk $e\in E\cup A$ minst en gång.

Givet $S\subset V$ , $\delta ^{+}(S) =\{(i,j)\in A:i\in S,j\in V\backslash S\}$ , ${\displaystyle \delta ^{-}(S)=\{(i,j)\in A:i\in V\backslash S,j\in S\}} , δ$ ( $displaystyle \delta (S)}$ anger uppsättningen av kanter med exakt en ändpunkt i $S$ , och $\delta ^{\star } =\delta (S)\cup \delta ^{+}(S)\cup \delta ^{-}$ . Givet en vertex ${\textstyle i}$ , $d_{i}^{-}$ (ograd) anger antalet bågar enter $i$ , $d_{i }^{+}$ (outdegree) är antalet bågar som lämnar ${\textstyle i}$ , och $d_{i}$ (grad) är antalet länkar som inträffar med $i$ . Observera att $d_{i}=|\delta ^{\star }(\{{i}\})|$ . En blandad graf $G=(V,E,A)$ kallas även om alla dess hörn har jämn grad, den kallas symmetrisk om ${ \displaystyle d_{i}^{-}=d_{i}^{+}}$ för varje vertex ${\textstyle i}$ , och det sägs vara balanserat om, givet någon delmängd $S$ av hörn , skillnaden mellan antalet bågar riktade från $S$ till $V\backslash S$ , $|\delta ^{+}(S)|$ , och antalet bågar riktade från $V\backslash S$ till $S$ , $|\delta ^{-}(S)|$ , är inte större än antalet oriktade kanter som förenar $S$ och $V\backslash S$ , $|\delta (S)|$ .

Det är ett välkänt faktum att en blandad graf $G$ är Eulerisk om och endast om $G$ är jämn och balanserad. Lägg märke till att om $G$ är jämn och symmetrisk, så är G också balanserad (och Eulerian). Dessutom, om $G$ är jämn, kan $MCPP$ lösas exakt i polynomtid.

Även MCPP Algorithm

1. Givet en jämn och starkt sammankopplad blandad graf $G=(V,E,A)$ , låt $A_{i}$ vara uppsättningen av bågar som erhålls genom att slumpvis tilldela en riktning till kanterna i $E$ och med samma kostnader. Beräkna $j}^{-}-d_{i}^{+}}$ för varje vertex i i den riktade grafen $(V,A\cup A_{1})$ . En vertex ${\textstyle i}$ med $s_{i}>0(s_{i}<0)$ kommer att betraktas som en källa (sink) med utbudsefterfrågan $s_{i}(-s_{i})$ . Observera att eftersom $G$ är en jämn graf, är alla tillgångar och krav jämna tal (noll anses vara ett jämnt tal).
2. Låt $A_{2}$ vara uppsättningen av bågar i motsatt riktning mot de i $A_{1}$ och med kostnaderna för de motsvarande kanterna, och låt $A_ {3}$ vara uppsättningen av bågar parallella med $A_{2}$ till noll kostnad.
3. För att tillfredsställa kraven ${\displaystyle s_{i}} för$$) {\displaystyle (V,A\ cup A_{1}\cup A_{2}\cup A_{3})}$ hörn, lös ett minimikostnadsflödesproblem i grafen , där varje båge i $A\cup A_{1}\cup A_{2}$ har oändlig kapacitet och varje båge i $A_{3}$ har kapacitet 2. Låt $x_{ij}$ vara det optimala flödet.
4. För varje båge $(i,j)$ i $A_{3}$ gör: Om ${\displaystyle x_{ij}=2},$ orientera sedan motsvarande kant i $G$ från $i$ till $j$ (riktningen, från $j$ till $i$ , tilldelad den associerade kanten i steg 1 var fel"); om $x_{ij}=0$ , orientera sedan motsvarande kant i G från $j$ till $i$ (i det här fallet var orienteringen i steg 1 "rätt" "). Observera att fallet $x_{ij}=1$ är omöjligt, eftersom alla flödesvärden genom bågar i $A_{3}$ är jämna tal.
5. Förstärk $G$ genom att lägga till $x_{ij}$ kopior av varje båge i $A\cup A_{1}\cup A_{2}$ . Den resulterande grafen är jämn och symmetrisk.

Heuristiska algoritmer

När den blandade grafen inte är jämn och noderna inte alla har jämn grad, kan grafen omvandlas till en jämn graf.

• Låt $\mathrm {G=\{V,E,A\}}$ vara en blandad graf som är starkt kopplad . Hitta de udda gradnoderna genom att ignorera bågriktningarna och få en minimal kostnadsmatchning. Förstärk grafen med kanterna från den minimala kostnadsmatchningen för att skapa en jämn graf $\mathrm {G'=\{V',E',A'\} }$ .
• Grafen är jämn men inte symmetrisk och en eulerisk blandad graf är jämn och symmetrisk. Lös ett minimikostnadsflödesproblem i $G'$ för att få en symmetrisk graf som kanske inte är jämn $G''$ .
• Det sista steget innebär att göra den symmetriska grafen $G''$ jämn. Märk noderna med udda grader $V_{O}$ . Hitta cykler som alternerar mellan linjer i bågmängden $A''\backslash A$ och linjer i kantmängden $E''$ som börjar och slutar vid punkter i ${\ displaystyle V_{O}}$ . Bågarna i $A''\backslash A$ bör betraktas som oriktade kanter, inte som riktade bågar.

Genetisk algoritm

En artikel publicerad av Hua Jiang et. al lade fram en genetisk algoritm för att lösa det blandade kinesiska brevbärarproblemet genom att operera på en population. Algoritmen fungerade bra jämfört med andra approximationsalgoritmer för MCPP.

Se även

• Kapaciterad ljusbågsdirigeringsproblem