First-fit bin packing
ஃபர்ஸ்ட் ஃபிட் (எஃப். எஃப்) என்பது தொட்டி பொதி செய்வதற்கான ஆன்லைன் வழிமுறை ஆகும். அதன் உள்ளீடு வெவ்வேறு அளவுகளின் பொருட்களின் பட்டியலாகும். அதன் வெளியீடு ஒரு பொதி ஆகும்-ஒவ்வொரு தொட்டியிலும் உள்ள பொருட்களின் அளவுகளின் கூட்டுத்தொகை அதிகபட்சமாக இருக்கும் வகையில், நிலையான திறன் கொண்ட தொட்டிகளாக பொருட்களைப் பிரிப்பது. வெறுமனே, முடிந்தவரை சில தொட்டிகளைப் பயன்படுத்த விரும்புகிறோம், ஆனால் தொட்டிகளின் எண்ணிக்கையைக் குறைப்பது ஒரு NP-கடினமான சிக்கலாகும். ஃபர்ஸ்ட் ஃபிட் அல்காரிதம் பின்வரும் ஹூரிஸ்டிக்கைப் பயன்படுத்துகிறதுஃ இது திறந்த தொட்டிகளின் பட்டியலை வைத்திருக்கிறது, இது ஆரம்பத்தில் காலியாக உள்ளது. ஒரு பொருள் வரும்போது, பொருள் ஏதேனும் இருந்தால், அதில் பொருந்தக்கூடிய முதல் தொட்டியைக் கண்டறியவும். அத்தகைய தொட்டி கண்டுபிடிக்கப்பட்டால், புதிய பொருள் அதற்குள் வைக்கப்படும். இல்லையெனில், ஒரு புதிய தொட்டி திறக்கப்பட்டு, வரும் உருப்படி அதற்குள் வைக்கப்படும். தோராய விகிதம் ஃபர்ஸ்ட் ஃபிட் பயன்படுத்திய தொட்டிகளின் எண்ணிக்கையை எஃப்எஃப் (எல்) என்றும், எல் பட்டியலுக்கு சாத்தியமான தொட்டிகளின் உகந்த எண்ணிக்கையை ஓபிடி (எல்) என்றும் குறிக்கிறது. எஃப்எஃப் (எல்) பகுப்பாய்வு பல படிகளில் செய்யப்பட்டது. எஃப்எஃப்-க்கான முதல் மேல் எல்லை 1971 இல் உல்மனால் நிரூபிக்கப்பட்டது. 1972 ஆம் ஆண்டில், இந்த மேல் எல்லை கரே, கிரஹாம் மற்றும் உல்மேன், ஜான்சன் மற்றும் டெமர்ஸ் ஆகியோரால் மேம்படுத்தப்பட்டது. 1976 ஆம் ஆண்டில், கரே, கிரஹாம், ஜான்சன், யாவோ மற்றும் சி-சிஹ் ஆகியோரால் இது மேம்படுத்தப்பட்டது, இது மற்றும் ஒருங்கிணைப்பு காரணமாக சமம். அடுத்த முன்னேற்றம், 2010 இல் சியா மற்றும் டான் ஆகியோரால், வரம்பைக் குறைத்தது. இறுதியாக, 2013 ஆம் ஆண்டில், இந்த வரம்பு டோசா மற்றும் ஸ்கால் ஆகியோரால் மேம்படுத்தப்பட்டது. அவர்கள் ஒரு எடுத்துக்காட்டு உள்ளீட்டு பட்டியலையும் வழங்குகிறார்கள், இதற்காக இந்த வரம்புடன் பொருந்துகிறது. ஆதார யோசனையை கீழே விளக்குகிறோம். அறிகுறியற்ற விகிதம் அதிகபட்சம் 2 என்பது அறிகுறியற்ற விகிதம் அதிகபட்சம் 2 என்பதற்கான சான்றாகும். 1/2 க்கும் குறைவான தொகை கொண்ட ஒரு எஃப். எஃப் தொட்டி இருந்தால், மீதமுள்ள அனைத்து பொருட்களின் அளவும் 1/2 க்கும் அதிகமாக இருக்கும், எனவே பின்வரும் அனைத்து தொட்டிகளின் கூட்டுத்தொகையும் 1/2 க்கும் அதிகமாக இருக்கும். எனவே, அதிகபட்சமாக ஒன்றைத் தவிர அனைத்து எஃப். எஃப் தொட்டிகளும் குறைந்தபட்சம் ஒன்றரை பங்கைக் கொண்டுள்ளன. அனைத்து உகந்த தொட்டிகளும் அதிகபட்சமாக 1 ஐக் கொண்டுள்ளன, எனவே அனைத்து அளவுகளின் கூட்டுத்தொகையும் அதிகபட்சமாக ஓபிடி ஆகும். எனவே, எஃப். எஃப் தொட்டிகளின் எண்ணிக்கை அதிகபட்சமாக 1 + ஓ. பி. டி/(1/2) = 2 * ஓ. பி. டி + 1 அறிகுறியற்ற விகிதம் அதிகபட்சமாக 1.75 ஆகும். மூன்றில் இரண்டு பங்கிற்கும் குறைவான தொகை கொண்ட எஃப்எப் தொட்டி இருந்தால், மீதமுள்ள அனைத்து பொருட்களின் அளவும் மூன்றில் ஒரு பங்கிற்கு மேல் இருக்கும். அளவுகள் அதிகபட்சமாக மூன்றில் ஒரு பங்காக இருப்பதால், பின்வரும் அனைத்து தொட்டிகளிலும் (கடைசி ஒன்றைத் தவிர) குறைந்தது இரண்டு உருப்படிகள் இருக்க வேண்டும், மேலும் தொகை மூன்றில் இரண்டு பங்கை விட பெரியதாக இருக்க வேண்டும். எனவே, அதிகபட்சமாக ஒன்றைத் தவிர அனைத்து எஃப்எஃப் தொட்டிகளும் குறைந்தபட்சம் மூன்றில் இரண்டு பங்கைக் கொண்டுள்ளன, மேலும் எஃப்எஃப் தொட்டிகளின் எண்ணிக்கை அதிகபட்சமாக 2 + ஓபிடி/(மூன்றில் இரண்டு) = மூன்றில் இரண்டு * ஓபிடி + 1 ஆகும். "சிக்கலான" உருப்படிகள் இரண்டில் ஒரு பங்கை விட பெரிய அளவு கொண்டவை. எனவே, பகுப்பாய்வை மேம்படுத்த, 1/2 ஐ விட பெரிய ஒவ்வொரு பொருளுக்கும் ஆர் போனஸ் கொடுப்போம். ஒரு பொருளின் எடையை அதன் அளவு மற்றும் அதன் போனஸ் என வரையறுக்கவும். பொருட்களின் தொகுப்பின் எடையை அதன் உள்ளடக்கங்களின் எடைகளின் கூட்டுத்தொகையாக வரையறுக்கவும். இப்போது, ஒரு உருப்படியுடன் (அதிகபட்சம் ஒன்றைத் தவிர) ஒவ்வொரு எஃப்எஃப் தொட்டியிலும் எடை குறைந்தது 1/2 + ஆர் ஆகவும், இரண்டு அல்லது அதற்கு மேற்பட்ட உருப்படிகளுடன் (அதிகபட்சம் ஒன்றைத் தவிர) ஒவ்வொரு எஃப்எஃப் தொட்டியிலும் எடை 2/3 ஆகவும் இருக்கும். R = 1/6 ஐ எடுத்துக்கொள்வது அனைத்து FF தொட்டிகளின் எடையும் குறைந்தது 2/3 ஆக இருக்கும். மறுபுறம், உகந்த பேக்கிங்கில் உள்ள ஒவ்வொரு தொட்டியிலும் எடை அதிகபட்சம் 1 + ஆர் = 7/6 ஆகும், ஏனெனில் அத்தகைய ஒவ்வொரு தொட்டியிலும் அதிகபட்சம் ஒரு பொருள் 1/2 ஐ விட பெரியதாக இருக்கும். எனவே, அனைத்து பொருட்களின் மொத்த எடை அதிகபட்சம் 7/6 * ஓபிடி ஆகும், மேலும் எஃப்எஃப் தொட்டிகளின் எண்ணிக்கை அதிகபட்சம் 2 + (7/6 * ஓபிடி/(2/3)) = 7/4 * ஓபிடி + 2 ஆகும். அறிகுறியற்ற விகிதம் அதிகபட்சம் 1.7 பின்வரும் ஆதாரம் இதிலிருந்து தழுவி எடுக்கப்படுகிறது. ஒரு உள்ளீட்டு உருப்படியின் எடையை உருப்படியின் அளவு x சில போனஸ் என பின்வருமாறு வரையறுக்கவும்ஃ அறிகுறியற்ற தோராய விகிதம் இரண்டு கூற்றுகளிலிருந்து பின்வருமாறுஃ உகந்த பேக்கிங்கில், ஒவ்வொரு தொட்டியின் எடையும் அதிகபட்சமாக 17/12 ஆக இருக்கும்; முதல்-பொருத்தம் பேக்கிங்கில், ஒவ்வொரு தொட்டியின் சராசரி எடையும் குறைந்தது 5/6 = 10/12 ஆக இருக்கும். எனவே, அறிகுறியற்ற முறையில், எஃப். எஃப் பேக்கிங்கில் உள்ள தொட்டிகளின் எண்ணிக்கை அதிகபட்சமாக 17/10 * ஓபிடி ஆக இருக்க வேண்டும். உரிமைகோரல் 1 ஐப் பொறுத்தவரை, அதிகபட்சம் 1 தொகை கொண்ட எந்த தொகுப்பு B க்கும், போனஸ் (B) அதிகபட்சம் 5/12 என்பதை நிரூபிக்க போதுமானது. உண்மையில்ஃ B க்கு 1/2 ஐ விட பெரிய உருப்படி எதுவும் இல்லையென்றால், அது 1/6 ஐ விட பெரிய ஐந்து உருப்படிகளைக் கொண்டுள்ளது, மேலும் அவை ஒவ்வொன்றின் போனஸ் அதிகபட்சம் 1/12 ஆகும்; B க்கு 1/2 ஐ விட பெரிய உருப்படி இருந்தால், ஆனால் [1/3,1 2] இல் உருப்படி இல்லை என்றால், அதற்கு (1/6,1 3) அதிகபட்சம் இரண்டு உருப்படிகளுக்கு இடமுண்டு, மேலும் அவற்றின் போனஸின் கூட்டுத்தொகை அதிகபட்சம் (1/2/2-1/6) = 1/12 ஆகும், எனவே மொத்த போனஸ் 4/12 + 1/12 = 5/12 ஆகும். B-இல் 1/2 ஐ விட பெரிய உருப்படியும், [1/3,1 2] இல் ஒரு உருப்படியும் இருந்தால், அதற்கு 1/6 ஐ விட பெரிய அளவிலான உருப்படிகளுக்கு இனி இடமில்லை, எனவே மொத்த போனஸ் மீண்டும் 4/12+1 12 = 5/12 ஆகும். எனவே, B இன் எடை அதிகபட்சம் 1 + 5/12 = 17/12 ஆகும். உரிமைகோரல் 2 க்கு, முதலில் ஒரு உருப்படியுடன் ஒரு FF பின் B ஐக் கவனியுங்கள். கூட்டுத்தொகை (B) <1/2 என்றால், பின்னர்-FF வேலை செய்யும் விதத்தில்-B க்குப் பிறகு செயலாக்கப்பட்ட அனைத்து பொருட்களும் 1/2 ஐ விட பெரியதாக இருக்க வேண்டும் (இல்லையெனில் அவை B இல் செருகப்பட்டிருக்கும்). எனவே, கூட்டுத்தொகை <1/2 உடன் அதிகபட்சம் ஒரு FF தொட்டி உள்ளது. இப்போது தொகை (பி)> 1/2 உடன் ஒரு உருப்படியுடன் மற்ற அனைத்து தொட்டிகளையும் கருத்தில் கொள்ளுங்கள். இந்த தொட்டிகள் அனைத்திற்கும், எடை (பி)> 1/2+1 3 = 5/6. இப்போது இரண்டு அல்லது அதற்கு மேற்பட்ட பொருட்களுடன் எஃப்எஃப் தொட்டிகள் பி ஐக் கவனியுங்கள். கூட்டுத்தொகை (B) <2/3 என்றால், பின்னர்-FF வேலை செய்யும் விதத்தில்-B க்குப் பிறகு செயலாக்கப்பட்ட அனைத்து பொருட்களும் 1/3 ஐ விட பெரியதாக இருக்க வேண்டும் (இல்லையெனில் அவை B இல் செருகப்பட்டிருக்கும்). எனவே, இரண்டு அல்லது அதற்கு மேற்பட்ட பொருட்களைக் கொண்ட பின்வரும் அனைத்து தொட்டிகளும் மூன்றில் இரண்டு பங்கை விட பெரியவை. எனவே இரண்டு அல்லது அதற்கு மேற்பட்ட உருப்படிகள் மற்றும் தொகை <2/3 உடன் அதிகபட்சம் ஒரு எஃப். எஃப் தொட்டி உள்ளது. இப்போது இரண்டு அல்லது அதற்கு மேற்பட்ட உருப்படிகள் மற்றும் தொகை> 2/3 கொண்ட மற்ற அனைத்து தொட்டிகளையும் கருத்தில் கொள்ளுங்கள். அவற்றை பி [1], பி [2], பி [கே], அவை திறக்கப்பட்ட வரிசையால் குறிக்கவும். 1,., k இல் உள்ள ஒவ்வொரு i க்கும், B [i] கூட்டுத்தொகை மற்றும் B [i + 1] இன் போனஸ் குறைந்தபட்சம் 5/6 என்று நிரூபிக்கிறோம்ஃ தொகை (B [i]) + போனஸ் (B [i + 1])> = 5/6. உண்மையில், கூட்டுத்தொகை (B [i])> = 5/6 என்றால் சமத்துவமின்மை அற்பமானது. இல்லையெனில், கூட்டுத்தொகை (B [i]): = 1-x ஆக இருக்கட்டும். x என்பது 1/6 மற்றும் 2/6 க்கு இடையில் உள்ளது என்பதை நினைவில் கொள்க, ஏனெனில் கூட்டுத்தொகை (B [i]) என்பது 2/3 மற்றும் 5/6 க்கு இடையில் உள்ளது. B [i + 1] என்பது B [i] க்குப் பிறகு திறக்கப்படுவதால், B [i + 1] குறைந்தது இரண்டு உருப்படிகளைக் கொண்டுள்ளது, c1 மற்றும் c2 என்று சொல்லுங்கள், அவை B [i] உடன் பொருந்தாது, அதாவதுஃ c1, c2> 1-தொகை (B [i]) = x> 1/6. பின்னர் c1 மற்றும் c2 ஒவ்வொன்றின் போனஸ் குறைந்தபட்சம் x/2-1/12 ஆகும். எனவே, B [i + 1] இன் போனஸ் குறைந்தபட்சம் x-1/6 ஆகும், எனவே தொகை (B [i]) + போனஸ் (B [i + 1])> = (1-x) + (x-1/6) = 5/6 ஆகும். மேற்கண்ட சமத்துவமின்மையை அடுத்தடுத்த ஜோடிகளுக்கு நாம் பயன்படுத்தலாம், மேலும் பெறலாம்ஃ தொகை (B [1]) + போனஸ் (B [2]) + தொகை (B [2]) + போனஸ் (B [3]) + + தொகை (B [k-1]) + போனஸ் (B [k])> = 5/6 * (k-1). எனவே, அனைத்து எஃப்எஃப் தொட்டிகளின் மொத்த எடை குறைந்தது 5/6 * (எஃப்எஃப்-3) ஆகும் (இதில் ஒரு உருப்படி தொட்டிக்கு 3 ஐ கூட்டுத்தொகை <1/2, ஒற்றை இரண்டு உருப்படி தொட்டிக்கு கூட்டுத்தொகை <2/3, மற்றும் இரண்டு உருப்படி தொட்டிகளிலிருந்து கே-1 ஐ கூட்டுத்தொகை> = 2/3 உடன் கழிக்கிறோம்). மொத்தத்தில், நாம் அந்த 17/12 * OPT> = 5/6 * (FF-3) ஐப் பெறுகிறோம், எனவே FF <= 17/10 * OPT + 3. டோசா மற்றும் ஸ்கால் ஒரு இறுக்கமான பகுப்பாய்வை வழங்குகிறார்கள், அது 3 ஐ அகற்றி, அந்த FF <= 17/10 * OPT ஐப் பெறுகிறது. 1.7OPT இன் செயல்திறன் பிணைப்பு இறுக்கமாக இருக்கும் நிகழ்வுகள் உள்ளன. பின்வரும் உதாரணம் அடிப்படையாக கொண்டது. தொட்டி திறன் 101, மற்றும்ஃ வரிசைஃ 6 (x7), 10 (x7), 16 (x3), 34 (x10), 51 (x10). உகந்த பேக்கிங் 10 தொட்டிகளைக் கொண்டுள்ளதுஃ [51+34 + 16] (x3), [51+34 + 10+6] (x7). அனைத்து தொட்டி தொகைகளும் 101 ஆகும். ஃபர்ஸ்ட் ஃபிட் பேக்கிங் 17 தொட்டிகளைக் கொண்டுள்ளதுஃ [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5), [51] (x10). தொட்டி தொகைகள்ஃ 92,68,68 (x5), 51 (x10). வெகுமதிகள் (101 ஆக இயல்பாக்கப்பட்டவை) 0,0,16.8 (x5), 33.7 (x10) ஆகும். மொத்த எடைகள் (101 ஆக இயல்பாக்கப்பட்டவை) 92,68,84.8 (x5), 84.7 (x10) ஆகும். கிட்டத்தட்ட அனைத்து எடைகளும் 101 * 5/6 = 84.1 க்கு அருகில் இருப்பதைக் காணலாம். சுத்திகரிக்கப்பட்ட முதல்-பொருத்தம் சுத்திகரிக்கப்பட்ட-முதல்-பொருத்தம் (ஆர். எஃப். எஃப்) என்பது தொட்டி பொதி செய்வதற்கான மற்றொரு ஆன்லைன் வழிமுறையாகும், இது முன்பு உருவாக்கப்பட்ட எஃப். எஃப் வழிமுறையை மேம்படுத்துகிறது. இதை ஆண்ட்ரூ சி-சி யாவோ வழங்கினார். அல்காரிதம் உருப்படிகள் அவற்றின் அளவுகளுக்கு ஏற்ப நான்கு வகுப்புகளாக வகைப்படுத்தப்படுகின்றன (தொட்டி திறன் 1 ஆக இருக்கும்):-துண்டு-அளவு. - துண்டு-அளவு. - துண்டு-அளவு. - துண்டு-அளவு. இதேபோல், தொட்டிகள் நான்கு பிரிவுகளாக வகைப்படுத்தப்பட்டுள்ளனஃ 1,2,3 மற்றும் 4. ஒரு நிலையான முழு எண்ணாக இருக்கட்டும். அடுத்த உருப்படி ஒரு தொட்டியில் ஒதுக்கப்பட்டுள்ளது-வகுப்பு 1, ஒரு-துண்டு என்றால், வகுப்பு 2, ஒரு-துண்டு என்றால், வகுப்பு 3, ஒரு-துண்டு என்றால், ஆனால் இதுவரை காணப்பட்ட th-துண்டு அல்ல, எந்த முழு எண்ணுக்கும். வகுப்பு 1, இதுவரை காணப்பட்ட பத்தாவது துண்டு என்றால், வகுப்பு 4, ஒரு துண்டு என்றால். பொருளின் வகுப்பு தேர்ந்தெடுக்கப்பட்டவுடன், அது முதலில் பொருந்தக்கூடிய தொட்டி பொதிகளைப் பயன்படுத்தி அந்த வகுப்பின் தொட்டிகளுக்குள் வைக்கப்படுகிறது. தற்போதைய உருப்படி ஒரு திறந்த தொட்டிக்குள் (மற்றொரு வகுப்பில் இருந்து) பொருந்துகிறது என்ற உண்மை இருந்தபோதிலும், இது ஒரு புதிய தொட்டியைத் திறக்கக்கூடும் என்பதால் ஆர். எஃப். எஃப் ஒரு எந்த-பொருத்தம் வழிமுறை அல்ல என்பதை நினைவில் கொள்க. தோராயமான விகிதம் ஆர்எஃப்எஃப் ஒரு தோராயமான உத்தரவாதத்தைக் கொண்டுள்ளது. for உடன் பட்டியல்களின் குடும்பம் உள்ளது. ஃபர்ஸ்ட்-ஃபிட்-டிக்ரீசிங் (எஃப்எஃப்டி) என்பது ஃபர்ஸ்ட்-ஃபிட்டின் ஆஃப்லைன் மாறுபாடு ஆகும்ஃ இது அனைத்து உள்ளீட்டு உருப்படிகளையும் ஏற்றுக்கொள்கிறது, அவற்றை இறங்கு அளவு மூலம் ஆர்டர் செய்கிறது மற்றும் ஃபர்ஸ்ட்-ஃபிட்டை அழைக்கிறது. அதன் அறிகுறியற்ற தோராய விகிதம் மிகவும் சிறந்ததுஃ 1.7 க்கு பதிலாக 1.222 ஆகும். செயல்பாடுகள் பைதான்ஃ ப்ராட்டிபி தொகுப்பில் முதல் பொருத்தம் செயல்படுத்தப்படுகிறது. குறிப்புகள் தொட்டி பொதி