Алгоритам за решавање лавиринта
 | Овај чланак можда захтева чишћење и/или прерађивање како би се задовољили стандарди квалитета Википедије. Проблем: Унос унутрашњих веза и референци. (децембар 2016) |
Постоји неколико различитих варијанти алгоритама за решавање лавиринта, који представљају аутоматизоване методе за решавање било ког лавиринта.
Насумични алгоритам миша, алгоритам праћења зида, алгоритам Џона Плеџа (ен. Jon Pledge) и Тремауксов (фр. Charles Pierre Trémaux) алгоритам су дизајнирани тако да се користе када се особа налази унутар самог лавиринта без икаквог познавања структуре и изгледа самог лавиринта, док су алгоритам испуњавања ћорсокака и алгритам најкраћег пута дизајнирани тако да се користи када особа или рачунарски програм унапред познаје структуру и изглед читавог лавиринта.
Лавиринти који не садрже петље познати су као *стандардни* или *савршени* лавиринти, и као такви еквивалентни су стаблима у теорији графова преко којих се могу и представљати. Према томе већина алгоритама за решавање лавиринта се ослањају на теорију графова.
Интуитивно, ако би се сви путеви у лавиринту исправно издвојили, као резултат могли би добити нешто што добро подсећа на структуру стабла.
Насумични алгоритам миша
[уреди | уреди извор]Ово је тривијални алгоритам који може бити искоришћен код веома неинтелигентних робота или на мишеве. Алгоритам се састоји од праћења путање којом се крећемо све док не дођемо до раскрснице са више могућности скретања, тада насумишно одабирамо коју ћемо путању надаље следити. Иако ће овакав алгоритам на крају увек пронаћи право решење, овај алгоритам може бити и екстремно спор. Разлог за то је што се путање које смо већ једном прошли не елиминишу из поновног разматрања када се на њих поново наиђе.
Алгоритам праћења зида
[уреди | уреди извор]
Алгоритам праћења зида, представља један од најпознатијих алгоритама за проналажење излаза из лавиринта, а такође је познат и под називима „правило леве руке“ и „правило десне руке“.
Уколико је лавиринт повезан, односно ако су сви његови зидови међусобно спојени или ако су спојени са спољашњом границом лавиринта, тада ако особа унутар лавиринта држи руку у контакту са зидом током целог проласка кроз лавиринт гарантовано долази до излаза из лавиринта ако излаз уопште и постоји, у супротном особа би се вратила на улаз у лавиринт и притом би обишла сваку путању у лавиринту барем једанпут.
Ако овај проблем погледамо с друге, тополошке, стране примећује се зашто је алгоритам праћења зида у могућности да увек пронађе право решење. Ако су зидови повезани, то значи да се могу раширити у кружницу.[1] Тако се алгоритам праћења зида редукује на пролазак ивицама те кружнице од улаза до излаза.
Уколико лавиринт није повезан (нпр. ако су улаз у лавиринт или излази из њега у центру самог лавиринта или путање прелазе једна преко друге или једна испод друге), није гарантовано да ће овај алгоритам заиста у таквим случајевима пронаћи излаз из лавиринта.
Алгоритам праћења зидова може се користити и у тродимензионалним и вишедимензионалним окружењима уколико те вишедимензионе путање могу бити пројектоване у дводимензионалној равни на детерминистички начин.
На пример, уколико у тродименѕионалном алгоритму путање „нагоре“ сматрамо путањама ка северо-западу, а путање „надоле“ сматрамо путањама ка југо-истоку, тада можемо употребити стандардна правила алгоритма праћења зида. Међутим, за разлику од дводимензионалног простора, овде је потребно у сваком моменту знати и тренутну оријентацију, да би се знало који смер је први налево или надесно..
Алгоритам Џона Плеџа
[уреди | уреди извор]Неповезани алгоритми се ипак на одређене начине могу решити коришћењем алгоритма праћења зида, уколико се улаз и излази из лавиринта налазе на спољашњим зидовима лавиринта. Међутим, уколико се улаз налази у унаутрашњости лавиринта, може се наћи на зиду који није спојан са зидом на коме се налази излаз, па би се коришћењем алгоритма праћења зидова особа вртела у круг и враћала на почетак не проналазећи излаз. Алгоритам Џона Плеџа може да реши овај проблем.
Плеџов алгоритам, дизајниран да заобиђе препреке, захтева кретање у унапред одређеном смеру.
Када се наиђе на препреку, једна рука (нпр. десна) наставља да прати препреку а такође прати се и број окрета на леву и десну страну коришћењем бројача окрета. Окретање на десну страну повећава вредност бројача, а окрет на леву страну смањује његову тренутну вредност. Када се особа поново окрене ка оригиналном унапред одређеном смеру, тада је бројач окрета поново враћен на вредност 0 и препрека је успешно савладана, особа наставља са кретањем у почетном оригиналном смеру ка свом циљу па ако се поново наиђе на препреку претходни поступак се понавља. Рука више не прати зид само када је бројач окрета поново постављен на 0. Овакав приступ омогућава алгоритму да избегне замке које су на пример облика великог латиничног слова Г - ("G").
У суштини алгоритам је врло једноставан и састоји се од провере неколико правила која се проверавају током проласка кроз лавиринт:
(алгоритам заснован на правилу десне руке)
1. Особа се креће унапред одређеним смером.
2. Када се наиђе на препреку први пут особа се окреће на леву страну. Бројач окрета се тада умањује за 1.
3. Врши се провера постојања препрека. Особа проверава да ли постоји препрека испред, десно или лево.
- Уколико нема препреке на десној страни особа се окреће на десну страну. Бројач окрета се увећава за 1.
- Уколико постоји препрека на десној страни, а не постоји препрека испред, особа се помера унапред за један корак. Бројач окрета не мења своју тренутну вредност.
- Уколико постоји препрека на десној страни и постоји препрека испред, особа се окреће на леву страну. Бројач окрета се тада умањује за 1.
Претходни подкораци корака 3 се наведеним редоследом проверавају све док се бројач окрета поново не врати на вредност 0 и тада сматрамо да је препрека успешно савладана.
4. Особа наставља да се креће почетним смером, све док се поново не наиђе на препреку или се стигне до излаза.
Алгоритам заснован на правилу леве руке може се аналогно извести из претходног.
На овај начин алгоритам омогућава особи која уме да проверава постојање препрека испред, лево и десно, успешно проналажење излаза на спољашњем зиду из било ког дводимензионалног лавиринта, независно од почетне позиције особе у лавиринту. Међутим овај алгоритам не пружа могућност решавања супротног проблема претходном проблему. Алгоритам неће радити ако се улаз налази на спољашњем зиду лавиринта, а неки циљ у унутрашњости лавиринта.
Јава код алгоритма Џона Плеџа заснованог на правилу леве руке за покретање робота
[уреди | уреди извор]
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 }
Тремауксов алгоритам
[уреди | уреди извор]Тремауксов алгоритам представља ефикасан метод проналажења изласка из лавиринта који захтева обележавање стазе којом особа пролази. Овим алгоритмом је гарантовано проналажење излаза за све лавиринте који имају добро дефинисане путање. Свака од путања је или још увек не посећена или је означена једном или је означена два пута.[2]
На улазу одабира се насумично смер којим се крећемо (уколико постоји више смерова од једног). Крећемо се одабраним смером све до не дођемо до прве раскрснице или до ћорсокака. Путању коју смо прешли обележавамо једном. Ако смо наишли на раскрсницу на којој постоји више од једног пута који су још увек необележени, поново насумично одабирамо пут којим настављамо даље и њега обележавамо. Уколико на раскрсници само један пут није обележен настављамо тим путем и њега обележавамо. Уколико наиђемо на ћорсокак враћамо се назад до прве раскрснице и пут обележавамо по други пут. Уколико, када се вратимо на раскрсницу нема више необележених путева ниједном, тада се даље враћамо неким од путева који смо прошли једном и тај пут обележавамо по други пут. Сви путеви обележени два пута се даље не разматрају. Даљим проверама на основу претходно наведених правила гарантовано је да ћемо доћи до излаза из лавиринта, а путања која нас води од излаза назад до улаза биће она путања која је обележена једном. Уколико не постоји излаз из лавиринта, овим методом вратићемо се поново на улаз након што обележимо све путање по два пута, по једном у сваком смеру.
Приметимо да је ово једна од варијанти алгоритма претраге у дубину.
Јава код Тремауксовог алгоритма за покретање робота
[уреди | уреди извор]
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}
Алгоритам испуњавања ћорсокака
[уреди | уреди извор]Алгоритам испуњавања ћорсокака је још један од алгоритама за проналажење излаза из лавиринта који испуњава све путање које не воде ка излазу и оставља неиспуњену само путању која води до циља. Може се користити како за решавање лавиринта на папиру, тако и за решавање лавиринта помоћу програма на рачунару, али не може се користити уколико се особа налази у самом лавиринту. Тада није позната целокупна структура лавиринта, а да би овај метод радио потребно је познавање читаве структуре лавиринта на самом старту.
Овај алгоритам функционише на следећи начин:[3]
1 пронаћи све ћорсокаке у лавиринту.
2 „испунити“ путању од сваког од ћорсокака до прве раскрснице.
Овај алгоритам не може прекинути путању од улаза до излаза из лавиринта јер сваки корак у алгоритму очува топологију лавиринта. Даље, овај метод се неће завршити ни прерано јер завршни резултат не садржи ћорсокаке.
Стога, ако је испуњавање ћорсокака урађено на савршеном лавиринту (лавиринту без петљи), једина путања која преостане биће решење. Уколико се примени на лавиринт који има петље, свако могуће решење ће остати као резултат и ништа више.
Алгоритам најкраћег пута
[уреди | уреди извор]Када лавиринт има више решења, можда желимо да пронађемо оно решење које нам даје најкраћи пут од почетка до краја. Један од могућих алгпоритама проналази најкраћу путању имплементирајући алгоритам претраге у дубину, док други, А* алгоритам, користи хеуристике. Алгоритам претраге у дубину користи редове како би се посетиле путање у редоследу који подразумева увећање удаљености од почетка све док се не дође до краја. Свака посећена путања чува податак о удаљености од почетка. Када се пронађе лпкација краја, прати се путања уназад до почетка, што представља најкраћу путању.
Види такође
[уреди | уреди извор]Референце
[уреди | уреди извор]- ^ Промена лавиринта у кружницу на сајту YouTube
- ^ Тремауксов алгоритам на сајту YouTube
- ^ Алгоритам испуњавања ћорсокака на сајту YouTube