Алгоритам за решавање лавиринта

Постоји неколико различитих варијанти алгоритама за решавање лавиринта, који представљају аутоматизоване методе за решавање било ког лавиринта.

Насумични алгоритам миша, алгоритам праћења зида, алгоритам Џона Плеџа (ен. 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 „испунити“ путању од сваког од ћорсокака до прве раскрснице.

Овај алгоритам не може прекинути путању од улаза до излаза из лавиринта јер сваки корак у алгоритму очува топологију лавиринта. Даље, овај метод се неће завршити ни прерано јер завршни резултат не садржи ћорсокаке.

Стога, ако је испуњавање ћорсокака урађено на савршеном лавиринту (лавиринту без петљи), једина путања која преостане биће решење. Уколико се примени на лавиринт који има петље, свако могуће решење ће остати као резултат и ништа више.

Алгоритам најкраћег пута[уреди | уреди извор]

Када лавиринт има више решења, можда желимо да пронађемо оно решење које нам даје најкраћи пут од почетка до краја. Један од могућих алгпоритама проналази најкраћу путању имплементирајући алгоритам претраге у дубину, док други, А* алгоритам, користи хеуристике. Алгоритам претраге у дубину користи редове како би се посетиле путање у редоследу који подразумева увећање удаљености од почетка све док се не дође до краја. Свака посећена путања чува податак о удаљености од почетка. Када се пронађе лпкација краја, прати се путања уназад до почетка, што представља најкраћу путању.