Partition problem
எண் கோட்பாடு மற்றும் கணினி அறிவியலில், பகிர்வு சிக்கல் அல்லது எண் பகிர்வு என்பது நேர்மறை முழு எண்களின் கொடுக்கப்பட்ட பல தொகுப்பு S ஐ S1 மற்றும் S2 ஆகிய இரண்டு துணைக்குழுக்களாகப் பிரிக்க முடியுமா என்பதைத் தீர்மானிக்கும் பணியாகும், அதாவது S1 இல் உள்ள எண்களின் கூட்டுத்தொகை S2 இல் உள்ள எண்களின் கூட்டுத்தொகைக்கு சமம். பகிர்வு சிக்கல் NP-முழுமையானது என்றாலும், ஒரு போலி-பல்லுறுப்புக்கோவை நேர மாறும் நிரலாக்க தீர்வு உள்ளது, மேலும் பல சந்தர்ப்பங்களில் சிக்கலை உகந்த முறையில் அல்லது தோராயமாக தீர்க்கும் ஹூரிஸ்டிக்ஸ் உள்ளன. இந்த காரணத்திற்காக, இது "எளிதான கடினமான பிரச்சினை" என்று அழைக்கப்படுகிறது. பகிர்வு சிக்கலின் உகப்பாக்கம் பதிப்பு உள்ளது, இது மல்டிசெட் S ஐ இரண்டு துணைக்குழுக்களாக S1, S2 ஆகப் பிரிப்பதாகும், இதனால் S1 இல் உள்ள உறுப்புகளின் கூட்டுத்தொகைக்கும் S2 இல் உள்ள உறுப்புகளின் கூட்டுத்தொகைக்கும் இடையிலான வேறுபாடு குறைக்கப்படுகிறது. உகப்பாக்கம் பதிப்பு NP-கடினமானது, ஆனால் நடைமுறையில் திறம்பட தீர்க்கப்படலாம். பகிர்வு சிக்கல் என்பது இரண்டு தொடர்புடைய சிக்கல்களின் ஒரு சிறப்பு வழக்குஃ துணைக்குழு தொகை சிக்கலில், S இன் துணைக்குழுவைக் கண்டுபிடிப்பதே குறிக்கோள், அதன் கூட்டுத்தொகை உள்ளீடாக கொடுக்கப்பட்ட ஒரு குறிப்பிட்ட இலக்கு எண் T ஆகும் (பகிர்வு சிக்கல் என்பது T என்பது S இன் கூட்டுத்தொகையில் பாதி). பல்வழி எண் பகிர்வில், ஒரு முழு எண் அளவுரு k உள்ளது, மேலும் S ஐ சமமான தொகையின் k துணைக்குழுக்களாக பிரிக்க முடியுமா என்பதை தீர்மானிப்பதே குறிக்கோள் (பகிர்வு சிக்கல் என்பது k = 2 கொண்ட சிறப்பு வழக்கு). இருப்பினும், இது 3-பகிர்வு சிக்கலை விட மிகவும் வேறுபட்டதுஃ அந்த சிக்கலில், துணைக்குழுக்களின் எண்ணிக்கை முன்கூட்டியே நிர்ணயிக்கப்படவில்லை-இது |S |/3 ஆக இருக்க வேண்டும், அங்கு ஒவ்வொரு துணைக்குழுவும் சரியாக 3 கூறுகளைக் கொண்டிருக்க வேண்டும். 3-பகிர்வு பகிர்வை விட மிகவும் கடினமானது-P = NP தவிர இதற்கு போலி-பல்லுறுப்புக்கோவை நேர வழிமுறை இல்லை. கொடுக்கப்பட்ட எடுத்துக்காட்டுகள் S = {3,1,1,2,2,1}, பகிர்வு சிக்கலுக்கான செல்லுபடியாகும் தீர்வு S1 = {1,1,1,2} மற்றும் S2 = {{2,3} ஆகிய இரண்டு தொகுப்புகளாகும். இரண்டு தொகுப்புகளின் கூட்டுத்தொகையும் 5 ஆகும், மேலும் அவை S ஐப் பிரிக்கின்றன. இந்த தீர்வு தனித்துவமானது அல்ல என்பதை நினைவில் கொள்க. S1 = {3,1,1} மற்றும் S2 = {2,2,1} மற்றொரு தீர்வாகும். நேர்மறை முழு எண்களின் ஒவ்வொரு பல தொகுப்புகளும் சமமான தொகையுடன் இரண்டு துணைக்குழுக்களாக ஒரு பகிர்வை கொண்டிருக்கவில்லை. அத்தகைய தொகுப்புக்கு ஒரு எடுத்துக்காட்டு S = {2,5} ஆகும். கணக்கீட்டு கடினத்தன்மை பகிர்வு சிக்கல் NP கடினமானது. துணை தொகுப்பு தொகை சிக்கலில் இருந்து குறைப்பதன் மூலம் இதை நிரூபிக்க முடியும். உட்பிரிவு கூட்டுத்தொகையின் ஒரு எடுத்துக்காட்டு நேர்மறை முழு எண்களின் தொகுப்பு S மற்றும் இலக்கு தொகை T ஐக் கொண்டுள்ளது; துல்லியமாக T கூட்டுத்தொகையுடன் S இன் துணைக்குழு உள்ளதா என்பதைத் தீர்மானிப்பதே குறிக்கோள். அத்தகைய ஒரு நிகழ்வைக் கருத்தில் கொண்டு, பகிர்வின் ஒரு நிகழ்வை உருவாக்குங்கள், இதில் உள்ளீட்டு தொகுப்பில் அசல் தொகுப்பு மற்றும் இரண்டு கூறுகள் உள்ளனஃ z1 மற்றும் z2, z1 = தொகை (S) மற்றும் z2 = 2T உடன். இந்த உள்ளீட்டு தொகுப்பின் கூட்டுத்தொகை தொகை (S) + z1 + z2 = 2 தொகை (S) + 2T ஆகும், எனவே பகிர்வுக்கான இலக்கு தொகை தொகை (S) + T ஆகும். பின்னர் கூட்டுத்தொகை (S′) = T, எனவே கூட்டுத்தொகை (S′z _ 1) = கூட்டுத்தொகை (S) + T, எனவே S′z _ 1 என்பது பகிர்வு நிகழ்வுக்கான தீர்வாகும். மாறாக, பிரிவினை நிகழ்வுக்கு ஒரு தீர்வு எஸ் உள்ளது என்று வைத்துக்கொள்வோம். பின்னர், S′ என்பது z1 அல்லது z2 ஐக் கொண்டிருக்க வேண்டும், ஆனால் இரண்டையும் கொண்டிருக்கக்கூடாது, ஏனெனில் அவற்றின் கூட்டுத்தொகை கூட்டுத்தொகை (S) + T ஐ விட அதிகமாக உள்ளது. S "இல் z2 இருந்தால், அது சரியாக (S) − T கூட்டுத்தொகையுடன் S இலிருந்து உறுப்புகளைக் கொண்டிருக்க வேண்டும், எனவே S இல் உள்ள மற்ற பொருள்கள் துணைத் தொகுப்பு நிகழ்வுக்கு ஒரு தீர்வாகும். தோராயமான வழிமுறைகள் மேலே குறிப்பிட்டுள்ளபடி, பகிர்வு சிக்கல் என்பது பல்வழி-பகிர்வு மற்றும் துணைக்குழு-கூட்டுத்தொகையின் ஒரு சிறப்பு வழக்கு. எனவே, இந்த சிக்கல்கள் ஒவ்வொன்றிற்கும் உருவாக்கப்பட்ட வழிமுறைகள் மூலம் அதைத் தீர்க்க முடியும். பல்வழி எண் பகிர்வுக்கு உருவாக்கப்பட்ட வழிமுறைகள் பின்வருமாறுஃ பேராசை எண் பகிர்வு-எண்களுக்கு மேல் சுழல்கள், மற்றும் தற்போதைய தொகை மிகச்சிறிய தொகுப்பில் ஒவ்வொரு எண்ணையும் வைக்கிறது. எண்கள் வரிசைப்படுத்தப்படாவிட்டால், இயக்க நேரம் O (n) ஆகவும், தோராய விகிதம் அதிகபட்சமாக 3/2 ஆகவும் இருக்கும் ("தோராய விகிதம்" என்பது வழிமுறை வெளியீட்டில் உள்ள பெரிய தொகை, உகந்த பகிர்வில் உள்ள பெரிய தொகையால் வகுக்கப்படுகிறது). எண்களை வரிசைப்படுத்துவது இயக்க நேரத்தை O (n log n) ஆக அதிகரிக்கிறது மற்றும் தோராய விகிதத்தை 7/6 ஆக மேம்படுத்துகிறது. எண்கள் ஒரே மாதிரியாக [0,1] இல் விநியோகிக்கப்பட்டால், தோராயமான விகிதம் கிட்டத்தட்ட நிச்சயமாகவும், எதிர்பார்ப்பிலும் இருக்கும். மிகப்பெரிய வேறுபாடு முறை (கர்மர்கர்-கார்ப் வழிமுறை என்றும் அழைக்கப்படுகிறது) எண்களை இறங்கு வரிசையில் வரிசைப்படுத்துகிறது மற்றும் எண்களை அவற்றின் வேறுபாடுகளால் மீண்டும் மீண்டும் மாற்றுகிறது. இயக்க நேர சிக்கலானது O (n log n) ஆகும். மிக மோசமான நிலையில், அதன் தோராய விகிதம் ஒத்திருக்கிறது-அதிகபட்சம் 7/6. இருப்பினும், சராசரி விஷயத்தில் இது பேராசை வழிமுறையை விட மிகச் சிறப்பாக செயல்படுகிறதுஃ எண்கள் [0,1] இல் ஒரே மாதிரியாக விநியோகிக்கப்படும்போது, அதன் தோராயமான விகிதம் அதிகபட்சமாக எதிர்பார்க்கப்படுகிறது. உருவகப்படுத்துதல் சோதனைகளிலும் இது சிறப்பாக செயல்படுகிறது. மல்டிஃபிட் வழிமுறை பைனரி தேடலைப் பயன்படுத்துகிறது, இது தொட்டி பொதி செய்வதற்கான ஒரு வழிமுறையுடன் இணைக்கப்பட்டுள்ளது. மிக மோசமான நிலையில், அதன் தோராய விகிதம் 8/7 ஆகும். துணைக்குழு தொகை சிக்கலில் ஒரு FPTAS உள்ளது, இது பகிர்வு சிக்கலுக்கும் பயன்படுத்தப்படலாம், இலக்கு தொகையை தொகை (S)/2 ஆக அமைப்பதன் மூலம். துல்லியமான வழிமுறைகள் உள்ளன, அவை எப்போதும் உகந்த பகிர்வை கண்டுபிடிக்கின்றன. சிக்கல் NP-கடினமானது என்பதால், அத்தகைய வழிமுறைகள் பொதுவாக அதிவேக நேரத்தை எடுக்கலாம், ஆனால் சில சந்தர்ப்பங்களில் நடைமுறையில் பயன்படுத்தப்படலாம். பல்வழி எண் பகிர்வுக்கு உருவாக்கப்பட்ட வழிமுறைகள் பின்வருமாறுஃ போலி பல்லுறுப்புக்கோவை நேர எண் பகிர்வு நினைவகத்தை எடுக்கும், இது உள்ளீட்டில் உள்ள மிகப்பெரிய எண். முழுமையான பேராசை வழிமுறை (சிஜிஏ) ஒரு பைனரி மரத்தை உருவாக்குவதன் மூலம் அனைத்து பகிர்வுகளையும் கருதுகிறது. மரத்தில் உள்ள ஒவ்வொரு மட்டமும் ஒரு உள்ளீட்டு எண்ணுடன் ஒத்திருக்கிறது, அங்கு வேர் மிகப்பெரிய எண்ணுடன் ஒத்திருக்கிறது, அதற்குக் கீழே உள்ள நிலை அடுத்த பெரிய எண்ணுடன் ஒத்திருக்கிறது. ஒவ்வொரு கிளையும் தற்போதைய எண்ணை வைக்கக்கூடிய வெவ்வேறு தொகுப்புடன் ஒத்திருக்கிறது. மரத்தை ஆழமான முதல் வரிசையில் பயணிக்க இடம் மட்டுமே தேவைப்படுகிறது, ஆனால் நேரம் ஆகலாம். ஒரு பேராசை ஹூரிஸ்டிக்கைப் பயன்படுத்துவதன் மூலம் இயக்க நேரத்தை மேம்படுத்தலாம்ஃ ஒவ்வொரு மட்டத்திலும், தற்போதைய எண் சிறிய தொகையுடன் தொகுப்பில் வைக்கப்படும் கிளையை முதலில் உருவாக்குங்கள். இந்த வழிமுறை முதலில் பேராசை எண் பகிர்வு மூலம் காணப்படும் தீர்வை கண்டறிகிறது, ஆனால் பின்னர் சிறந்த தீர்வுகளைத் தேடுகிறது. இந்த யோசனையின் சில மாறுபாடுகள் துணைக்குழு-தொகை சிக்கலுக்கான முழு பல்லுறுப்புக்கோவை-நேர தோராய திட்டங்களாகும், எனவே பகிர்வு சிக்கலுக்கும் கூட. முழுமையான கர்மார்கர்-கார்ப் வழிமுறை (சி. கே. கே) ஒரு பைனரி மரத்தை உருவாக்குவதன் மூலம் அனைத்து பகிர்வுகளையும் கருத்தில் கொள்கிறது. ஒவ்வொரு மட்டமும் ஒரு ஜோடி எண்களுக்கு ஒத்திருக்கிறது. இடது கிளை அவற்றை வெவ்வேறு துணைக்குழுக்களில் வைப்பதற்கு ஒத்திருக்கிறது (அதாவது, அவற்றின் வேறுபாட்டால் அவற்றை மாற்றுவது), வலது கிளை அவற்றை ஒரே துணைக்குழுவில் வைப்பதற்கு ஒத்திருக்கிறது (அதாவது, அவற்றின் கூட்டுத்தொகையால் அவற்றை மாற்றுவது). இந்த வழிமுறை முதலில் மிகப்பெரிய வேறுபாடு முறையால் கண்டறியப்பட்ட தீர்வை கண்டுபிடிக்கும், ஆனால் பின்னர் சிறந்த தீர்வுகளைக் கண்டறியத் தொடங்கும். இது சீரற்ற நிகழ்வுகளில் சிஜிஏவை விட கணிசமாக வேகமாக இயங்குகிறது. ஒரு சமமான பகிர்வு இருக்கும்போது அதன் நன்மை மிகப் பெரியது, மேலும் பல அளவிலான வரிசைகளில் இருக்கலாம். நடைமுறையில், எண்கள் அதிகபட்சம் 12 குறிப்பிடத்தக்க இலக்கங்களைக் கொண்டிருந்தால் தன்னிச்சையான அளவிலான சிக்கல்களை சி. கே. கே மூலம் தீர்க்க முடியும். சி. கே. கே எந்த நேரத்திலும் ஒரு வழிமுறையாகவும் இயங்க முடியும்ஃ இது முதலில் கே. கே தீர்வைக் கண்டறிந்து, பின்னர் நேரம் அனுமதிக்கும் போது படிப்படியாக சிறந்த தீர்வுகளைக் கண்டறிகிறது (மோசமான நிகழ்வுகளுக்கு உகந்த தன்மையை அடைய அதிவேக நேரம் தேவைப்படலாம்). இதற்கு இடம் தேவை, ஆனால் மோசமான நிலையில் நேரம் ஆகலாம். உட்பிரிவு தொகைக்கு உருவாக்கப்பட்ட வழிமுறைகள் பின்வருமாறுஃ ஹொரோவிட்ஸ் மற்றும் சானி-காலப்போக்கில் இயங்குகிறது, ஆனால் இடம் தேவைப்படுகிறது. ஷ்ரோப்பல் மற்றும் ஷமீர்-சரியான நேரத்தில் ஓடுகிறார்கள், அதற்கு மிகக் குறைந்த இடம் தேவைப்படுகிறது. ஹவ்கிரேவ்-கிரஹாம் மற்றும் ஜூக்ஸ்-காலப்போக்கில் இயங்குகிறது, ஆனால் இது ஒரு சீரற்ற வழிமுறையாகும், இது முடிவெடுக்கும் சிக்கலை மட்டுமே தீர்க்கிறது (உகப்பாக்கம் சிக்கல் அல்ல). கடினமான நிகழ்வுகள் மற்றும் கட்டம்-மாற்றம் செட் ஒன்று மட்டுமே, அல்லது எந்த பகிர்வுகளும் அவற்றின் உள்ளீட்டு அளவுகளுடன் ஒப்பிடும்போது தீர்க்க கடினமாக (அல்லது மிகவும் விலை உயர்ந்த) இருக்கும். தொகுப்பின் அளவுடன் ஒப்பிடும்போது மதிப்புகள் சிறியதாக இருக்கும்போது, சரியான பகிர்வுகள் அதிகமாக இருக்கும். இந்த சிக்கல் ஒரு "கட்ட மாற்றத்திற்கு" உட்படும் என்று அறியப்படுகிறது; சில செட்களுக்கு சாத்தியம் மற்றும் மற்றவர்களுக்கு சாத்தியமில்லை. m என்பது தொகுப்பில் உள்ள எந்த எண்ணையும் வெளிப்படுத்தத் தேவையான பிட்களின் எண்ணிக்கை மற்றும் n என்பது தொகுப்பின் அளவு என்றால், பல தீர்வுகளைக் கொண்டிருக்க முனைகிறது மற்றும் சில அல்லது தீர்வுகள் இல்லை. n மற்றும் m பெரியதாகும்போது, ஒரு சரியான பகிர்வின் நிகழ்தகவு முறையே 1 அல்லது 0 ஆக செல்கிறது. இது முதலில் ஜென்ட் மற்றும் வால்ஷ் ஆகியோரின் அனுபவ சான்றுகளின் அடிப்படையில் வாதிடப்பட்டது, பின்னர் மெர்டென்ஸின் புள்ளிவிவர இயற்பியலின் முறைகளைப் பயன்படுத்தி, பின்னர் போர்க்ஸ், சேஸ் மற்றும் பிட்டெல் ஆகியோரால் நிரூபிக்கப்பட்டது. நிகழ்தகவு பதிப்பு ஒரு தொடர்புடைய சிக்கல், பிறந்தநாள் முரண்பாட்டைப் போலவே, உள்ளீட்டு தொகுப்பின் அளவை தீர்மானிப்பதாகும், இதனால் தொகுப்பில் உள்ள ஒவ்வொரு உறுப்பும் தோராயமாக 1 மற்றும் சில கொடுக்கப்பட்ட மதிப்பிற்கு இடையில் சீரான விநியோகத்துடன் தேர்ந்தெடுக்கப்படுகிறது என்ற அனுமானத்தின் கீழ் ஒரு தீர்வு இருப்பதாக ஒரு பாதி நிகழ்தகவு உள்ளது. இந்த சிக்கலுக்கான தீர்வு பிறந்தநாள் முரண்பாட்டைப் போலவே எதிர் உள்ளுணர்வாக இருக்கலாம். மாறுபாடுகள் மற்றும் பொதுமைப்படுத்தல்கள் சம-கார்டினாலிட்டி பகிர்வு என்பது ஒரு மாறுபாடு ஆகும், இதில் இரு பகுதிகளும் சமமான எண்ணிக்கையிலான உருப்படிகளைக் கொண்டிருக்க வேண்டும், மேலும் சமமான தொகையைக் கொண்டிருக்க வேண்டும். இந்த மாறுபாடு NP-கடினமானது. சான்று. சில n எண்களுடன் ஒரு நிலையான பகிர்வு நிகழ்வைக் கொடுத்தால், n பூஜ்ஜியங்களைச் சேர்ப்பதன் மூலம் சம-கார்டினாலிட்டி-பகிர்வு நிகழ்வை உருவாக்குங்கள். தெளிவாக, புதிய நிகழ்வு ஒரு சம-கார்டினாலிட்டி சம-தொகை பகிர்வைக் கொண்டுள்ளது, அசல் நிகழ்வு சம-தொகை பகிர்வைக் கொண்டிருந்தால். சமநிலைப்படுத்தப்பட்ட எண் பகிர்வையும் பார்க்கவும். தனித்துவமான பகிர்வு என்பது அனைத்து உள்ளீட்டு முழு எண்களும் தனித்துவமாக இருக்கும் ஒரு மாறுபாடு ஆகும். இந்த மாறுபாடு NP-கடினமானது. தயாரிப்பு பகிர்வு என்பது ஒரு முழு எண்களின் தொகுப்பை ஒரே பெருக்கத்துடன் (ஒரே தொகையை விட) இரண்டு தொகுப்புகளாகப் பிரிப்பதில் உள்ள சிக்கலாகும். இந்த சிக்கல் வலுவாக NP-கடினமானது. கோவல்யோவ் மற்றும் பெஷ் ஆகியோர் பகிர்வு வகை சிக்கல்களின் NP-கடினத்தன்மையை நிரூபிப்பதற்கான பொதுவான அணுகுமுறையைப் பற்றி விவாதிக்கின்றனர். பயன்பாடுகள் பகிர்வு சிக்கலின் ஒரு பயன்பாடு தேர்தல்களை கையாளுவதாகும். மூன்று வேட்பாளர்கள் (ஏ, பி மற்றும் சி) உள்ளனர் என்று வைத்துக்கொள்வோம். ஒரு ஒற்றை வேட்பாளர் மதிப்பெண் அடிப்படையில் வாக்களிக்கும் விதியைப் பயன்படுத்தி தேர்ந்தெடுக்கப்பட வேண்டும், எ. கா. வீட்டோ விதி (ஒவ்வொரு வாக்காளரும் ஒரு வேட்பாளரை வீட்டோ செய்கிறார்கள், மிகக் குறைந்த வீட்டோக்களைக் கொண்ட வேட்பாளர் வெற்றி பெறுகிறார்). ஒரு கூட்டணி சி தேர்ந்தெடுக்கப்படுவதை உறுதிப்படுத்த விரும்பினால், அவர்கள் ஒவ்வொருவருக்கும் கிடைக்கும் மிகக் குறைந்த எண்ணிக்கையிலான வீட்டோக்களை அதிகரிக்க அவர்கள் தங்கள் வாக்குகளை ஏ மற்றும் பி இடையே பிரிக்க வேண்டும். வாக்குகள் எடைபோடப்பட்டால், பிரச்சினையை பகிர்வு சிக்கலாகக் குறைக்கலாம், இதனால் அதை சி. கே. கே பயன்படுத்தி திறம்பட தீர்க்க முடியும். மதிப்பெண்களை அடிப்படையாகக் கொண்ட வேறு எந்த வாக்களிப்பு விதிக்கும் இது பொருந்தும். குறிப்புகள் குறிப்புகள் எண் பகிர்வு பலவீனமான NP-முழுமையான சிக்கல்கள்