Tientarkastustehtävä

Kiinan postimiesongelma ( CPP ) , postimiesreitti tai tientarkastusongelma on löytää  lyhin suljettu polku tai sykli, joka kulkee (yhdistetyn) painotetun suuntaamattoman graafin jokaisen reunan läpi . Jos kuvaajassa on Eulerin sykli (suljettu polku, joka kulkee minkä tahansa reunan läpi tarkalleen kerran), tämä sykli on optimaalinen ratkaisu. Muussa tapauksessa optimointiongelmana on löytää iteroidusta graafista pienin määrä reunoja (tai reunojen osajoukko, jolla on pienin mahdollinen kokonaispaino) siten, että tuloksena olevalla multigrafilla on Eulerin sykli [1] . Tämä ongelma voidaan ratkaista polynomiajassa [2] .

Ongelmaa tutki alun perin vuonna 1960 kiinalainen matemaatikko Kwon Mei-Ko, jonka artikkeli käännettiin kiinasta englanniksi vuonna 1962 [3] . Vaihtoehtoinen nimi "Chinese Postman Problem" annettiin hänen kunniakseen. Useat lähteet antavat nimen joko Alan J. Goldmanille tai Jack Edmondsille, jotka olivat tuolloin National Institute of Standards and Technologyn palveluksessa [4] [5] .

Ohjaamaton ratkaisu

Suuntamaton tientarkastusongelma voidaan ratkaista polynomiajassa T -risteyksen käsitteeseen perustuvalla algoritmilla . Olkoon T graafin kärkijoukon osajoukko. Reunajoukkoa J kutsutaan T -liitokseksi , jos joukko pisteitä, joissa on pariton määrä reunoja J :stä, joka yhdistää kärjen sen naapureihin, vastaa tarkasti joukkoa T . T -yhteys on olemassa, jos mikä tahansa graafin yhdistetty komponentti sisältää parillisen määrän pisteitä T :stä . T -liitoksen tehtävänä on löytää T -risteys, jossa on vähiten reunoja tai pienin kokonaispaino.

Jokaiselle T : lle pienin T -yhteys (jos sellainen on) sisältää välttämättä polkuja, jotka yhdistävät T :n kärjet pareiksi. Polut ovat sellaiset, että kokonaispituus tai kokonaispaino on mahdollisimman pieni. Optimaalisessa ratkaisussa kahdella näistä poluista ei ole yhteisiä reunoja, mutta ne voivat jakaa kärjet. Pienin T -liitos voidaan saada rakentamalla täydellinen graafi T :n huipuille , jonka reunat edustavat lyhimpiä polkuja tietyssä syötegraafissa, ja sitten etsimällä pienimmän painoisen täydellisen yhteensopivuuden tuosta täydellisestä graafista. Vastaavat reunat edustavat alkuperäisen graafin polkuja, joiden liitos muodostaa halutun T -liitoksen. Täydellisen kaavion rakentaminen ja siitä vastaavan löytäminen voidaan tehdä vaiheittain.

Tientarkastustehtävässä T : n tulee olla kaikkien parittoman asteen pisteiden joukko. Tehtävän ehtojen mukaan koko graafi on yhdistettävä (muuten ei ole ohitusta), ja kättelylemman mukaan siinä on parillinen määrä parittomia pisteitä, joten T -yhteys on aina olemassa. T -risteyksen reunojen kaksinkertaistaminen saa annetusta graafista Eulerin monigraafin (yhdistetty graafi, jossa jokaisella kärjellä on parillinen aste), mikä tarkoittaa, että sillä on Eulerin sykli , reitti, joka vierailee multigrafin jokaisessa reunassa täsmälleen yhden kerran. Tämä reitti on optimaalinen ratkaisu tietarkastuksen ongelmaan [6] [2] .

Ratkaisusuuntautunut

Suunnatussa graafissa pätevät samat perusideat, mutta on käytettävä erilaista tekniikkaa. Jos Eulerin kaavio, sinun on löydettävä Eulerin sykli. Jos ei, on löydettävä T -liitokset, mikä tarkoittaa polkujen etsimistä pisteistä, joiden in -aste on suurempi kuin sen ulos -aste , kärkeen, jonka out -aste on suurempi kuin sen in -aste , jotta sisään- aste, joka on yhtä suuri kuin graafin kunkin kärjen ulko-aste. Tämä voidaan ratkaista esimerkkinä minimikustannusvirtausongelmasta , jossa lähde on yhtä suuri kuin tulopuoliastetta ja kuluttaja, joka vastaa lähdön puoliastetta. Tämä ongelma ratkeaa ajoissa . Ratkaisu on olemassa, jos ja vain, jos annettu graafi on vahvasti kytketty [2] [7] .

Postimiehen tehtävä tuulen kanssa

Postimiehen tuuliongelma on muunnelma tientarkastusongelmasta, jossa syöte on suuntaamaton graafi, mutta jossa jokaisella reunalla on eri hinta kulkea eri suuntiin. Toisin kuin suunnattujen ja suuntaamattomien graafien ratkaisut, ongelma on NP-täydellinen [8] [9] .

Sovellukset

Lukuisat kombinatoriset ongelmat rajoittuvat kiinalaiseen postimiesongelmaan, mukaan lukien maksimileikkauksen löytäminen tasograafista ja minimikeskipituuden sykli suuntaamattomasta graafista [10] .

Vaihtoehdot

Kiinalaisen postimiesongelman useita muunnelmia tutkittiin ja niiden NP-täydellisyys osoitettiin [11]

Katso myös

Muistiinpanot

  1. ↑ Roberts, Tesman, 2009 , s. 640–642.
  2. ↑ 1 2 3 Edmonds ja Johnson, 1973 , s. 88–124.
  3. ↑ Kwan, 1960 , s. 263-266.
  4. ↑ Pieterse, musta, 2014 .
  5. ↑ Grötschel, Yuan, 2012 , s. 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 , s. 221-227.
  10. ↑ Schrijver, 2002 .
  11. ↑ Crescenzi, Kann, 2000 .
  12. ↑ Roberts, Tesman, 2009 , s. 642–645.

Kirjallisuus

Linkit