Լայնությամբ որոնումը և դրա օգտագործումը

Ներածական հոդվածում փնտրում էիր լաբիրինթոսից դուրս գալու ճանապարհը։ Դու սկսում էիր՝ ասելով, որ նպատակակետն իրենից զրո քայլ է հետ։ Հետո գտնում էիր բոլոր քառակուսիները, որոնք մի քայլ էին հետ նպատակակետից։ Հետո բոլոր քառակուսիները, որոնք երկու քայլ էին հետ նպատակակետից։ Հետո երեք քայլ, և այդպես շարունակ այնքան, մինչև կհասնեիր այն քառակուսուն, որի վրայից պետք է սկսեր մարդուկը։ Եթե անընդհատ տեսնես, թե $k$‍ հեռավորություն ունեցող որ քառակուսուց ես եկել, որ հասնես $k+1$‍ հեռավորություն ունեցող քառակուսուն, դու կարող ես գտնել մարդուկի ճանապարհը դեպի նպատակակետը։

Ահա այն խնդրում մեր տեսած լաբիրինթոսի նկարը․

Հիմա սա կարող ես հասկանալ որպես ուղղություն չունեցող գրաֆիկ։ Ամեն մի գագաթը համապատասխանում է քառակուսու հետ, որ պատի մաս չէ, և ամեն մի կողը միացնում է հարևան քառակուսիները։

Վերևի եղանակով գտած ճանապարհն ունի մի կարևոր հատկություն․ ոչ մի այլ ճանապարհով ավելի քիչ քայլ չենք կատարում, որովհետև դա գտնելու համար օգտագործել ենք ալգորիթմ, որ կոչվում է լայնությամբ որոնում։ Լայնությամբ որոնումը, գտնում է ամենակարճ ճանապարհները տրված սկզբնակետից դեպի մյուս բոլոր կետերը և հաշվում հեռավորությունն ըստ կողերի քանակի։

Ահա լայնությամբ որոնման մեկ այլ օրինակ․ «Քևին Բեյքոնի վեց աստիճանները» խաղը։ Այստեղ խաղացողները սկսում են մի դերասանից, կապում են նրան մեկ այլ դերասանի հետ՝ ընդհանուր ֆիլմով, և այդպես այնքան, մինչև կկարողանան դերասանին կապել Քևին Բեյքոնի հետ։ Որքան ավելի կարճ լինի այդ հաջորդականությունը, այնքան ավելի լավ, և զարմանալի է, թե որքան դերասան կամ դերասանուհի կարող է վեց կամ ավելի քիչ քայլով հասնել Քևին Բեյքոնին։ Օրինակ՝ վերցնենք Քեյթ Բելլին՝ Ավստրալացի դերասանուհու։ Նա խաղացել է Մակբեթում Նեշ Էջերթոնի հետ 2006 թվականին։ Էջերթոնը խաղացել է Մատրիցա ֆիլմում Լոուրենս Ֆիշբորնի հետ 2003 թվականին։ Իսկ Ֆիշբորնը խաղացել է Խորհրդավոր գետ ֆիլմում Քևին Բեյքոնի հետ 2003\ թվականին։ Հետևաբար, Քեյթ Բելլի «Քևին Բեյքոն թիվը» 3\ է։ Իրականում շատ տարբեր ճանապարհներ կան, որոնցով գտնում ենք, որ այդ թիվը 3-ն է։ Դու կարող ես յուրաքանչյուր դերասանի կամ դերասանուհու Քևին Բեյքոն թիվը գտնել այստեղ։

Ինչպես և կռահեցիր, այս կայքը ստեղծում է ուղղություն չունեցող գրաֆիկ, որտեղ յուրաքանչյուր գագաթը համապատասխանում է դերասանին կամ դերասանուհուն, և եթե երկու հոգի խաղացել են նույն ֆիլմում, ապա այդ երկու գագաթներն ունեն ընդհանուր կող։ Լայնությամբ որոնումը սկսվում է Քևին Բեյքոնի գագաթից ու փնտրում դեպի բոլոր մյուս դերասանները կամ դերասանուհիները տանող ամենակարճ ճանապարհը։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։