Next-fit-decreasing bin packing
નેક્સ્ટ-ફિટ-ડિક્રીઝિંગ (એન. એફ. ડી.) એ બિન પેકિંગ માટેનું એક અલ્ગોરિધમ છે. તેનું ઇનપુટ વિવિધ કદની વસ્તુઓની યાદી છે. તેનું ઉત્પાદન એક પેકિંગ છે-વસ્તુઓનું નિશ્ચિત ક્ષમતાના ડબ્બામાં વિભાજન, જેમ કે દરેક ડબ્બામાં વસ્તુઓના કદનો સરવાળો મહત્તમ ક્ષમતા હોય છે. આદર્શ રીતે, આપણે શક્ય તેટલા ઓછા ડબ્બાનો ઉપયોગ કરવા માંગીએ છીએ, પરંતુ ડબ્બાની સંખ્યા ઘટાડવી એ એન. પી.-હાર્ડ સમસ્યા છે. એન. એફ. ડી. અલ્ગોરિધમ નીચેની સંશોધનાત્મક પદ્ધતિનો ઉપયોગ કરે છેઃ વસ્તુઓને સૌથી મોટાથી નાના સુધી ઓર્ડર કરો. ખાલી ડબ્બાને શરૂ કરો અને તેને "ઓપન બિન" કહો. ક્રમમાં દરેક વસ્તુ માટે, તપાસો કે તે ખુલ્લા ડબ્બામાં બંધબેસે છે કે કેમઃ જો તે બંધબેસે છે, તો તેમાં નવી વસ્તુ મૂકો. નહિંતર, વર્તમાન ડબ્બાને બંધ કરો, નવી ડબ્બો ખોલો અને વર્તમાન વસ્તુને તેની અંદર મૂકો. ટૂંકમાંઃ એન. એફ. ડી. ઘટતા કદ દ્વારા વસ્તુઓનો ઓર્ડર આપે છે, અને પછી નેક્સ્ટ-ફિટ બિન પેકિંગને કૉલ કરે છે. પરફોર્મન્સ અપર બાઉન્ડ બેકર અને કોફમેને સાબિત કર્યું કે, દરેક પૂર્ણાંક r માટે, જ્યારે બધી વસ્તુઓનું કદ મહત્તમ 1/r હોય, ત્યારે RFD નો એસિમ્પ્ટોટિક અંદાજ ગુણોત્તર સંતોષાય છે, જ્યાં એક ક્રમ છે જેના પ્રથમ ઘટકો આશરે 1.69103,1.42312,1.30238 છે. ખાસ કરીને, r = 1 લેવાથી તે સૂચવે છે. પાછળથી, એન. એફ. ડી. નું પણ સંભવિત રીતે વિશ્લેષણ કરવામાં આવ્યું છે. વેરિયન્ટ્સ નેક્સ્ટ-ફિટ એક યાદી અને તેના ઇન્વર્સને સમાન સંખ્યામાં ડબ્બાઓમાં પેક કરે છે. તેથી, નેક્સ્ટ-ફિટ-ઈન્ક્રીઝિંગનું પ્રદર્શન નેક્સ્ટ-ફિટ-ઈન્ક્રીઝિંગ જેવું જ છે. જો કે, જ્યારે સામાન્ય ખર્ચ માળખાં હોય ત્યારે નેક્સ્ટ-ફિટ-ઇન્ક્રેસિંગ વધુ સારું પ્રદર્શન કરે છે. સંદર્ભો બિન પેકિંગ