კრუსკალის ალგორითმის ლაბირინთში გენერატორი

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

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

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

კრუსკალის ალგორითმის შესახებ

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

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

როგორ მუშაობს კრუსკალის ალგორითმი ლაბირინთის გენერირებისთვის

ნაბიჯი 1: ინიციალიზაცია

• ლაბირინთში თითოეული უჯრედი ცალკე კომპლექტად (უნიკალური კომპონენტი) მიიჩნიეთ.
• ჩამოთვალეთ მიმდებარე უჯრედებს შორის არსებული ყველა კედელი, როგორც პოტენციური კიდეები.

ნაბიჯი 2: კედლების დახარისხება

• კედლები შემთხვევით ან შეუსაბამებლად დაალაგეთ. თუ მას კრუსკალის ნამდვილი ალგორითმის სახით ახორციელებთ, კედლები შემთხვევითი თანმიმდევრობით დაალაგეთ (რადგან ლაბირინთის გენერირებას წონები არ სჭირდება).

ნაბიჯი 3: პროცესის კედლები

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

ნაბიჯი 4: გააგრძელეთ დასრულებამდე

• გაიმეორეთ ეს პროცესი მანამ, სანამ ყველა უჯრედი არ დაუკავშირდება ერთმანეთს და არ ჩამოყალიბდება ერთიანი გაშლილი ხე.
• ბოლოს, თითოეული უჯრედი სხვებთან დაკავშირებულია მარყუჟების ან იზოლირებული მონაკვეთების გარეშე.

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

დამატებითი საკითხავი

თუ ეს პოსტი მოგეწონათ, შეიძლება ეს რჩევებიც მოგეწონოთ:

• ნადირობა და მოკვლა მეზის გენერატორი
• რეკურსიული Backtracker Maze გენერატორი
• ელერის ალგორითმის ლაბირინთის გენერატორი