Next-fit bin packing
નેક્સ્ટ-ફિટ એ બિન પેકિંગ માટેનું ઓનલાઇન અલ્ગોરિધમ છે. તેનું ઇનપુટ વિવિધ કદની વસ્તુઓની યાદી છે. તેનું ઉત્પાદન એક પેકિંગ છે-વસ્તુઓનું નિશ્ચિત ક્ષમતાના ડબ્બામાં વિભાજન, જેમ કે દરેક ડબ્બામાં વસ્તુઓના કદનો સરવાળો મહત્તમ ક્ષમતા હોય છે. આદર્શ રીતે, આપણે શક્ય તેટલા ઓછા ડબ્બાનો ઉપયોગ કરવા માંગીએ છીએ, પરંતુ ડબ્બાની સંખ્યા ઘટાડવી એ એન. પી.-હાર્ડ સમસ્યા છે. નેક્સ્ટ-ફિટ અલ્ગોરિધમ નીચેના હ્યુરિસ્ટિકનો ઉપયોગ કરે છેઃ તે વર્તમાન બિન રાખે છે, જે શરૂઆતમાં ખાલી હોય છે. જ્યારે કોઈ વસ્તુ આવે છે, ત્યારે તે તપાસ કરે છે કે તે વસ્તુ વર્તમાન ડબ્બામાં બંધબેસે છે કે કેમ. જો તે બંધબેસે છે, તો તેને તેની અંદર મૂકવામાં આવે છે. નહિંતર, વર્તમાન ડબ્બો બંધ કરવામાં આવે છે, એક નવો ડબ્બો ખોલવામાં આવે છે અને આવનારી વસ્તુને આ નવા ડબ્બાની અંદર મૂકવામાં આવે છે. નેક્સ્ટ-ફિટ એ બાઉન્ડેડ સ્પેસ અલ્ગોરિધમ છે-તેને કોઈપણ સમયે ખોલવા માટે માત્ર એક આંશિક રીતે ભરેલા ડબ્બાની જરૂર પડે છે. ડેવિડ એસ. જ્હોનસન દ્વારા 1973 માં તેમના ડોક્ટરલ થીસીસમાં અલ્ગોરિધમનો અભ્યાસ કરવામાં આવ્યો હતો. નેક્સ્ટફિટનો ચાલી રહેલો સમય, સૂચિમાં વસ્તુઓની સંખ્યા ક્યાં છે તેના દ્વારા સીમિત કરી શકાય છે. અંદાજ ગુણોત્તર એન. એફ. (એલ) દ્વારા નેક્સ્ટફિટ દ્વારા ઉપયોગમાં લેવાતા ડબ્બાની સંખ્યા સૂચવે છે, અને ઓ. પી. ટી. (એલ) દ્વારા એલ. માટે શક્ય ડબ્બાની મહત્તમ સંખ્યા સૂચવે છે. સાબિતીનો અંતઃપ્રેરણા નીચે મુજબ છે. આ અલ્ગોરિધમ દ્વારા ઉપયોગમાં લેવાતા ડબ્બાઓની સંખ્યા ડબ્બાઓની મહત્તમ સંખ્યાના બમણાથી વધુ નથી. બીજા શબ્દોમાં કહીએ તો, 2 ડબ્બાઓ મહત્તમ અડધા ભરેલા હોવા અશક્ય છે કારણ કે આવી સંભાવના સૂચવે છે કે અમુક સમયે, બરાબર એક ડબ્બા મહત્તમ અડધા ભરેલા હતા અને મહત્તમ કદની વસ્તુને સમાવવા માટે નવું ખોલવામાં આવ્યું હતું. પરંતુ પ્રથમમાં ઓછામાં ઓછી જગ્યા હોવાથી, અલ્ગોરિધમ કોઈપણ વસ્તુ માટે નવું બિન ખોલશે નહીં જેનું કદ વધુમાં વધુ હોય. ડબ્બા કરતાં વધુ ભર્યા પછી અથવા તેના કરતા મોટા કદની વસ્તુ આવે તો જ અલ્ગોરિધમ નવો ડબ્બા ખોલી શકે છે. આમ જો આપણી પાસે ડબ્બા હોય, તો ઓછામાં ઓછા અડધાથી વધુ ડબ્બા ભરેલા હોય છે. તેથી, તા. કારણ કે તે મહત્તમ મૂલ્યની નીચી સીમા છે, આપણે તે મેળવીએ છીએ અને તેથી. લોઅર બાઉન્ડ દરેક માટે, એવી સૂચિ અસ્તિત્વમાં છે કે અને. યાદીઓનો પરિવાર કે જેના માટે તે ધરાવે છે તે સાથે દ્વારા આપવામાં આવે છે. આ સૂચિ માટેના શ્રેષ્ઠ ઉકેલમાં કદની બે વસ્તુઓ અને કદની વસ્તુઓ સાથેનો એક ડબ્બો હોય છે (એટલે કે, કુલ ડબ્બો), જ્યારે એન. એફ. દ્વારા પેદા થયેલ ઉકેલમાં કદની એક વસ્તુ અને કદની એક વસ્તુ સાથે ડબ્બો હોય છે. મર્યાદિત વસ્તુનું કદ જો વસ્તુનું મહત્તમ કદ હોય, તો એસિમ્પ્ટોટિક અંદાજ ગુણોત્તર સંતોષાય છેઃ બધા માટે; બધા માટે. અન્ય ગુણધર્મો નેક્સ્ટ-ફિટ એક યાદી અને તેના ઇન્વર્સને સમાન સંખ્યામાં ડબ્બાઓમાં પેક કરે છે. નેક્સ્ટ-કે-ફિટ (એનકેએફ) નેક્સ્ટ-કે-ફિટ એ નેક્સ્ટ-ફિટનો એક પ્રકાર છે, પરંતુ માત્ર એક ડબ્બા ખુલ્લા રાખવાને બદલે, અલ્ગોરિધમ છેલ્લા ડબ્બા ખુલ્લા રાખે છે અને પ્રથમ ડબ્બા પસંદ કરે છે જેમાં વસ્તુ બંધબેસે છે. કારણ કે, એન. કે. એફ. એન. એફ. ના પરિણામોની સરખામણીમાં સુધારેલા પરિણામો પહોંચાડે છે, જો કે, તેના કરતા મોટા સ્થિર મૂલ્યોમાં વધારો અલ્ગોરિધમને તેના સૌથી ખરાબ-કેસ વર્તનમાં વધુ સુધારે છે. જો અલ્ગોરિધમ એ લગભગ એનીફિટ-અલ્ગોરિધમ છે અને પછી. નેક્સ્ટ-ફિટ-ડિક્રીઝિંગ (એન. એફ. ડી.) એ નેક્સ્ટ-ફિટનો ઓફલાઇન પ્રકાર છેઃ તે તમામ ઇનપુટ વસ્તુઓને સ્વીકારે છે, તેમને ઉતરતા કદ દ્વારા ઓર્ડર કરે છે અને નેક્સ્ટ-ફિટને કૉલ કરે છે. તેનો એસિમ્પ્ટોટિક અંદાજ ગુણોત્તર ઘણો સારો છેઃ 2 ને બદલે 1.7 કરતા ઓછો. સંદર્ભો બિન પેકિંગ