If you're seeing this message, it means we're having trouble loading external resources on our website.

თუ ვებფილტრს იყენებთ, დარწმუნდით, რომ *.kastatic.org და *.kasandbox.org დომენები არ არის დაბლოკილი.

ძირითადი მასალა

სიგანეში ძებნა და მისი გამოყენებები

შესავალ სახელმძღვანელოში თქვენ ლაბირინთში გადაადგილებებით მიაღწიეთ სამიზნეს. თავიდან თქვით, რომ სამიზნე არის საკუთარი თავიდან ნული ნაბიჯით დაშორებული. შემდეგ იპოვეთ ყველა კვადრატი, რომელიც ერთი ნაბიჯით არის დაშორებული მისგან. შემდეგ იპოვეთ ყველა კვადრატი, რომელიც ორი ნაბიჯით არის დაშორებული მისგან. შემდეგ სამი ნაბიჯი და ა.შ. მანამ, სანამ მიაღწიეთ თქვენს საწყის კვადრატამდე. თუ ჩაინიშნავდით, k მანძილით დაშორებული რომელი კვადრატიდან მოხვედით k+1 მანძილით დაშორებულ კვადრატზე, შეძლებდით „ბექტრეკინგით“ (უკუსვლით) გეპოვათ გზა საწყისი ადგილიდან სამიზნემდე.
აი, სურათი, რომელიც შესავალ სახელმძღვანელოში ვნახეთ:
ახლა თქვენ ამჩნევთ, რომ ეს არამიმართული გრაფია. თითოეული წვერო შეესაბამება კვადრატს, რომელიც არ არის კედლის ნაწილი და თითოეული წიბო ეხება მეზობელ კვადრატებს.
ზემოთ მოცემულ გზას აქვს მნიშვნელოვანი თვისება: არც ერთი სხვა გზა საწყისიდან სამიზნემდე არ გადის ნაკლები რაოდენობის კვადრატზე. ეს იმიტომ, რომ მის საპოვნელად ჩვენ გამოვიყენეთ ალგორითმი სახელად სიგანეში ძებნა. ორობითი ძებნა, აგრეთვე ცნობილი, როგორც BFS, პოულობს უმოკლეს გზებს მოცემული საწყისი წვეროდან ყველა სხვა წვერომდე (გზის სიგრძე ითვლება მასში არსებული წიბოების რაოდენობით).
აი, სიგანეში ძებნის კიდევ ერთი მაგალითი: „კევინ ბეკონის 6 ხარისხის“ თამაში. აქ მოთამაშეები ცდილობენ, მსახიობები დააკავშირონ კევინ ბეკონთან იმ ჯაჭვის მიხედვით, თუ ვინ გამოჩნდა ვისთან ერთად ფილმში. რაც უფრო მოკლეა ჯაჭვი, მით უკეთესი და გამაოგნებელია, რამდენ მსახიობს შეუძლია კევინ ბეკონთან მისვლა ექვსი ან ნაკლები სიგრძის ჯაჭვით. მაგალითისთვის, ავიღოთ კეიტ ბელი, ავსტრალიელი მსახიობი. ის იყო მაკბეტში ნეშ ედჯერტონთან ერთად 2006-ში; ედჯერტონი იყო მატრიცა 2-ში ლოურენს ფიშბურნთან ერთად 2003-ში; ხოლო ფიშბურნი იყო იდუმალ მდინარეში კევინ ბეკონთან ერთად 2003-ში. ასე რომ, კეიტ ბელის „კევინ ბეკონის რიცხვი“ არის 3. რეალურად, არსებობს რამდენიმე გზა იმის საპოვნელად, რომ კეიტ ბელის კევინ ბეკონის რიცხვი არის 3. ნებისმიერი მსახიობის კევინ ბეკონის რიცხვის პოვნა შეგიძლიათ კევინ ბეკონის წინასწარმეტყველების ვებგვერდზე.
როგორც უკვე მიხვდით, კევინ ბეკონის წინასწარმეტყველის ვებგვერდი ინახავს მიუმართავ (არამიმართულ) გრაფს, რომელშიც თითოეული წვერო შეესაბამება მსახიობს და თუ ორი მსახიობი მონაწილეობდა ერთსა და იმავე ფილმში, მათ შორის წიბო არის გავლებული. სიგანეში ძებნა კევინ ბეკონის შესაბამისი წვეროდან პოულობს უმოკლეს ჯაჭვს ყველა სხვა მსახიობამდე.

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

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

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