க்ருஸ்கலின் அல்காரிதம் பிரமை ஜெனரேட்டர்

க்ருஸ்கலின் வழிமுறை என்பது பிரமை உருவாக்கத்திற்கு ஏற்றவாறு மாற்றியமைக்கக்கூடிய ஒரு குறைந்தபட்ச ஸ்பேனிங் ட்ரீ வழிமுறையாகும். இது சரியான பிரமைகளை உருவாக்குவதற்கு மிகவும் பயனுள்ளதாக இருக்கும். க்ருஸ்கலின் வழிமுறைக்கு மாற்றாக ப்ரிமின் வழிமுறை உள்ளது, இது ஒரு குறைந்தபட்ச ஸ்பேனிங் ட்ரீ வழிமுறையாகும், ஆனால் அவை ஒரே மாதிரியான பிரமைகளை உருவாக்குவதாலும், க்ருஸ்கலின் இயக்கங்கள் வேகமாக இருப்பதாலும், ப்ரிமின் வழிமுறைகளை செயல்படுத்துவதில் நான் கவலைப்படவில்லை.

ஒரு சரியான பிரமை என்பது ஒரு பிரமை, அதில் பிரமையின் எந்தப் புள்ளியிலிருந்தும் மற்றொரு புள்ளிக்கு சரியாக ஒரு பாதை இருக்கும். அதாவது நீங்கள் வட்டங்களில் சுற்றிச் செல்ல முடியாது, ஆனால் நீங்கள் அடிக்கடி முட்டுச்சந்துகளைச் சந்திப்பீர்கள், இதனால் நீங்கள் திரும்பிச் செல்ல வேண்டிய கட்டாயம் ஏற்படும்.

இங்கே உருவாக்கப்பட்ட பிரமை வரைபடங்கள் தொடக்க மற்றும் முடிவு நிலைகள் இல்லாத இயல்புநிலை பதிப்பைக் கொண்டுள்ளன, எனவே அவற்றை நீங்களே தீர்மானிக்கலாம்: பிரமையின் எந்தப் புள்ளியிலிருந்தும் வேறு எந்தப் புள்ளிக்கும் ஒரு தீர்வு இருக்கும். நீங்கள் உத்வேகம் விரும்பினால், பரிந்துரைக்கப்பட்ட தொடக்க மற்றும் முடிவு நிலையை நீங்கள் இயக்கலாம் - மேலும் இரண்டிற்கும் இடையிலான தீர்வைக் கூட பார்க்கலாம்.

க்ருஸ்கலின் அல்காரிதம் பற்றி

க்ருஸ்கலின் வழிமுறையை அமெரிக்க கணிதவியலாளர், புள்ளியியல் நிபுணர் மற்றும் கணினி விஞ்ஞானி ஜோசப் பெர்னார்ட் க்ருஸ்கால் ஜூனியர் உருவாக்கியுள்ளார். அவர் முதன்முதலில் இந்த வழிமுறையை 1956 ஆம் ஆண்டு தனது "ஒரு வரைபடத்தின் மிகக் குறுகிய விரிவடையும் துணை மரம் மற்றும் பயணிக்கும் விற்பனையாளர் பிரச்சினை" என்ற கட்டுரையில் விவரித்தார்.

இந்த வழிமுறை ஒரு வரைபடத்தின் குறைந்தபட்ச ஸ்பேனிங் ட்ரீ (MST) ஐக் கண்டறிய வடிவமைக்கப்பட்டுள்ளது, இது அனைத்து செங்குத்துகளும் சுழற்சிகளைத் தவிர்த்து குறைந்தபட்ச மொத்த விளிம்பு எடையுடன் இணைக்கப்பட்டுள்ளதை உறுதி செய்கிறது.

பிரமை உருவாக்கத்திற்கு க்ருஸ்கலின் அல்காரிதம் எவ்வாறு செயல்படுகிறது

படி 1: துவக்கு

• பிரமையில் உள்ள ஒவ்வொரு செல்லையும் தனித்தனி தொகுப்பாக (ஒரு தனித்துவமான கூறு) கருதுங்கள்.
• அருகிலுள்ள செல்களுக்கு இடையே உள்ள அனைத்து சுவர்களையும் சாத்தியமான விளிம்புகளாக பட்டியலிடுங்கள்.

படி 2: சுவர்களை வரிசைப்படுத்துங்கள்

• சுவர்களை மாற்றவும் அல்லது சீரற்ற முறையில் வரிசைப்படுத்தவும். உண்மையான க்ருஸ்கலின் வழிமுறையாக இதை செயல்படுத்தினால், சுவர்களை சீரற்ற வரிசையில் வரிசைப்படுத்தவும் (பிரமை உருவாக்கத்திற்கு எடைகள் தேவையில்லை என்பதால்).

படி 3: செயல்முறை சுவர்கள்

• மாற்றப்பட்ட சுவர்கள் வழியாக மீண்டும் செய்யவும்.
• சுவரால் வகுக்கப்படும் இரண்டு செல்கள் வெவ்வேறு தொகுப்புகளைச் சேர்ந்தவை என்றால் (அதாவது, அவை இன்னும் பிரமையில் இணைக்கப்படவில்லை), சுவரை அகற்றி தொகுப்புகளை ஒன்றிணைக்கவும்.
• அவை ஏற்கனவே ஒரே தொகுப்பில் இருந்தால், சுவரைத் தவிர்க்கவும் (சுழற்சிகளைத் தவிர்க்க).

படி 4: முடியும் வரை தொடரவும்

• அனைத்து செல்களும் இணைக்கப்பட்டு, ஒற்றை விரிந்த மரத்தை உருவாக்கும் வரை இந்த செயல்முறையை மீண்டும் செய்யவும்.
• முடிவில், ஒவ்வொரு கலமும் சுழல்கள் அல்லது தனிமைப்படுத்தப்பட்ட பிரிவுகள் இல்லாமல் மற்றவற்றுடன் இணைக்கப்பட்டுள்ளது.

க்ருஸ்கலின் வழிமுறை தொகுப்புகளை இணைப்பதை நம்பியிருப்பதால், யூனியன்-ஃபைண்ட் வழிமுறையைப் பயன்படுத்தி அதை மேம்படுத்தலாம், இது பிரமை உருவாக்கத்தின் போது இணைக்கப்பட்ட செல்களைக் கண்காணிக்க ஒரு திறமையான வழியை வழங்குகிறது. யூனியன்-ஃபைண்ட் வழிமுறையின் எனது PHP செயல்படுத்தலை இங்கே காணலாம்: PHP இல் Disjoint Set (Union-Find Algorithm)