Основно съдържание
Компютърни науки
Намиране на маршрут
Понякога задачи, които изглеждат много различни, се оказват подобни, след като помислиш как да ги решиш. Какво е общото между играта Pac-Man, кралското семейство на Великобритания и шофирането до Орландо? Всички те включват задачи за намиране на маршрут или търсене на пътека:
- Как са свързани настоящият принц Уилям с крал Уилям III, който финансира Колежа на Уилям и Мети през 1693г?
- Какъв път трябва да следва едно духче, за да настигне Pac-Man възможно най-бързо?
- Какъв е най-добрият начин да стигнем от Далас, Тексас до Орландо, Флорида?
За да отговорим на тези въпроси, ни трябва някаква информация.
Например едно родословно дърво на кралското семейство на Великобритания би показало връзките между хората, които са пряко свързани. Принц Уилям е син на Чарлз Филип Артър Уиндзор. Чарлз е син на кралица Елизабет II. Задачата е да намерим кратка верига в родословното дърво, която да свързва принц Уилям и Уилям III, като използваме тези преки връзки. Както можеш да видиш на дървото по-долу, това може да стане с немалко връзки.
За Пак Ман ни трябва карта на лабиринта. Тази карта показва връзките между близки празни квадрати от лабиринта – или липса на връзки, ако между квадратите има стена – а задачата е да открием път по черните квадрати, който да отведе духчето до Pac-Man.
За да намерим маршрута от Далас до Орландо, можем да използваме карта на САЩ, която да показва връзките, или пътищата, между близките градове. Няма път, който да свързва директно Далас и Орландо, но има няколко поредици от пътища.
Проучване на лабиринт
Игрите с лабиринти са забавни, така че нека разучим една такава в дълбочина. В нашата игра главният герой може да се движи до различни местополижения в лабиринта.
Като играч, ти можеш да контролираш главния герой, като кликваш върху следващото местоположение в лабиринта, след което компютърът ще открие начин, по който да придвижи героя дотам. Местоположението се отбелязва с червен правоъгълник, съдържащ думата "GOAL" и героят започва от първото си местоположение – стартовото квадратче. Поиграй си:
Забеляза ли как героят се премести към целта? За да направи това, програмата трябва да определи точен набор от движения, които героят трябва да изпълни, за да отиде там, където е кликнал потребителят, а след това да анимира тези движения. Може да има няколко пътя, по които да се придвижи героят и програмата трябва да избере най-добрият от тях.
Преди да се избере алгоритъм, трябва да се установят правила за движението: стените са направени от сиви квадратчета, а позволените местоположения са празни. Във всяка стъпка героят може да се придвижи от едно квадратче в неговото съседно квадратче. Този герой, подобно на топа в шаха, не може да се движи по диагонал.
Ето и идеята на алгоритъма, който програмата използва: премести се 1 стъпка по-близо до целта – мястото, на което е кликнал потребителят – с всяка стъпка. Но какво означава "по-близко до целта"? Ако се движението в права линия по посока на целта, героят често ще се сблъсква със стена. Алгоритъмът трябва да определя кой от заобикалящите квадрати наистина е "по-близо до целта", а ние можем да направим това, като зададем "стойност" на всеки квадрат, която да отразява най-малкият брой стъпки, които героят трябва да направи, за да достигне от този връх до целта. Ето един алгоритъм за задаване на стойност на всеки квадрат:
- Започваме от квадрата на целта. Колко далеч е целта от целта? Нула стъпки, отбелязваме целта с числото 0.
- Намираме всички квадрати, които имат точно една стъпка до целта. Отбелязваме ги с числото 1. В този лабиринт, ако целта е в изходния квадрат, има само един квадрат, който да е на точно една стъпка.
- Сега намираме всички квадрати в лабиринта, които са на точно две стъпки от целта. Тези квадрати са на една стъпка от тези, които са маркирани с 1, и все още не са отбелязани. Отбелязваме тези квадрати с числото 2.
- Маркираме всички квадрати в лабиринта, които са на точно три стъпки от целта. Тези квадрати са на 1 стъпка от квадратите, маркирани с 2, и все още не са отбелязани. Маркираме тези квадрати с числото 3.
- Продължаваме да маркираме квадратите в лабиинта по възходящ ред на разстоянието им от целта. След като маркираме с числото k, маркираме с числото k, plus, 1 всички квадрати, които са на една стъпка от тези, маркирани с k, и все още не са били маркирани.
Накрая алгоритъмът маркира квадрата, от който тръгва героят. Тогава програмата може да намери пътя до целта, като избере последователност от квадрати от началото, такива, че стойностите на квадратите да намаляват. Ако си представиш, че числото е височината на квадрата, това ще бъде спускане.
Можеш да си поиграеш с алгоритъма за маркиране на стойностите по-долу. Кликни върху "Рестартирай алгоритъма", за да започнеш отначало.
Ами ако потребителят се опитва да стигне от началното квадратче до целта? Като използваме алгоритъма за маркиране на квадрати, началният квадрат е на 13 стъпки от целта. Ето едно изображение на връзките между възможните позиции на героя, началото, целта и най-краткото разстояние до целта:
Има квадратче непосредствено на юг от старта, което е само на 12 стъпки от целта. Така че първият ход е "на юг". На юг от това квадратче стъпките стават 11. Така че пак отиваме на юг. Още веднъж на юг и стъпките са 10. След това правим ход на изток; остават 9 стъпки. Още два хода на изток и стъпките стават 7. След това 5 стъпки на север и стигаме до 2. Накрая отиваме веднъж на запад и ни остава 1 стъпка, която правим на север – към целта.
В момента няма да обясняваме точно как се имплементира този алгоритъм за търсене в лабиринта, но ти можеш да се позабавляваш, като помислиш как можеш да представиш лабиринта и героя в JavaScript и как да имплементираш алгоритъма.
Това съдържание е резултат от съвместната дейност на преподавателите Томас Кормен и Девин Балком от Компютърни науки Дартмут, както и компютърния екип на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.
Искаш ли да се присъединиш към разговора?
Все още няма публикации.