First-fit-decreasing bin packing
ફર્સ્ટ-ફિટ-ડિક્રીઝિંગ (એફ. એફ. ડી.) એ બિન પેકિંગ માટેનું એક અલ્ગોરિધમ છે. તેનું ઇનપુટ વિવિધ કદની વસ્તુઓની યાદી છે. તેનું ઉત્પાદન એક પેકિંગ છે-વસ્તુઓનું નિશ્ચિત ક્ષમતાના ડબ્બામાં વિભાજન, જેમ કે દરેક ડબ્બામાં વસ્તુઓના કદનો સરવાળો મહત્તમ ક્ષમતા હોય છે. આદર્શ રીતે, આપણે શક્ય તેટલા ઓછા ડબ્બાનો ઉપયોગ કરવા માંગીએ છીએ, પરંતુ ડબ્બાની સંખ્યા ઘટાડવી એ એન. પી.-હાર્ડ સમસ્યા છે, તેથી આપણે લગભગ-શ્રેષ્ઠ હ્યુરિસ્ટિકનો ઉપયોગ કરીએ છીએ. વર્ણન એફ. એફ. ડી. અલ્ગોરિધમ નીચે પ્રમાણે કામ કરે છે. સૌથી મોટીથી લઈને સૌથી નાની વસ્તુઓનો ઓર્ડર આપો. એક નવો ખાલી ડબ્બો ખોલો, બિન #1. સૌથી મોટીથી લઈને સૌથી નાની દરેક વસ્તુ માટે, પ્રથમ ડબ્બો શોધો જેમાં વસ્તુ બંધબેસે છે, જો કોઈ હોય તો. જો આવી પેટી મળી આવે, તો તેમાં નવી વસ્તુ મૂકો. નહિંતર, એક નવો ખાલી ડબ્બો ખોલો અને તેમાં નવી વસ્તુ મૂકો. ટૂંકમાંઃ એફ. એફ. ડી. ઘટતા કદ દ્વારા વસ્તુઓનો ઓર્ડર આપે છે, અને પછી ફર્સ્ટ-ફિટ બિન પેકિંગ કહે છે. એફ. એફ. ડી. અલ્ગોરિધમનું સમકક્ષ વર્ણન નીચે મુજબ છે. સૌથી મોટીથી લઈને સૌથી નાની વસ્તુઓનો ઓર્ડર આપો. જ્યારે વસ્તુઓ બાકી છેઃ એક નવો ખાલી ડબ્બો ખોલો. સૌથી મોટીથી લઈને સૌથી નાની દરેક વસ્તુ માટેઃ જો તે વર્તમાન ડબ્બામાં ફિટ થઈ શકે, તો તેને દાખલ કરો. પ્રમાણભૂત વર્ણનમાં, આપણે વસ્તુઓ પર એકવાર લૂપ કરીએ છીએ, પરંતુ ઘણા ખુલ્લા ડબ્બા રાખીએ છીએ. સમકક્ષ વર્ણનમાં, આપણે ઘણી વખત વસ્તુઓ પર લૂપ કરીએ છીએ, પરંતુ દરેક વખતે માત્ર એક જ ખુલ્લી ડબ્બો રાખીએ છીએ. કામગીરીનું વિશ્લેષણ એફ. એફ. ડી. ની કામગીરીનું અનેક તબક્કામાં વિશ્લેષણ કરવામાં આવ્યું હતું. નીચે, એફ. એફ. ડી. દ્વારા ઇનપુટ સમૂહ એસ અને બિન-ક્ષમતા સી માટે ઉપયોગમાં લેવાતા ડબ્બાની સંખ્યા સૂચવે છે. જ્હોન્સને તેમના ડોક્ટરલ થીસીસમાં સાબિત કર્યું કે કોઈપણ કિસ્સામાં એસ અને ક્ષમતા સી. 1985 માં, બી. એસ. બેકરે થોડો સરળ પુરાવો આપ્યો અને બતાવ્યું કે એડિટિવ કોન્સ્ટન્ટ 3 થી વધુ નથી. યુએ મિનિએ સાબિત કર્યું કે 1991માં અને 1997માં લી રોંગેંગ સાથે મળીને આ વિશ્લેષણમાં સુધારો કર્યો. 2007 માં જ્યોર્જી ડોસાએ ચુસ્ત બાઉન્ડ સાબિત કર્યું અને જેના માટે એક ઉદાહરણ રજૂ કર્યું. સૌથી ખરાબ ઉદાહરણ ડોસા દ્વારા આપવામાં આવેલ નીચલા બાઉન્ડનું ઉદાહરણ નીચે મુજબ છેઃ બે બિન રૂપરેખાંકનોને ધ્યાનમાં લોઃ;. જો શ્રેષ્ઠ ઉકેલમાં 4 નકલો અને 2 નકલો હોય, તો એફ. એફ. ડી. નીચેના ડબ્બાઓની ગણતરી કરશેઃ રૂપરેખાંકન સાથે 4 ડબ્બા, રૂપરેખાંકન સાથે 1 ડબ્બા, રૂપરેખાંકન સાથે 1 ડબ્બા, રૂપરેખાંકન સાથે 1 ડબ્બા, રૂપરેખાંકન સાથે 1 અંતિમ ડબ્બા, એટલે કે કુલ 8 ડબ્બા, જ્યારે મહત્તમમાં માત્ર 6 ડબ્બા હોય છે. તેથી, ઉપલી સીમા ચુસ્ત છે, કારણ કે. આ ઉદાહરણને તમામ કદમાં વિસ્તૃત કરી શકાય છેઃ શ્રેષ્ઠ રૂપરેખાંકનમાં 9k + 6 ડબ્બા છેઃ 6k + 4 પ્રકાર B1 અને 3k + 2 પ્રકાર B2. પરંતુ એફ. એફ. ડી. ને ઓછામાં ઓછા 11 હજાર + 8 ડબ્બાની જરૂર છે. એકવિધતાના ગુણધર્મો અંતર્જ્ઞાનથી વિપરીત, સીનું એકવિધ કાર્ય નથી. તેવી જ રીતે, એસમાં વસ્તુઓના કદનું એકવિધ કાર્ય નથીઃ શક્ય છે કે વસ્તુ કદમાં સંકોચાય, પરંતુ ડબ્બાની સંખ્યામાં વધારો થાય. જો કે, એફ. એફ. ડી. અલ્ગોરિધમ "એસિમ્પ્ટોટિક મોનોટોનિક" ગુણધર્મ ધરાવે છે, જે નીચે પ્રમાણે વ્યાખ્યાયિત થયેલ છે. દરેક ઉદાહરણ S અને પૂર્ણાંક m માટે, મિનકેપ (S, m) ને સૌથી નાની ક્ષમતા C એવી રીતે રહેવા દો કે દરેક પૂર્ણાંક m માટે, મિનરેશિઓ (m) એ r ≤ 1 સંખ્યાઓની અનંત સંખ્યા એવી રીતે હોવી જોઈએ કે, તમામ ઇનપુટ સમૂહો S માટે,. આ તે રકમ છે જેના દ્વારા આપણે ડબ્બાઓને "ફૂલાવવાની" જરૂર છે જેથી એફ. એફ. ડી. ડબ્બાઓની મહત્તમ સંખ્યા પ્રાપ્ત કરે. પછી, દરેક ઇનપુટ S માટે અને દરેક r ± લઘુતમ ગુણોત્તર (m) માટે,. આ, ખાસ કરીને, દર્શાવે છે કે ઉપરોક્ત વ્યાખ્યામાં અનંતને લઘુત્તમ દ્વારા બદલી શકાય છે. ઉદાહરણો ઉદાહરણ તરીકે, ધારો કે ઇનપુટ છેઃ 44,24,24,22,21,17,8,6. ક્ષમતા 60 સાથે, એફ. એફ. ડી. 3 ડબ્બા પેક કરે છેઃ 44,8,8; 24,24,6,6; 22,21,17. પરંતુ ક્ષમતા 61 સાથે, એફ. એફ. ડી. 4 ડબ્બા પેક કરે છેઃ 44,17; 24,24,8; 22,21,8,6; 6. આનું કારણ એ છે કે, ક્ષમતા 61 સાથે, 17 પ્રથમ ડબ્બામાં બંધબેસે છે, અને આમ નીચેના 8,8 નો માર્ગ અવરોધે છે. બીજા ઉદાહરણ તરીકે, ધારો કે ઇનપુટ્સ છેઃ 51,28,28,28,27,25,12,12,10,10,10,10,10,10,10,10. ક્ષમતા 75 સાથે, એફ. એફ. ડી. 4 ડબ્બાઓ પેક કરે છેઃ 51,12,12,28,28,10,28,27,10,25,10,10,10,10, પરંતુ ક્ષમતા 76 સાથે, તેને 5 ડબ્બાઓની જરૂર છેઃ 51,25,28,28,12,27,12,10,10,10,10,10. ક્ષમતા 60 સાથે ઉપરોક્ત ઉદાહરણનો વિચાર કરો. જો 17 16 બને, તો પરિણામી પેકિંગ છેઃ 44,16; 24,24,8; 22,21,8,6; 6. 'મોડિફાઇડ ફર્સ્ટ-ફિટ-ડીક્રીઝિંગ મોડિફાઇડ ફર્સ્ટ ફિટ ડીસ્ક્રીઝિંગ' (એમ. એફ. એફ. ડી.) અડધા ડબ્બાથી મોટી વસ્તુઓ માટે એફ. એફ. ડી. પર સુધારો કરે છે, જેમાં વસ્તુઓને કદ દ્વારા મોટા, મધ્યમ, નાના અને નાના એમ ચાર કદના વર્ગોમાં વર્ગીકૃત કરવામાં આવે છે, જે અનુક્રમે કદ> 1/2 ડબ્બા,> 1/3 ડબ્બા,> 1/6 ડબ્બા અને નાની વસ્તુઓને અનુરૂપ હોય છે. પછી તે પાંચ તબક્કાઓમાંથી પસાર થાય છેઃ દરેક મોટી વસ્તુ માટે એક ડબ્બો ફાળવો, જેનો ક્રમ સૌથી મોટો અને સૌથી નાનો હોય. ડબ્બાઓમાંથી આગળ વધો. દરેક પરઃ જો બાકીની સૌથી નાની મધ્યમ વસ્તુ બંધબેસતી ન હોય, તો આ ડબ્બાને અવગણો. નહિંતર, સૌથી મોટી બાકી રહેલી મધ્યમ વસ્તુ મૂકો જે બંધબેસે છે. મધ્યમ વસ્તુ ન હોય તેવા ડબ્બામાંથી પાછળની તરફ આગળ વધો. દરેક પરઃ જો બાકીની બે સૌથી નાની નાની વસ્તુઓ બંધબેસતી ન હોય, તો આ ડબ્બાને અવગણો. નહિંતર, બાકી રહેલી સૌથી નાની નાની વસ્તુ અને સૌથી મોટી બાકી રહેલી નાની વસ્તુ મૂકો જે બંધબેસે છે. બધા ડબ્બામાંથી આગળ વધો. જો કોઈપણ કદના વર્ગની બાકીની સૌથી નાની વસ્તુ બંધબેસતું નથી, તો આ ડબ્બાને અવગણો. નહિંતર, સૌથી મોટી વસ્તુ મૂકો જે બંધબેસે છે અને આ ડબ્બામાં રહે છે. બાકીની વસ્તુઓને નવા ડબ્બામાં પેક કરવા માટે એફ. એફ. ડી. નો ઉપયોગ કરો. આ અલ્ગોરિધમનો સૌપ્રથમ અભ્યાસ જ્હોનસન અને ગેરી દ્વારા 1985માં કરવામાં આવ્યો હતો, જ્યાં તેમણે તે સાબિત કર્યું હતું. 1995માં યુએ અને ઝાંગ દ્વારા આ મર્યાદામાં સુધારો કરવામાં આવ્યો હતો, જેમણે તે સાબિત કર્યું હતું. અન્ય પ્રકારો બેસ્ટ-ફિટ-ડિક્રીઝિંગ (બી. એફ. ડી.) એ એફ. એફ. ડી. સાથે ખૂબ સમાન છે, સિવાય કે સૂચિને સૉર્ટ કર્યા પછી, તેની પ્રક્રિયા બેસ્ટ-ફિટ બિન પેકિંગ દ્વારા કરવામાં આવે છે. તેનો એસિમ્પ્ટોટિક અંદાજ ગુણોત્તર FFD-11/9 જેટલો જ છે. અમલીકરણ પાયથોનઃ પી. આર. ટી. પી. પી. પેકેજમાં ફર્સ્ટ-ફિટ ઘટવાનું અમલીકરણ છે. મલ્ટીફિટ અલ્ગોરિધમ પણ જુઓ-સમાન-મશીનોના સમયપત્રક માટેનું એક અલ્ગોરિધમ, જે એફ. એફ. ડી. નો સબરૂટીન તરીકે ઉપયોગ કરે છે. સંદર્ભો બિન પેકિંગ