Problem kitajskega poštarja

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka NusaSkala.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

V DELU

Problem Kitajskega poštarja uporabljamo, ko želimo kako najti najkrajšo pot v povezanem neobteženem ali obteženem grafu, kjer je pogoj, da vsako povezavo danega grafa prehodimo vsaj enkrat in največ dvakrat. Da bi lažje razumeli, si predstavljamo poštarja, ki se sprehaja po mreži ulic (v našem primeru je to graf) in želi v kar najkrajšem času v vsako hišo dostaviti pošto (hiše so točke na danem grafu) ter se nato vrniti nazaj na glavno pošto (torej v začetno točko). Poštar želi prihraniti nepotreben čas, napor in denar ter opraviti svoje delo na čim krajši relaciji. Metoda za reševanje je bila izdelana in razvita z namenom najti najboljši "sistem" dostavljanja pošte. Če so vse ulice v omrežju dvosmerne, potem pravimo, da je naš graf neusmerjen in je problem tudi enostavnejši. Pri enosmernih ulicah se problem malce zakomplicira. Vsaka točka na grafu ima svojo stopnjo. Če iz določene hiše vodita dve poti, oziroma ulici, potem je hiša, v našem primeru točka, sode stopnje, če iz nje vodi liho število poti, imamo točko lihe stopnje. Če imajo vse točke sodo stopnjo, lahko naredimo po našem omrežju Eulerjev obhod, kar pomeni, da lahko naredimo takšen obhod, v katerem bomo vsako ulico prehodili natanko enkrat in se na koncu vrnili v začetno točko. Vsaka Eulerjeva krožna pot je hkrati tudi optimalna rešitev Problema kitajskega poštarja. Seveda pa v realnosti ni mogoče vedno pričakovati takšnega grafa, še manj pa ga vnaprej napovedati. Če imamo na grafu tudi točke lihe stopnje, jih lahko spremenimo v sode s podvajanjem povezav. Povedano po domače: Med dve točki lihe stopnje poljubno dodamo povezavo, da dobimo točke sode stopnje. Optimalna rešitev problema je v tem, da podvojimo tiste povezave, katerih skupna teža, oziroma cena bo najmanjša, pri tem pa preslikamo prvotni graf G v G', tako da bo G' Eulerjev graf. Problem kitajskega poštarja je rahlo podoben Problemu trgovskega potnika, le da mora popotnik obiskati vse hiše in mu ni treba nujno prehoditi vsake povezave.

Primeri uporabe v realnem življenju:

V realnem življenju se pri reševanju različnih problemov dostikrat srečamo s Problemom kitajskega poštarja. Uporabljamo ga v primerih, ko želimo najti optimalno pot v nekem omrežju, pa naj bo cestno, električno, železniško,itd. Vsi ti primeri imajo skupen cilj - minimizirati razdalje, prepotovane skozi določeno mrežo, s tem da moramo obiti vsako povezavo.

Železnica: Inšpektor po koncu zime želi pregledati vse železniške tire, da bi našel morebitne pomanjkljivosti, napake, okvare. To je razlog, zakaj Problem Kitajskega poštarja drugače imenujemo tudi moderno angleško "Route Inspection Problem", ki ga lahko prevedemo kot "Problem nadzorovanja povezav". Tirnice želimo pregledati kar se da hitro. Če je možno, bi inšpektor rad zaključil v isti točki kot je začel, recimo na železniški postaji. V našem primeru je problem kitajskega poštarja zelo uporaben, če predpostavljamo, da imamo na voljo poenostavljen graf železniških tirov.

Eulerjeva krožna pot, če obstaja, rešuje problem snežnega pluga, ko želimo splužiti vse ceste, vsako le enkrat in se vrniti na začetek. Kot pri drugih primerih iz realnega življenja tudi tu ne moremo pričakovati, da bodo pogoji s sodimi stopnjami veljali za našo ulico. Če se bo torej izkazalo, da moramo po neki ulici dvakrat, bomo izbrali takšno, ki je čim krajša.

Izdelava zemljevida: Recimo da moramo narediti zemljevid mesta, na katerem so označene ceste, kjer je dovoljen promet

za tovorna vozila. Vsaka tovarna mora imeti cesto, po kateri lahko tovornjak pripelje tovor. Tovor je treba prepeljati do vseh tovarn v čim krajšem času, se pravi je treba minimizirati celotno pot, saj želimo hkrati opraviti čim manj kilometrov.

Avtobusni promet:Praktičen primer, na katerem je pametno uporabiti Problem kitajskega poštarja je tudi načrtovanje avtobusnega usmerjanja. Da bi prihranili stroške goriva, morajo tudi avtobusni prevozniki svoj problem pretvoriti na matemični način. Prav tako kot pri opravljanju poštnih storitev pri veliki množici naslovnikov, se tudi tu splača mrežo ulic definirati kot graf in nato na njem uporabiti metode za reševanje Problema kitajskega poštarja. Avtobusne postaje naj bodo naše točke grafa, ceste po katerih vozi avtobus pa povezave grafa. Cilj je, da avtobus čim hitreje (seveda po omejitvah) ljudi prepelje od začetne do končne postaje, s tem da obide vsa postajališča in se na koncu vrne spet na začetno mesto.

Splet: Konec koncev si lahko tudi svetovni splet, bolj znan kot "www" predstavljamo kot nekakšen graf. Vsak računalnik je točka in vsaka povezava telefonska linija, naš cilj pa bi lahko bil izboljšati (minimizirati) razdalje (pretok) informacij in posledično izboljšati zmogljivost in predvsem hitrost podatkov.

Nekateri matematiki, ki so se ukvarjali z raziskovanjem in iskanjem možnih pristopov pri iskanju optimalne poti po danem grafu, so ugotavljali, da se kot najbolj uporaben in natančen izkaže prav način, oziroma metode, ki se uporabljajo za reševanje Problema kitajskega poštarja.


Slika:slika_13.jpg

Osebna orodja