Väginspektionsuppgift

Det  kinesiska brevbärarproblemet ( CPP ) , brevbärarvägen eller väginspektionsproblemet är att hitta den kortaste stängda vägen eller cykeln som går genom varje kant av en (ansluten) vägd oriktad graf . Om grafen har en Euler-cykel (en stängd bana som korsar vilken kant som helst exakt en gång), så är denna cykel den optimala lösningen. Annars är optimeringsproblemet att hitta det minsta antalet kanter i den itererade grafen (eller delmängden av kanter med minsta möjliga totalvikt) så att den resulterande multigrafen har en Eulerisk cykel [1] . Detta problem kan lösas i polynomtid [2] .

Problemet studerades ursprungligen 1960 av den kinesiske matematikern Kwon Mei-Ko, vars uppsats översattes från kinesiska till engelska 1962 [3] . Det alternativa namnet "Chinese Postman Problem" gavs för att hedra honom. Olika källor tillskriver namnet till antingen Alan J. Goldman eller Jack Edmonds, som var anställda av National Institute of Standards and Technology vid den tiden [4] [5] .

Oriktad lösning

Det oriktade väginspektionsproblemet kan lösas i polynomtid med en algoritm baserad på konceptet med en T -korsning. Låt T vara en delmängd av grafens vertexuppsättning. En kantmängd J kallas en T -korsning om samlingen av hörn som har ett udda antal kanter från J som förbinder vertexet med dess grannar exakt matchar mängden T . En T -koppling existerar om någon ansluten komponent i grafen innehåller ett jämnt antal hörn från T . Uppgiften för en T -korsning är att hitta en T -korsning med minst antal kanter eller minsta totalvikt.

För varje T innehåller den minsta T -förbindelsen (om den finns) nödvändigtvis vägar som kopplar samman T :s hörn i par. Banorna kommer att vara sådana att den totala längden eller totalvikten blir så liten som möjligt. I den optimala lösningen kommer inte två av dessa vägar att dela kanter, men de kan dela hörn. Den minsta T -kopplingen kan erhållas genom att konstruera en komplett graf på topparna av T med kanter som representerar de kortaste vägarna i en given ingångsgraf, och sedan hitta den minsta vikten perfekt matchning i den fullständiga grafen. Matchande kanter representerar banor i den ursprungliga grafen vars förening bildar den önskade T -fogen. Att bygga en komplett graf och sedan hitta en matchning i den kan göras i steg.

För väginspektionsproblemet bör T vara uppsättningen av alla hörn av udda grad. Enligt villkoren för problemet måste hela grafen kopplas ihop (annars finns det ingen bypass), och genom handskakningslemma har den ett jämnt antal udda hörn, så en T -koppling finns alltid. Fördubbling av kanterna på en T -korsning gör att den givna grafen blir en Eulerisk multigraf (en sammankopplad graf där varje vertex har en jämn grad), vilket innebär att den har en Eulerisk cykel , en rutt som besöker varje kant av multigrafen exakt en gång. Denna väg kommer att vara den optimala lösningen på problemet med väginspektioner [6] [2] .

Lösningsorienterad

På en riktad graf gäller samma grundidéer, men en annan teknik måste användas. Om Euler-grafen, måste du hitta Euler-cykeln. Om inte, måste man hitta T -korsningar, vilket innebär att hitta vägar från hörn med en in -grad större än sin ut -grad till en vertex med en ut -grad större än sin in -grad , för att göra in- grad lika med ut-graden för varje vertex i grafen. Detta kan lösas som ett exempel på minimikostnadsflödesproblemet , där det finns en källa lika med ingången halvgrad och en konsument lika med output halvgrad. Detta problem är löst i tid . En lösning finns om och endast om den givna grafen är starkt kopplad [2] [7] .

Uppgiften för brevbäraren med vinden

Brevbärarvindproblemet är en variant av väginspektionsproblemet där ingången är en oriktad graf, men där varje kant har olika kostnad att färdas i olika riktningar. Till skillnad från lösningar för riktade och oriktade grafer är problemet NP-komplett [8] [9] .

Applikationer

Många kombinatoriska problem reduceras till det kinesiska brevbärarproblemet, inklusive att hitta den maximala sektionen i en plan graf och cykeln med minsta medellängd i en oriktad graf [10] .

Alternativ

Flera varianter av det kinesiska brevbärarproblemet studerades och deras NP-fullständighet visades [11]

Se även

Anteckningar

  1. ↑ Roberts, Tesman, 2009 , sid. 640–642.
  2. ↑ 1 2 3 Edmonds och Johnson, 1973 , sid. 88–124.
  3. ↑ Kwan, 1960 , sid. 263–266.
  4. ↑ Pieterse, Black, 2014 .
  5. ↑ Grötschel, Yuan, 2012 , sid. 43–50.
  6. ↑ Lawler, 1976 .
  7. ↑ Eiselt, Gendeaeu, Laporte, 1995 , sid. 231–242.
  8. ↑ Guan, 1984 , sid. 41–46.
  9. ↑ 1 2 Lenstra, Rinnooy, 1981 , sid. 221–227.
  10. ↑ Schrijver, 2002 .
  11. ↑ Crescenzi, Kann, 2000 .
  12. ↑ Roberts, Tesman, 2009 , sid. 642–645.

Litteratur

Länkar