First-fit bin packing
ફર્સ્ટ-ફિટ (એફ. એફ.) એ બિન પેકિંગ માટેનું ઓનલાઇન અલ્ગોરિધમ છે. તેનું ઇનપુટ વિવિધ કદની વસ્તુઓની યાદી છે. તેનું ઉત્પાદન એક પેકિંગ છે-વસ્તુઓનું નિશ્ચિત ક્ષમતાના ડબ્બામાં વિભાજન, જેમ કે દરેક ડબ્બામાં વસ્તુઓના કદનો સરવાળો મહત્તમ ક્ષમતા હોય છે. આદર્શ રીતે, આપણે શક્ય તેટલા ઓછા ડબ્બાનો ઉપયોગ કરવા માંગીએ છીએ, પરંતુ ડબ્બાની સંખ્યા ઘટાડવી એ એન. પી.-હાર્ડ સમસ્યા છે. ફર્સ્ટ-ફિટ અલ્ગોરિધમ નીચેના હ્યુરિસ્ટિકનો ઉપયોગ કરે છેઃ તે ખુલ્લા ડબ્બાની યાદી રાખે છે, જે શરૂઆતમાં ખાલી હોય છે. જ્યારે કોઈ વસ્તુ આવે, ત્યારે પ્રથમ ડબ્બો શોધો જેમાં વસ્તુ ફિટ થઈ શકે, જો કોઈ હોય તો. જો આવી બિન મળી આવે, તો નવી વસ્તુ તેની અંદર મૂકવામાં આવે છે. નહિંતર, એક નવો ડબ્બો ખોલવામાં આવે છે અને આવનારી વસ્તુ તેની અંદર મૂકવામાં આવે છે. અંદાજ ગુણોત્તર એફએફ (એલ) દ્વારા ફર્સ્ટ-ફિટ દ્વારા ઉપયોગમાં લેવાતા ડબ્બાઓની સંખ્યા અને ઓ. પી. ટી. (એલ) દ્વારા સૂચિ એલ માટે શક્ય ડબ્બાઓની મહત્તમ સંખ્યા સૂચવે છે. એફએફ (એલ) નું વિશ્લેષણ ઘણા પગલાંઓમાં કરવામાં આવ્યું હતું. એફએફ માટે પ્રથમ ઉપલી સીમા 1971માં ઉલમેન દ્વારા સાબિત કરવામાં આવી હતી. 1972માં, ગેરે, ગ્રેહામ અને ઉલમેન, જ્હોનસન અને ડેમર્સ દ્વારા આ ઉપલી સીમા સુધારવામાં આવી હતી. 1976માં, તેમાં ગેરી, ગ્રેહામ, જ્હોનસન, યાઓ અને ચી-ચિહ દ્વારા સુધારો કરવામાં આવ્યો હતો, જે અને ની અભિન્નતાને કારણે સમકક્ષ છે. આગામી સુધારો, 2010 માં ઝિયા અને ટેન દ્વારા, ની મર્યાદાને ઘટાડી. છેવટે, 2013 માં, ડોસા અને સ્ગોલ દ્વારા આ મર્યાદામાં સુધારો કરવામાં આવ્યો હતો. તેઓ એક ઉદાહરણ ઇનપુટ સૂચિ પણ રજૂ કરે છે, જે આ બાઉન્ડ સાથે મેળ ખાય છે. નીચે આપણે સાબિતી વિચાર સમજાવીએ છીએ. એસિમ્પ્ટોટિક ગુણોત્તર વધુમાં વધુ 2 અહીં એ વાતનો પુરાવો છે કે એસિમ્પ્ટોટિક ગુણોત્તર વધુમાં વધુ 2 છે. જો અડધાથી ઓછી રકમ ધરાવતી એફ. એફ. ડબ્બા હોય, તો બાકીની તમામ વસ્તુઓનું કદ અડધાથી વધુ હોય છે, તેથી નીચેના તમામ ડબ્બાઓનો સરવાળો અડધાથી વધુ હોય છે. તેથી, મહત્તમ એક સિવાયના તમામ એફ. એફ. ડબ્બામાં ઓછામાં ઓછો અડધો ભાગ હોય છે. બધા શ્રેષ્ઠ ડબ્બામાં મહત્તમ 1 નો સરવાળો હોય છે, તેથી તમામ કદનો સરવાળો મહત્તમ ઓ. પી. ટી. હોય છે. તેથી, એફ. એફ. ડબ્બાની સંખ્યા મહત્તમ 1 + ઓ. પી. ટી./(1/2) = 2 * ઓ. પી. ટી. + 1 એસિમ્પ્ટોટિક રેશિયો મહત્તમ 1.75 છે. જો ત્યાં 2/3 કરતાં ઓછી રકમ ધરાવતી એફ. એફ. બિન હોય, તો બાકીની તમામ વસ્તુઓનું કદ 1/3 કરતા વધારે હોય છે. કદ મહત્તમ 1/2 હોવાથી, નીચેના તમામ ડબ્બામાં (કદાચ છેલ્લા એક સિવાય) ઓછામાં ઓછી બે વસ્તુઓ હોય છે, અને રકમ 2/3 કરતા મોટી હોય છે. તેથી, મહત્તમ એક સિવાયના તમામ એફ. એફ. ડબ્બામાં ઓછામાં ઓછો 2/3નો સરવાળો હોય છે, અને એફ. એફ. ડબ્બાની સંખ્યા મહત્તમ 2 + ઓ. પી. ટી./(2/3) = 3/2 * ઓ. પી. ટી. + 1 હોય છે. "સમસ્યારૂપ" વસ્તુઓ એ છે કે જેનું કદ અડધો ભાગ કરતાં મોટું હોય. તેથી, વિશ્લેષણમાં સુધારો કરવા માટે, ચાલો દરેક વસ્તુને અડધાથી મોટી આરનું બોનસ આપીએ. વસ્તુનું વજન તેના કદ અને તેના બોનસ તરીકે વ્યાખ્યાયિત કરો. વસ્તુઓના સમૂહના વજનને તેની સામગ્રીના વજનના સરવાળા તરીકે વ્યાખ્યાયિત કરો. હવે, એક વસ્તુ સાથે દરેક એફ. એફ. ડબ્બાનું વજન (મહત્તમ એક સિવાય) ઓછામાં ઓછું 1/2 + આર છે, અને બે અથવા વધુ વસ્તુઓ સાથે દરેક એફ. એફ. ડબ્બાનું વજન (મહત્તમ એક સિવાય) 2/3 છે. આર = 1/6 લેવાથી તમામ એફએફ ડબ્બાનું વજન ઓછામાં ઓછું 2/3 થાય છે. બીજી બાજુ, શ્રેષ્ઠ પેકિંગમાં દરેક ડબ્બાનું વજન વધુમાં વધુ 1 + આર = 7/6 હોય છે, કારણ કે આવા દરેક ડબ્બામાં વધુમાં વધુ એક વસ્તુ અડધી કરતાં મોટી હોય છે. તેથી, તમામ વસ્તુઓનું કુલ વજન મહત્તમ 7/6 * ઓ. પી. ટી. છે, અને એફ. એફ. ડબ્બાની સંખ્યા મહત્તમ 2 + (7/6 * ઓ. પી. ટી./(2/3)) = 7/4 * ઓ. પી. ટી. + 2 છે. એસિમ્પ્ટોટિક રેશિયો વધુમાં વધુ 1.7 નીચે આપેલા પુરાવા પરથી સ્વીકારવામાં આવે છે. ઇનપુટ આઇટમના વજનને આઇટમના કદ x કેટલાક બોનસ તરીકે વ્યાખ્યાયિત કરો જે નીચે મુજબ ગણવામાં આવે છેઃ એસિમ્પ્ટોટિક અંદાજ ગુણોત્તર બે દાવાઓથી અનુસરે છેઃ શ્રેષ્ઠ પેકિંગમાં, દરેક ડબ્બાનું વજન મહત્તમ 17/12 હોય છે; ફર્સ્ટ-ફિટ પેકિંગમાં, દરેક ડબ્બાનું સરેરાશ વજન ઓછામાં ઓછું 5/6 = 10/12 હોય છે. તેથી, લક્ષણવિહીન રીતે, એફ. એફ. પેકિંગમાં ડબ્બાઓની સંખ્યા મહત્તમ 17/10 * ઓ. પી. ટી. હોવી જોઈએ. દાવો 1 માટે, તે સાબિત કરવા માટે પૂરતું છે કે, કોઈપણ સમૂહ B માટે મહત્તમ 1 રકમ સાથે, બોનસ (B) મહત્તમ 5/12 છે. ખરેખરઃ જો બી પાસે 1/2 થી મોટી કોઈ વસ્તુ ન હોય, તો તેમાં 1/6 કરતા મોટી મહત્તમ પાંચ વસ્તુઓ હોય છે, અને તેમાંથી દરેકનું બોનસ મહત્તમ 1/12 હોય છે; જો બી પાસે 1/2 થી મોટી વસ્તુ હોય પરંતુ [1/3,1 2] માં કોઈ વસ્તુ ન હોય, તો તેમાં (1/6,1 3) માં મહત્તમ બે વસ્તુઓ માટે જગ્યા હોય છે, અને તેમના બોનસનો સરવાળો મહત્તમ (1/2/2-1/6) = 1/12 હોય છે, તેથી કુલ બોનસ 4/12 + 1/12 = 5/12 છે. જો બી પાસે 1/2 કરતા મોટી વસ્તુ અને [1/3,1 2] માં વસ્તુ હોય, તો તેમાં 1/6 કરતા મોટા કદની વસ્તુઓ માટે વધુ જગ્યા નથી, તેથી કુલ બોનસ ફરીથી 4/12+1 12 = 5/12 છે. તેથી, B નું વજન વધુમાં વધુ 1 + 5/12 = 17/12 છે. દાવો 2 માટે, પહેલા એક જ વસ્તુ સાથે એફ. એફ. બિન બી. નો વિચાર કરો. જો સરવાળો (બી) <1/2 હોય, તો-જે રીતે એફએફ કામ કરે છે-બી પછી પ્રક્રિયા કરાયેલી તમામ વસ્તુઓ 1/2 કરતા મોટી હોવી જોઈએ (અન્યથા તે બીમાં દાખલ કરવામાં આવી હોત). તેથી, સરવાળો <1/2 સાથે વધુમાં વધુ એક એફ. એફ. બિન હોય છે. હવે સરવાળો (બી)> 1/2 સાથે એક જ વસ્તુ સાથે અન્ય તમામ ડબ્બા બી નો વિચાર કરો. આ તમામ ડબ્બાઓ માટે, વજન (B)> 1/2+1 3 = 5/6 છે. હવે બે કે તેથી વધુ વસ્તુઓ સાથે એફ. એફ. ડબ્બો બી નો વિચાર કરો. જો સરવાળો (બી) <2/3 હોય, તો પછી-જે રીતે એફએફ કામ કરે છે-બી પછી પ્રક્રિયા કરવામાં આવેલી તમામ વસ્તુઓ 1/3 કરતા મોટી હોવી જોઈએ (અન્યથા તે બીમાં દાખલ કરવામાં આવી હોત). તેથી, બે કે તેથી વધુ વસ્તુઓવાળા નીચેના બધા ડબ્બો 2/3 કરતા મોટા હોય છે. તેથી બે અથવા વધુ વસ્તુઓ અને સરવાળો <2/3 સાથે વધુમાં વધુ એક એફ. એફ. બિન હોય છે. હવે બે કે તેથી વધુ વસ્તુઓ અને સરવાળો> 2/3 સાથેના અન્ય તમામ ડબ્બાને ધ્યાનમાં લો. તેમને B [1], B [2],. B [k] દ્વારા દર્શાવો, જે ક્રમમાં તેઓ ખોલવામાં આવે છે. 1,., k માં દરેક i માટે આપણે સાબિત કરીએ છીએ કે B [i] વત્તા B [i + 1] ના બોનસનો સરવાળો ઓછામાં ઓછો 5/6 છેઃ સરવાળો (B [i]) + બોનસ (B [i + 1])> = 5/6. ખરેખર, જો સરવાળો (B [i])> = 5/6 હોય તો અસમાનતા તુચ્છ છે. નહિંતર, ચાલો સરવાળો (B [i]): = 1-x. નોંધ લો કે x એ 1/6 અને 2/6 ની વચ્ચે છે, કારણ કે સરવાળો (B [i]) 2/3 અને 5/6 ની વચ્ચે છે. B [i + 1] ને B [i] પછી ખોલવામાં આવે છે, તેથી B [i + 1] માં ઓછામાં ઓછી બે વસ્તુઓ હોય છે, જેમ કે c1 અને c2, જે B [i] માં બંધબેસતા નથી, એટલે કેઃ c1, c2> 1-સરવાળો (B [i]) = x> 1/6. પછી c1 અને c2 દરેકનું બોનસ ઓછામાં ઓછું x/2-1/12 છે. તેથી, B [i + 1] નું બોનસ ઓછામાં ઓછું x-1/6 છે, તેથી સરવાળો (B [i]) + બોનસ (B [i + 1])> = (1-x) + (x-1/6) = 5/6 છે. આપણે ઉપરોક્ત અસમાનતાને ક્રમિક જોડીઓ પર લાગુ કરી શકીએ છીએ અને મેળવી શકીએ છીએઃ સરવાળો (બી [1]) + બોનસ (બી [2]) + સરવાળો (બી [2]) + બોનસ (બી [3]) + + સરવાળો (બી [કે-1]) + બોનસ (બી [કે])> = 5/6 * (કે-1). તેથી, તમામ એફ. એફ. ડબ્બાઓનું કુલ વજન ઓછામાં ઓછું 5/6 * (એફ. એફ.-3) છે (જ્યાં આપણે એક વસ્તુના ડબ્બા માટે 3 ને સરવાળો <1/2 સાથે, એક વસ્તુના ડબ્બા માટે સરવાળો <2/3 સાથે, અને બે વસ્તુના ડબ્બાઓમાંથી કે-1 ને સરવાળો> = 2/3 સાથે બાદ કરીએ છીએ). એકંદરે, આપણને તે 17/12 * OPT> = 5/6 * (FF-3) મળે છે, તેથી FF <= 17/10 * OPT + 3. ડોસા અને Sgall એક કડક વિશ્લેષણ રજૂ કરે છે જે 3 થી છુટકારો મેળવે છે, અને તે FF <= 17/10 * OPT મેળવે છે. લોઅર બાઉન્ડ એવા ઉદાહરણો છે કે જેના પર 1.7OPT નું પ્રદર્શન બાઉન્ડ ચુસ્ત હોય છે. નીચેનું ઉદાહરણ તેના પર આધારિત છે. બિન ક્ષમતા 101 છે, અનેઃ ક્રમ છેઃ 6 (x7), 10 (x7), 16 (x3), 34 (x10), 51 (x10). શ્રેષ્ઠ પેકિંગમાં 10 ડબ્બા હોય છેઃ [51+34 + 16] (x3), [51+34 + 10+6] (x7). તમામ બિન રકમ 101 છે. ફર્સ્ટ ફિટ પેકિંગમાં 17 ડબ્બા હોય છેઃ [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5), [51] (x10). બિન રકમ છેઃ 92,68,68 (x5), 51 (x10). પારિતોષિકો (101 સુધી સામાન્ય) 0,0,16.8 (x5), 33.7 (x10) છે. કુલ વજન (101 સુધી સામાન્ય) 92,68,84.8 (x5), 84.7 (x10) છે. તે જોઈ શકાય છે કે લગભગ તમામ વજન 101 * 5/6 = 84.1 ની નજીક છે. રિફાઈન્ડ ફર્સ્ટ-ફિટ રિફાઈન્ડ-ફર્સ્ટ-ફિટ (આર. એફ. એફ.) એ બિન પેકિંગ માટેનું બીજું ઓનલાઇન અલ્ગોરિધમ છે, જે અગાઉ વિકસિત એફ. એફ. અલ્ગોરિધમમાં સુધારો કરે છે. તે એન્ડ્રુ ચી-ચિહ યાઓ દ્વારા રજૂ કરવામાં આવ્યું હતું. અલ્ગોરિધમ વસ્તુઓને તેમના કદ અનુસાર ચાર વર્ગોમાં વર્ગીકૃત કરવામાં આવે છે (જ્યાં ડબ્બાની ક્ષમતા 1 છે):-ટુકડો-કદ. - ટુકડો-કદ. - ટુકડો-કદ. - ટુકડો-કદ. તેવી જ રીતે, ડબ્બાને ચાર વર્ગોમાં વર્ગીકૃત કરવામાં આવે છેઃ 1,2,3 અને 4. ચાલો એક નિશ્ચિત પૂર્ણાંક હોઈએ. આગળની વસ્તુને બિનમાં સોંપવામાં આવે છે-વર્ગ 1, જો એક-ટુકડો હોય, તો વર્ગ 2, જો એક-ટુકડો હોય, તો વર્ગ 3, જો એક-ટુકડો હોય, પરંતુ કોઈપણ પૂર્ણાંક માટે અત્યાર સુધી જોવાયેલ છઠ્ઠો ટુકડો નહીં. વર્ગ 1, જો અત્યાર સુધી જોવામાં આવેલ છઠ્ઠો ભાગ છે, તો વર્ગ 4, જો એક ભાગ છે. એકવાર વસ્તુનો વર્ગ પસંદ થઈ જાય પછી, તેને પ્રથમ-ફિટ બિન પેકિંગનો ઉપયોગ કરીને તે વર્ગના ડબ્બામાં મૂકવામાં આવે છે. નોંધ લો કે આર. એફ. એફ. એ એની-ફિટ અલ્ગોરિધમ નથી કારણ કે વર્તમાન વસ્તુ ખુલ્લી બિન (અન્ય વર્ગમાંથી) ની અંદર બંધબેસે છે તે હકીકત હોવા છતાં તે નવી બિન ખોલી શકે છે. અંદાજ ગુણોત્તર આર. એફ. એફ. ની અંદાજિત બાંયધરી છે. માટે સાથે યાદીઓનો એક પરિવાર અસ્તિત્વમાં છે. ફર્સ્ટ-ફિટ-ડિક્રીઝિંગ (એફ. એફ. ડી.) એ ફર્સ્ટ-ફિટનો ઓફલાઇન પ્રકાર છેઃ તે તમામ ઇનપુટ વસ્તુઓને સ્વીકારે છે, તેમને ઉતરતા કદ દ્વારા ઓર્ડર કરે છે અને ફર્સ્ટ-ફિટને કૉલ કરે છે. તેનો એસિમ્પ્ટોટિક અંદાજ ગુણોત્તર ઘણો સારો છેઃ 1.7 ને બદલે લગભગ 1.222. અમલીકરણ પાયથોનઃ પીઆરટીપી પેકેજમાં ફર્સ્ટ-ફિટનું અમલીકરણ હોય છે. સંદર્ભો બિન પેકિંગ