გზის გამკვლევი

ხანდახან ის ამოცანები, რომლებიც თავიდან რთული ჩანს, ჩვენთვის ნაცნობი ხდება, როცა მათ ამოხსნაზე ფიქრს ვიწყებთ. რა აქვთ პაკ-მენს, ბრიტანეთის სამეფო ოჯახსა და ორლანდოში მგზავრობას საერთო? ყველა მათგანი შეიცავს გზის პოვნის/ძებნის ამოცანებს:

რა საერთო აქვთ ახლანდელ პრინც უილიამსა და მეფე უილიამ III-ს, რომელმაც დააარსა უილიამისა და მერის კოლეჯი 1693 წელს?
რა გზას უნდა გაჰყვეს აჩრდილი, რათა მან რაც შეიძლება სწრაფად მიაღწიოს პაკ-მენამდე?
რომელია საუკეთესო გზა დალასიდან (ტექსასი) ორლანდომდე (ფლორიდა) მისასვლელად?

იმისთვის, რომ მოცემული შეკითხვებიდან ნებისმიერს ვუპასუხოთ, უნდა გვქონდეს რაღაც ინფორმაცია.

მაგალითად, ბრიტანეთის სამეფო ოჯახის საგვარეულო ხე გვაჩვენებდა კავშირს იმ ადამიანებს შორის, რომლებიც უშუალოდ ენათესავებიან ერთმანეთს. პრინცი უილიამი არის ჩარლზ ფილიპ არტურ უინძორის შვილი. ჩარლზი არის დედოფალ ელისაბედ II-ის შვილი. ამოცანა გულისხმობს მოკლე ჯაჭვის პოვნას პრინც უილიამსა და უილიამ III-ს შორის, ასეთივე პიდაპირი კავშირების მეშვეობით. როგორც ქვემოთ მოცემული ხიდან ჩანს, მათ შორის საკმაოდ ბევრი პირდაპირი კავშირია.

პაკ-მენისთვის ლაბირინთის რუკა გვჭირდება. რუკა გვაჩვენებს კავშირებს მოსაზღვრე ღია კვადრატებს შორის — ან კავშირის უქონლობას, თუ მათ შორის კედელია აღმართული — ამოცანა კი გულისხმობს გზის პოვნას იმ შავი კვადრატების გასწვრივ, რომელთაც მიჰყავთ აჩრდილი პაკ-მენამდე.

იმისთვის, რომ ვიპოვოთ მარშრუტი დალასიდან ორლანდომდე, შეგვიძლია გამოვიყენოთ აშშ-ის რუკა, რომელზეც აღნიშნული იქნება კავშირები — გზები — ახლომდებარე ქალაქებს შორის. არ არსებობს გზა, რომელიც დალასს პირდაპირ დააკავშირებს ორლანდოსთან, მაგრამ თუ გამოვიყენებთ გზების მიმდევრობას, მივაღწევთ შედეგს.

გამოვიკვლიოთ ლაბირინთი

ლაბირინთული თამაშები სახალისოა, ამიტომ, მოდით, უფრო ღრმად შევისწავლოთ ერთ-ერთი მათგანი. ჩვენს თამაშში მთავარ პერსონაჟს შეუძლია ლაბირინთში სხვადასხვა ადგილზე მისვლა. როგორც ადამიანი მოთამაშე, თქვენ მართავთ მთავარ პერსონაჟს ლაბირინთში თქვენ მიერ არჩეულ კვადრატზე დაწკაპუნებით, კომპიუტერი კი გაარკვევს, როგორ მიიყვანოს პერსონაჟი დანიშნულების ადგილამდე. სამიზნე მონიშნულია წითელი მართკუთხედით რომელსაც ჰქვია „GOAL“ (სამიზნე), ხოლო ადგილს საიდანაც პერსონაჟი იწყებს მოძრაობას, ჰქვია საწყისი კვადრატი. სცადეთ მისი თამაში ქვემოთ:

შენიშნეთ, როგორ მივიდა პერსონაჟი მიზნამდე? ეს რომ მოხდეს, პროგრამამ უნდა განსაზღვროს მოძრაობათა სწორი თანმიმდევრობა, რომელსაც უნდა მიჰყვეს პერსონაჟი, რათა მომხმარებლის მიერ არჩეულ ადგილას მოხვდეს, და შემდეგ უნდა შეასრულოს ეს მოძრაობები. შეიძლება პერსონაჟისთვის მიზნამდე მისაღწევი მრავალი გზა არსებობდეს, თუმცა პროგრამამ მათგან საუკეთესო უნდა აარჩიოს.

სანამ ალგორითმის შექმნას შევუდგებით, მანამდე უნდა დადგინდეს მოძრაობის წესები: კედლები დამზადებულია ნაცრისფერი კვადრატებისგან, მოძრაობისთვის ნებადართული ადგილები კი ცარიელია. ყოველ ნაბიჯზე პერსონაჟს შეუძლია ერთი კვადრატიდან მოსაზღვრე კვადრატზე გადასვლა. ამ პერსონაჟს, ისევე როგორც ჭადრაკის ეტლს, არ შეუძლია დიაგონალურად გადაადგილება.

იდეა, რომელიც ამ პროგრამის ალგორითმს უდევს საფუძვლად, შემდეგში მდგომარეობს: ყოველ ნაბიჯზე ერთი კვადრატით მიუახლოვდით სამიზნეს — ადგილს, სადაც მომხმარებელმა დააწკაპუნა. მაგრამ რას ნიშნავს „მიუახლოვდი სამიზნეს“? მიზნის მიმართულებით სწორი ხაზის გასწვრივ მოძრაობით პერსონაჟი ხშირად კედელს მიეჯახება. ალგორითმმა უნდა განსაზღვროს, რომელი შემომსაზღვრელი კვადრატები არის ნამდვილად „ახლოს სამიზენესთან“, ამის გაკეთება კი შეგვიძლია თითოეული კვადრატისთვის „ღირებულების“ მინიჭებით, რომელიც წარმოადგენს იმ ნაბიჯების უმცირეს რაოდენობას, რომელიც უნდა შეასრულოს პერსონაჟმა მიზნამდე მისაღწევად. აი, ალგორითმი, რომელშიც თითოეულ კვადრატს მინიჭებული აქვს ღირებულება:

დაიწყეთ სამიზნე კვადრატით. რამდენად შორსაა სამიზნე საკუთარი თავისგან? ნული ნაბიჯით, მონიშნეთ სამიზნე რიცხვი 0-ით.
ლაბირინთში იპოვეთ ყოველი კვადრატი, რომელიც ზუსტად ერთი ნაბიჯითაა დაშორებული სამიზნისგან. მონიშნეთი ისინი რიცხვი 1-ით. ამ ლაბირინთში, თუ სამიზნე არის გასასვლელ კვადრატში, მაშინ არსებობს მხოლოდ ერთი კვადრატი რომელიც ზუსტად ერთი ნაბიჯითაა დაშორებული სამიზნისგან.
ახლა იპოვეთ ყოველი კვადრატი ლაბირინთში, რომელიც ზუსტად ორი ნაბიჯითაა დაშორებული მიზანს. ეს კვადრატები მხოლოდ ერთი ნაბიჯით არიან დაშორებული 1-იანით მონიშნულ კვადრატებსა და იმ კვადრატებს, რომლებიც ჯერ არ მოგვინიშნავს. მონიშნეთ ეს კვადრატები 2-ით.
მონიშნეთ ყოველი კვადრატი ლაბირინთში, რომელიც ზუსტად სამი ნაბიჯით არის დაშორებული სამიზნეს. ეს კვადრატები ერთი ნაბიჯით არიან დაშორებული 2-ით მონიშნულ კვადრატებს და ასევე იმ კვადრატებს, რომლებიც ჯერ არ მოგვინიშნავს. მონიშნეთ ისინი რიცხვი 3-ით.
განაგრძეთ კვადრატების მონიშვნა ლაბირინთში სამიზნიდან აღმავალი წესით. მას შემდეგ, რაც მონიშნავთ კვადრატებს $k$ ‍ რიცხვით, მონიშნეთ ყოველი კვადრატი $k + 1$ ‍ -ით, რომელიც ერთი ნაბიჯითაა დაშორებული $k$ ‍ -თი მონიშნული კვადრატებისგან.

საბოლოოდ, ალგორითმი მონიშნავს კვადრატს, საიდანაც პერსონაჟი იწყებს მოძრაობას. შემდეგ კი პროგრამას შეუძლია, იპოვოს გზა საწყისი წერტილიდან სამიზნემდე იმ კვადრატთა მიმდევრობის არჩევით, რომელთა რიცხვებიც გზის გასწვრივ მუდამ მცირდება. თუ რიცხვს შეხედავთ, როგორც კვადრატის სიმაღლეს, მაშინ ეს ყველაფერი დაღმართზე სიარულს დაემსგავსება.

ქვემოთ შეგიძლიათ ითამაშოთ ღირებულების მოსანიშნი ალგორითმით. დააწკაპუნეთ „Restart algorithm-ს“ თამაშის ხელახლა დასაწყებად.

რა მოხდება, თუ მომხმარებელი საწყისი უჯრიდან მიზნამდე მიღწევას ეცდება? უჯრების მოსანიშნი ალგორითმის მიხედვით, საწყისი უჯრა 13 ნაბიჯითაა დაშორებული მიზანს. აქ გვაქვს სურათი, რომელზეც ასახულია კავშირები შესაძლო ლოკაციებს შორის, დასაწყისი, მიზანი და ასევე უმოკლესი მანძილი თითოეული ადგილიდან მიზნამდე:

დასაწყისის სამხრეთით არის კვადრატი, რომელიც მხოლოდ 12 ნაბიჯით არის დაშორებული მიზნიდან. ასე რომ, პირველი ნაბიჯია „სამხრეთი“. ამ კვადრატის სამხრეთი არის 11. ისევ სამხრეთი. ისევ სამხრეთი, მივალთ10-ზე. შემდეგ აღმოსავლეთი ორჯერ, მივალთ 8-ზე. ჩრდილოეთი — 7-ზე, აღმოსავლეთი — 6-ზე, შემდეგ 5-ჯერ ჩრდილოეთი — 2-ზე. ვამთავრებთ ერთჯერ დასავლეთით წასვლით — 1-ზე — შემდეგ ერთხელ ჩრდილოეთით და ვაღწევთ მიზანს.

ჩვენ ახლა არ განვიხილავთ, ზუსტად როგორ უნდა დავწეროთ ეს ლაბირინთში ძებნის ალგორითმი, მაგრამ შეიძლება, თქვენთვის სახალისო იყოს იმაზე ფიქრი, თუ როგორ წარმოადგენდით ლაბირინთსა და პერსონაჟს JavaScript-ის გამოყენებით და როგორ დაწერდით ალგორითმს.

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტერული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.

გსურთ, შეუერთდეთ დისკუსიას?

შესვლა

დავალაგოთ:

პოსტები ჯერ არ არის.

გესმით ინგლისური? დააწკაპუნეთ აქ და გაეცანით განხილვას ხანის აკადემიის ინგლისურენოვან გვერდზე.