First-fit-decreasing bin packing
ஃபர்ஸ்ட்-ஃபிட்-டிக்ரீசிங் (எஃப்எஃப்டி) என்பது தொட்டி பொதி செய்வதற்கான ஒரு வழிமுறையாகும். அதன் உள்ளீடு வெவ்வேறு அளவுகளின் பொருட்களின் பட்டியலாகும். அதன் வெளியீடு ஒரு பொதி ஆகும்-ஒவ்வொரு தொட்டியிலும் உள்ள பொருட்களின் அளவுகளின் கூட்டுத்தொகை அதிகபட்சமாக இருக்கும் வகையில், நிலையான திறன் கொண்ட தொட்டிகளாக பொருட்களைப் பிரிப்பது. வெறுமனே, முடிந்தவரை சில தொட்டிகளைப் பயன்படுத்த விரும்புகிறோம், ஆனால் தொட்டிகளின் எண்ணிக்கையைக் குறைப்பது ஒரு NP-கடினமான சிக்கலாகும், எனவே தோராயமாக உகந்த ஹூரிஸ்டிக்கைப் பயன்படுத்துகிறோம். விளக்கம் எஃப்எஃப்டி வழிமுறை பின்வருமாறு செயல்படுகிறது. பெரியது முதல் சிறியது வரை பொருட்களை ஆர்டர் செய்யுங்கள். ஒரு புதிய வெற்று தொட்டி, தொட்டி #1 ஐத் திறக்கவும். பெரியது முதல் சிறியது வரை ஒவ்வொரு பொருளுக்கும், பொருள் பொருந்தக்கூடிய முதல் தொட்டி ஏதேனும் இருந்தால் அதைக் கண்டறியவும். அத்தகைய தொட்டி கண்டுபிடிக்கப்பட்டால், புதிய பொருளை அதில் வைக்கவும். இல்லையெனில், ஒரு புதிய வெற்று தொட்டியைத் திறந்து அதில் புதிய பொருளை வைக்கவும். சுருக்கமாகஃ எஃப்எஃப்டி இறங்கு அளவு மூலம் பொருட்களை ஆர்டர் செய்கிறது, பின்னர் முதலில் பொருந்தும் தொட்டி பேக்கிங் என்று அழைக்கிறது. எஃப்எஃப்டி வழிமுறையின் சமமான விளக்கம் பின்வருமாறு. பெரியது முதல் சிறியது வரை பொருட்களை ஆர்டர் செய்யுங்கள். மீதமுள்ள உருப்படிகள் இருக்கும்போதுஃ ஒரு புதிய வெற்று தொட்டியைத் திறக்கவும். பெரியது முதல் சிறியது வரையிலான ஒவ்வொரு பொருளுக்கும்ஃ அது தற்போதைய தொட்டியில் பொருந்த முடிந்தால், அதை செருகவும். நிலையான விளக்கத்தில், நாம் உருப்படிகளை ஒரு முறை சுழற்றுவோம், ஆனால் பல திறந்த தொட்டிகளை வைத்திருப்போம். சமமான விளக்கத்தில், நாம் பல முறை உருப்படிகளை சுழற்றுவோம், ஆனால் ஒவ்வொரு முறையும் ஒரு திறந்த தொட்டியை மட்டுமே வைத்திருப்போம். செயல்திறன் பகுப்பாய்வு எஃப்எஃப்டியின் செயல்திறன் பல படிகளில் பகுப்பாய்வு செய்யப்பட்டது. கீழே, உள்ளீட்டு தொகுப்பு எஸ் மற்றும் பின்-திறன் சி ஆகியவற்றிற்கு எஃப்எஃப்டி பயன்படுத்தும் தொட்டிகளின் எண்ணிக்கையைக் குறிக்கிறது. 1973 இல், டிஎஸ். ஜான்சன் தனது முனைவர் ஆய்வறிக்கையில் எந்தவொரு சந்தர்ப்பத்திலும் எஸ் மற்றும் திறன் சி. 1985 இல், பி. எஸ். பேக்கர் சற்று எளிமையான ஆதாரத்தைக் கொடுத்தார், மேலும் சேர்க்கை மாறிலி 3 க்கு மேல் இல்லை என்பதைக் காட்டினார். 1991 ஆம் ஆண்டிலும் 1997 ஆம் ஆண்டிலும் இந்த பகுப்பாய்வை லி ரோங்ஹெங்குடன் இணைந்து மேம்படுத்தியதாக யூ மினியி நிரூபித்தார். 2007 ஆம் ஆண்டில் ஜியோர்கி டோசா இறுக்கமான பிணைப்பை நிரூபித்து அதற்கு ஒரு உதாரணத்தை வழங்கினார். மோசமான உதாரணம் டோசா வழங்கிய கீழ் வரம்பு எடுத்துக்காட்டு பின்வருமாறுஃ இரண்டு தொட்டி உள்ளமைவுகளைக் கவனியுங்கள்ஃ;. உகந்த தீர்வில் 4 பிரதிகள் மற்றும் 2 பிரதிகள் இருந்தால், எஃப்எஃப்டி பின்வரும் தொட்டிகளைக் கணக்கிடும்ஃ உள்ளமைவுடன் 4 தொட்டிகள், உள்ளமைவுடன் 1 தொட்டி, உள்ளமைவுடன் 1 தொட்டி, உள்ளமைவுடன் 1 தொட்டி, உள்ளமைவுடன் 1 இறுதி தொட்டி, அதாவது, மொத்தம் 8 தொட்டி, உகந்த 6 தொட்டிகள் மட்டுமே உள்ளன. எனவே, மேல் எல்லை இறுக்கமாக உள்ளது, ஏனெனில். இந்த உதாரணத்தை அனைத்து அளவுகளுக்கும் நீட்டிக்க முடியும்ஃ உகந்த உள்ளமைவில் 9k + 6 தொட்டிகள் உள்ளனஃ 6k + 4 வகை B1 மற்றும் 3k + 2 வகை B2. ஆனால் எஃப்எஃப்டிக்கு குறைந்தபட்சம் 11k + 8 தொட்டிகள் தேவை, அதாவது. மோனோடோனிசிட்டி பண்புகள் உள்ளுணர்வுக்கு மாறாக, சி இன் மோனோடோனிக் செயல்பாடு அல்ல. இதேபோல், எஸ் இல் உள்ள பொருட்களின் அளவுகளின் மோனோடோனிக் செயல்பாடு அல்லஃ ஒரு பொருளின் அளவு சுருங்கக்கூடும், ஆனால் தொட்டிகளின் எண்ணிக்கை அதிகரிக்கும். இருப்பினும், எஃப்எஃப்டி வழிமுறை ஒரு "அறிகுறியற்ற மோனோடோனிசிட்டி" பண்பைக் கொண்டுள்ளது, இது பின்வருமாறு வரையறுக்கப்படுகிறது. S மற்றும் முழு எண் m ஆகிய ஒவ்வொரு நிகழ்வுக்கும், MinCap (S, m) மிகச்சிறிய திறன் C ஆக இருக்கட்டும், அதாவது ஒவ்வொரு முழு எண் m க்கும், MinRatio (m) அனைத்து உள்ளீட்டு செட்களுக்கும் r ≤ 1 எண்களின் முடிவிலியாக இருக்கட்டும். எஃப்எஃப்டி உகந்த எண்ணிக்கையிலான தொட்டிகளை அடையும் வகையில் தொட்டிகளை "உயர்த்த" வேண்டிய தொகை இது. பின்னர், ஒவ்வொரு உள்ளீடு S க்கும் மற்றும் ஒவ்வொரு r ≤ மின்ராஷியோ (m) க்கும்,. குறிப்பாக, மேற்கண்ட வரையறையில் உள்ள முடிவிலியை குறைந்தபட்சத்தால் மாற்ற முடியும் என்பதை இது காட்டுகிறது. எடுத்துக்காட்டாக, உள்ளீடு 44,24,24,22,21,17,8,6 என்று வைத்துக்கொள்வோம். திறன் 60 உடன், எஃப்எஃப்டி 3 தொட்டிகளை பேக் செய்கிறதுஃ 44,8,8; 24,24,6,6; 22,21,17. ஆனால் 61 திறன் கொண்ட எஃப்எஃப்டி 4 தொட்டிகளை பேக் செய்கிறதுஃ 44,17; 24,24,8; 22,21,8,6; 6. ஏனென்றால், திறன் 61 உடன், 17 முதல் தொட்டியில் பொருந்துகிறது, இதனால் பின்வரும் 8,8 க்கு வழி தடுக்கிறது. மற்றொரு எடுத்துக்காட்டாக, உள்ளீடுகள்ஃ 51,28,28,28,27,25,12,12,10,10,10,10,10,10,10 என்று வைத்துக்கொள்வோம். திறன் 75 உடன், எஃப்எஃப்டி 4 தொட்டிகளைக் கொண்டுள்ளதுஃ 51,12,12,28,28,10,28,27,10,25,10,10,10,10. ஆனால் திறன் 76 உடன், அதற்கு 5 தொட்டிகள் தேவைஃ 51,25,28,28,12,28,27,12,10,10,10,10,10. 17 ஆனது 16 ஆக மாறினால், அதன் விளைவாக வரும் பேக்கிங்ஃ 44,16; 24,24,8; 22,21,8,6; 6 ஆகும். மாற்றியமைக்கப்பட்ட முதல்-பொருத்தம்-குறைத்தல் மாற்றியமைக்கப்பட்ட முதல் பொருத்தம் குறைத்தல் (எம். எஃப். எஃப். டி) அளவு அடிப்படையில் பெரிய, நடுத்தர, சிறிய மற்றும் சிறிய என நான்கு அளவு வகுப்புகளாக வகைப்படுத்துவதன் மூலம் அரை தொட்டிக்கு மேல் உள்ள பொருட்களுக்கு எஃப். எஃப். டி. யில் மேம்படுகிறது, இது முறையே அளவு> 1/2 தொட்டி,> 1/3 தொட்டி,> 1/6 தொட்டி மற்றும் சிறிய பொருட்களுடன் தொடர்புடையது. பின்னர் அது ஐந்து கட்டங்களில் தொடர்கிறதுஃ ஒவ்வொரு பெரிய பொருளுக்கும் ஒரு தொட்டியை ஒதுக்குங்கள், பெரியது முதல் சிறியது வரை வரிசைப்படுத்தப்பட்டது. தொட்டிகள் வழியாக முன்னோக்கிச் செல்லுங்கள். ஒவ்வொன்றிலும்ஃ மீதமுள்ள சிறிய நடுத்தர உருப்படி பொருந்தவில்லை என்றால், இந்த தொட்டியைத் தவிர்க்கவும். இல்லையெனில், மீதமுள்ள மிகப்பெரிய நடுத்தர உருப்படியை பொருத்தமாக வைக்கவும். நடுத்தர உருப்படியைக் கொண்டிராத தொட்டிகள் வழியாக பின்னோக்கிச் செல்லுங்கள். ஒவ்வொன்றிலும்ஃ மீதமுள்ள இரண்டு சிறிய சிறிய பொருட்கள் பொருந்தவில்லை என்றால், இந்த தொட்டியைத் தவிர்க்கவும். இல்லையெனில், மீதமுள்ள மிகச்சிறிய சிறிய உருப்படியையும், மீதமுள்ள மிகப்பெரிய சிறிய உருப்படியையும் பொருத்தமாக வைக்கவும். அனைத்து தொட்டிகளிலும் முன்னோக்கிச் செல்லுங்கள். ஏதேனும் அளவு வகுப்பில் எஞ்சியிருக்கும் மிகச்சிறிய உருப்படி பொருந்தவில்லை என்றால், இந்த தொட்டியைத் தவிர்க்கவும். இல்லையெனில், பொருந்தக்கூடிய மிகப்பெரிய பொருளை இந்த தொட்டியில் வைக்கவும். மீதமுள்ள பொருட்களை புதிய தொட்டிகளில் அடைக்க FFD ஐப் பயன்படுத்தவும். இந்த வழிமுறை முதன்முதலில் ஜான்சன் மற்றும் கரே ஆகியோரால் 1985 இல் ஆய்வு செய்யப்பட்டது, அங்கு அவர்கள் அதை நிரூபித்தனர். இந்த வரம்பு 1995 ஆம் ஆண்டில் யூ மற்றும் ஜாங் ஆகியோரால் மேம்படுத்தப்பட்டது, அவர்கள் அதை நிரூபித்தனர். மற்ற வகைகள் சிறந்த-பொருத்தம்-குறைப்பு (பி. எஃப். டி) எஃப். எஃப். டி உடன் மிகவும் ஒத்திருக்கிறது, பட்டியல் வரிசைப்படுத்தப்பட்ட பிறகு, அது சிறந்த-பொருத்தம் தொட்டி பொதி மூலம் செயலாக்கப்படுகிறது. இதன் அறிகுறியற்ற தோராய விகிதம் FFD-11/9 ஐப் போன்றது. செயலாக்கங்கள் பைதான்ஃ ப்ராட்டிபி தொகுப்பில் ஃபர்ஸ்ட் ஃபிட் டிரிசிங் செயல்படுத்தப்படுகிறது. மல்டிஃபிட் வழிமுறையையும் பார்க்கவும்-ஒரே மாதிரியான இயந்திரங்கள் திட்டமிடலுக்கான ஒரு வழிமுறை, இது எஃப்எஃப்டியை ஒரு சப்ரூட்டினாகப் பயன்படுத்துகிறது. குறிப்புகள் தொட்டி பொதி