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