Útvizsgálati feladat

A  kínai postás probléma ( CPP ), a postás útvonal vagy az útellenőrzési probléma az, hogy meg kell találni a legrövidebb zárt utat vagy ciklust, amely átmegy egy (összekapcsolt) súlyozott irányítatlan gráf minden élén . Ha a gráfnak van Euler-ciklusa (zárt út, amely bármely élen pontosan egyszer halad át), akkor ez a ciklus az optimális megoldás. Ellenkező esetben az optimalizálási probléma az, hogy az iterált gráfban meg kell találni a legkisebb számú élt (vagy a lehető legkisebb össztömegű élek részhalmazát), hogy a kapott multigráf Euler-ciklussal rendelkezzen [1] . Ez a probléma polinomiális időben megoldható [2] .

A problémát eredetileg 1960-ban Kwon Mei-Ko kínai matematikus tanulmányozta, akinek írását 1962-ben fordították le kínairól angolra [3] . Tiszteletére adták a "Kínai Postás Probléma" alternatív nevet. Különféle források a nevet Alan J. Goldmannek vagy Jack Edmondsnak tulajdonítják, akik akkoriban a National Institute of Standards and Technology alkalmazottai voltak [4] [5] .

Irányítatlan megoldás

Az irányítatlan útellenőrzési probléma polinomiális időben megoldható egy T -elágazás koncepción alapuló algoritmussal . Legyen T a gráf csúcshalmazának egy részhalmaza. Egy J élhalmazt T -átmenetnek nevezünk , ha a J -ből a csúcsot szomszédaival összekötő páratlan számú élű csúcsok gyűjteménye pontosan megegyezik a T halmazzal . T -kapcsolat létezik, ha a gráf bármely összekapcsolt komponense páros számú csúcsot tartalmaz T -ből . A T -elágazás feladata, hogy megtalálja a legkevesebb élszámú vagy a legkisebb össztömegű T -átmenetet.

Bármely T esetén a legkisebb T -kapcsolat (ha létezik) szükségszerűen tartalmaz olyan utakat, amelyek T csúcsait párokká kötik . Az utak olyanok lesznek, hogy a teljes hossza vagy össztömeg a lehető legkisebb legyen. Az optimális megoldásban ezek közül az útvonalak közül kettőnek nincs közös éle, de megoszthatják a csúcsokat. A legkisebb T -egyesítést úgy kaphatjuk meg, hogy T csúcsaira egy teljes gráfot készítünk , amelynek élei a legrövidebb utakat reprezentálják egy adott bemeneti gráfban, majd megtaláljuk a legkisebb súlyú tökéletes illeszkedést ebben a teljes gráfban. Az egyező élek olyan útvonalakat jelentenek az eredeti gráfban, amelyek egyesítése a kívánt T -csatlakozást alkotja. Egy komplett gráf felépítése, majd abban egyezés megtalálása lépésenként történhet .

Az útellenőrzési feladathoz T az összes páratlan fokú csúcs halmaza. A feladat feltételei szerint a teljes gráfot össze kell kötni (egyébként nincs bypass), a handshake lemma alapján pedig páros számú páratlan csúcsa van, tehát mindig létezik T -kapcsolat. A T -elágazás éleinek megkettőzésével az adott gráf Euler-multigráf lesz (egy olyan összefüggő gráf, amelyben minden csúcsnak páros foka van), ami azt jelenti, hogy van egy Euler-ciklusa , egy olyan útvonal, amely pontosan meglátogatja a multigráf minden élét. egyszer. Ez az útvonal lesz az optimális megoldás a közúti ellenőrzés problémájára [6] [2] .

Megoldásorientált

Irányított gráfon ugyanazok az alapgondolatok érvényesek, de más technikát kell alkalmazni. Ha az Euler-gráf, akkor meg kell találnia az Euler-ciklust. Ha nem, akkor meg kell találni a T -elágazásokat, ami azt jelenti, hogy a bemeneti fokozatnál nagyobb be-fokkal rendelkező csúcsokból kell megkeresni egy olyan csúcsot, amelynek ki-fokja nagyobb , mint az in -degree . foka megegyezik a gráf minden csúcsának külső fokával. Ez megoldható a minimális költségáramlási probléma példájaként , amelyben a bemeneti félfokkal egyenlő forrás és a kimeneti félfokkal egyenlő fogyasztó található. Ez a probléma idővel megoldódik . Megoldás akkor és csak akkor létezik, ha az adott gráf erősen összefügg [2] [7] .

A postás feladata a széllel

A postás szélprobléma az útellenőrzési probléma egy olyan változata, amelyben a bemenet egy irányítatlan gráf, de minden élnek eltérő költsége van a különböző irányokba való utazáshoz. Az irányított és irányítatlan gráfok megoldásaival ellentétben a probléma NP-teljes [8] [9] .

Alkalmazások

Számos kombinatorikus probléma redukálódik a kínai postás problémára, beleértve a maximális szakasz megtalálását egy síkgráfban és a minimális átlagos hosszúságú ciklust egy irányítatlan gráfban [10] .

Opciók

A kínai postás-probléma számos változatát tanulmányozták, és kimutatták azok NP-teljességét [11]

Lásd még

Jegyzetek

  1. ↑ Roberts, Tesman, 2009 , p. 640–642.
  2. ↑ 1 2 3 Edmonds és Johnson, 1973 , p. 88–124.
  3. ↑ Kwan, 1960 , p. 263–266.
  4. ↑ Pieterse, Fekete, 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.

Irodalom

Linkek