Úkol silniční inspekce

Problém  čínského pošťáka ( CPP ), cesta pošťáka nebo problém silniční kontroly spočívá v nalezení nejkratší uzavřené cesty nebo cyklu, který prochází každým okrajem (souvisejícího) váženého neorientovaného grafu . Pokud má graf Eulerův cyklus (uzavřená dráha, která prochází kteroukoli hranou právě jednou), pak je tento cyklus optimálním řešením. Jinak je optimalizačním problémem najít nejmenší počet hran v iterovaném grafu (nebo podmnožinu hran s nejmenší možnou celkovou váhou) tak, aby výsledný multigraf měl eulerovský cyklus [1] . Tento problém lze vyřešit v polynomiálním čase [2] .

Problém byl původně studován v roce 1960 čínským matematikem Kwon Mei-Ko, jehož práce byla přeložena z čínštiny do angličtiny v roce 1962 [3] . Na jeho počest byl dán alternativní název „Chinese Postman Problem“. Různé zdroje připisují jméno buď Alanu J. Goldmanovi nebo Jacku Edmondsovi, kteří byli v té době zaměstnáni Národním institutem pro standardy a technologii [4] [5] .

Neorientované řešení

Problém neřízené silniční kontroly lze vyřešit v polynomiálním čase pomocí algoritmu založeného na konceptu T -křižovatky. Nechť T je podmnožina vrcholové množiny grafu. Hranová množina J se nazývá T -spoj , pokud kolekce vrcholů, které mají lichý počet hran od J spojující vrchol s jeho sousedy, přesně odpovídá množině T . T -spojení existuje, pokud jakákoli souvislá složka grafu obsahuje sudý počet vrcholů z T . Úkolem T - křižovatky je najít T - křižovatku s nejmenším počtem hran nebo nejmenší celkovou hmotností.

Pro jakékoli T nejmenší T -spojení (pokud existuje) nutně obsahuje cesty, které spojují vrcholy T do párů. Dráhy budou takové, aby celková délka nebo celková hmotnost byla co nejmenší. V optimálním řešení žádné dvě z těchto cest nebudou sdílet hrany, ale mohou sdílet vrcholy. Nejmenší T -spojení lze získat sestrojením úplného grafu na vrcholech T s hranami reprezentujícími nejkratší cesty v daném vstupním grafu a poté nalezením dokonalé shody s nejmenší váhou v tomto úplném grafu. Odpovídající hrany představují cesty v původním grafu, jejichž spojení tvoří požadovaný T -spojení. Sestavení kompletního grafu a následné nalezení shody v něm lze provést v krocích.

Pro problém silniční kontroly by T mělo být množinou všech vrcholů lichého stupně. Podle podmínek úlohy musí být celý graf propojen (jinak neexistuje obchvat) a podle lemmatu handshake má sudý počet lichých vrcholů, takže vždy existuje T -spojení. Zdvojnásobení hran T -přechodu způsobí, že se daný graf stane eulerovským multigrafem (souvislým grafem, ve kterém má každý vrchol sudý stupeň), což znamená, že má eulerovský cyklus , cestu, která navštíví každou hranu multigrafu přesně. jednou. Tato trasa bude optimálním řešením problému silniční kontroly [6] [2] .

Orientace na řešení

Na orientovaném grafu platí stejné základní myšlenky, ale je třeba použít jinou techniku. Pokud jde o Eulerův graf, musíte najít Eulerův cyklus. Pokud ne, je třeba najít T -přechody, což znamená najít cesty z vrcholů s in- stupeňem větším než jeho ven- stupeň k vrcholu s out- stupněm větším než je jeho in- stupeň , aby se dosáhlo in- stupeň rovný vnějšímu stupni pro každý vrchol grafu. To lze vyřešit jako příklad problému toku minimálních nákladů , ve kterém existuje zdroj rovný vstupnímu půlstupni a spotřebitel rovný výstupnímu půlstupně. Tento problém je vyřešen včas . Řešení existuje právě tehdy, když je daný graf silně souvislý [2] [7] .

Úkol pošťáka s větrem

Problém s větrem pošťáka je variantou problému silniční kontroly, ve kterém je vstupem neorientovaný graf, ale ve kterém má každá hrana jiné náklady na cestování v různých směrech. Na rozdíl od řešení pro orientované a neorientované grafy je problém NP-úplný [8] [9] .

Aplikace

Četné kombinatorické problémy jsou redukovány na problém čínského pošťáka, včetně nalezení maximálního řezu v rovinném grafu a cyklu minimální průměrné délky v neorientovaném grafu [10] .

Možnosti

Bylo studováno několik variant problému čínského pošťáka a byla prokázána jejich NP-úplnost [11]

Viz také

Poznámky

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

Literatura

Odkazy