Harmonic bin packing
હાર્મોનિક બિન-પેકિંગ એ બિન પેકિંગ માટે ઓનલાઇન અલ્ગોરિધમ્સનો એક પરિવાર છે. આવા અલ્ગોરિધમનો ઇનપુટ વિવિધ કદની વસ્તુઓની સૂચિ છે. આઉટપુટ એ એક પેકિંગ છે-વસ્તુઓનું નિશ્ચિત ક્ષમતાના ડબ્બામાં વિભાજન, જેમ કે દરેક ડબ્બામાં વસ્તુઓના કદનો સરવાળો મહત્તમ ક્ષમતા પર હોય છે. આદર્શ રીતે, આપણે શક્ય તેટલા ઓછા ડબ્બાનો ઉપયોગ કરવા માંગીએ છીએ, પરંતુ ડબ્બાની સંખ્યા ઘટાડવી એ એન. પી.-હાર્ડ સમસ્યા છે. હાર્મોનિક બિન-પેકિંગ અલ્ગોરિધમ્સ હાર્મોનિક પ્રગતિને અનુસરીને વસ્તુઓને તેમના કદના આધારે વર્ગોમાં વિભાજિત કરવા પર આધાર રાખે છે. આ વિચારના ઘણા પ્રકારો છે. હાર્મોનિક-કે અલ્ગોરિધમ કદના અંતરાલને સુસંગત રીતે અને તેના જેવા ટુકડાઓમાં વિભાજિત કરે છે. એક વસ્તુને-વસ્તુ કહેવામાં આવે છે, જો. અલ્ગોરિધમ ખાલી ડબ્બાના સમૂહને દરેક વસ્તુના પ્રકાર માટે એક બિન પ્રકાર માટે અનંત વર્ગોમાં વિભાજિત કરે છે. પ્રકારના ડબ્બાનો ઉપયોગ ફક્ત પ્રકારની વસ્તુઓને પેક કરવા માટે કરવામાં આવે છે. માટે પ્રકારનાં દરેક બિનમાં બરાબર-વસ્તુઓ હોઈ શકે છે. અલ્ગોરિધમ હવે નીચે પ્રમાણે કાર્ય કરે છેઃ જો આગામી વસ્તુ-વસ્તુ માટે હોય, તો વસ્તુને પ્રથમ (માત્ર ખુલ્લી) ડબ્બામાં મૂકવામાં આવે છે જેમાં એક કરતા ઓછા ટુકડા હોય અથવા જો આવી કોઈ ડબ્બો અસ્તિત્વમાં ન હોય તો તે નવું ખોલે છે. જો આગામી વસ્તુ-આઇટમ હોય, તો અલ્ગોરિધમ તેને નેક્સ્ટ-ફિટનો ઉપયોગ કરીને પ્રકારનાં ડબ્બામાં મૂકે છે. આ અલ્ગોરિધમનો સૌપ્રથમ લી અને લી દ્વારા વર્ણવવામાં આવ્યો હતો. તેમાં સમયની જટિલતા છે જ્યાં n એ ઇનપુટ વસ્તુઓની સંખ્યા છે. દરેક તબક્કે, મોટાભાગે ખુલ્લા ડબ્બો હોય છે જેનો ઉપયોગ સંભવિત રીતે વસ્તુઓ મૂકવા માટે થઈ શકે છે, એટલે કે, તે કે-બાઉન્ડેડ સ્પેસ અલ્ગોરિધમ છે. લી અને લીએ એસિમ્પ્ટોટિક અંદાજ ગુણોત્તરનો પણ અભ્યાસ કર્યો હતો. તેઓએ એક ક્રમ વ્યાખ્યાયિત કર્યો, અને સાબિત કર્યું કે તેના માટે તે ધરાવે છે. કારણ કે તે તેને જાળવી રાખે છે. વધુમાં, તેઓએ રિફાઈન્ડ-હાર્મોનિક (આર. એચ.) માટે સૌથી ખરાબ ઉદાહરણોનું એક કુટુંબ રજૂ કર્યું રિફાઈન્ડ-હાર્મોનિક રિફાઈન્ડ-ફર્સ્ટ-ફિટના વિચારો સાથે હાર્મોનિક-કે અલ્ગોરિધમનો વિચારોને જોડે છે. તે રિફાઈન્ડ-ફર્સ્ટ-ફિટ જેવી વસ્તુઓ કરતાં મોટી વસ્તુઓ મૂકે છે, જ્યારે નાની વસ્તુઓ હાર્મોનિક-કે નો ઉપયોગ કરીને મૂકવામાં આવે છે. આ વ્યૂહરચના માટેનો અંતઃપ્રેરણા એ છે કે માત્ર તેના કરતા મોટા ટુકડાઓ ધરાવતા ડબ્બાઓ માટે વિશાળ કચરો ઘટાડવો. અલ્ગોરિધમ નીચેના અંતરાલોના સંદર્ભમાં વસ્તુઓનું વર્ગીકરણ કરે છેઃ,,,, માટે, અને. અલ્ગોરિધમ-વસ્તુઓને હાર્મોનિક-કેની જેમ મૂકે છે, જ્યારે તે અને વસ્તુઓની અલગ વ્યૂહરચનાને અનુસરે છે. વસ્તુઓ અને વસ્તુઓને ડબ્બામાં પેક કરવાની ચાર શક્યતાઓ છે. એક-ડબ્બામાં માત્ર એક જ વસ્તુ હોય છે. એક-ડબ્બામાં માત્ર એક જ વસ્તુ હોય છે. એક-ડબ્બામાં એક વસ્તુ અને એક વસ્તુ હોય છે. એક-ડબ્બામાં બે વસ્તુઓ હોય છે. એક-ડબ્બો એ ડબ્બાને સૂચવે છે જે બીજી વસ્તુ સમાવવા માટે નિયુક્ત કરવામાં આવે છે. અલ્ગોરિધમ ઉકેલમાં અનુરૂપ ડબ્બાની સંખ્યાઓની ગણતરી કરવા માટે N _ a, N _ b, N _ ab, N _ b b અને N _ b 'સંખ્યાઓનો ઉપયોગ કરે છે. વધુમાં, યાદી L = (i _ 1, \dot i _ n): 1 માટે N _ c = N _ b + N _ ab અલ્ગોરિધમ રિફાઈન્ડ-હાર્મોનિક-k. N _ a = N _ b = N _ bb = N _ b '= N _ c = 02. જો i _ j એ I _ k-પીસ હોય તો તેને પેક કરવા માટે એલ્ગોરિધમ હાર્મોનિક-k નો ઉપયોગ કરો. અન્યથા જો i _ j એ I _ a-આઇટમ હોય તો પછી જો N _ b! = 1 હોય, તો પછી i _ j ને કોઈપણ J _ b-બિનમાં પેક કરો; N _ b--; N _ ab + +; અન્યથા i _ j ને નવા (ખાલી) બિનમાં મૂકો; N _ a + +; 4. અન્યથા જો i _ j એ I _ b-આઇટમ હોય તો પછી જો N _ b '= 1 હોય તો i _ j ને I _ b'-બિનમાં મૂકો; N _ b '= 0; N _ bb + +; 5. અન્યથા જો N _ bb <= 3N _ c હોય તો પછી i _ b મૂકો. તેઓએ સાબિત કર્યું કે તે માટે તે ધરાવે છે. અન્ય પ્રકારો મોડિફાઇડ હાર્મોનિક (એમ. એચ.) એસિમ્પ્ટોટિક રેશિયો ધરાવે છે. સંશોધિત હાર્મોનિક 2 (MH2) એસિમ્પ્ટોટિક ગુણોત્તર ધરાવે છે. હાર્મોનિક + 1 (H + 1) એસિમ્પ્ટોટિક ગુણોત્તર ધરાવે છે. હાર્મોનિક + + (H + +) એસિમ્પ્ટોટિક ગુણોત્તર ધરાવે છે અને. સંદર્ભો બિન પેકિંગ