Sarcina de inspecție rutieră

Problema  poștașului chinez ( CPP ), ruta poștașului sau problema inspecției rutiere este de a găsi cea mai scurtă cale închisă sau ciclu care trece prin fiecare margine a unui grafic nedirecționat ponderat (conectat) . Dacă graficul are un ciclu Euler (o cale închisă care traversează orice muchie exact o dată), atunci acest ciclu este soluția optimă. În caz contrar, problema de optimizare este de a găsi cel mai mic număr de muchii în graficul iterat (sau submulțimea de muchii cu cea mai mică greutate totală posibilă) astfel încât multigraful rezultat să aibă un ciclu eulerian [1] . Această problemă poate fi rezolvată în timp polinomial [2] .

Problema a fost studiată inițial în 1960 de matematicianul chinez Kwon Mei-Ko, a cărui lucrare a fost tradusă din chineză în engleză în 1962 [3] . Numele alternativ „Problema poștașului chinez” a fost dat în onoarea lui. Diverse surse atribuie numele fie lui Alan J. Goldman, fie lui Jack Edmonds, care erau angajați de Institutul Național de Standarde și Tehnologie la acea vreme [4] [5] .

Soluție nedirecționată

Problema inspecției rutiere nedirecționate poate fi rezolvată în timp polinomial cu un algoritm bazat pe conceptul de joncțiune T. Fie T o submulțime a mulțimii de vârfuri a graficului. O mulțime de muchii J se numește joncțiune T dacă colecția de vârfuri care au un număr impar de muchii de la J care leagă vârful de vecinii săi se potrivește exact cu mulțimea T . O conexiune T există dacă orice componentă conexă a graficului conține un număr par de vârfuri din T . Sarcina unei joncțiuni T este de a găsi o joncțiune T cu cel mai mic număr de muchii sau cea mai mică greutate totală.

Pentru orice T , cea mai mică conexiune T (dacă există) conține în mod necesar căi care conectează vârfurile lui T în perechi. Căile vor fi astfel încât lungimea totală sau greutatea totală să fie cât mai mică posibil. În soluția optimă, nici două dintre aceste căi nu vor împărtăși muchii, dar pot împărtăși vârfuri. Cea mai mică unire T poate fi obținută prin construirea unui grafic complet pe vârfurile lui T cu muchii reprezentând cele mai scurte căi dintr-un grafic de intrare dat și apoi găsirea celei mai mici potriviri perfecte în acel grafic complet. Muchiile potrivite reprezintă trasee în graficul original a căror unire formează unirea în T dorită . Construirea unui grafic complet și apoi găsirea unei potriviri în acesta se poate face în pași.

Pentru problema inspecției rutiere, T ar trebui să fie mulțimea tuturor vârfurilor de grad impar. După condițiile problemei, întregul grafic trebuie să fie conectat (altfel nu există ocolire), iar după lema de strângere de mână, are un număr par de vârfuri impare, deci o conexiune T există întotdeauna. Dublarea muchiilor unei joncțiuni T face ca graficul dat să devină un multigraf eulerian (un graf conex în care fiecare vârf are un grad par), ceea ce implică faptul că are un ciclu eulerian , un traseu care vizitează fiecare muchie a multigrafului exact. o singura data. Acest traseu va fi soluția optimă la problema inspecției rutiere [6] [2] .

Orientat către soluții

Pe un grafic orientat, se aplică aceleași idei de bază, dar trebuie utilizată o tehnică diferită. Dacă graficul Euler, trebuie să găsiți ciclul Euler. Dacă nu, trebuie să găsiți joncțiuni T , ceea ce înseamnă să găsiți căi de la vârfuri cu un grad în interior mai mare decât gradul în exterior la un vârf cu un grad în exterior mai mare decât gradul în interior, pentru a face in- grad egal cu gradul de exterior pentru fiecare vârf al graficului. Acest lucru poate fi rezolvat ca o instanță a problemei fluxului de cost minim , în care există o sursă egală cu jumătate de grad de intrare și un consumator egal cu jumătate de grad de ieșire. Această problemă este rezolvată în timp . O soluție există dacă și numai dacă graficul dat este puternic legat [2] [7] .

Sarcina poștașului cu vântul

Problema vântului poștașului este o variantă a problemei inspecției rutiere în care intrarea este un grafic nedirecționat, dar în care fiecare muchie are un cost diferit de deplasare în direcții diferite. Spre deosebire de soluțiile pentru graficele direcționate și nedirecționate, problema este NP-complet [8] [9] .

Aplicații

Numeroase probleme combinatorii sunt reduse la problema poștașului chinezesc, inclusiv găsirea secțiunii maxime într-un graf plan și a ciclului de lungime medie minimă într-un graf nedirecționat [10] .

Opțiuni

Au fost studiate mai multe variante ale problemei poștașului chinezesc și a fost demonstrată completitudinea lor NP [11]

Vezi și

Note

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

Literatură

Link -uri