Next-fit bin packing
அடுத்த பொருத்தம் தொட்டி பொதி செய்வதற்கான ஆன்லைன் வழிமுறை ஆகும். அதன் உள்ளீடு வெவ்வேறு அளவுகளின் பொருட்களின் பட்டியலாகும். அதன் வெளியீடு ஒரு பொதி ஆகும்-ஒவ்வொரு தொட்டியிலும் உள்ள பொருட்களின் அளவுகளின் கூட்டுத்தொகை அதிகபட்சமாக இருக்கும் வகையில், நிலையான திறன் கொண்ட தொட்டிகளாக பொருட்களைப் பிரிப்பது. வெறுமனே, முடிந்தவரை சில தொட்டிகளைப் பயன்படுத்த விரும்புகிறோம், ஆனால் தொட்டிகளின் எண்ணிக்கையைக் குறைப்பது ஒரு NP-கடினமான சிக்கலாகும். அடுத்த பொருத்தமான வழிமுறை பின்வரும் ஹூரிஸ்டிக்கைப் பயன்படுத்துகிறதுஃ இது ஒரு தற்போதைய தொட்டியை வைத்திருக்கிறது, இது ஆரம்பத்தில் காலியாக உள்ளது. ஒரு பொருள் வரும்போது, அது தற்போதைய தொட்டியில் பொருந்துகிறதா என்பதை சரிபார்க்கிறது. அது பொருந்தினால், அது அதற்குள் வைக்கப்படுகிறது. இல்லையெனில், தற்போதைய தொட்டி மூடப்பட்டு, ஒரு புதிய தொட்டி திறக்கப்பட்டு, வரவிருக்கும் பொருள் இந்த புதிய தொட்டி உள்ளே வைக்கப்படுகிறது. நெக்ஸ்ட்-ஃபிட் என்பது ஒரு எல்லைக்குட்பட்ட விண்வெளி வழிமுறை-இதற்கு எந்த நேரத்திலும் ஒரு பகுதி நிரப்பப்பட்ட தொட்டி மட்டுமே திறந்திருக்க வேண்டும். இந்த வழிமுறையை டேவிட் எஸ். ஜான்சன் 1973 ஆம் ஆண்டில் தனது முனைவர் ஆய்வறிக்கையில் ஆய்வு செய்தார். இயக்க நேரம் நெக்ஸ்ட்ஃபிட்டின் இயங்கும் நேரத்தை, பட்டியலில் உள்ள உருப்படிகளின் எண்ணிக்கை எங்கு உள்ளது என்பதன் மூலம் கட்டுப்படுத்தலாம். தோராய விகிதம் NF (L) மூலம் நெக்ஸ்ட்ஃபிட் பயன்படுத்தும் தொட்டிகளின் எண்ணிக்கையையும், ஒபிடி (L) மூலம் எல். மேல் பிணைக்கப்பட்ட பட்டியலுக்கு சாத்தியமான தொட்டிகளின் உகந்த எண்ணிக்கையையும் குறிக்கிறது. பின்னர், ஒவ்வொரு பட்டியலுக்கும், ஆதாரத்திற்கான உள்ளுணர்வு பின்வருமாறு. இந்த வழிமுறையால் பயன்படுத்தப்படும் தொட்டிகளின் எண்ணிக்கை உகந்த தொட்டிகளின் எண்ணிக்கையை விட இரண்டு மடங்கு அதிகமாக இருக்காது. வேறு வார்த்தைகளில் கூறுவதானால், 2 தொட்டிகள் அதிகபட்சம் பாதி நிரம்பியிருப்பது சாத்தியமற்றது, ஏனெனில் அத்தகைய சாத்தியம் ஒரு கட்டத்தில், சரியாக ஒரு தொட்டி அதிகபட்சம் பாதி நிரம்பியிருப்பதைக் குறிக்கிறது, மேலும் ஒரு பெரிய பொருளுக்கு இடமளிக்க ஒரு புதிய தொட்டி திறக்கப்பட்டது. ஆனால் முதல் உருப்படியில் குறைந்தபட்சம் ஒரு இடமாவது இருப்பதால், அதிகபட்ச அளவு கொண்ட எந்தவொரு பொருளுக்கும் அல்காரிதம் ஒரு புதிய தொட்டியைத் திறக்காது. தொட்டியை விட அதிகமாக நிரப்பிய பின்னரே அல்லது அதை விட பெரிய அளவு கொண்ட ஒரு பொருள் வந்தால் மட்டுமே, வழிமுறை ஒரு புதிய தொட்டியைத் திறக்கலாம். எனவே நம்மிடம் தொட்டிகள் இருந்தால், குறைந்தபட்சம் தொட்டிகள் பாதிக்கும் மேலாக நிரம்பியிருக்கும். எனவே, உகந்த மதிப்பின் குறைந்த வரம்பாக இருப்பதால், நாம் அதைப் பெறுகிறோம். லோயர் பௌண்ட் ஒவ்வொன்றிற்கும், மற்றும் போன்ற ஒரு பட்டியல் உள்ளது. அது வைத்திருக்கும் பட்டியல்களின் குடும்பம் அதனுடன் வழங்கப்படுகிறது. இந்த பட்டியலுக்கான உகந்த தீர்வில் அளவு கொண்ட இரண்டு பொருட்கள் கொண்ட தொட்டிகளும், அளவு கொண்ட பொருட்களுடன் ஒரு தொட்டியும் (அதாவது, மொத்த தொட்டிகள்) உள்ளன, அதே நேரத்தில் NF ஆல் உருவாக்கப்படும் கரைசலில் ஒரு உருப்படி அளவு மற்றும் ஒரு உருப்படி அளவு கொண்ட தொட்டிகள் உள்ளன. வரம்புக்குட்பட்ட உருப்படியின் அளவு ஒரு பொருளின் அதிகபட்ச அளவு என்றால், அறிகுறியற்ற தோராய விகித விகிதம் திருப்தி அளிக்கிறதுஃ அனைவருக்கும்; அனைவருக்கும். மற்ற பண்புகள் நெக்ஸ்ட்-ஃபிட் ஒரு பட்டியலையும் அதன் தலைகீழையும் அதே எண்ணிக்கையிலான தொட்டிகளில் இணைக்கிறது. நெக்ஸ்ட்-கே-ஃபிட் (என். கே. எஃப்) நெக்ஸ்ட்-கே-ஃபிட் என்பது நெக்ஸ்ட்-ஃபிட்டின் ஒரு மாறுபாடு, ஆனால் ஒரு தொட்டியை மட்டுமே திறந்து வைப்பதற்குப் பதிலாக, வழிமுறை கடைசி தொட்டிகளைத் திறந்து வைத்திருக்கிறது மற்றும் உருப்படி பொருந்தும் முதல் தொட்டியைத் தேர்ந்தெடுக்கிறது. ஏனெனில், NF இன் முடிவுகளுடன் ஒப்பிடும்போது மேம்படுத்தப்பட்ட முடிவுகளை NkF வழங்குகிறது, இருப்பினும், நிலையான மதிப்புகளை விட பெரியதாக அதிகரிப்பது வழிமுறையை அதன் மோசமான-வழக்கு நடத்தையில் மேலும் மேம்படுத்துகிறது. அல்காரிதம் ஒரு அலஸ்ட்அனிஃபிட்-அல்காரிதம் என்றால், பின்னர். நெக்ஸ்ட்-ஃபிட்-டிக்ரீசிங் (என்எஃப்டி) என்பது நெக்ஸ்ட்-ஃபிட்டின் ஆஃப்லைன் மாறுபாடு ஆகும்ஃ இது அனைத்து உள்ளீட்டு உருப்படிகளையும் ஏற்றுக்கொள்கிறது, அவற்றை இறங்கு அளவு மூலம் ஆர்டர் செய்கிறது மற்றும் நெக்ஸ்ட்-ஃபிட்டை அழைக்கிறது. அதன் அறிகுறியற்ற தோராய விகிதம் மிகவும் சிறந்ததுஃ 2 க்கு பதிலாக 1.7 க்கும் குறைவாக உள்ளது. குறிப்புகள் தொட்டி பொதி