Търсене по широчина и неговите приложения

Във въведителния урок ние си поиграхме с герой, който се придвижва през лабиринт, за да достигне до някаква цел. Започнахме, като казахме, че целта е на нула стъпки от самата себе си. След това намерихме всички квадратчета, които бяха на една стъпка разстояние от целта. След това всички квадратчета на 2 стъпки от целта. След това три стъпки и т. н., докато не достигнем до квадратчето, откъдето започва нашия герой. Ако следим от кое квадратче на разстояние $k$‍ сме дошли, за да стигнем до квадратче на разстояние $k+1$‍, можем да намерим маршрут от героя до целта.

Ето картинката, която видяхме във въвеждащия урок:

Сега можем да видим, че това е ненасочен граф. Всеки връх отговаря на квадратче, което не е част от стената, и всяко ребро свързва два съседни квадрата.

Пътят намерен чрез метода, описан по-горе, има едно много важно свойство: няма друг маршрут от героя до целта, който минава през по-малко квадратчета. Това е така, защото за да го намерим използвахме алгоритъм, известен като Обхождане в ширина. Обхождането в ширина, още известно като БФС (BFS), намира най-късия път от даден начален връх до всички останали върхове, от гледна точка на броя върхове върху пътищата.

Ето още един пример за обхождане в ширина: играта "шестте степени на Kevin Bacon". В нея играчите се опитват да свържат филмови актьори и актриси с Кевин Бейкън с верига от хора, които са участвали заедно във филм. Колкото по-къса е веригата, толкова по-добре, и е поразително колко много актьори и актриси могат да стигнат до Кевин Бейкън с верига от шест или по-малко човека. Да вземем за пример Кейт Бел, австралийска актриса. Тя участва в MacBeth с Наш Едгъртън през 2006 г.; Едгъртън участва в The Matrix Reloaded с Лорънс Фишбърн през 2003 г.; а Фишбърн участва заедно с Кевин Бейкън в Mystic River през 2003 г. Следователно "номерът на Кевин Бейкън" на Кейт Бел е 3. Всъщност има няколко начина да се намери, че това число е 3. Може да потърсиш аналогичните такива числа за всеки актьор и актриса в сайта на Оракула на Бейкън.

Както най-вероятно отгатна, сайтът поддържа неориентиран граф, в който всеки връх съответства на актьор или актриса, и ако двама човека са участвали заедно във филм, то те са свързани с ребро. Обхождането в ширина от върха на Кевин Бейкън намира най-кратката последователност от хора до всеки актьор или актриса.

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.