ორობითი ძიება

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

ორობითი ძებნის ალგორითმის გამოყენების ერთ-ერთი ყველაზე გავრცელებული მაგალითი არის მასივში ნივთის პოვნა. მაგალითად, Tycho-2-ის ვარსკვლავთა კატალოგი შეიცავს ინფორმაციას 2,539,913 ყველაზე კაშკაშა ვარსკვლავის შესახებ ჩვენს გალაქტიკაში. დავუშვათ, გინდათ კატალოგში რომელიღაც კონკრეტული ვარსკვლავის მოძებნა მისი სახელის მიხედვით. თუ პროგრამა შეამოწმებს ყველა ვარსკვლავს პირველიდან დაწყებული, ალგორითმით, რომელსაც წრფივი ძებნის ალგორითმი ჰქვია, კომპიუტერს შეიძლება მთელი კატალოგის შემოწმება მოუწიოს იმ ვარსკვლავის საპოვნელად, რომელსაც თქვენ ეძებთ. თუ კატალოგი დალაგებული იქნება ანბანურად ვარსკვლავების სახელის მიხედვით, მაშინ ორობითი ძებნის ალგორითმს არ მოუწევს 22 ვარსკვლავზე მეტის გადამოწმება, უარეს შემთხვევაშიც კი.

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

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

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

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

ყოველ ჯერზე ირჩევთ ვარიანტს, რომელიც დაახლოებით 2 ტოლ ნაწილად ყოფს აზრიან ვარიანტებს. თუ თქვენი ვარაუდი არაა სწორი, მაშინ მე გეუბნებით, ჩემი რიცხვი უფრო მაღალია თუ უფრო დაბალი. ამით შეძლებთ აზრიანი ვარიანტების დაახლოებით ნახევარი გამორიცხოთ. მაგალითად, თუ აზრიანი ვარიანტების მიმდინარე დიაპაზონია 26-იდან 80-მდე, ივარაუდებდით შუა წერტილს $(26+80)/2$‍, იგივე 53-ს. თუ გეტყვით, რომ 53 არის ჩემს რიცხვზე მეტი, ამოყრით ყველა ვარიანტს 53-დან 80-მდე, აზრიან ვარიანტებად დაგრჩებათ 26-დან 52-მდე, რითაც მათი დიაპაზონი გაანახევრეთ.

მიხვედრის თამაშისთვის აზრიანი ვარიანტების სიმრავლისთვის თვალყურის დევნება შეგვიძლია რამდენიმე ცვლადის გამოყენებით. ცვლადი $min$‍ იყოს ამ რაუნდის აზრიანი ვარიანტების მიმდინარე მინიმუმი, ხოლო ცვლადი $max$‍ იყოს ამ რაუნდის აზრიანი ვარიანტების მიმდინარე მაქსიმუმი. შემომავალი მონაცემები არის რიცხვი $n$‍ — უდიდესი რიცხვი, რომელიც შეიძლება, რომ თქვენმა მეტოქემ ჩაიფიქროს. ჩვენ დაშვებული გვაქვს, რომ უმცირესი შესაძლო რიცხვი არის ერთი, მაგრამ მარტივად შეიძლება ალგორითმის მოდიფიკაცია ისე, რომ მინიმალური რიცხვისათვის მეორე შემომავალი მონაცემი დავამატოთ.

აი, მიხვედრის თამაშის სათამაშოდ ორობითი ძიების გამოყენების ნაბიჯ-ნაბიჯ აღწერა:

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

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

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