ক্রুসকালের অ্যালগরিদম গোলকধাঁধা জেনারেটর

ক্রুসকালের অ্যালগরিদম হল একটি ন্যূনতম স্প্যানিং ট্রি অ্যালগরিদম যা মেজ জেনারেশনের জন্য অভিযোজিত করা যেতে পারে। এটি নিখুঁত মেজ তৈরির জন্য বিশেষভাবে কার্যকর। ক্রুসকালের অ্যালগরিদমের বিকল্প হল প্রিমের অ্যালগরিদম, যা একটি ন্যূনতম স্প্যানিং ট্রি অ্যালগরিদমও, কিন্তু যেহেতু তারা একই রকম মেজ তৈরি করে এবং ক্রুসকালের দ্রুত রান হয়, তাই আমি প্রিমের বাস্তবায়নের ঝামেলা করিনি।

একটি নিখুঁত গোলকধাঁধা হল এমন একটি গোলকধাঁধা যেখানে গোলকধাঁধার যেকোনো বিন্দু থেকে অন্য যেকোনো বিন্দুতে ঠিক একটি পথ থাকে। এর মানে হল আপনি বৃত্তাকারে ঘুরে বেড়াতে পারবেন না, তবে আপনি প্রায়শই অচল প্রান্তের মুখোমুখি হবেন, যা আপনাকে ঘুরে ফিরে যেতে বাধ্য করবে।

এখানে তৈরি করা গোলকধাঁধা মানচিত্রগুলিতে কোনও শুরু এবং শেষ অবস্থান ছাড়াই একটি ডিফল্ট সংস্করণ রয়েছে, তাই আপনি নিজেই সেগুলি সিদ্ধান্ত নিতে পারেন: গোলকধাঁধার যেকোনো বিন্দু থেকে অন্য যেকোনো বিন্দুতে একটি সমাধান থাকবে। আপনি যদি অনুপ্রেরণা চান, তাহলে আপনি একটি প্রস্তাবিত শুরু এবং শেষ অবস্থান সক্ষম করতে পারেন - এবং এমনকি উভয়ের মধ্যে সমাধানও দেখতে পারেন।

ক্রুসকালের অ্যালগরিদম সম্পর্কে

ক্রুসকালের অ্যালগরিদম তৈরি করেছিলেন জোসেফ বার্নার্ড ক্রুসকাল, জুনিয়র, একজন আমেরিকান গণিতবিদ, পরিসংখ্যানবিদ এবং কম্পিউটার বিজ্ঞানী। তিনি প্রথম ১৯৫৬ সালে তার "অন দ্য শর্টেস্ট স্প্যানিং সাবট্রি অফ আ গ্রাফ অ্যান্ড দ্য ট্র্যাভেলিং সেলসম্যান প্রবলেম" প্রবন্ধে অ্যালগরিদমটি বর্ণনা করেছিলেন।

অ্যালগরিদমটি একটি গ্রাফের ন্যূনতম স্প্যানিং ট্রি (MST) খুঁজে বের করার জন্য ডিজাইন করা হয়েছে, যাতে নিশ্চিত করা যায় যে সমস্ত শীর্ষবিন্দু ন্যূনতম সম্ভাব্য মোট প্রান্ত ওজনের সাথে সংযুক্ত রয়েছে এবং চক্র এড়ানো যায়।

ক্রুসকালের অ্যালগরিদম কীভাবে গোলকধাঁধা তৈরির জন্য কাজ করে

ধাপ ১: আরম্ভ করুন

• গোলকধাঁধার প্রতিটি কোষকে একটি পৃথক সেট (একটি অনন্য উপাদান) হিসাবে বিবেচনা করুন।
• সংলগ্ন কোষগুলির মধ্যে সমস্ত দেয়ালকে সম্ভাব্য প্রান্ত হিসাবে তালিকাভুক্ত করুন।

ধাপ ২: দেয়াল সাজান

• দেয়ালগুলো এলোমেলোভাবে সাজান অথবা এলোমেলোভাবে সাজান। যদি এটি সত্যিকারের ক্রুসকালের অ্যালগরিদম হিসেবে বাস্তবায়ন করা হয়, তাহলে দেয়ালগুলোকে এলোমেলোভাবে সাজান (যেহেতু গোলকধাঁধা তৈরির জন্য ওজনের প্রয়োজন হয় না)।

ধাপ ৩: দেয়াল প্রক্রিয়াকরণ

• এলোমেলো দেয়ালের মধ্য দিয়ে পুনরাবৃত্তি করুন।
• যদি প্রাচীর দ্বারা বিভক্ত দুটি কক্ষ ভিন্ন সেটের হয় (অর্থাৎ, তারা এখনও গোলকধাঁধায় সংযুক্ত না থাকে), তাহলে প্রাচীরটি সরিয়ে সেটগুলিকে একত্রিত করুন।
• যদি তারা ইতিমধ্যেই একই সেটে থাকে, তাহলে দেয়াল এড়িয়ে যান (চক্র এড়াতে)।

ধাপ ৪: সম্পূর্ণ না হওয়া পর্যন্ত চালিয়ে যান

• এই প্রক্রিয়াটি পুনরাবৃত্তি করুন যতক্ষণ না সমস্ত কোষ সংযুক্ত হয়, একটি একক স্প্যানিং ট্রি তৈরি করে।
• শেষে, প্রতিটি কোষ লুপ বা বিচ্ছিন্ন অংশ ছাড়াই অন্যদের সাথে সংযুক্ত থাকে।

যেহেতু ক্রুসকালের অ্যালগরিদম সেট মার্জ করার উপর নির্ভর করে, তাই এটি ইউনিয়ন-ফাইন্ড অ্যালগরিদম ব্যবহার করে অপ্টিমাইজ করা যেতে পারে, যা মেজ জেনারেশনের সময় সংযুক্ত কোষগুলি ট্র্যাক করার একটি কার্যকর উপায় প্রদান করে। আপনি এখানে ইউনিয়ন-ফাইন্ড অ্যালগরিদমের আমার পিএইচপি বাস্তবায়ন দেখতে পারেন: পিএইচপিতে বিচ্ছিন্ন সেট (ইউনিয়ন-ফাইন্ড অ্যালগরিদম)