Karmarkar–Karp bin packing algorithms
கர்மார்கர்-கார்ப் (கே. கே.) தொட்டி பொதி செய்யும் வழிமுறைகள் தொட்டி பொதி செய்யும் சிக்கலுக்கான பல தொடர்புடைய தோராயமான வழிமுறைகள் ஆகும். தொட்டி பொதி சிக்கல் என்பது வெவ்வேறு அளவிலான பொருட்களை ஒரே மாதிரியான திறன் கொண்ட தொட்டிகளில் பொதி செய்வதில் உள்ள ஒரு சிக்கலாகும், அதாவது மொத்த தொட்டிகளின் எண்ணிக்கை முடிந்தவரை சிறியதாக இருக்கும். உகந்த தீர்வை கண்டுபிடிப்பது கணக்கீட்டு ரீதியாக கடினம். கர்மார்கர் மற்றும் கார்ப் ஒரு வழிமுறையை உருவாக்கினர், இது பல்லுறுப்புக்கோவை நேரத்தில் இயங்குகிறது மற்றும் அதிகபட்ச தொட்டிகளுடன் ஒரு தீர்வை கண்டுபிடிக்கும், இதில் ஓபிடி என்பது உகந்த தீர்வில் உள்ள தொட்டிகளின் எண்ணிக்கை. சற்று வித்தியாசமான தோராய உத்தரவாதங்கள் மற்றும் இயக்க நேர வரம்புகளுடன் வேறு பல வழிமுறைகளையும் அவர்கள் உருவாக்கினர். கே. கே வழிமுறைகள் தொட்டி பொதி செய்யும் ஆய்வில் ஒரு திருப்புமுனையாக கருதப்பட்டனஃ முன்பு அறியப்பட்ட வழிமுறைகள் பெருக்க தோராயத்தைக் கண்டறிந்தன, அங்கு தொட்டிகளின் எண்ணிக்கை சில மாறிலிகளுக்கு அதிகபட்சமாக இருந்தது, அல்லது அதிகபட்சமாக. கே. கே. வழிமுறைகள் தான் முதலில் ஒரு சேர்க்கை தோராயத்தை அடைந்தன. உள்ளீடு ஒரு தொட்டி பொதி சிக்கலுக்கான உள்ளீடு வெவ்வேறு அளவுகளின் உருப்படிகளின் தொகுப்பாகும், a1,. an. பின்வரும் குறியீடு பயன்படுத்தப்படுகிறதுஃ n-உருப்படிகளின் எண்ணிக்கை. m-வெவ்வேறு உருப்படி அளவுகளின் எண்ணிக்கை. 1 இல் உள்ள ஒவ்வொரு ஐக்கும், மீஃ சி என்பது ஐ-வது அளவு; நி என்பது அளவு சி கொண்ட பொருட்களின் எண்ணிக்கை. பி-தொட்டி அளவு. ஒரு எடுத்துக்காட்டு I ஐப் பொறுத்தவரை, நாம் பின்வருவனவற்றைக் குறிக்கிறோம்ஃ ஒபிடி (ஐ) = எடுத்துக்காட்டு I இன் உகந்த தீர்வு. எஃப்ஓபிடி (ஐ) = (ஏ1 +. + அன்)/பி = கோட்பாட்டளவில் உகந்த எண்ணிக்கையிலான தொட்டிகள், அனைத்து தொட்டிகளும் உருப்படிகள் அல்லது உருப்படி பின்னங்களால் முழுமையாக நிரப்பப்படும் போது. வெளிப்படையாக, FOPT (I) ≤ OPT (I). உயர் நிலை திட்டம் கேகே வழிமுறைகள் அடிப்படையில் உள்ளமைவு நேரியல் நிரலை தீர்க்கின்றனஃ இங்கே, ஏ என்பது எம் வரிசைகளைக் கொண்ட ஒரு அணி. A இன் ஒவ்வொரு நெடுவரிசையும் ஒரு சாத்தியமான உள்ளமைவைக் குறிக்கிறது-உருப்படி அளவுகளின் பல தொகுப்பு, அதாவது இந்த அளவுகள் அனைத்தின் கூட்டுத்தொகையும் அதிகபட்சம் B ஆகும். உள்ளமைவுகளின் தொகுப்பு சி. x என்பது சி அளவு கொண்ட ஒரு திசையன். x இன் ஒவ்வொரு உறுப்பு xc அமைவு சி பயன்படுத்தப்படும் நேரங்களின் எண்ணிக்கையைக் குறிக்கிறது. எடுத்துக்காட்டுஃ உருப்படி அளவுகள் 3,3,3,3,3,4,4,4,4,4, மற்றும் B = 12 என்று வைத்துக்கொள்வோம். பின்னர் சி = 10 சாத்தியமான உள்ளமைவுகள் உள்ளனஃ 3333; 333; 33,334,344; 4,44,444. அணி A க்கு இரண்டு வரிசைகள் உள்ளனஃ s = 3 க்கு [4,3,2,2,1,1,1,0,0,0] மற்றும் s = 4 க்கு [0,0,0,1,0,1,2,1,2,3]. ஒவ்வொரு அளவிலும் 5 உருப்படிகள் இருப்பதால் திசையன் n என்பது [5,5] ஆகும். சாத்தியமான உகந்த தீர்வு x = [1,0,0,0,0,0,1,0,0,1], இது 3333,344,444 உள்ளமைவுகளுடன் மூன்று தொட்டிகளைப் பயன்படுத்துவதற்கு ஒத்ததாகும். இந்தப் பிரச்சினையைத் தீர்ப்பதில் இரண்டு முக்கிய சிக்கல்கள் உள்ளன. முதலாவதாக, இது ஒரு முழு எண் நேரியல் நிரலாகும், இது கணக்கீட்டு ரீதியாக தீர்க்க கடினமாக உள்ளது. இரண்டாவதாக, மாறிகளின் எண்ணிக்கை சி-உள்ளமைவுகளின் எண்ணிக்கை, இது மிகப்பெரியதாக இருக்கலாம். கே. கே வழிமுறைகள் பல நுட்பங்களைப் பயன்படுத்தி இந்த சிரமங்களைச் சமாளிக்கின்றன, அவற்றில் சில ஏற்கனவே டி-லா-வேகா மற்றும் லுக்கர் ஆகியோரால் அறிமுகப்படுத்தப்பட்டன. இங்கே வழிமுறை ஒரு உயர் நிலை விளக்கம் (எங்கே அசல் நிகழ்வு): 1-அ. சிறிய பொருட்களை அகற்றுவதன் மூலம் கட்டமைக்கப்பட்ட ஒரு எடுத்துக்காட்டாக இருக்கட்டும். 2-அ. உருப்படிகளை தொகுப்பதன் மூலமும், ஒவ்வொரு குழுவிலும் உள்ள உருப்படிகளின் அளவை குழுவில் உள்ள மிக உயர்ந்த உருப்படியுடன் வட்டமிடுவதன் மூலமும் கட்டமைக்கப்பட்ட ஒரு எடுத்துக்காட்டாக இருக்கட்டும். 3-அ. ஒருங்கிணைப்பு கட்டுப்பாடுகள் இல்லாமல், உள்ளமைவு நேரியல் நிரலை உருவாக்குங்கள். 4. தளர்த்தப்பட்ட நேரியல் நிரலுக்கு a (பின்ன) தீர்வு x ஐக் கணக்கிடுங்கள். 3-பி. ஒரு ஒருங்கிணைந்த தீர்வுக்கு x ஐ சுற்றவும். 2-பி. ஒரு தீர்வைப் பெற உருப்படிகளை "குழுவிலக்கு". 1-பி. ஒரு தீர்வைப் பெற சிறிய பொருட்களைச் சேர்க்கவும். கீழே, இந்த படிகள் ஒவ்வொன்றையும் ஒவ்வொன்றாக விவரிக்கிறோம். படி 1. சிறிய உருப்படிகளை நீக்குவது மற்றும் சேர்ப்பது சிறிய உருப்படிகளை அகற்றுவதற்கான உந்துதல் என்னவென்றால், அனைத்து உருப்படிகளும் பெரியதாக இருக்கும்போது, ஒவ்வொரு தொட்டியிலும் உள்ள உருப்படிகளின் எண்ணிக்கை சிறியதாக இருக்க வேண்டும், எனவே சாத்தியமான உள்ளமைவுகளின் எண்ணிக்கை (ஒப்பீட்டளவில்) சிறியதாக இருக்கும். நாம் சில மாறிலிகளைத் தேர்ந்தெடுத்து, அதை விட சிறிய அனைத்து உருப்படிகளையும் அசல் நிகழ்விலிருந்து அகற்றுகிறோம். இதன் விளைவாக நிகழும் நிகழ்வாக இருக்கட்டும். ஒவ்வொரு தொட்டியிலும் பெரும்பாலான பொருட்கள் இருக்கலாம் என்பதை நினைவில் கொள்க. நாங்கள் பேக் செய்து சில தொட்டிகளுடன் ஒரு பேக்கிங் பெறுகிறோம். இப்போது, சிறிய உருப்படிகளை ஏற்கனவே இருக்கும் தொட்டிகளில் தன்னிச்சையான வரிசையில் சேர்க்கிறோம், இடம் இருக்கும் வரை. தற்போதுள்ள தொட்டிகளில் அதிக இடம் இல்லாதபோது, நாம் ஒரு புதிய தொட்டியைத் திறக்கிறோம் (அடுத்த பொருத்தமான தொட்டி பொதிகளைப் போல). இறுதி பேக்கிங்கில் உள்ள தொட்டிகளின் எண்ணிக்கையாக இருக்கட்டும். பிறகுஃ ஆதாரம். புதிய தொட்டிகள் திறக்கப்படாவிட்டால், தொட்டிகளின் எண்ணிக்கை இருக்கும். ஒரு புதிய தொட்டி திறக்கப்பட்டால், கடைசி தொட்டியைத் தவிர அனைத்து தொட்டிகளும் குறைந்தபட்சம் மொத்த அளவைக் கொண்டிருக்கலாம், எனவே மொத்த நிகழ்வு அளவு குறைந்தபட்சம் இருக்கும். எனவே, உகந்த தீர்வுக்கு குறைந்தபட்சம் தொட்டிகளாவது தேவை. எனவே. குறிப்பாக, g = 1/n ஐ எடுத்துக்கொள்வதன் மூலம், நாம் பெறுகிறோம்ஃ, ஏனெனில். எனவே, அனைத்து பொருட்களும் 1/n ஐ விட பெரியவை என்று கருதுவது பொதுவானது. படி 2. உருப்படிகளை தொகுத்தல் மற்றும் தொகுக்காதது உருப்படிகளை தொகுப்பதற்கான உந்துதல் வெவ்வேறு உருப்படி அளவுகளின் எண்ணிக்கையைக் குறைப்பதும், உள்ளமைவு LP இல் உள்ள கட்டுப்பாடுகளின் எண்ணிக்கையைக் குறைப்பதும் ஆகும். பொதுவான தொகுப்பு செயல்முறைஃ இறங்கு அளவு மூலம் பொருட்களை வரிசைப்படுத்துங்கள். பொருட்களை குழுக்களாகப் பிரிக்கவும். ஒவ்வொரு குழுவிற்கும், குழுவில் உள்ள அனைத்து பொருட்களின் அளவையும் குழுவில் உள்ள மிகப்பெரிய அளவிற்கு மாற்றவும். பல்வேறு வகைப்படுத்தல் முறைகள் உள்ளன. நேரியல் தொகுப்பு ஒரு முழு எண் அளவுருவாக இருக்கட்டும். குழு 1 இல் மிகப்பெரிய உருப்படிகளை வைக்கவும்; குழு 2 இல் அடுத்த பெரிய உருப்படிகள்; மற்றும் பல (கடைசி குழுவில் உருப்படிகளை விட குறைவாக இருக்கலாம்). அசல் உதாரணமாக இருக்கட்டும். முதல் குழு (மிகப்பெரிய பொருட்களின் குழு) மற்றும் முதல் குழு இல்லாமல் குழுப்படுத்தப்பட்ட நிகழ்வாக இருக்கட்டும். பின்னர்ஃ அனைத்து பொருட்களிலும் ஒரே அளவு இருக்கும். வெவ்வேறு அளவுகளின் எண்ணிக்கையில் உள்ளது. - குழு 1 இல் குழு 2 இல் ஆதிக்கம் செலுத்துவதால் (குழு 1 இல் உள்ள அனைத்து k உருப்படிகளும் குழு 2 இல் உள்ள k உருப்படிகளை விட பெரியவை); இதேபோல், குழு 2 இல் குழு 3 இல் ஆதிக்கம் செலுத்துகிறது. - ஒவ்வொரு பொருளையும் ஒரே தொட்டியில் அடைக்க முடியும் என்பதால். எனவே, உண்மையில், தொட்டிகளுடன் ஒரு தீர்வைக் கொடுத்தால், பெரும்பாலான தொட்டிகளுடன் ஒரு தீர்வைப் பெறலாம். வடிவியல் தொகுப்பு ஒரு முழு எண் அளவுருவாக இருக்கட்டும். வடிவியல் தொகுப்பு இரண்டு படிகளில் தொடர்கிறதுஃ ஒவ்வொரு நிகழ்விலும், அனைத்து அளவுகளும் இடைவெளியில் இருக்கும் வகையில் நிகழ்வை பல நிகழ்வுகளாகப் பிரிக்கவும். அனைத்து உருப்படிகளும் குறைந்தபட்சம் அளவைக் கொண்டிருந்தால், நிகழ்வுகளின் எண்ணிக்கை அதிகபட்சமாக இருக்கும் என்பதை நினைவில் கொள்க. ஒவ்வொரு நிகழ்விலும், அளவுருவுடன் நேரியல் வட்டமிடுதல் செய்யுங்கள். இதன் விளைவாக வரும் நிகழ்வுகளாக இருக்கட்டும். மற்றும் விடுங்கள். பின்னர், வெவ்வேறு அளவுகளின் எண்ணிக்கை பின்வருமாறு வரையறுக்கப்படுகிறதுஃ அனைத்து r க்கும், மற்றும். உள்ள அனைத்து பொருட்களும் அதை விட பெரியவை என்பதால், எங்களிடம் உள்ளது. அனைத்து r க்கும் சுருக்கமாக கொடுக்கிறது. தொட்டிகளின் எண்ணிக்கை பின்வருமாறு வரையறுக்கப்பட்டுள்ளதுஃ அனைத்து r க்கும்,-உருப்படிகள் இருப்பதால், அவை அனைத்தும் சிறியவை, எனவே அவற்றை பெரும்பாலான தொட்டிகளில் பேக் செய்யலாம். எனவே, எனவே, மாற்று வடிவியல் தொகுப்பு ஒரு முழு எண் அளவுருவாக இருக்கட்டும். இறங்கு அளவு மூலம் பொருட்களை ஆர்டர் செய்யுங்கள். ஒவ்வொரு குழுவிலும் உள்ள மொத்த அளவு குறைந்தபட்சம் இருக்கும் வகையில் அவற்றை குழுக்களாகப் பிரிக்கவும். ஒவ்வொரு பொருளின் அளவும் B ஐ விட குறைவாக இருப்பதால், ஒவ்வொரு குழுவிலும் உள்ள பொருட்களின் எண்ணிக்கை குறைந்தது. ஒவ்வொரு குழுவிலும் உள்ள பொருட்களின் எண்ணிக்கை பலவீனமாக அதிகரித்து வருகிறது. அனைத்து உருப்படிகளும் அதை விட பெரியதாக இருந்தால், ஒவ்வொரு குழுவிலும் உள்ள உருப்படிகளின் எண்ணிக்கை அதிகபட்சமாக இருக்கும். ஒவ்வொரு குழுவிலும், பெரிய உருப்படிகள் மட்டுமே வட்டமிடப்படுகின்றன. இதை இவ்வாறு செய்யலாம்ஃ . படி 3. LP ஐ உருவாக்குதல் மற்றும் தீர்வை வட்டமிடுதல் ஒருங்கிணைந்த கட்டுப்பாடுகள் இல்லாமல் உள்ளமைவு நேரியல் நிரலை நாம் கருதுகிறோம்ஃ இங்கே, ஒவ்வொரு உள்ளமைவின் பின்ன எண்ணைப் பயன்படுத்த அனுமதிக்கப்படுகிறோம். எடுத்துக்காட்டுஃ அளவு 3 கொண்ட 31 உருப்படிகளும் அளவு 4 கொண்ட 7 உருப்படிகளும் உள்ளன என்று வைத்துக்கொள்வோம், தொட்டி அளவு 10 ஆகும். கட்டமைப்புகள்ஃ 4,44,34,334,3,33,333. கட்டுப்பாடுகள் [0,0,1,2,1,2,3] * x = 31 மற்றும் [1,2,1,1,0,0,0] * x = 7 ஆகும். பின்ன LP க்கு ஒரு உகந்த தீர்வு [0,0,0,7,0,0,17/3] அதாவதுஃ உள்ளமைவு 334 மற்றும் 17/3 உள்ளமைவு 333 இன் 7 தொட்டிகள் உள்ளன. இரண்டு வெவ்வேறு உள்ளமைவுகள் மட்டுமே தேவை என்பதை நினைவில் கொள்க. நேரியல் நிரலின் உகந்த தீர்வை எல்ஓபிடி மூலம் குறிக்கவும். பின்வரும் தொடர்புகள் வெளிப்படையானவைஃ FOPT (I) ≤ LOPT (I), ஏனெனில் அனைத்து தொட்டிகளும் உருப்படிகள் அல்லது பொருட்களின் பின்னங்களால் முழுமையாக நிரப்பப்படும் போது FOPT (I) என்பது தொட்டிகளின் (ஒருவேளை பகுதியளவு) எண்ணிக்கையாகும். எந்தவொரு தீர்வும் மிகவும் திறமையானதாக இருக்க முடியாது என்பது தெளிவாகிறது. எல்ஓபிடி (I) என்பது குறைவான கட்டுப்பாடுகளுடன் கூடிய மினிமைசேஷன் சிக்கலுக்கான தீர்வாக இருப்பதால், எல்ஓபிடி (I) ≤ ஓபிடி (I) ஆகும். ஓபிடி (ஐ) <2 * ஓபிடி (ஐ), குறைந்தபட்சம் 2 * ஓபிடி (ஐ) தொட்டிகளைக் கொண்ட எந்தவொரு பொதியிலும், குறைந்தபட்சம் நிரப்பப்பட்ட இரண்டு தொட்டிகளின் கூட்டுத்தொகை அதிகபட்சம் பி ஆகும், எனவே அவற்றை ஒரே தொட்டியில் இணைக்கலாம். பின்ன எல். பி. க்கான ஒரு தீர்வை பின்வருமாறு ஒரு ஒருங்கிணைந்த தீர்வுக்கு வட்டமிடலாம். பின்ன எல். பி. க்கு x என்ற தீர்வு நம்மிடம் உள்ளது என்று வைத்துக்கொள்வோம். ஒருங்கிணைந்த ஐஎல்பி-க்கான தீர்வாக x ஐ பின்வருமாறு சுற்றுவோம். x என்பது பின்ன LP இன் உகந்த அடிப்படை சாத்தியமான தீர்வாக இருக்கட்டும். இது தொட்டிகள் என்று வைத்துக்கொள்வோம் (இது ஒரு பின்ன எண்ணாக இருக்கலாம் என்பதைக் கவனியுங்கள்). பின்ன LP க்கு m கட்டுப்பாடுகள் இருப்பதால் (ஒவ்வொரு தனித்துவமான அளவிற்கும் ஒன்று), x அதிகபட்சம் m பூஜ்ஜியமற்ற மாறிகளைக் கொண்டுள்ளது, அதாவது அதிகபட்சம் m வெவ்வேறு உள்ளமைவுகள் பயன்படுத்தப்படுகின்றன. x இலிருந்து ஒரு முக்கிய பகுதியையும் எஞ்சிய பகுதியையும் கொண்ட ஒரு ஒருங்கிணைந்த பொதிகளை நாம் உருவாக்குகிறோம். முதன்மைப் பகுதியில் ஒவ்வொரு கட்டமைப்பு c இன் தரை (xc) தொட்டிகள் உள்ளன, இதற்கு xc> 0 ஆகும். எஞ்சிய பகுதிக்கு (R ஆல் குறிக்கப்படுகிறது), நாம் இரண்டு கேண்டிடேட் பேக்கிங்குகளை உருவாக்குகிறோம்ஃ ஒவ்வொரு உள்ளமைவிலும் ஒரு ஒற்றை தொட்டி c க்கு xc> 0; அனைத்து m தொட்டிகளிலும் தேவை. 2 * க்கும் குறைவான ஃபோப்ட் (ஆர்) தொட்டிகளுடன் ஒரு பேராசை பேக்கிங் (குறைந்தது 2 * ஃபோப்ட் (ஆர்) தொட்டிகள் இருந்தால், இரண்டு மிகச்சிறிய தொட்டிகளையும் இணைக்கலாம்). இந்த பொதிகளில் மிகச் சிறியது குறைந்தபட்சம் (மீ, 2 * எஃப்ஓபிடி (ஆர்)) ≤ சராசரி (மீ, 2 * எஃப்ஓபிடி (ஆர்)) = எஃப்ஓபிடி (ஆர்) + எம்/2 தேவைப்படுகிறது. இதனுடன் சேர்த்து, பிரதான பகுதியின் வட்டமான தொட்டிகள் பெரும்பாலான தொட்டிகளில் விளைச்சல் அளிக்கின்றன. இந்த மாற்று வழிமுறையின் செயலாக்க நேரம் O (n log n) ஆகும். இதுவும் அதையே குறிக்கிறது. படி 4. பின்ன எல். பி. யைத் தீர்ப்பதில் உள்ள முக்கிய சவால் என்னவென்றால், அது ஒரு பெரிய எண்ணிக்கையிலான மாறிகளைக் கொண்டிருக்கலாம்-ஒவ்வொரு சாத்தியமான உள்ளமைவிற்கும் ஒரு மாறி. இரட்டை LP பின்ன LP இன் இரட்டை நேரியல் நிரல்ஃ இது m மாறிகள் மற்றும் C கட்டுப்பாடுகளைக் கொண்டுள்ளது-ஒவ்வொரு உள்ளமைவிற்கும் ஒரு கட்டுப்பாடு. இது பின்வரும் பொருளாதார விளக்கத்தைக் கொண்டுள்ளது. ஒவ்வொரு அளவு s க்கும், எதிர்மறை அல்லாத விலையை நாம் தீர்மானிக்க வேண்டும். நமது லாபம் என்பது அனைத்து பொருட்களின் மொத்த விலையாகும். ஒவ்வொரு கட்டமைப்பிலும் உள்ள பொருட்களின் மொத்த விலை அதிகபட்சம் 1 என்ற வரம்புகளுக்கு உட்பட்டு லாபத்தை அதிகரிக்க விரும்புகிறோம். இந்த LP இப்போது m மாறிகள் மட்டுமே உள்ளது, ஆனால் ஒரு பெரிய எண்ணிக்கையிலான கட்டுப்பாடுகள் உள்ளன. அனைத்து கட்டுப்பாடுகளையும் பட்டியலிடுவது கூட சாத்தியமற்றது. அதிர்ஷ்டவசமாக, நீள்வட்ட முறையின் மாறுபாட்டைப் பயன்படுத்தி, அனைத்து கட்டுப்பாடுகளையும் பட்டியலிடாமல் எந்தவொரு குறிப்பிட்ட துல்லியத்திற்கும் சிக்கலை தீர்க்க முடியும். இந்த மாறுபாடு உள்ளீடாக பெறுகிறது, ஒரு பிரிப்பு ஆரக்கிள்ஃ ஒரு திசையன் y ≤ 0 கொடுக்கப்பட்ட ஒரு செயல்பாடு, பின்வரும் இரண்டு விருப்பங்களில் ஒன்றைத் தருகிறதுஃ y சாத்தியமானது என்று உறுதிப்படுத்தவும், அதாவது, அல்லது-y சாத்தியமற்றது என்று உறுதிப்படுத்தவும், மீறப்பட்ட ஒரு குறிப்பிட்ட கட்டுப்பாட்டைத் திருப்பவும், அதாவது, ஒரு திசையன் a. நீள்வட்ட முறை ஒரு பெரிய நீள்வட்டத்துடன் தொடங்குகிறது, இது முழு சாத்தியமான களத்தையும் கொண்டுள்ளது. ஒவ்வொரு படிநிலையிலும் t, தற்போதைய நீள்வட்டத்தின் மையத்தை எடுத்து, அதை பிரிப்பு ஆரக்கிளுக்கு அனுப்புகிறதுஃ ஆரக்கிள் அது சாத்தியம் என்று சொன்னால், நாம் ஒரு "உகந்த வெட்டு" செய்கிறோம்ஃ நீள்வட்டத்திலிருந்து அனைத்து புள்ளிகளையும் y க்கு வெட்டுகிறோம். இந்த புள்ளிகள் நிச்சயமாக உகந்தவை அல்ல. ஆரக்கிள் அது சாத்தியமற்றது என்று கூறி, கட்டுப்பாடு a ஐ மீறினால், நாம் ஒரு "சாத்தியக்கூறு வெட்டு" செய்கிறோம்ஃ நீள்வட்டத்திலிருந்து அனைத்து புள்ளிகளையும் y க்கு வெட்டுகிறோம். இந்த புள்ளிகள் நிச்சயமாக சாத்தியமற்றவை. ஒரு வெட்டு செய்த பிறகு, ஒரு புதிய, சிறிய நீள்வட்டத்தை உருவாக்குகிறோம். இந்த செயல்முறை ஒரு தோராயமான தீர்வாக, நேர பல்லுறுப்புக்கோவையில் தேவையான துல்லியத்தில் ஒருங்கிணைக்கிறது என்பதைக் காட்டலாம். இரட்டை LP க்கான ஒரு பிரிப்பு ஆரக்கிள் நமக்கு சில m எதிர்மறை அல்லாத எண்கள் வழங்கப்படுகின்றன. பின்வரும் இரண்டு விருப்பங்களுக்கு இடையில் நாம் முடிவு செய்ய வேண்டும்ஃ ஒவ்வொரு சாத்தியமான உள்ளமைவிற்கும், இந்த உள்ளமைவுடன் தொடர்புடைய கூட்டுத்தொகை அதிகபட்சம் 1 ஆகும்; இதன் பொருள் y சாத்தியமானது. ஒரு சாத்தியமான உள்ளமைவு உள்ளது, இதற்கு கூட்டுத்தொகை 1 ஐ விட பெரியது; இதன் பொருள் y சாத்தியமற்றது. இந்த விஷயத்தில், நாம் உள்ளமைவையும் திருப்பித் தர வேண்டும். இந்த சிக்கலை ஒரு நாப்சாக் சிக்கலைத் தீர்ப்பதன் மூலம் தீர்க்க முடியும், அங்கு உருப்படி மதிப்புகள், உருப்படி எடைகள் மற்றும் எடை திறன் பி (தொட்டி அளவு). உகந்த நாப்சாக் கரைசலின் மொத்த மதிப்பு அதிகபட்சம் 1 ஆக இருந்தால், y சாத்தியமானது என்று நாம் கூறுகிறோம். உகந்த நாப்சாக் கரைசலின் மொத்த மதிப்பு 1 ஐ விட அதிகமாக இருந்தால், y சாத்தியமற்றது என்றும், உகந்த நாப்சாக் கரைசலில் உள்ள உருப்படிகள் ஒரு கட்டுப்பாட்டை மீறும் ஒரு உள்ளமைவுடன் ஒத்திருக்கின்றன என்றும் நாம் கூறுகிறோம் (ஏனெனில் இந்த உள்ளமைவுக்கு ஒத்த திசையன் a). நாப்சாக் சிக்கலை போலி-பல்லுறுப்புக்கோவை நேரத்தில் மாறும் நிரலாக்கத்தால் தீர்க்க முடியும்ஃ, இங்கு m என்பது உள்ளீடுகளின் எண்ணிக்கை மற்றும் V என்பது வெவ்வேறு சாத்தியமான மதிப்புகளின் எண்ணிக்கை. ஒரு பல்லுறுப்புக்கோவை-நேர வழிமுறையைப் பெற, உள்ளீட்டு வட்டத்தைப் பயன்படுத்தி நாப்ஸாக் சிக்கலை தோராயமாக தீர்க்க முடியும். சகிப்புத்தன்மையுடன் ஒரு தீர்வை நாம் விரும்புகிறோம் என்று வைத்துக்கொள்வோம். நாம் ஒவ்வொன்றையும்/n இன் அருகிலுள்ள பெருக்கல் வரை வட்டமிடலாம். பின்னர், 0 மற்றும் 1 க்கு இடையில் சாத்தியமான மதிப்புகளின் எண்ணிக்கை n/, மற்றும் இயக்க நேரம். குறைந்தபட்சம் உகந்த தீர்வு கழித்தல்/n ஆகும். தோராயமான பிரிப்பு ஆரக்கிள் கொண்ட நீள்வட்ட முறை நீள்வட்ட முறை தோராயமான பிரிப்பு ஆரக்கிளைப் பயன்படுத்த மாற்றியமைக்கப்பட வேண்டும். தற்போதைய நீள்வட்ட மையத்தைப் பொறுத்தவரைஃ தோராயமான ஆரக்கிள் 1 ஐ விட பெரிய மதிப்புள்ள ஒரு தீர்வைத் திருப்பித் தந்தால், அது நிச்சயமாக சாத்தியமற்றது, மேலும் தீர்வு ஒரு தடையை மீறும் ஒரு உள்ளமைவுக்கு ஒத்திருக்கிறது. நாம் ஒரு "சாத்தியக்கூறு வெட்டு" செய்கிறோம், நீள்வட்டத்தை அனைத்து புள்ளிகளையும் குறைக்கிறோம். தோராயமான ஆரக்கிள் அதிகபட்சம் 1 மதிப்புடன் ஒரு தீர்வைத் திருப்பித் தந்தால், அது சாத்தியமானதாகவோ அல்லது சாத்தியமற்றதாகவோ இருக்கலாம், ஆனால் வட்டமிடுவது (அதைக் குறிக்கிறது) சாத்தியமாகும். வட்டத்தின் வரையறையின்படி, அது நமக்குத் தெரியும். நாம் இன்னும் ஒரு "உகந்த வெட்டு" செய்கிறோம்ஃ நீள்வட்டத்திலிருந்து அனைத்து புள்ளிகளையும் y க்கு வெட்டுகிறோம். இது சாத்தியமற்றதாக இருக்கலாம், எனவே அதன் மதிப்பு ஓ. பி. டி. யை விட அதிகமாக இருக்கலாம். எனவே, உகந்த நோக்கம் கொண்ட சில புள்ளிகளை நாம் அகற்றலாம். இருப்பினும், அகற்றப்பட்ட புள்ளிகள் திருப்தி அளிக்கின்றன; அதன் மதிப்பு மதிப்பை விட அதிகமாக இருந்தால் எந்த புள்ளியும் அகற்றப்படாது. தோராயமான பிரிப்பு ஆரக்கிளைப் பயன்படுத்துவது இரட்டை LP க்கு ஒரு சாத்தியமான தீர்வை y * வழங்குகிறது, அதிகபட்ச மறு செய்கைகளுக்குப் பிறகு, எங்கே. தோராயமான பிரிப்பு ஆரக்கிள் கொண்ட நீள்வட்ட முறையின் மொத்த இயக்க நேரம். எலிப்சாய்டு முறையின் போது, வடிவத்தின் அதிகபட்ச க்யூ கட்டுப்பாடுகளைப் பயன்படுத்துகிறோம். நீள்வட்ட முறையின் y * விளைவில் அவை எந்த விளைவையும் ஏற்படுத்தாததால், மற்ற அனைத்து கட்டுப்பாடுகளையும் அகற்ற முடியும். இன்னும் அதிகமான கட்டுப்பாடுகளை நாம் அகற்ற முடியும். m மாறிகள் கொண்ட எந்த LP யிலும், உகந்த தீர்வை தீர்மானிக்க போதுமான m கட்டுப்பாடுகளின் தொகுப்பு உள்ளது என்பது அறியப்படுகிறது (அதாவது, இந்த m கட்டுப்பாடுகள் மட்டுமே பயன்படுத்தப்பட்டாலும் உகந்த மதிப்பு ஒரே மாதிரியாக இருக்கும்). மேலே உள்ளபடி நீள்வட்ட முறையை நாம் மீண்டும் மீண்டும் இயக்கலாம், ஒவ்வொரு முறையும் ஒரு குறிப்பிட்ட கட்டுப்பாடுகளை அகற்ற முயற்சி செய்யலாம். இதன் விளைவாக ஏற்படும் பிழை அதிகபட்சமாக இருந்தால், இந்த கட்டுப்பாடுகளை நிரந்தரமாக அகற்றுவோம். நமக்கு அதிகபட்ச நீக்குதல்கள் தேவை என்பதைக் காட்டலாம், எனவே குவிப்பு பிழை அதிகபட்சமாக உள்ளது. நாம் கட்டுப்பாடுகளின் தொகுப்புகளை தீர்மானகரமாக முயற்சித்தால், மோசமான நிலையில், எம் சோதனைகளில் ஒன்று வெற்றி பெறுகிறது, எனவே பெரும்பாலான நேரங்களில் நீள்வட்ட முறையை இயக்க வேண்டும். சீரற்ற முறையில் அகற்றுவதற்கான கட்டுப்பாடுகளை நாம் தேர்வுசெய்தால், எதிர்பார்க்கப்படும் எண்ணிக்கையிலான மறு செய்கைகள். இறுதியாக, நம்மிடம் குறைக்கப்பட்ட இரட்டை LP உள்ளது, m மாறிகள் மற்றும் m கட்டுப்பாடுகள் மட்டுமே உள்ளன. குறைக்கப்பட்ட LP இன் உகந்த மதிப்பு குறைந்தபட்சம், எங்கே. முதன்மை LP ஐத் தீர்ப்பது LP இரட்டைத்தன்மை தேற்றத்தின் மூலம், முதன்மை LP இன் குறைந்தபட்ச மதிப்பு இரட்டை LP இன் அதிகபட்ச மதிப்புக்கு சமம், இதை நாம் LOPT ஆல் குறிக்கிறோம். குறைக்கப்பட்ட இரட்டை LP ஐப் பெற்றவுடன், அதன் இரட்டை LP ஐ எடுத்து, குறைக்கப்பட்ட முதன்மை LP ஐ எடுத்துக்கொள்கிறோம். இந்த LP இல் m மாறிகள் மட்டுமே உள்ளன-இது C உள்ளமைவுகளில் m க்கு மட்டுமே தொடர்புடையது. குறைக்கப்பட்ட இரட்டை எல்பியின் அதிகபட்ச மதிப்பு குறைந்தபட்சம். குறைக்கப்பட்ட முதன்மையான LP இன் உகந்த தீர்வு அதிகபட்சமாக உள்ளது என்பதைக் காட்டலாம். இந்த தீர்வு அதிகபட்சம் m உள்ளமைவுகளைப் பயன்படுத்தி உகந்த தொட்டி பொதிகளை வழங்குகிறது. தீர்மானகரமான வழிமுறையின் மொத்த இயக்க நேரம், அனைத்து உருப்படிகளும் அதை விட பெரியதாக இருக்கும்போது, இதுஃ சீரற்ற வழிமுறையின் எதிர்பார்க்கப்படும் மொத்த இயக்க நேரம்ஃ எண்ட்-டு-எண்ட் வழிமுறைகள் கர்மார்கர் மற்றும் கார்ப் மூன்று வழிமுறைகளை வழங்கினர், அவை மேலே உள்ள நுட்பங்களை வெவ்வேறு அளவுருக்களுடன் பயன்படுத்துகின்றன. இந்த அனைத்து வழிமுறைகளின் இயக்க நேரமும் ஒரு செயல்பாட்டைப் பொறுத்தது, இது ஒரு பல்லுறுப்புக்கோவை செயல்பாடாகும், இது பின்ன LP ஐ சகிப்புத்தன்மை h = 1 உடன் தீர்க்க எடுக்கும் நேரத்தை விவரிக்கிறது, அதாவது, தீர்மானகரமான பதிப்பிற்கு,. அல்காரிதம் 1 விரும்பிய தோராய துல்லியத்தைக் குறிக்கும் ஒரு மாறிலியாக இருக்கட்டும். 1-ஏ. செட். g. 2-a ஐ விட சிறிய அனைத்து பொருட்களையும் அகற்றுவதன் மூலம் கட்டமைக்கப்பட்ட ஒரு எடுத்துக்காட்டாக இருக்கட்டும். செட். k அளவுருவுடன் நேரியல் குழுவால் கட்டமைக்கப்பட்ட ஒரு நிகழ்வாக இருக்கட்டும், மீதமுள்ள நிகழ்வாக இருக்கட்டும் (k மிகப்பெரிய உருப்படிகளின் குழு). என்பதைக் கவனத்தில் கொள்ளுங்கள். 3-அ. ஒருங்கிணைப்பு கட்டுப்பாடுகள் இல்லாமல், உள்ளமைவு நேரியல் நிரலை உருவாக்குங்கள். 4. சகிப்புத்தன்மை h = 1 உடன் x என்ற தீர்வை கணக்கிடுங்கள். இதன் விளைவாக தொட்டிகளுடன் ஒரு பகுதியளவு தொட்டி பொதி செய்யப்படுகிறது. ரன்-டைம். 3-பி. ஒரு ஒருங்கிணைந்த தீர்வுக்கு x ஐ சுற்றவும். பின்னப் பகுதிக்கு பெரும்பாலான தொட்டிகளில் சேர்க்கவும். தொட்டிகளின் மொத்த எண்ணிக்கை. 2-பி. அதிகபட்ச கே தொட்டிகளில் பொருட்களை பேக் செய்யுங்கள்; ஒரு பேக்கிங் பெறுங்கள். தொட்டிகளின் எண்ணிக்கை. 1-பி. ஒரு தீர்வைப் பெற g ஐ விட சிறிய உருப்படிகளைச் சேர்க்கவும். தொட்டிகளின் எண்ணிக்கைஃ மொத்தத்தில், தொட்டிகளின் எண்ணிக்கை உள்ளது மற்றும் இயக்க நேரம் உள்ளது. தேர்ந்தெடுப்பதன் மூலம் நாம் பெறுகிறோம். அல்காரிதம் 2 ஒரு உண்மையான அளவுருவாகவும், பின்னர் தீர்மானிக்கப்பட வேண்டிய ஒரு முழு எண் அளவுருவாகவும் இருக்கட்டும். 1-ஏ. g. 2 ஐ விட சிறிய அனைத்து பொருட்களையும் அகற்றுவதன் மூலம் கட்டமைக்கப்பட்ட ஒரு எடுத்துக்காட்டாக இருக்கட்டும். செய்யும்போதுஃ 2-அ. k அளவுருவைக் கொண்டு மாற்று வடிவியல் தொகுப்பைச் செய்யுங்கள். இதன் விளைவாக வரும் நிகழ்வாக இருக்கட்டும், மீதமுள்ள நிகழ்வாக இருக்கட்டும். எங்களிடம் உள்ளது. 3-அ. ஒருங்கிணைப்பு கட்டுப்பாடுகள் இல்லாமல், உள்ளமைவு நேரியல் நிரலை உருவாக்குங்கள். 4. சகிப்புத்தன்மை h = 1 உடன் x என்ற தீர்வை கணக்கிடுங்கள். இதன் விளைவாக தொட்டிகளுடன் ஒரு பகுதியளவு தொட்டி பொதி செய்யப்படுகிறது. ரன்-டைம். 3-பி. ஒரு ஒருங்கிணைந்த தீர்வுக்கு x ஐ சுற்றவும். பின்னப் பகுதிக்கு தொட்டிகளைச் சேர்க்க வேண்டாம். அதற்கு பதிலாக, பேக் செய்யப்பட்ட பொருட்களை அகற்றுங்கள். 2-பி. பெரும்பாலான தொட்டிகளில் பொருட்களை பேக் செய்யுங்கள். 2. ஒருமுறை, மீதமுள்ள பொருட்களை பெரும்பாலான தொட்டிகளில் பேராசையுடன் மூடுங்கள். படி 2 இல் வளையத்தின் ஒவ்வொரு மறு செய்கையிலும், x இன் பின்னப் பகுதி அதிகபட்சம் m (K) வடிவங்களைக் கொண்டுள்ளது, எனவே. ஒவ்வொரு மறு செய்கையிலும் கே காரணி மூலம் எஃப்ஓபிடி குறைகிறது, எனவே மறு செய்கைகளின் எண்ணிக்கை அதிகபட்சமாக இருக்கும். எனவே, பயன்படுத்தப்படும் மொத்த தொட்டிகளின் எண்ணிக்கை பின்வருமாறுஃ 1-பி. ஒரு தீர்வைப் பெற g ஐ விட சிறிய உருப்படிகளைச் சேர்க்கவும். தொட்டிகளின் எண்ணிக்கைஃ ரன்-டைம் உள்ளே உள்ளது. இப்போது, நாம் k = 2 மற்றும் g = 1/FOPT (I) ஐத் தேர்ந்தெடுத்தால், நாம் பெறுகிறோம்ஃ, எனவேஃ, எனவே மொத்த தொட்டிகளின் எண்ணிக்கை உள்ளது. ரன்-டைம். ஒரே வழிமுறையை வெவ்வேறு அளவுருக்களுடன் துல்லியத்துடன் ரன்-டைம் பரிமாற்றத்திற்கு பயன்படுத்தலாம். சில அளவுருக்களுக்கு, மற்றும் என்பதைத் தேர்ந்தெடுக்கவும். பின்னர், பெரும்பாலான தொட்டிகளில் பேக்கிங் தேவைப்படுகிறது, மேலும் ரன்-டைம் உள்ளே உள்ளது. அல்காரிதம் 3 m அளவுகளின் எண்ணிக்கை சிறியதாக இருக்கும்போது மூன்றாவது அல்காரிதம் பயனுள்ளதாக இருக்கும் (உயர் பெருக்க தொட்டி பொதியையும் பார்க்கவும்). 1-ஏ. செட். g ஐ விட சிறிய அனைத்து உருப்படிகளையும் அகற்றுவதன் மூலம் கட்டமைக்கப்பட்ட ஒரு எடுத்துக்காட்டாக இருக்கட்டும். அப்படியானால்ஃ 3-a. ஒருங்கிணைப்பு கட்டுப்பாடுகள் இல்லாமல், உள்ளமைவு நேரியல் நிரலை உருவாக்குங்கள். 4. சகிப்புத்தன்மை h = 1 உடன் x என்ற தீர்வை கணக்கிடுங்கள். இதன் விளைவாக தொட்டிகளுடன் ஒரு பகுதியளவு தொட்டி பொதி செய்யப்படுகிறது. ரன்-டைம். 3-பி. ஒரு ஒருங்கிணைந்த தீர்வுக்கு x ஐ சுற்றவும். பின்னப் பகுதிக்கு தொட்டிகளைச் சேர்க்க வேண்டாம். அதற்கு பதிலாக, பேக் செய்யப்பட்ட பொருட்களை அகற்றுங்கள். மீதமுள்ள துண்டுகளில் அல்காரிதம் 2 இன் படி 2 ஐ இயக்கவும். 1-பி. ஒரு தீர்வைப் பெற g ஐ விட சிறிய உருப்படிகளைச் சேர்க்கவும். தொட்டிகளின் எண்ணிக்கைஃ இது பெரும்பாலான தொட்டிகளில் பயன்படுத்தப்படுகிறது, மேலும் ரன்-டைம் உள்ளே உள்ளது. மேம்பாடுகள் மேலும் சிறந்த தோராயங்களை வழங்குவதற்காக கே. கே நுட்பங்கள் பின்னர் மேம்படுத்தப்பட்டன. ரோத்வாஸ் அல்காரிதம் 2 இன் அதே திட்டத்தை பயன்படுத்துகிறார், ஆனால் படி 2 இல் வேறுபட்ட ரவுண்டிங் நடைமுறையுடன். அவர் ஒரு "க்ளூயிங்" படிநிலையை அறிமுகப்படுத்தினார், அதில் சிறிய பொருட்கள் ஒன்றாக ஒட்டப்பட்டு ஒரு பெரிய பொருளைத் தருகின்றன. சிறிய உருப்படியின் அளவை சுமார் அதிகரிக்க இந்த க்ளூயிங் பயன்படுத்தப்படலாம். அனைத்து அளவுகளும் குறைந்தபட்சம் இருக்கும்போது, அல்காரிதம் 2 இன் உத்தரவாதத்தில் நாம் மாற்றலாம், மேலும் பெறலாம்ஃ, இது ஒரு தொட்டிகளை வழங்குகிறது. ஹோபர்க் மற்றும் ரோத்வாஸ் இதே போன்ற ஒரு திட்டத்தை பயன்படுத்துகின்றனர், இதில் பொருட்கள் முதலில் "கொள்கலன்களில்" அடைக்கப்படுகின்றன, பின்னர் கொள்கலன்கள் தொட்டிகளில் அடைக்கப்படுகின்றன. அவற்றின் அல்காரிதம் பெரும்பாலான தொட்டிகளில் தேவைப்படுகிறது. குறிப்புகள் தொட்டி பொதி