Algoritam za rešavanje lavirinta
Ovaj članak možda zahteva čišćenje i/ili prerađivanje kako bi se zadovoljili standardi kvaliteta Vikipedije. Problem: Unos unutrašnjih veza i referenci. (decembar 2016) |
Postoji nekoliko različitih varijanti algoritama za rešavanje lavirinta, koji predstavljaju automatizovane metode za rešavanje bilo kog lavirinta.
Nasumični algoritam miša, algoritam praćenja zida, algoritam Džona Pledža (en. Jon Pledge) i Tremauksov (fr. Charles Pierre Trémaux) algoritam su dizajnirani tako da se koriste kada se osoba nalazi unutar samog lavirinta bez ikakvog poznavanja strukture i izgleda samog lavirinta, dok su algoritam ispunjavanja ćorsokaka i algritam najkraćeg puta dizajnirani tako da se koristi kada osoba ili računarski program unapred poznaje strukturu i izgled čitavog lavirinta.
Lavirinti koji ne sadrže petlje poznati su kao *standardni* ili *savršeni* lavirinti, i kao takvi ekvivalentni su stablima u teoriji grafova preko kojih se mogu i predstavljati. Prema tome većina algoritama za rešavanje lavirinta se oslanjaju na teoriju grafova.
Intuitivno, ako bi se svi putevi u lavirintu ispravno izdvojili, kao rezultat mogli bi dobiti nešto što dobro podseća na strukturu stabla.
Nasumični algoritam miša
urediOvo je trivijalni algoritam koji može biti iskorišćen kod veoma neinteligentnih robota ili na miševe. Algoritam se sastoji od praćenja putanje kojom se krećemo sve dok ne dođemo do raskrsnice sa više mogućnosti skretanja, tada nasumišno odabiramo koju ćemo putanju nadalje slediti. Iako će ovakav algoritam na kraju uvek pronaći pravo rešenje, ovaj algoritam može biti i ekstremno spor. Razlog za to je što se putanje koje smo već jednom prošli ne eliminišu iz ponovnog razmatranja kada se na njih ponovo naiđe.
Algoritam praćenja zida
uredi
Algoritam praćenja zida, predstavlja jedan od najpoznatijih algoritama za pronalaženje izlaza iz lavirinta, a takođe je poznat i pod nazivima „pravilo leve ruke“ i „pravilo desne ruke“.
Ukoliko je lavirint povezan, odnosno ako su svi njegovi zidovi međusobno spojeni ili ako su spojeni sa spoljašnjom granicom lavirinta, tada ako osoba unutar lavirinta drži ruku u kontaktu sa zidom tokom celog prolaska kroz lavirint garantovano dolazi do izlaza iz lavirinta ako izlaz uopšte i postoji, u suprotnom osoba bi se vratila na ulaz u lavirint i pritom bi obišla svaku putanju u lavirintu barem jedanput.
Ako ovaj problem pogledamo s druge, topološke, strane primećuje se zašto je algoritam praćenja zida u mogućnosti da uvek pronađe pravo rešenje. Ako su zidovi povezani, to znači da se mogu raširiti u kružnicu.[1] Tako se algoritam praćenja zida redukuje na prolazak ivicama te kružnice od ulaza do izlaza.
Ukoliko lavirint nije povezan (npr. ako su ulaz u lavirint ili izlazi iz njega u centru samog lavirinta ili putanje prelaze jedna preko druge ili jedna ispod druge), nije garantovano da će ovaj algoritam zaista u takvim slučajevima pronaći izlaz iz lavirinta.
Algoritam praćenja zidova može se koristiti i u trodimenzionalnim i višedimenzionalnim okruženjima ukoliko te višedimenzione putanje mogu biti projektovane u dvodimenzionalnoj ravni na deterministički način.
Na primer, ukoliko u trodimenѕionalnom algoritmu putanje „nagore“ smatramo putanjama ka severo-zapadu, a putanje „nadole“ smatramo putanjama ka jugo-istoku, tada možemo upotrebiti standardna pravila algoritma praćenja zida. Međutim, za razliku od dvodimenzionalnog prostora, ovde je potrebno u svakom momentu znati i trenutnu orijentaciju, da bi se znalo koji smer je prvi nalevo ili nadesno..
Algoritam Džona Pledža
urediNepovezani algoritmi se ipak na određene načine mogu rešiti korišćenjem algoritma praćenja zida, ukoliko se ulaz i izlazi iz lavirinta nalaze na spoljašnjim zidovima lavirinta. Međutim, ukoliko se ulaz nalazi u unautrašnjosti lavirinta, može se naći na zidu koji nije spojan sa zidom na kome se nalazi izlaz, pa bi se korišćenjem algoritma praćenja zidova osoba vrtela u krug i vraćala na početak ne pronalazeći izlaz. Algoritam Džona Pledža može da reši ovaj problem.
Pledžov algoritam, dizajniran da zaobiđe prepreke, zahteva kretanje u unapred određenom smeru.
Kada se naiđe na prepreku, jedna ruka (npr. desna) nastavlja da prati prepreku a takođe prati se i broj okreta na levu i desnu stranu korišćenjem brojača okreta. Okretanje na desnu stranu povećava vrednost brojača, a okret na levu stranu smanjuje njegovu trenutnu vrednost. Kada se osoba ponovo okrene ka originalnom unapred određenom smeru, tada je brojač okreta ponovo vraćen na vrednost 0 i prepreka je uspešno savladana, osoba nastavlja sa kretanjem u početnom originalnom smeru ka svom cilju pa ako se ponovo naiđe na prepreku prethodni postupak se ponavlja. Ruka više ne prati zid samo kada je brojač okreta ponovo postavljen na 0. Ovakav pristup omogućava algoritmu da izbegne zamke koje su na primer oblika velikog latiničnog slova G - ("G").
U suštini algoritam je vrlo jednostavan i sastoji se od provere nekoliko pravila koja se proveravaju tokom prolaska kroz lavirint:
(algoritam zasnovan na pravilu desne ruke)
1. Osoba se kreće unapred određenim smerom.
2. Kada se naiđe na prepreku prvi put osoba se okreće na levu stranu. Brojač okreta se tada umanjuje za 1.
3. Vrši se provera postojanja prepreka. Osoba proverava da li postoji prepreka ispred, desno ili levo.
- Ukoliko nema prepreke na desnoj strani osoba se okreće na desnu stranu. Brojač okreta se uvećava za 1.
- Ukoliko postoji prepreka na desnoj strani, a ne postoji prepreka ispred, osoba se pomera unapred za jedan korak. Brojač okreta ne menja svoju trenutnu vrednost.
- Ukoliko postoji prepreka na desnoj strani i postoji prepreka ispred, osoba se okreće na levu stranu. Brojač okreta se tada umanjuje za 1.
Prethodni podkoraci koraka 3 se navedenim redosledom proveravaju sve dok se brojač okreta ponovo ne vrati na vrednost 0 i tada smatramo da je prepreka uspešno savladana.
4. Osoba nastavlja da se kreće početnim smerom, sve dok se ponovo ne naiđe na prepreku ili se stigne do izlaza.
Algoritam zasnovan na pravilu leve ruke može se analogno izvesti iz prethodnog.
Na ovaj način algoritam omogućava osobi koja ume da proverava postojanje prepreka ispred, levo i desno, uspešno pronalaženje izlaza na spoljašnjem zidu iz bilo kog dvodimenzionalnog lavirinta, nezavisno od početne pozicije osobe u lavirintu. Međutim ovaj algoritam ne pruža mogućnost rešavanja suprotnog problema prethodnom problemu. Algoritam neće raditi ako se ulaz nalazi na spoljašnjem zidu lavirinta, a neki cilj u unutrašnjosti lavirinta.
Java kod algoritma Džona Pledža zasnovanog na pravilu leve ruke za pokretanje robota
uredi
1 // код који се односи на кретање особе унапред
2 public boolean isActive() {
3 return true;
4 }
5 public Velocities act() {
6 double rotationalVelocity = 0.0;
7 return new Velocities(TRANSLATIONAL_VELOCITY, rotationalVelocity);
8 }
9
10
11 // код који се односи на скретање у десну страну
12 public boolean isActive() {
13 if (turningRightCount > 0) {
14 return true;
15 }
16 RangeSensorBelt bumpers = getSensors().getBumpers();
17 // провера постојања предње препреке.
18 if (bumpers.hasHit(0)) {
19 backingUpCount = 10;
20 turningRightCount = getRotationCount();
21
22 return true;
23 } else {
24 return false;
25 }
26 }
27
28 public Velocities act() {
29 if (backingUpCount > 0) {
30
31 backingUpCount--;
32
33 return new Velocities(-TRANSLATIONAL_VELOCITY, 0.0);
34 } else {
35 turningRightCount--;
36
37 return new Velocities(0.0, -Math.PI / 2);
38 }
39 }
40
41
42 public boolean isActive() {
43 if (postGoingForwardCount > 0) {
44 return true;
45 }
46
47 RangeSensorBelt sonars = getSensors().getSonars();
48 // провера левог сензора.
49 if (sonars.getMeasurement(1) > 1.0) {
50 // могуће је скренути лево.
51 preGoingForwardCount = 20;
52 postGoingForwardCount = 40;
53 turnLeftCount = getRotationCount();
54
55 return true;
56 } else {
57 return false;
58 }
59 }
60
61 public Velocities act() {
62 if (preGoingForwardCount > 0) {
63 preGoingForwardCount--;
64
65 return new Velocities(TRANSLATIONAL_VELOCITY, 0.0);
66 } else if (turnLeftCount > 0) {
67 turnLeftCount--;
68
69 return new Velocities(0.0, Math.PI / 2);
70 } else {
71 postGoingForwardCount--;
72
73 return new Velocities(TRANSLATIONAL_VELOCITY, 0.0);
74 }
75 }
76
77
78 public boolean isActive() {
79 RangeSensorBelt sonars = getSensors().getSonars();
80
81 // да ли смо стигли ван лавиринта?
82 double clearDistance = 1.2;
83 return sonars.getMeasurement(0) > clearDistance
84 && sonars.getMeasurement(1) > clearDistance
85 && sonars.getMeasurement(3) > clearDistance
86 && sonars.getMeasurement(2) > clearDistance;
87 }
88
89 public Velocities act() {
90 // заустављање
91 return new Velocities(0.0, 0.0);
92 }
Tremauksov algoritam
urediTremauksov algoritam predstavlja efikasan metod pronalaženja izlaska iz lavirinta koji zahteva obeležavanje staze kojom osoba prolazi. Ovim algoritmom je garantovano pronalaženje izlaza za sve lavirinte koji imaju dobro definisane putanje. Svaka od putanja je ili još uvek ne posećena ili je označena jednom ili je označena dva puta.[2]
Na ulazu odabira se nasumično smer kojim se krećemo (ukoliko postoji više smerova od jednog). Krećemo se odabranim smerom sve do ne dođemo do prve raskrsnice ili do ćorsokaka. Putanju koju smo prešli obeležavamo jednom. Ako smo naišli na raskrsnicu na kojoj postoji više od jednog puta koji su još uvek neobeleženi, ponovo nasumično odabiramo put kojim nastavljamo dalje i njega obeležavamo. Ukoliko na raskrsnici samo jedan put nije obeležen nastavljamo tim putem i njega obeležavamo. Ukoliko naiđemo na ćorsokak vraćamo se nazad do prve raskrsnice i put obeležavamo po drugi put. Ukoliko, kada se vratimo na raskrsnicu nema više neobeleženih puteva nijednom, tada se dalje vraćamo nekim od puteva koji smo prošli jednom i taj put obeležavamo po drugi put. Svi putevi obeleženi dva puta se dalje ne razmatraju. Daljim proverama na osnovu prethodno navedenih pravila garantovano je da ćemo doći do izlaza iz lavirinta, a putanja koja nas vodi od izlaza nazad do ulaza biće ona putanja koja je obeležena jednom. Ukoliko ne postoji izlaz iz lavirinta, ovim metodom vratićemo se ponovo na ulaz nakon što obeležimo sve putanje po dva puta, po jednom u svakom smeru.
Primetimo da je ovo jedna od varijanti algoritma pretrage u dubinu.
Java kod Tremauksovog algoritma za pokretanje robota
uredi
1 package maze.ai;
2
3 import java.awt.Dimension;
4 import java.util.ArrayList;
5 import java.util.List;
6
7 import maze.model.Direction;
8 import maze.model.MazeCell;
9
10 /**
11 * Maze solving algorithm that provides a right wall follower with a memory so
12 * it prefers unexplored cells.
13 */
14 public class Tremaux extends RobotBase
15 {
16 private Direction[][] ballOfString;
17 private List<RobotStep> moveQueue = new ArrayList<RobotStep>();
18 private boolean turbo = false;
19
20 /**
21 * This returns the name of the mathematician who came up with this process
22 */
23 @Override
24 public String toString()
25 {
26 return "Tremaux";
27 }
28
29 /**
30 * This function should be called by the controller any time a new run is to
31 * commence
32 */
33 @Override
34 public void initialize()
35 {
36 super.initialize();
37
38 Dimension size = robotLocation.getMazeSize();
39 ballOfString = new Direction[(int) size.getWidth()][(int) size.getHeight()];
40
41 for (int i = 0; i < size.getWidth(); i++)
42 {
43 for (int j = 0; j < size.getHeight(); j++)
44 {
45 ballOfString[i][j] = null;
46 }
47 }
48 ballOfString[0][size.height - 1] = Direction.North;
49 this.moveQueue.clear();
50 }
51
52 /**
53 * This returns the state of the turbo flag. Turbo should be true when
54 * traversing previously explored territories.
55 */
56 public boolean isInTurboMode()
57 {
58 return turbo;
59 }
60
61 /**
62 * This returns the next step for the robot to take. It should be called by
63 * the controller.
64 */
65 public RobotStep nextStep()
66 {
67 RobotStep next;
68 if (getDirection(robotLocation.getCurrentLocation()) == null)
69 {
70 setDirection();
71 }
72 if (moveQueue.isEmpty() == true)
73 {
74 if ( (robotLocation.isWallRight() == false) && (getRightNeighborDirection() == null))
75 {
76 next = RobotStep.RotateRight;
77 moveQueue.add(RobotStep.MoveForward);
78 turbo = false;
79 }
80 else if ( (robotLocation.isWallFront() == false) && (getFrontNeighborDirection() == null))
81 {
82 next = RobotStep.MoveForward;
83 turbo = false;
84 }
85 else if ( (robotLocation.isWallLeft() == false) && (getLeftNeighborDirection() == null))
86 {
87 next = RobotStep.RotateLeft;
88 moveQueue.add(RobotStep.MoveForward);
89 turbo = false;
90 }
91 else
92 //Retrace the steps
93 {
94 turbo = true;
95 if (robotLocation.getDirection() == getDirection(robotLocation.getCurrentLocation()))
96 {
97 next = RobotStep.MoveForward;
98 }
99 else if (robotLocation.getDirection().getLeft() == getDirection(robotLocation.getCurrentLocation()))
100 {
101 next = RobotStep.RotateLeft;
102 moveQueue.add(RobotStep.MoveForward);
103 }
104 else if (robotLocation.getDirection().getRight() == getDirection(robotLocation.getCurrentLocation()))
105 {
106 next = RobotStep.RotateRight;
107 moveQueue.add(RobotStep.MoveForward);
108 }
109 else
110 {
111 next = RobotStep.RotateRight;
112 moveQueue.add(RobotStep.RotateRight);
113 moveQueue.add(RobotStep.MoveForward);
114 }
115 }
116 }
117 else
118 {
119 next = moveQueue.get(0);
120 moveQueue.remove(0);
121 }
122 return next;
123 }
124
125 /**
126 * This returns the direction for the understanding for the neighbor to the
127 * left.
128 */
129 private Direction getLeftNeighborDirection()
130 {
131 return getNeighborDirection(robotLocation.getDirection().getLeft());
132 }
133
134 /**
135 * This returns the direction for the understanding for the neighbor to the
136 * front.
137 */
138 private Direction getFrontNeighborDirection()
139 {
140 if (robotLocation.getCurrentLocation().getY() == 1)
141 {
142 return null;
143 }
144 return getNeighborDirection(robotLocation.getDirection());
145 }
146
147 /**
148 * This returns the direction for the understanding for the neighbor to the
149 * right.
150 */
151 private Direction getRightNeighborDirection()
152 {
153 return getNeighborDirection(robotLocation.getDirection().getRight());
154 }
155
156 /**
157 * This returns the direction for the understanding for the neighbor to the
158 * direction given from the current cell.
159 */
160 private Direction getNeighborDirection(Direction direction)
161 {
162 MazeCell here = robotLocation.getCurrentLocation();
163 MazeCell there;
164 Dimension size = robotLocation.getMazeSize();
165 if ( (direction == Direction.North) && (here.getY() != 1))
166 {
167 there = new MazeCell(here.getX(), here.getY() - 1);
168 }
169 else if ( (direction == Direction.South) && (here.getY() != size.getHeight()))
170 {
171 there = new MazeCell(here.getX(), here.getY() + 1);
172 }
173 else if ( (direction == Direction.East) && (here.getX() != size.getWidth()))
174 {
175 there = new MazeCell(here.getX() + 1, here.getY());
176 }
177 else if ( (direction == Direction.West) && (here.getX() != 1))
178 {
179 there = new MazeCell(here.getX() - 1, here.getY());
180 }
181 else
182 {
183 return null;
184 }
185 return getDirection(there);
186 }
187
188
189 /**
190 * This sets the direction for the understanding for the current cell.
191 */
192 private void setDirection()
193 {
194 Direction wayBack = robotLocation.getDirection().getOpposite();
195 MazeCell here = robotLocation.getCurrentLocation();
196 ballOfString[here.getX() - 1][here.getY() - 1] = wayBack;
197 }
198
199 /**
200 * This returns the direction for the understanding for the given cell
201 */
202 private Direction getDirection(MazeCell currentLocation)
203 {
204 return ballOfString[currentLocation.getX() - 1][currentLocation.getY() - 1];
205 }
206
207 /**
208 * This returns the understanding of the maze. Tremaux's understanding is the
209 * directions needed to return to the start.
210 */
211 public Direction[][] getUnderstandingDir()
212 {
213 return ballOfString;
214 }
215}
Algoritam ispunjavanja ćorsokaka
urediAlgoritam ispunjavanja ćorsokaka je još jedan od algoritama za pronalaženje izlaza iz lavirinta koji ispunjava sve putanje koje ne vode ka izlazu i ostavlja neispunjenu samo putanju koja vodi do cilja. Može se koristiti kako za rešavanje lavirinta na papiru, tako i za rešavanje lavirinta pomoću programa na računaru, ali ne može se koristiti ukoliko se osoba nalazi u samom lavirintu. Tada nije poznata celokupna struktura lavirinta, a da bi ovaj metod radio potrebno je poznavanje čitave strukture lavirinta na samom startu.
Ovaj algoritam funkcioniše na sledeći način:[3]
1 pronaći sve ćorsokake u lavirintu.
2 „ispuniti“ putanju od svakog od ćorsokaka do prve raskrsnice.
Ovaj algoritam ne može prekinuti putanju od ulaza do izlaza iz lavirinta jer svaki korak u algoritmu očuva topologiju lavirinta. Dalje, ovaj metod se neće završiti ni prerano jer završni rezultat ne sadrži ćorsokake.
Stoga, ako je ispunjavanje ćorsokaka urađeno na savršenom lavirintu (lavirintu bez petlji), jedina putanja koja preostane biće rešenje. Ukoliko se primeni na lavirint koji ima petlje, svako moguće rešenje će ostati kao rezultat i ništa više.
Algoritam najkraćeg puta
urediKada lavirint ima više rešenja, možda želimo da pronađemo ono rešenje koje nam daje najkraći put od početka do kraja. Jedan od mogućih algporitama pronalazi najkraću putanju implementirajući algoritam pretrage u dubinu, dok drugi, A* algoritam, koristi heuristike. Algoritam pretrage u dubinu koristi redove kako bi se posetile putanje u redosledu koji podrazumeva uvećanje udaljenosti od početka sve dok se ne dođe do kraja. Svaka posećena putanja čuva podatak o udaljenosti od početka. Kada se pronađe lpkacija kraja, prati se putanja unazad do početka, što predstavlja najkraću putanju.
Vidi takođe
urediReference
uredi- ^ Promena lavirinta u kružnicu na sajtu YouTube
- ^ Tremauksov algoritam na sajtu YouTube
- ^ Algoritam ispunjavanja ćorsokaka na sajtu YouTube