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

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

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

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

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

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

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

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

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

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

ნაბიჯი 2: დაალაგეთ კედლები

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

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

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

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

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

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