کروسکل کا الگورتھم میز جنریٹر

کرسکل کا الگورتھم ایک کم سے کم پھیلے ہوئے درخت کا الگورتھم ہے جسے بھولبلییا نسل کے لیے ڈھال لیا جا سکتا ہے۔ یہ کامل بھولبلییا بنانے کے لیے خاص طور پر موثر ہے۔ کرسکل کے الگورتھم کا ایک متبادل پرائم کا الگورتھم ہے، جو کہ ایک کم سے کم پھیلے ہوئے درخت کا الگورتھم بھی ہے، لیکن چونکہ وہ ایک جیسی میزیں تیار کرتے ہیں اور کرسکل تیزی سے چلتا ہے، اس لیے میں نے پرائمز کو لاگو کرنے کی زحمت نہیں کی۔

ایک کامل بھولبلییا ایک بھولبلییا ہے جس میں بھولبلییا کے کسی بھی نقطہ سے کسی دوسرے مقام تک بالکل ایک راستہ ہوتا ہے۔ اس کا مطلب ہے کہ آپ حلقوں میں گھومنا ختم نہیں کر سکتے ہیں، لیکن آپ کو اکثر مردہ سروں کا سامنا کرنا پڑے گا، جو آپ کو پیچھے مڑنے اور واپس جانے پر مجبور کرے گا۔

یہاں تیار کردہ بھولبلییا کے نقشوں میں بغیر کسی آغاز اور اختتامی پوزیشنوں کے پہلے سے طے شدہ ورژن شامل ہے، لہذا آپ خود ان کا فیصلہ کر سکتے ہیں: بھولبلییا کے کسی بھی نقطہ سے کسی دوسرے مقام تک حل ہوگا۔ اگر آپ الہام چاہتے ہیں، تو آپ تجویز کردہ آغاز اور اختتامی پوزیشن کو فعال کر سکتے ہیں - اور یہاں تک کہ دونوں کے درمیان حل بھی دیکھیں۔

کرسکل کے الگورتھم کے بارے میں

کرسکل کا الگورتھم جوزف برنارڈ کرسکل، جونیئر، ایک امریکی ریاضی دان، شماریات دان، اور کمپیوٹر سائنس دان نے بنایا تھا۔ اس نے سب سے پہلے الگورتھم کو 1956 میں اپنے مقالے "آن دی شارٹسٹ اسپیننگ سب ٹری آف اے گراف اینڈ دی ٹریولنگ سیلز مین پرابلم پر" میں بیان کیا۔

الگورتھم کو گراف کے کم از کم پھیلے ہوئے درخت (MST) کو تلاش کرنے کے لیے ڈیزائن کیا گیا ہے، اس بات کو یقینی بناتا ہے کہ تمام چوٹیوں کو سائیکلوں سے گریز کرتے ہوئے کم سے کم ممکنہ کل کنارے کے وزن کے ساتھ منسلک کیا گیا ہے۔

کرسکل کا الگورتھم بھولبلییا جنریشن کے لیے کیسے کام کرتا ہے۔

مرحلہ 1: شروع کریں۔

• بھولبلییا میں ہر سیل کو الگ سیٹ (ایک منفرد جزو) کے طور پر سمجھیں۔
• ممکنہ کناروں کے طور پر ملحقہ خلیوں کے درمیان تمام دیواروں کی فہرست بنائیں۔

مرحلہ 2: دیواروں کو ترتیب دیں۔

• دیواروں کو شفل یا تصادفی طور پر ترتیب دیں۔ اگر اسے ایک حقیقی کرسکل کے الگورتھم کے طور پر لاگو کیا جائے تو دیواروں کو بے ترتیب ترتیب میں ترتیب دیں (چونکہ بھولبلییا کی نسل کو وزن کی ضرورت نہیں ہے)۔

مرحلہ 3: دیواروں پر عمل کریں۔

• بدلی ہوئی دیواروں کے ذریعے دہرائیں۔
• اگر دیوار کے ذریعہ تقسیم کردہ دو خلیات مختلف سیٹوں سے تعلق رکھتے ہیں (یعنی، وہ ابھی تک بھولبلییا میں جڑے نہیں ہیں)، دیوار کو ہٹا دیں اور سیٹوں کو ملا دیں۔
• اگر وہ پہلے سے ہی ایک ہی سیٹ میں ہیں، تو دیوار کو چھوڑ دیں (سائیکل سے بچنے کے لیے)۔

مرحلہ 4: مکمل ہونے تک جاری رکھیں

• اس عمل کو اس وقت تک دہرائیں جب تک کہ تمام خلیات آپس میں جڑ نہ جائیں، ایک ہی پھیلا ہوا درخت بن جائے۔
• آخر میں، ہر سیل دوسروں سے بغیر لوپس یا الگ تھلگ حصوں کے جڑا ہوتا ہے۔

چونکہ کرسکل کا الگورتھم سیٹوں کو ضم کرنے پر انحصار کرتا ہے، اس لیے اسے یونین فائنڈ الگورتھم کا استعمال کرتے ہوئے بہتر بنایا جا سکتا ہے، جو کہ بھولبلییا پیدا کرنے کے دوران منسلک خلیوں کو ٹریک کرنے کا ایک موثر طریقہ فراہم کرتا ہے۔ آپ یونین فائنڈ الگورتھم کے میرے پی ایچ پی کے نفاذ کو یہاں دیکھ سکتے ہیں: لنک

مزید پڑھنا

اگر آپ اس پوسٹ سے لطف اندوز ہوتے ہیں، تو آپ ان تجاویز کو بھی پسند کر سکتے ہیں:

• ایلر کا الگورتھم بھولبلییا جنریٹر
• بار بار چلنے والا بیک ٹریکر بھولبلییا جنریٹر
• بھولبھلی جنریٹر کا شکار کریں اور مار ڈالیں