Հիմնական նյութ
Համակարգչային գիտություն
Ճանապարհ գտնելու խաղ
Երբ մտածում ես լուծման մասին, երբեմն դժվար թվացող շատ խնդիրներ իրար նման են դառնում։ Ի՞նչ նմանություն ունեն, օրինակ, Պակ-Ման խաղը, Մեծ Բրիտանիայի թագավորական տոհմածառը կամ մեքենայով դեպի Թբիլիսի գնալը։ Սրանք բոլորը ներառում են ուղին գտնելու խնդիրներ․
- Ինչպե՞ս է արքայազն Ուիլյամը կապվում Ուիլյամ Երրորդ թագավորի հետ, ով 1693-ին ստեղծել է Ուիլյամ և Մերի քոլեջը։
- Ի՞նչ ուղով պետք է շարժվի ուրվականը, որպեսզի բռնի Պակ-Մանին։
- Ո՞րն է Երևանից Թբիլիսի գնալու ամենակարճ ճանապարհը։
Մեզ պետք են որոշակի տեղեկություններ՝ այս հարցերին պատասխանելու համար։
Օրինակ Մեծ Բրիտանիայի տոհմածառը ցույց է տալիս մարդկանց միջև կապը։ Արքայազն Ուիլյամը Չարլզ Ֆիլիպ Արթուր Վինդզորի որդին է։ Չարլզը Էլիզաբեթ II թագուհու որդին է։ Խնդիրը պահանջում է գտնել Ուիլյամ արքայազնի և Ուիլյամ թագավորի միջև ամենակարճ կապը տոհմածառում՝ կիրառելով անմիջական կապերը։ Ինչպես տեսնում ես, մեզ պետք կգան բազում քայլեր՝ Ուիլյամ թագավորին հասնելու համար։
Պակ-Մանի դեպքում մեզ պետք է լաբիրինթոսի քարտեզը։ Այս քարտեզը ցույց է տալիս հարևան բաց քառակուսիների կապը։ Խնդիրը պահանջում է սև քառակուսիներով գտնել այն ամենակարճ ուղին, որն ուրվականին կհասցնի Պակ-Մանի մոտ։
Երևանից Թբիլիսի ճանապարհը գտնելու համար մեզ պետք է Հայաստանի և Վրաստանի քարտեզը, որը ճանապարհներով կապում է իրար մոտ գտնվող քաղաքները։ Ոչ մի ճանապարհով Երևանից միանգամից չես հասնի Թբիլիսի, ուստի պետք է գտնես երկու քաղաքները կապող ճանապարհների մի ամբողջ հերթականություն։
Բացահայտում ենք լաբիրինթոսը
Լաբիրինթոսներով խաղերը զվարճալի են, և մենք հիմա կխորանանք դրանցից մեկի մեջ։ Մեր խաղում հերոսը կարող է գտնել լաբիրինթոսի ելքը տանող ուղիներ։
Որպես խաղացող՝ դու կառավարում ես հերոսին՝ սեղմելով այն վանդակի վրա, որտեղ պետք է նա գնա։ Նպատակը (անգլերենով գրված է «GOAL») ներկված է կարմիր գույնով, իսկ հերոսը սկսում է սկզբնական քառակուսուց։ Փորձիր խաղալ:
Տեսա՞ր՝ ինչպես հերոսը հասավ նպատակակետին։ Դրա համար ծրագիրը գտնում է բոլոր հնարավոր ուղիները, որոնցով կարող է հերոսը հասնել նպատակակետին, իսկ հետո հերոսին քայլեցնում է ամենակարճ ուղով։ Այլ կերպ ասած՝ ծրագիրը գտնում է նպատակակետին հասնելու ամենաարագ ճանապարհը:
Նախքան ալգորիթմ որոշելը ծրագիրը պետք է հասկանա, թե որ քառակուսին է հատակ, իսկ որը՝ պատ։ Պատերը մոխրագույն քառակուսիներն են, և դրանցով որևէ շարժումն արգելվում է։ Յուրաքանչյուր քայլին հերոսը կարող է մի քառակուսուց շարժվել դեպի հարևան քառակուսին։ Այս հերոսը, ինչպես շախմատում նավակը, չի կարող շարժվել անկյունագծով։
Փորձենք հասկանալ, թե ինչ ալգորիթմ է օգտագործում ծրագիրը․ յուրաքանչյուր քայլին շարժվել մի քայլ մոտ դեպի խաղացողի սեղմած վայրը՝ նպատակակետը։ Բայց ի՞նչ է նշանակում «մի քայլ մոտ»։ Ուղիղ գծով դեպի նպատակակետը շարժվելիս հերոսը համարյա միշտ կբախվի պատին։ Ալգորիթմը պետք է հասկանա, թե ամեն քայլին քառակուսիներից որն է իրոք ավելի մոտ գտնվում նպատակակետին, և մենք կարող ենք դա սահմանել՝ ամեն քառակուսուն տալով «կշիռ», որը ցույց է տալիս քայլերի նվազագույն քանակը։ Ահա ամեն քառակուսուն կշիռ տալու ալգորիթմը․
- Սկսում ենք GOAL քառակուսուց։ Որքա՞ն հեռու է GOAL-ը GOAL-ից։ Զրո քայլ։ Այդտեղ գրում ենք 0։
- Գտիր բոլոր քառակուսիները, որոնք մեկ քայլով են հեռու GOAL-ից։ Այդտեղ գրիր 1։ Այս լաբիրինթոսում միայն մի քառակուսի է մեկ քայլ հեռու GOAL-ից։
- Հիմա գտիր բոլոր քառակուսիները, որոնք երկու քայլով են հեռու GOAL-ից։ Այս քառակուսիները մեկով հեռու են 1-ով նշված քառակուսուց։ Այդտեղ գրիր 2։
- Նշագրիր բոլոր քառակուսիները, որոնք GOAL-ից երեք քայլով են հեռու։ Այս քառակուսիները մեկով հեռու են 2-ով նշված քառակուսիներից և դեռ նշագրված չեն։ Այդտեղ գրիր 3։
- Այդպես շարունակիր նշագրել լաբիրինթոսի բոլոր քառակուսիները։ k-երորդ քառակուսին նշագրելուց հետո k-ից մի քայլ հեռու քառակուսիները նշագրիր k, plus, 1-ով։
Ի վերջո ալգորիթմը կհասնի սկզբի քառակուսուն։ Ծրագիրն այնուհետև գնում է դեպի նպատակակետ տանող այն ճանապարհը, որտեղ ամեն հաջորդ քառակուսու վրա գրված թիվը մեկով փոքր է նախորդից։
Կարող ես ինքդ փորձել կիրառել սովորածդ այս ալգորիթմով։ Սեղմիր «Restart algorithm»։
Եթե խաղացողը փորձում է սկսել սկզբի քառակուսուց՝ օգտագործելով քառակուսին նշագրելու ալգորիթմը, նա արդեն գիտի, որ սկզբի քառակուսին 13 քայլով հեռու է ելքից։ Ահա բոլոր հնարավոր ուղիների պատկերը, քառակուսիների նշագրումները և յուրաքանչյուր քառակուսու հեռավորությունը նպատակակետից:
Սկզբի քառակուսու անմիջապես ներքևում գտնվող քառակուսին 12 քայլով հեռու է նպատակակետից։ Հետևաբար, պետք է գնանք այնտեղ։ Դրա ներքևում գտնվողը 11\ քայլով է հեռու։ Գնում ենք նորից ներքև։ Հետո գնում ենք 10։ Հետո դեպի աջ՝ 9։ Երկու անգամ էլ աջ՝ մինչև 7, հետո հինգ քայլ վերև՝ մինչև 2։ Հետո մի քայլ գնում ենք ձախ՝ դեպի 1, և վերջապես մի քայլ վերև՝ դեպի նպատակակետը։
Մենք առայժմ չենք քննարկի՝ ինչպես օգտագործել լաբիրինթոս որոնելու այս ալգորիթմը, բայց կարող ես մի փոքր մտածել, թե ինչպես է այս ամբողջը գրվում JavaScript-ում, և ինչպես ես օգտագործում ալգորիթմն այնտեղ։
Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։
Ուզո՞ւմ ես միանալ խոսակցությանը։
Հրաշալի է։Բայց մենք կարող ենք պայման թելադրել առաջարկված քայլերը կիրառելիս(2 ձայն)