Najkraća putanja 2D
Shortest Path 2D
Program ' Shortest Path 2D ' je unapređena verzija programa ' Najkraća putanja 2D '. Unapređenje se odnosi na promenu GUI, sobzirom da se radi o Windows Form Aplikaciji. Drugo bitno unapređenje je ugrađen algoritam za korekciju izabrane najkraće putanje, koji vrši male korekcije pravca putanje u smislu sprečavanja pojave takozvane cik cak putanje. Opis i implementaciju algoritma možete videti u okviru izvornog programskog koda koji preuzimate na linku na dnu strane. Besplatnu verziju programa možete pruzeti klikom na sliku levo. Za ispravan rad neophodan je Microsoftov .Net framework 4.0 ( ^ ) !
Opis i uputstvo se nalaze u okviru ' help ' opcije, ono što je bitno :
* simbol neprohodne tačke
O simbol polazne tačke
O simbol krajnje tačke
o simbol odabrane putanje
Postavljanje neprohodne, polazne i krajnje tačke se vrši tako što se klikne na prazno polje u mreži, kada se prvo nacrta neprohodna tačka. Klikom na neprohodnu tačku , menjamo je u polaznu, a klikom na polaznu, menjamo je u krajnju tačku. Program neće da pokrene pretragu za najkraćom putanjom ukoliko nisu postavljene polazna i krajnja tačka. Algoritam za korekciju putanje i još neke korisne opcije se nalaze u okviru ' options ' u okviru glavnog menija.
Najkraća putanja 2D
Program „Najkraća putanja 2D“ je namenjen za pronalaženje najkraće prohodne putanje između dve tačke koje pripadaju istoj dvodimenzionalnoj ravni. Ravan je tačno utvrđenih dimenzija na kojoj sve tačke imaju isto rastojanje od susednih tačaka, kao i određenu vrednost za karakteristiku tačke - 'Prohodnost tačke' , koja može da ima dve vrednosti : prohodna ili neprohodna. Prohodna putanja predstavlja skup međusobno povezanih prohodnih tačaka od polazne do krajnje tačke. Postoji mnogo različitih algoritama za rešavanje ovakvog problema, pogledajte tekst na sledećem linku (^).
Algoritam koji je primenjen za rešavanje ovog problema se sastoji iz dva dela.
- Prvi deo je određivanje vrednost za udaljenost svake prohodne tačke na ravni od polazne tačke.
- Drugi deo je odabir najkraće prohodne putanje.
Prvi deo Algoritma je najlakše razumeti kroz sledeću tekstualno-grafičku prezentaciju. Ravan možemo da predstavimo kao dvodimenzionalnu matricu.
Primer :
1 2 3 4 5 6 7
1 # # # # # # #
2 # A # . . . # A - polazna tačka
3 # . # . # . # B - krajnja tačka
4 # . . . . . # . - prohodna tačka
5 # . # . # . # # - neprohodna tačka
6 # . . . . B #
7 # # # # # # #
U prvom koraku postavimo vrednost za udaljenost polazne tačke na jedan.
1 2 3 4 5 6 7
1 # # # # # # #
2 # 1 # . . . # 1 - polazna tačka
3 # . # . # . # B - krajnja tačka
4 # . . . . . # . - prohodna tačka
5 # . # . # . # # - neprohodna tačka
6 # . . . . B #
7 # # # # # # #
U drugom koraku za svaku prohodnu tačku za koju nije određena udaljenost od polazne tačke određujemo udaljenost tako što pronalazimo onu susednu tačku koja ima najmanju vrednost za udaljenost i tu vrednost uvećavamo za jedan. U prvom slučaju to je tačka na koordinatama (2,3) s dodeljenom vrednošću za udaljenost dva, zbog toga što u svom susedstvu ima samo polaznu tačku čija je vrednost za udaljenost jedan.
1 2 3 4 5 6 7
1 # # # # # # #
2 # 1 # . . . # 1 - polazna tačka
3 # 2 # . # . # B - krajnja tačka
4 # . . . . . # . - prohodna tačka
5 # . # . # . # # - neprohodna tačka
6 # . . . . B # 2 - nova prohodna tačka kojoj je određena udaljenost
7 # # # # # # #
Ponavljamo drugi korak sve dok se pojavljuju nove prohodne tačke kojima je određena udaljenost.
1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 # # # # # # # 1 # # # # # # # 1 # # # # # # # 1 # # # # # # #
2 # 1 # . . . # 2 # 1 # . . . # 2 # 1 # 5 5 . # 2 # 1 # 5 5 6 #
3 # 2 # . # . # 3 # 2 # 4 # . # 3 # 2 # 4 # . # 3 # 2 # 4 # 6 #
4 # 3 3 . . . # 4 # 3 3 4 . . # 4 # 3 3 4 5 . # 4 # 3 3 4 5 6 #
5 # . # . # . # 5 # 4 # 4 # . # 5 # 4 # 4 # . # 5 # 4 # 4 # 6 #
6 # . . . . B # 6 # . . . . B # 6 # 5 5 5 5 B # 6 # 5 5 5 5 B #
7 # # # # # # # 7 # # # # # # # 7 # # # # # # # 7 # # # # # # #
Ponavljanje drugog koraka se odvija po principima rada celularnog automata i stvaranja novih generacija ćelija (^). Svaka prohodna tačka u ravni kojoj se odredi udaljenost se tretira kao novonastala generacija ćelija. U tom smislu se drugi korak ponavlja sve dok se pojavljuju nove generacije ćelija.
Drugi deo algoritma jeste odabir najkraće putanje od krajnje do polazne tačke, pod uslovom da ista postoji.
1 - Pozicioniramo pokazivač na koordinate krajnje tačke.
2 - Proverimo sve susedne tačke i odaberemo onu koja ima najmanju vrednost za udaljenost.
3 - Ukoliko ima više tačaka u okruženju sa istom najmanjom vrednošću odaberemo jednu po slučajnom principu. Ovaj korak može da bude i drugačiji, u primeru programa je implementirana funkcija koja određuje koja će tačka biti odabrana na osnovu vrednosti za udaljenost i blizine tačke zamišljenoj pravoj liniji koja prolazi kroz polaznu i krajnju tačku.
4 - Postavljamo pokazivač na odabranu tačku i ponavljamo korake 2, 3 i 4 sve dok ne dođemo do polazne tačke.
1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 # # # # # # # 1 # # # # # # # 1 # # # # # # # 1 # # # # # # #
2 # A # 5 5 6 # 2 # A # 5 5 6 # 2 # A # 5 5 6 # 2 # A # 5 5 6 #
3 # 2 # 4 # 6 # 3 # 2 # 4 # 6 # 3 # 2 # 4 # 6 # 3 # o # 4 # 6 #
4 # 3 3 4 5 6 # 4 # 3 3 4 5 6 # 4 # 3 o 4 5 6 # 4 # 3 o 4 5 6 #
5 # 4 # 4 # 6 # 5 # 4 # o # 6 # 5 # 4 # o # 6 # 5 # 4 # o # 6 #
6 # 5 5 5 o B # 6 # 5 5 5 o B # 6 # 5 5 5 o B # 6 # 5 5 5 o B #
7 # # # # # # # 7 # # # # # # # 7 # # # # # # # 7 # # # # # # #
1 2 3 4 5 6 7
1 # # # # # # #
2 # A # . . . # A - polazna tačka
3 # o # . # . # B - krajnja tačka
4 # . o . . . # . - prohodna tačka
5 # . # o # . # # - neprohodna tačka
6 # . . . o B # o - odabrana najkraća prohodna putanja
7 # # # # # # #
Na prikazu iznad se vidi jedna od mnogobrojnih mogućih prohodnih putanja od polazne do krajnje tačke koja je ujedno i najkraća. Termin 'Prohodna putanja' se namerno potencira zbog mogućnosti da se prohodnost putanje okarakteriše na drugačiji način. U samom programu prohodna putanja je definisana tako da nije moguće dijagonalno kretanje ukoliko se u susedstvu u smeru kretanja nalaze neprohodne tačke, pa bi u tom slučaju tekstualno-grafički prikaz matrice s određenim udaljenostima tačaka od polazne tačke izgledao ovako :
1 2 3 4 5 6 7
1 # # # # # # #
2 # 1 # 7 8 9 #
3 # 2 # 6 # 8 # 1 - polazna tačka
4 # 3 4 5 6 7 # B - krajnja tačka
5 # 4 # 6 # 8 # . - prohodna tačka
6 # 5 6 7 8 B # # - neprohodna tačka
7 # # # # # # #
A prikaz matrice s odabranom najkraćom putanjom ovako :
1 2 3 4 5 6 7
1 # # # # # # #
2 # A # 7 8 9 # A - polazna tačka
3 # o # 6 # 8 # B - krajnja tačka
4 # o o o o o # . - prohodna tačka
5 # 4 # 6 # o # # - neprohodna tačka
6 # 5 6 7 8 B # o - odabrana najkraća prohodna putanja
7 # # # # # # #
Odmah se uočava razlika u dužini putanje , četiri u prvom slučaju u odnosu na sedam u drugom. Implementiran kao konzolna aplikacija u programskom jeziku C#, program predstavlja jedno od mnogobrojnih rešenja za ovakvu vrstu problema. Na dole navedenom linku ili klikom na sliku programa, možete preuzeti izvršnu verziju programa ili kompletan programski kod. Za ispravan rad programa neophodan je Microsoft-ov .Net framework 4.0 ( ^ ) !