Програмирането... изходът от лабиринта
Може би някои от вас са гледали филма "Бегащият в лабиринта", където група тийнейджъри живеят в дефиле насред лабиринт, обитаван от чудовища? Те намират изход чрез умело използване на улики. Но има алгоритми и дори програми, способни да намерят изход от лабиринта. Ще говорим за тях.
Как да мина през лабиринта?
Защо имаме нужда от някакъв лабиринт лабиринт, ще попита читателят? И как можем да го намерим с помощта на програмата? В края на краищата, тя не вижда напусканията? И тогава в края на краищата има правилото за "лява" и "дясна" ръка, което вероятно прави възможно намирането на изход във всеки лабиринт.
Наистина програмата за изход не вижда. Но правилото "лява или дясна" ръка лесно може да не работи, ако лабиринтът има независими елементи, които не са свързани с непрекъснати стени с останалата част от системата от ходове. Тогава остава само... общ етаж за целия лабиринт, който по никакъв начин няма да ни помогне да определим правилната посока.
Освен това има изключително сложни лабиринти с изключителна сложност, които не са лесни за следване и може да отнеме много време, за да намерите пътя си през тях. Има криволичещи пътеки с много разклонения, които могат да бъдат преодолени по най-краткия път, спестявайки провизии, сила или гориво за кола (в зависимост от това, което ви подсказва въображението). И те ще се окажат много дълги, ако се движите по случаен път.
Лабиринтът може да не е лабиринт, а карта на метрото или пътна карта, която трябва да пропуснете с най-ниска цена, или серпентина от планински проломи, сред стръмните склонове на които трябва да изберете най-достъпния. С една дума, има много опции. И така, какво трябва да направим?
Вездесъщата матрица
Но пътуването е само половината от историята. В съвременната реалност най-важното е да имате под ръка най-краткия, удобен иевтин начин за ускоряване на транспортирането и победа над конкурентите. А компилирането на най-краткия път вече е задача, която може да бъде напълно решена за компютър.
Ние си представяме целия маршрут, изминат от една или друга (в зависимост от условията на задачата) машина като двуизмерна (в някои особено трудни случаи - триизмерна) матрица. Спомняте ли си научнофантастичния филм "Матрицата"? Той включваше плоска структура от много клетки, пълни с човешки тела. Нашата матрица ще съдържа клетки с данни, разположени на еднакво разстояние една от друга - по примера на обикновена географска карта в Google или Yandex.
В най-простата си форма матрицата ще бъде хоризонтално поле. Представете си шахматна дъска. Всеки квадрат ще получи подобни шахматни координати. Да кажем, че третата клетка отгоре ще бъде четвъртата в своя ред. Ако това е дефиле, тогава стойността на самата клетка може да бъде височината или стръмността на наклона. Ако има стръмни стени около пътя, тогава клетката или е проходима, или не.
Разбира се, ако нашият лабиринт има няколко нива и дори с пресичане на височини, ще е необходима триизмерна матрица, но ние няма да я разгледаме. Ако забележите, дори в съвременните игри нивата са направени независими, тоест те могат да бъдат представени и като двумерни матрици с допълнителни параметри.
Разходка през лабиринта
За съжаление самият компютър няма да види пътеките, дори ако има цифрова карта под ръка. Той трябва да предложи алгоритъм, който ще осигури ефективно търсене на път в матрица, пълна с конвенционални числа. И така, използваме най-простия алгоритъм за преминаване на лабиринта - вълновия алгоритъм. И ние ще се движим само надясно, наляво, нагоре и надолу (можете да ходите и по диагонал, но това все още няма да разгледаме).
Движението на "вълната" прилича на разминаващи се кръгове по водата или срутване, когато много камъчета падат от планината. Около началната точка, ако тя не се намира на ръба на матрицата-карта, винаги има още четири точки. Трябва да проверим дали са свободни да преминат? Инструкцията към компютъра би звучала така: „продължете направо и проверете дали клетката отпред е свободна? Ако да, тогава отидете там и го променете с един. Ако не, тогава се върнете и проверете дали клетката отзад е свободна? Ако е така, отидете там и го маркирайте с единица. Ако не, проверете дали клетката вдясно е свободна? Ако да, тогава отидете там и го маркирайте с единица. Ако не, проверете клетката отляво.
Ако има свободни клетки около точката или, в този случай, началото на нашето пътуване, те ще бъдат маркирани с „едно“. В следващата стъпка ще трябва да маркираме с "две" всички свободни клетки около клетките с "едно", разбира се, с изключение на вече маркираните. Клетките с "двойка" ще придобият собствена задача - ще маркират свободното пространство с "тройка" и т.н. Така вълната се "разпръсква" от центъра, огъвайки се около препятствията и моментално достига до финалната линия - изхода от лабиринта.
И така, как да намерим най-краткия път? Много просто. Необходимо е на всяка стъпка, започвайки да броите от финалната линия, да търсите клетки, маркирани с все по-малко число. От "деветката" търсим "осмичката", от нея - "седемката" и т.н. В 95% от случаите по този начин се намира най-краткият път. Но, за съжаление, не винаги. Ако наборът от препятствия има сложна форма, тогава "вълната" може да "цикли". Следователно програмата трябва да зададе някакво емпирично ограничение за броя на повторенията. За да може тя да ти каже например: „така майсторе, няма как“.
Вълнова реализация
На ниво софтуер вълновият алгоритъм е изграден доста просто. Ние сме лабиринтътили сканираме или обработваме съответно, получавайки матрица, чиито стойности на клетките отразяват проходимостта или запушването на нейните възли. След това въвеждаме тази матрица в програмата или я изпращаме на входа като файл.
След това създаваме три цикъла (задължително три), които заобикалят цялата матрица, генерирайки вълна. Външният контур трябва да има граница не по-малка от дължината на дългата страна на матрицата. Вътрешните цикли се изграждат както обикновено: един за броя на редовете, а вторият за броя на колоните. По принцип е възможно и обратното.
Тогава имаме нужда от някои условия. По-точно има много условия, всяко от които програмата трябва да провери. Необходимо е да се изясни какво представлява всяка една от клетките, разположени около началната точка - тупикова ли е или е свободна клетка? Или може би е клетка - завършване. Или може би начален? За простота ще маркираме само свободните клетки с „вълна“. Разбира се, необходимо е да се провери дали клетката не е крайната. И, разбира се, струва си да завършите работата на трите цикъла, когато преминете финалната линия.
Има още един важен момент - за да бъде отбелязана всяка вълна с числа във възходящ ред, ни е необходим коефициент, който трябва да бъде увеличен преди края на външния цикъл, който е "генераторът" на вълната. Ще наричаме този коефициент Ni. Факторът Nk ще бъде детерминантата на максималния брой повторения. Направихме матрицата квадратна и броят на клетките в нея ще бъде означен с променливата n. Нека наречем нашия масив лаборатория - от думата "лабиринт". Променливите, работещи във вътрешните цикли, ще бъдат обичайните i, j, във външните - l. Променливите z и k ще получат стойностите на изходната точка на лабиринта, когато цикълът приключи.
Нека приключим циклите с командата break и етикета на етикета. Както знаем, прекъсването спира само своетоцикъл. Затова ще извадим етикета за външен.
За полагане на пътя имаме масив, подобен на първия. За удобство се попълва с еднакви номера. Съответно, след края на тази част от програмата, която поставя вълната, ще работи втората - маркиране на най-краткия маршрут. Тук имаме нужда само от два цикъла, тъй като около всяка точка, в нашия случай, ще има само една точка най-близо до входа и няма да е необходимо да проверяваме всичко. След като намерим тази точка, присвояваме нейните координати на нашите променливи z и k, като по този начин се придвижваме една стъпка към изхода. Ще обозначим самата клетка с коефициента Ni, като го намаляваме с една единица за всяка итерация на външния цикъл.
Ето как изглежда тази Java програма в най-опростения за възприемане вид, без функции и методи. Ще добавя, че за удобство и разбиране го намалих до един списък и направих изхода на маршрута в отделен масив, пълен с хомогенни числа.
Кодът работи на всекикомпилатор на Java. Може да се копира и стартира. Можете да изследвате вълновия алгоритъм за преминаване на различни препятствия със сложна форма. Ако е необходимо, можете да го пренапишете вC, да го използвате в лаборатория, да създадете подходящ метод или функция или дори да напишете малка игра. Кодът е снабден с кратки обяснения на английски език.