Нашли сте се у ћорсокаку и не видите излаз? НЕ ОЧАЈАВАЈТЕ! Ево како ЈЕДНИМ ПОТЕЗОМ можете изаћи из лавиринта!
Лавиринт је грађевина у Кнососу, на острву Криту.
По легенди то је био дворац краља Миноса. По легенди у лавиринту је био затворен Минотаур. Лавиринт је био срушен око 1700. године п. н. е.
Међутим, питање које многи постављају јесте да ли постоји метод за излажење из лавиринта?
МОЗГАЛИЦА КОЈА ЈЕ ЗАЛУДЕЛА СВЕТ: Можете ли да нађете излаз из лавиринта? (ФОТО)
Милан из Београда одвео дете код лекара због крпеља: Након интервенције добио је ОГРОМАН РАЧУН (ФОТО)
Дете у прегрејаном ауту, а посебно ако је ове боје, може доживети топлотни удар за само сат времена!
Алгоритам праћења зида, представља један од најпознатијих алгоритама за проналажење излаза из лавиринта, а такође је познат и под називима "правило леве руке" и "правило десне руке".
Уколико је лавиринт повезан, односно ако су сви његови зидови међусобно спојени или ако су спојени са спољашњом границом лавиринта, тада ако особа унутар лавиринта држи руку у контакту са зидом током целог проласка кроз лавиринт гарантовано долази до излаза из лавиринта ако излаз уопште и постоји, у супротном особа би се вратила на улаз у лавиринт и притом би обишла сваку путању у лавиринту барем једанпут.
Ако овај проблем погледамо с друге, тополошке, стране примећује се зашто је алгоритам праћења зида у могућности да увек пронађе право решење.
Ако су зидови повезани, то значи да се могу раширити у кружницу. Тако се алгоритам праћења зида редукује на пролазак ивицама те кружнице од улаза до излаза.
ПУТИН НАМ ВРАЋА ДРАГОЦЕНОСТ: Страница Јеванђеља стиже 20. октобра, а ево шта ће Србија поклонити њима као знак захвалности
ОВАЈ АПАРАТ ЈЕ НАЈОПАСНИЈИ КАД ГРМИ, А НИЈЕ МОБИЛНИ ТЕЛЕФОН: Када је невреме, МОЖЕ ВАС УБИТИ!
РОДИТЕЉИ, БУДИТЕ ОПРЕЗНИ Ово је једна потенцијално СМРТОНОСНА ГРЕШКА када су у питању ваша ДЕЦА!
Уколико лавиринт није повезан (нпр. ако су улаз у лавиринт или излази из њега у центру самог лавиринта или путање прелазе једна преко друге или једна испод друге), није гарантовано да ће овај алгоритам заиста у таквим случајевима пронаћи излаз из лавиринта.
Алгоритам праћења зидова може се користити и у тродимензионалним и вишедимензионалним окружењима уколико те вишедимензионе путање могу бити пројектоване у дводимензионалној равни на детерминистички начин.
На пример, уколико у тродименѕионалном алгоритму путање на "горе" сматрамо путањама ка северо-западу, а путање на „доле“ сматрамо путањама ка југо-истоку, тада можемо употребити стандардна правила алгоритма праћења зида. Међутим, за разлику од дводимензионалног простора, овде је потребно у сваком моменту знати и тренутну оријентацију, да би се знало који смер је први налево или надесно..
Међутим, уколико се улаз налази у унаутрашњости лавиринта, може се наћи на зиду који није спојан са зидом на коме се налази излаз, па би се коришћењем алгоритма праћења зидова особа вртела у круг и враћала на почетак не проналазећи излаз. Алгоритам Џона Плеџа може да реши овај проблем.
Плеџов алгоритам, дизајниран да заобиђе препреке, захтева кретање у напред одређеном смеру.
Када се наиђе на препреку, једна рука (нпр. десна) наставља да прати препреку а такође прати се и број окрета на леву и десну страну коришћењем бројача окрета. Окретање на десну страну повећава вредност бројача, а окрет на леву страну смањује његову тренутну вредност. Када се особа поново окрене ка оригиналном унапред одређеном смеру, тада је бројач окрета поново враћен на вредност 0 и препрека је успешно савладана, особа наставља са кретањем у почетном оригиналном смеру ка свом циљу па ако се поново наиђе на препреку претходни поступак се понавља. Рука више не прати зид само када је бројач окрета поново постављен на 0. Овакав приступ омогућава алгоритму да избегне замке које су на пример облика великог латиничног слова Г - ("Г").
У суштини алгоритам је врло једноставан и састоји се од провере неколико правила која се проверавају током проласка кроз лавиринт:
(алгоритам заснован на правилу десне руке)
1. Особа се креће унапред одређеним смером.
2. Када се наиђе на препреку први пут особа се окреће на леву страну. Бројач окрета се тада умањује за 1.
3. Врши се провера постојања препрека. Особа проверава да ли постоји препрека испред, десно или лево.
Уколико нема препреке на десној страни особа се окреће на десну страну. Бројач окрета се увећава за 1.
Уколико постоји препрека на десној страни, а не постоји препрека испред, особа се помера унапред за један корак. Бројач окрета не мења своју тренутну вредност.
Уколико постоји препрека на десној страни и постоји препрека испред, особа се окреће на леву страну. Бројач окрета се тада умањује за 1.
Претходни подкораци корака 3 се наведеним редоследом проверавају све док се бројач окрета поново не врати на вредност 0 и тада сматрамо да је препрека успешно савладана.
4. Особа наставља да се креће почетним смером, све док се поново не наиђе на препреку или се стигне до излаза.
Алгоритам заснован на правилу леве руке може се аналогно извести из претходног.
На овај начин алгоритам омогућава особи која уме да проверава постојање препрека испред, лево и десно, успешно проналажење излаза на спољашњем зиду из било ког дводимензионалног лавиринта, независно од почетне позиције особе у лавиринту. Међутим овај алгоритам не пружа могућност решавања супротног проблема претходном проблему. Алгоритам неће радити ако се улаз налази на спољашњем зиду лавиринта, а неки циљ у унутрашњости лавиринта.
