Ені бойынша іздеу және оның қолдануы

Кіріспе нұсқаулығында, сіз мақсатқа жету үшін кейіпкердің лабиринт бойымен қозғалуын қамтамасыз етесіз. Сіз мақсат өз-өзінен нөл қадамда деп айтудан бастадыңыз. Содан кейін сіз мақсаттан бір қадам қашықтықта болған барлық квадраттарды таптыңыз. Содан кейін барлық квадраттар мақсаттан екі қадам қашықтықта. Содан кейін үш қадам қашықтықта және тағы да солай кете береді, сіздің кейіпкеріңіз басталған алаңға жеткенінше. Егер сіз $k+1$‍ қашықтықтағы квадратқа жеткіңіз келсе $k$‍ қашықтықта қай шаршыдан келгенін қадағалап, кейіпкердің мақсатқа дейінгі жолын таба аласыз

Міне, біз кіріспе нұсқаулығында көрген суретіміз:

Енді сіз оны бағдарланбаған граф ретінде тани аласыз. Әр шың қабырғаның бөлігі болып табылмайтын шаршыға сәйкес келеді және әр шеті көрші квадраттарға түседі.

Жоғарыда сипатталған процедураның көмегімен табылған жол маңызды қасиетке ие: сипаттан мақсатқа дейінгі басқа маршрут аз квадраттардан өтпейді. Себебі біз оны табу үшін ені бойынша іздеу деп аталатын алгоритмді қолдандық. Ені бойынша іздеу, сонымен қатар BFS деп аталады, берілген бастапқы шыңнан жолдардағы жиектер саны бойынша барлық басқа шыңдарға дейінгі ең қысқа жолды табады.

Ені бойынша іздеуге тағы бір мысал: "Кевин Бэконның алты дәрежесі" ойыны. Мұнда ойыншылар кинорежиссерлер мен актрисаларды Кевин Бэконмен фильмде кіммен бірге ойнайтындардың тізбегіне сәйкес байланыстыруға тырысады. Тізбек неғұрлым қысқа болса, соғұрлым жақсы және таңқаларлық, алты немесе одан да аз адам тізбегіндегі Кевин Бэконға қанша актер мен актриса жете алады. Мысал ретінде австралиялық актриса Кейт Беллді алайық. Ол 2006 жылы Нэш Эдгертонмен бірге Макбетте болды; Эдгертон 2003 жылы Лоуренс Фишбернмен бірге Жүктелген матрицада болды; және Фишберн 2003 жылы Кевин Бэконмен бірге Мистик Риверде болды. Сондықтан Кейт Беллдің "Кевин Бэконның саны" 3құрайды. Кевин Бэкон Кейт Беллдің саны 3екенін білудің бірнеше жолы бар. Кевин Бэконның кез-келген актердің немесе актрисаның нөмірін Bacon Oracle веб-сайтынан көре аласыз.

Сіз болжағандай, Bacon Oracle веб-сайты әр шыңы актерге немесе актрисаға сәйкес келетін бағдарланбаған графты қолдайды, егер бір фильмде екі адам ойнаған болса, онда олардың шыңдарында оқиға болады. Ені бойынша іздеу алгоритімі алдымен Кевин Бэконді іздеу үшін барлық басқа актерлер мен актрисалардан ең қысқа тізбегін табады.

Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.