Promjena jezika

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Prijavite se u Mathigon

ili

Novi profil     Resetiranje lozinke     

Grafikoni i mreže
Uvod
Königsberški mostovi
Rukovanje i druženje
Ravni grafikoni
Bojanje karte
Problem putničkog prodavca
Problemi s planiranjem
Grafovi u svakodnevnom životu

Podijeli

Poništavanje napretka

Ovim ćete izbrisati podatke o napretku i chatu za sva poglavlja ovog tečaja i ne možete ih poništiti!

Riječnik

Odaberite jednu od ključnih riječi s lijeve strane ...

Grafikoni i mrežeProblem putničkog prodavca

Vrijeme čitanja: ~15 min

Razmislimo još jednom o mrežama i kartama. Zamislite da dostavna služba mora posjetiti ${tsn} različite gradove radi distribucije paketa. O tim gradovima možemo misliti kao o vrhovima na grafu. Ako su svi gradovi povezani cestama, ovo je , pa postoji ${tsn} × (${tsn} - 1) 2 = ${tsn*(tsn-1)/2} rubova ukupno.

Kamion za dostavu mora posjetiti sve gradove, bilo kojim redoslijedom. U problemu mostova Königsberg željeli smo pronaći staze koje putuju duž svakog ruba točno jednu. Sada želimo pronaći staze koje obilaze svaki vrh točno jednom. Ove se staze nazivaju Hamiltonski ciklusi.

Postoji bezbroj različitih mogućnosti za Hamiltonove cikluse u cjelovitim grafovima. Zapravo možemo odabrati bilo koju točku kao vršku i zatim odabrati bilo koji od preostalih gradova bilo kojim redoslijedom:

Diagram coming soon…

Diagram Coming Soon…

U grafikonu sa ${tsn1} gradovima, svaki Hamiltonov ciklus također mora sadržavati ${tsn1} gradova. Sada,

    To znači da, ukupno, postoji ${tsnPaths(tsn1)} mogućih staza. Skraćenica za ovaj proizvod je ${tsn1}! ili ${tsn1} Faktorski.

    Mogli biste zamisliti da možda neće biti moguće putovati izravno između dva grada - a da ne prođete kroz neki drugi grad. U tom slučaju više nemamo kompletan graf, a pronalazak broja Hamiltonovih ciklusa, ako oni uopšte postoje, postaje mnogo teže.

    Do sada smo zanemarili činjenicu da bi neki gradovi mogli biti dalje od ostalih. U stvarnom životu, međutim, ovo je vrlo važno razmatranje: ne želimo samo pronaći bilo koji put, već želimo pronaći najkraći. To se zove Problem prodavca putovanja. To se mora riješiti ne samo u transportu i logistici, već i pri postavljanju tranzistora na mikročipove, radi bržeg računala ili pri analizi strukture DNA.

    Jedna jednostavna metoda bilo bi isprobati sve moguće staze, pronalazeći duljinu svakog, a zatim birajte najkraći. Međutim, pokazali smo da čak i sa samo 533 gradova ima ${tsn2}! = ${factorial(tsn2)} mogući putevi. Jednom kada imate stotine ili tisuće vrhova, iskušavanje svih mogućih staza postaje nemoguće, čak i koristeći moćna računala.

    Nažalost, ne postoji učinkovitiji algoritam za rješavanje problema putničkog prodavca. Umjesto toga, matematičari i računalni znanstvenici razvili su različite algoritme koji pronalaze dobra rješenja, čak i ako možda nisu baš najbolja. Ovi algoritmi, koji daju samo približna rješenja, nazivaju se Heuristika.

    Pokušajte preurediti gradove na ovoj karti i promatrajte kako se mijenja najkraći put između njih. Gradove možete ukloniti dodirom na njih, a gradove možete dodati klikom bilo gdje na karti (do 8):

    pohlepni algoritam (ili najbliži algoritam susjeda) vrlo je jednostavan: krenete u slučajni grad i uzastopno se preselite u najbliži grad koji prije niste posjetili. Kad jednom posjetite sve gradove, zaustavite se.

    Animacija uskoro stiže ...

    Možete pokazati da su u prosjeku staze pronađene pohlepnim algoritmom 25% duže od najkraćeg mogućeg puta.

    2-opt algoritam započinje slučajnim mogućim putem. Zatim nekoliko puta odaberete dva ruba i zamijenite ih ako bi to umanjilo duljinu staze. Zaustavite se kad ne možete dodatno smanjiti duljinu zamjenom bilo kojeg para rubova.

    Animacija uskoro stiže ...

    Ispada da je priroda, prije nego što su računala uopće postojala, pronašla pametan način pronalaska optimalnih staza između različitih mjesta: u kolonijama mrava.

    Mravi žele pronaći najkraće moguće rute između svog gnijezda i mogućih izvora hrane. Oni mogu međusobno komunicirati kemikalijama koje ostave na tragu i koje drugi mravi mogu slijediti.

    • Kolonija mrava šalje mnogo izviđača koji u početku putuju nasumičnim pravcima. Kad pronađu hranu, vraćaju se, ostavljajući za sobom trag feromona.
    • Ostali mravi imaju tendenciju da slijede trag kada pronađu jednog, koji ih vodi do hrane. Na povratku, oni polažu više feromona i na taj način pojačavaju trag.
    • S vremenom feromon isparava. Što je put duži, to više treba vremena da mravi putuju po njemu i tako feromon ima više vremena za isparavanje. S druge strane, kratki se putovi mogu brže pojačati pa se njihova snaga brže povećava.

    Dijagram uskoro stiže ...

    Algoritmi sustava Ant Colony (ACS) pokušavaju ponoviti ovo ponašanje na računalima, koristeći mnoge "virtualne" mrave. Vrlo brzo mogu naći vrlo dobra rješenja za problem putničkog prodavača.

    Jedno posebno korisno svojstvo ACS algoritama je ta što se oni mogu neprekidno pokretati i prilagođavati u grafičkom obliku u stvarnom vremenu. Te bi promjene mogle biti uzrokovane prometnim nesrećama i zatvaranjem cesta na uličnim mrežama ili padom prometa na web poslužiteljima računalnih mreža.

    Problem prodavača putovanja je težak, što znači da je to vrlo teško riješiti računalima (barem za veliki broj gradova).

    Pronalaženje brzog i točnog algoritma imalo bi ozbiljne implikacije na području računarske znanosti: to bi značilo da postoje brzi algoritmi za svih NP-teških problema. Također bi većinu Internet sigurnosti učinilo beskorisnom, što se oslanja na činjenicu da se vjeruje da su određeni problemi vrlo teški za računala.

    Pronalaženje brzog algoritma za rješavanje problema Putničkog prodavača također bi riješilo jedan od najpoznatijih otvorenih problema iz matematike i računarske znanosti, problem P vs NP. To je jedan od sedam problema sa tisućljetnom nagradom, a svaki nosi nagradu u iznosu od milion dolara.

    Archie