Partition problem
સંખ્યા સિદ્ધાંત અને કોમ્પ્યુટર વિજ્ઞાનમાં, વિભાજન સમસ્યા અથવા સંખ્યા વિભાજન એ નક્કી કરવાનું કાર્ય છે કે હકારાત્મક પૂર્ણાંકોના આપેલ મલ્ટીસેટ S ને બે ઉપગણ S1 અને S2 માં વિભાજિત કરી શકાય કે કેમ જેથી S1 માં સંખ્યાઓનો સરવાળો S2 માં સંખ્યાઓના સરવાળા બરાબર હોય. જોકે પાર્ટીશનની સમસ્યા એન. પી.-પૂર્ણ છે, ત્યાં એક સ્યુડો-પોલિનોમિયલ ટાઇમ ડાયનેમિક પ્રોગ્રામિંગ સોલ્યુશન છે, અને એવા હ્યુરિસ્ટિક્સ છે જે સમસ્યાને ઘણા કિસ્સાઓમાં હલ કરે છે, ક્યાં તો શ્રેષ્ઠ રીતે અથવા લગભગ. આ કારણોસર, તેને "સૌથી સરળ મુશ્કેલ સમસ્યા" કહેવામાં આવી છે. પાર્ટીશન સમસ્યાનું ઓપ્ટિમાઇઝેશન વર્ઝન છે, જે મલ્ટીસેટ S ને બે સબસેટ S1, S2 માં વિભાજિત કરવાનું છે, જેથી S1 માં તત્વોના સરવાળા અને S2 માં તત્વોના સરવાળા વચ્ચેનો તફાવત ઓછો થાય. ઓપ્ટિમાઇઝેશન વર્ઝન એન. પી.-હાર્ડ છે, પરંતુ વ્યવહારમાં અસરકારક રીતે ઉકેલી શકાય છે. પાર્ટીશન સમસ્યા એ બે સંબંધિત સમસ્યાઓનો એક વિશેષ કેસ છેઃ સબસેટ સમ સમસ્યામાં, ધ્યેય એ S નો સબસેટ શોધવાનો છે જેનો સરવાળો ચોક્કસ લક્ષ્ય સંખ્યા T છે જે ઇનપુટ તરીકે આપવામાં આવે છે (પાર્ટીશન સમસ્યા એ વિશેષ કેસ છે જેમાં T એ S નો અડધો સરવાળો છે). બહુપથ સંખ્યા વિભાજનમાં, એક પૂર્ણાંક પરિમાણ k હોય છે, અને ધ્યેય એ નક્કી કરવાનો હોય છે કે શું S ને સમાન રકમના k ઉપગણમાં વિભાજિત કરી શકાય છે (વિભાજન સમસ્યા એ ખાસ કેસ છે જેમાં k = 2). જો કે, તે 3-પાર્ટીશન સમસ્યા કરતાં તદ્દન અલગ છેઃ તે સમસ્યામાં, સબસેટ્સની સંખ્યા અગાઉથી નક્કી કરવામાં આવતી નથી-તે |S |/3 હોવી જોઈએ, જ્યાં દરેક સબસેટમાં બરાબર 3 ઘટકો હોવા જોઈએ. 3-પાર્ટીશન પાર્ટીશન કરતાં ઘણું મુશ્કેલ છે-જ્યાં સુધી P = NP ન હોય ત્યાં સુધી તેમાં કોઈ સ્યુડો-પોલિનોમિયલ ટાઇમ અલ્ગોરિધમ નથી. આપેલ ઉદાહરણો S = {3,1,1,2,2,1}, પાર્ટીશન સમસ્યાનો માન્ય ઉકેલ બે સમૂહો S1 = {1,1,1,2} અને S2 = {{2,3} છે. બંને સમૂહોનો સરવાળો 5 થાય છે, અને તેઓ S વિભાજન કરે છે. નોંધ લો કે આ ઉકેલ અનન્ય નથી. S1 = {3,1,1} અને S2 = {2,2,1} એ બીજો ઉકેલ છે. હકારાત્મક પૂર્ણાંકોના દરેક મલ્ટીસેટમાં સમાન સરવાળા સાથે બે સબસેટ્સમાં વિભાજન હોતું નથી. આવા સમૂહનું ઉદાહરણ S = {2,5} છે. કોમ્પ્યુટેશનલ કઠિનતા પાર્ટીશનની સમસ્યા એન. પી. હાર્ડ છે. આ સબસેટ સમ પ્રોબ્લેમમાંથી ઘટાડો કરીને સાબિત કરી શકાય છે. સબસેટસમના ઉદાહરણમાં હકારાત્મક પૂર્ણાંકોનો સમૂહ S અને લક્ષ્ય સરવાળો T હોય છે; ધ્યેય એ નક્કી કરવાનો છે કે બરાબર T ના સરવાળા સાથે S નો સબસેટ છે કે કેમ. આવા ઉદાહરણને ધ્યાનમાં રાખીને, પાર્ટીશનનું એક ઉદાહરણ બનાવો જેમાં ઇનપુટ સેટમાં મૂળ સમૂહ વત્તા બે ઘટકો છેઃ z1 અને z2, z1 = સરવાળો (S) અને z2 = 2T સાથે હોય. આ ઇનપુટ સમૂહનો સરવાળો સરવાળો (S) + z1 + z2 = 2 સરવાળો (S) + 2T છે, તેથી પાર્ટીશન માટેનો લક્ષ્ય સરવાળો સરવાળો (S) + T છે. પછી સરવાળો (S′) = T, તેથી સરવાળો (S′z _ 1) = સરવાળો (S) + T, તેથી S′z _ 1 એ પાર્ટીશન ઉદાહરણનો ઉકેલ છે. તેનાથી વિપરીત, ધારો કે વિભાજનના ઉદાહરણનો ઉકેલ S "અસ્તિત્વમાં છે. પછી, S′ માં કાં તો z1 અથવા z2 હોવો જોઈએ, પરંતુ બન્ને નહીં, કારણ કે તેમનો સરવાળો સરવાળો (S) + T કરતા વધારે છે. જો S "માં z1 હોય, તો તેમાં બરાબર T ના સરવાળા સાથે S માંથી તત્વો હોવા જોઈએ, તેથી S" બાદબાકી z1 એ સબસેટસમ ઉદાહરણનો ઉકેલ છે. જો S "માં z2 હોય, તો તેમાં બરાબર સરવાળો (S) − T ના સરવાળા સાથે S માંથી તત્વો હોવા જોઈએ, તેથી S માં અન્ય પદાર્થો સબસેટસમ ઉદાહરણનો ઉકેલ છે. એપ્રોક્સીમેશન એલ્ગોરિધમ્સ ઉપર જણાવ્યા મુજબ, પાર્ટીશન સમસ્યા એ મલ્ટીવે-પાર્ટીશનિંગ અને સબસેટ-સમનો એક ખાસ કેસ છે. તેથી, આ દરેક સમસ્યા માટે વિકસિત અલ્ગોરિધમ્સ દ્વારા તેને ઉકેલી શકાય છે. મલ્ટીવે નંબર પાર્ટીશનિંગ માટે વિકસાવવામાં આવેલા અલ્ગોરિધમ્સમાં નીચેનાનો સમાવેશ થાય છેઃ લોભી નંબર પાર્ટીશનિંગ-સંખ્યાઓ પર લૂપ્સ, અને દરેક સંખ્યાને સેટમાં મૂકે છે જેનો વર્તમાન સરવાળો સૌથી નાનો છે. જો સંખ્યાઓને ક્રમબદ્ધ કરવામાં ન આવે, તો રનટાઇમ O (n) છે અને અંદાજ ગુણોત્તર મહત્તમ 3/2 છે ("અંદાજ ગુણોત્તર" નો અર્થ એલ્ગોરિધમ આઉટપુટમાં મોટો સરવાળો, શ્રેષ્ઠ પાર્ટીશનમાં મોટા સરવાળા દ્વારા વિભાજિત). સંખ્યાઓને ક્રમબદ્ધ કરવાથી રનટાઇમ વધીને ઓ (એન લોગ એન) થાય છે અને અંદાજ ગુણોત્તર સુધરીને 7/6 થાય છે. જો સંખ્યાઓ [0,1] માં સમાનરૂપે વહેંચવામાં આવે, તો અંદાજ ગુણોત્તર લગભગ ચોક્કસ અને અપેક્ષિત હોય છે. સૌથી મોટી વિભેદક પદ્ધતિ (જેને કર્મકાર-કાર્પ અલ્ગોરિધમ પણ કહેવાય છે) સંખ્યાઓને ઉતરતા ક્રમમાં સૉર્ટ કરે છે અને સંખ્યાઓને તેમના તફાવતો દ્વારા વારંવાર બદલે છે. રનટાઇમ જટિલતા ઓ (એન લોગ એન) છે. સૌથી ખરાબ કિસ્સામાં, તેનો અંદાજ ગુણોત્તર સમાન છે-મહત્તમ 7/6. જો કે, સરેરાશ કિસ્સામાં તે લોભી અલ્ગોરિધમ કરતાં ઘણું સારું પ્રદર્શન કરે છેઃ જ્યારે સંખ્યાઓ [0,1] માં સમાનરૂપે વહેંચવામાં આવે છે, ત્યારે તેનો અંદાજ ગુણોત્તર અપેક્ષા મુજબ સૌથી વધુ હોય છે. તે સિમ્યુલેશન પ્રયોગોમાં પણ વધુ સારું પ્રદર્શન કરે છે. મલ્ટિફિટ અલ્ગોરિધમ બિન પેકિંગ માટેના અલ્ગોરિધમ સાથે સંયુક્ત દ્વિસંગી શોધનો ઉપયોગ કરે છે. સૌથી ખરાબ સ્થિતિમાં, તેનો અંદાજ ગુણોત્તર 8/7 છે. સબસેટ સમ પ્રોબ્લેમમાં FPTAS છે જેનો ઉપયોગ પાર્ટીશન પ્રોબ્લેમ માટે પણ કરી શકાય છે, લક્ષ્ય રકમને સરવાળો (S)/2 પર સેટ કરીને. ચોક્કસ અલ્ગોરિધમ્સ ચોક્કસ અલ્ગોરિધમ્સ છે, જે હંમેશા શ્રેષ્ઠ પાર્ટીશન શોધે છે. સમસ્યા એન. પી.-હાર્ડ હોવાથી, આવા અલ્ગોરિધમ્સ સામાન્ય રીતે ઘાતાંકીય સમય લઈ શકે છે, પરંતુ અમુક કિસ્સાઓમાં વ્યવહારીક રીતે ઉપયોગી હોઈ શકે છે. મલ્ટીવે નંબર પાર્ટીશનિંગ માટે વિકસાવવામાં આવેલા અલ્ગોરિધમ્સમાં નીચેનાનો સમાવેશ થાય છેઃ સ્યુડોપોલિનોમિયલ ટાઇમ નંબર પાર્ટીશનિંગ મેમરી લે છે, જ્યાં ઇનપુટમાં સૌથી મોટી સંખ્યા છે. સંપૂર્ણ લોભી અલ્ગોરિધમ (સી. જી. એ.) દ્વિસંગી વૃક્ષનું નિર્માણ કરીને તમામ પાર્ટીશનોને ધ્યાનમાં લે છે. વૃક્ષનું દરેક સ્તર ઇનપુટ નંબરને અનુરૂપ હોય છે, જ્યાં મૂળ સૌથી મોટી સંખ્યાને અનુરૂપ હોય છે, નીચેનું સ્તર આગામી સૌથી મોટી સંખ્યા વગેરેને અનુરૂપ હોય છે. દરેક શાખા એક અલગ સમૂહને અનુરૂપ હોય છે જેમાં વર્તમાન સંખ્યા મૂકી શકાય છે. વૃક્ષને ઊંડાણપૂર્વક-પ્રથમ ક્રમમાં પસાર કરવા માટે માત્ર જગ્યાની જરૂર પડે છે, પરંતુ તેમાં સમય લાગી શકે છે. લોભી હ્યુરિસ્ટિકનો ઉપયોગ કરીને રનટાઇમમાં સુધારો કરી શકાય છેઃ દરેક સ્તરમાં, પ્રથમ શાખા વિકસાવો જેમાં વર્તમાન સંખ્યા સૌથી નાની રકમ સાથે સમૂહમાં મૂકવામાં આવે છે. આ અલ્ગોરિધમ પહેલા લોભી સંખ્યા વિભાજન દ્વારા મળતો ઉકેલ શોધે છે, પરંતુ પછી વધુ સારા ઉકેલો શોધવા માટે આગળ વધે છે. આ વિચારની કેટલીક ભિન્નતાઓ સબસેટ-સમ સમસ્યા માટે સંપૂર્ણ બહુપદી-સમય અંદાજ યોજનાઓ છે, અને તેથી પાર્ટીશન સમસ્યા માટે પણ. સંપૂર્ણ કર્મકાર-કાર્પ અલ્ગોરિધમ (સી. કે. કે.) દ્વિસંગી વૃક્ષનું નિર્માણ કરીને તમામ પાર્ટીશનોને ધ્યાનમાં લે છે. દરેક સ્તર સંખ્યાઓની જોડીને અનુરૂપ છે. ડાબી શાખા તેમને જુદા જુદા ઉપગણમાં મૂકવાને અનુરૂપ છે (એટલે કે, તેમને તેમના તફાવત દ્વારા બદલવામાં આવે છે), અને જમણી શાખા તેમને સમાન ઉપગણમાં મૂકવાને અનુરૂપ છે (એટલે કે, તેમને તેમના સરવાળા દ્વારા બદલવામાં આવે છે). આ અલ્ગોરિધમ પહેલા સૌથી મોટી ભિન્નતા પદ્ધતિ દ્વારા મળેલો ઉકેલ શોધે છે, પરંતુ પછી વધુ સારા ઉકેલો શોધવા માટે આગળ વધે છે. તે અવ્યવસ્થિત કિસ્સાઓમાં સી. જી. એ. કરતા નોંધપાત્ર રીતે વધુ ઝડપથી ચાલે છે. જ્યારે સમાન પાર્ટીશન અસ્તિત્વમાં હોય ત્યારે તેનો ફાયદો ઘણો મોટો હોય છે, અને તે તીવ્રતાના ઘણા ક્રમમાં હોઈ શકે છે. વ્યવહારમાં, જો સંખ્યાઓમાં મહત્તમ 12 નોંધપાત્ર અંકો હોય તો મનસ્વી કદની સમસ્યાઓ સી. કે. કે. દ્વારા ઉકેલી શકાય છે. સી. કે. કે. કોઈપણ સમયે અલ્ગોરિધમ તરીકે પણ ચાલી શકે છેઃ તે પહેલા કે. કે. ઉકેલ શોધે છે, અને પછી સમયની મંજૂરી સાથે ઉત્તરોત્તર વધુ સારા ઉકેલો શોધે છે (સંભવતઃ શ્રેષ્ઠતા સુધી પહોંચવા માટે ઘાતાંકીય સમયની જરૂર પડે છે, સૌથી ખરાબ કિસ્સાઓમાં). તેને જગ્યાની જરૂર છે, પરંતુ સૌથી ખરાબ કિસ્સામાં સમય લાગી શકે છે. સબસેટ રકમ માટે વિકસાવવામાં આવેલા અલ્ગોરિધમ્સમાં નીચેનાનો સમાવેશ થાય છેઃ હોરોવિટ્ઝ અને સાનહી-સમયસર ચાલે છે, પરંતુ જગ્યાની જરૂર પડે છે. શ્રોપ્પેલ અને શમીર-સમયસર દોડે છે અને તેમને ઘણી ઓછી જગ્યાની જરૂર પડે છે. હાઉગ્રેવ-ગ્રેહામ અને જોક્સ-સમયસર ચાલે છે, પરંતુ તે એક રેન્ડમાઇઝ્ડ અલ્ગોરિધમ છે જે ફક્ત નિર્ણયની સમસ્યાનું સમાધાન કરે છે (ઓપ્ટિમાઇઝેશન સમસ્યા નહીં). હાર્ડ ઇન્સ્ટન્સ અને ફેઝ-ટ્રાન્ઝિશન સેટ માત્ર એક અથવા કોઈ પાર્ટીશન સાથે તેમના ઇનપુટ કદની તુલનામાં ઉકેલવા માટે સૌથી મુશ્કેલ (અથવા સૌથી મોંઘા) હોય છે. જ્યારે મૂલ્યો સમૂહના કદની સરખામણીમાં નાના હોય છે, ત્યારે સંપૂર્ણ પાર્ટીશનોની શક્યતા વધુ હોય છે. આ સમસ્યા "તબક્કા સંક્રમણ" માંથી પસાર થવા માટે જાણીતી છે; કેટલાક સમૂહો માટે સંભવિત અને અન્ય માટે અસંભવિત છે. જો m એ સમૂહમાં કોઈપણ સંખ્યાને વ્યક્ત કરવા માટે જરૂરી બિટ્સની સંખ્યા હોય અને n એ સમૂહનું કદ હોય તો તેમાં ઘણા ઉકેલો હોય છે અને તેમાં થોડા અથવા કોઈ ઉકેલો હોતા નથી. જેમ જેમ n અને m મોટા થાય છે, તેમ તેમ સંપૂર્ણ પાર્ટીશનની સંભાવના અનુક્રમે 1 અથવા 0 થાય છે. આ મૂળરૂપે જેન્ટ અને વોલ્શ દ્વારા પ્રયોગમૂલક પુરાવાના આધારે દલીલ કરવામાં આવી હતી, ત્યારબાદ મર્ટન્સ દ્વારા આંકડાકીય ભૌતિકશાસ્ત્રની પદ્ધતિઓનો ઉપયોગ કરીને, અને બાદમાં બોર્ગ્સ, ચેયસ અને પિટેલ દ્વારા સાબિત કરવામાં આવી હતી. સંભવિત સંસ્કરણ એક સંબંધિત સમસ્યા, જે કંઈક અંશે જન્મદિવસના વિરોધાભાસ જેવી જ છે, તે ઇનપુટ સમૂહનું કદ નક્કી કરવાની છે જેથી આપણી પાસે અડધા ભાગની સંભાવના હોય કે ત્યાં એક ઉકેલ છે, એવી ધારણા હેઠળ કે સમૂહમાં દરેક તત્વ અવ્યવસ્થિત રીતે પસંદ કરવામાં આવે છે 1 અને કેટલાક આપેલ મૂલ્ય વચ્ચે સમાન વિતરણ સાથે. જન્મદિવસના વિરોધાભાસની જેમ આ સમસ્યાનો ઉકેલ પ્રતિકૂળ હોઈ શકે છે. વિવિધતાઓ અને સામાન્યીકરણ સમાન-કાર્ડિનાલિટી પાર્ટીશન એ એક પ્રકાર છે જેમાં બંને ભાગોમાં સમાન રકમ હોવા ઉપરાંત સમાન સંખ્યામાં વસ્તુઓ હોવી જોઈએ. આ વેરિઅન્ટ એનપી-હાર્ડ પણ છે. પુરાવો. અમુક n સંખ્યાઓ સાથે પ્રમાણભૂત પાર્ટીશન ઉદાહરણ આપવામાં આવે તો, n શૂન્ય ઉમેરીને સમાન-કાર્ડિનાલિટી-પાર્ટીશન ઉદાહરણ બનાવો. સ્પષ્ટપણે, નવા ઉદાહરણમાં સમાન-કાર્ડિનાલિટી સમાન-રકમ પાર્ટીશન છે જો મૂળ ઉદાહરણમાં સમાન-રકમ પાર્ટીશન હોય. બેલેન્સ્ડ નંબર પાર્ટીશનિંગ પણ જુઓ. વિશિષ્ટ પાર્ટીશન એ એક પ્રકાર છે જેમાં તમામ ઇનપુટ પૂર્ણાંકો અલગ હોય છે. આ વેરિઅન્ટ એનપી-હાર્ડ પણ છે. ઉત્પાદન વિભાજન એ પૂર્ણાંકોના સમૂહને સમાન ઉત્પાદન (સમાન રકમને બદલે) સાથે બે સમૂહમાં વિભાજિત કરવાની સમસ્યા છે. આ સમસ્યા મજબૂત રીતે એન. પી.-હાર્ડ છે. કોવાલ્યોવ અને પેસ પાર્ટીશન-પ્રકારની સમસ્યાઓની એન. પી.-કઠોરતા સાબિત કરવા માટે સામાન્ય અભિગમની ચર્ચા કરે છે. અરજીઓ પાર્ટીશન સમસ્યાનો એક ઉપયોગ ચૂંટણીઓમાં હેરફેર માટે છે. ધારો કે ત્રણ ઉમેદવાર (એ, બી અને સી) છે. એક જ ઉમેદવારને સ્કોરિંગના આધારે મતદાનના નિયમનો ઉપયોગ કરીને ચૂંટવો જોઈએ, દા. ત. વીટો નિયમ (દરેક મતદાર એક જ ઉમેદવારને વીટો કરે છે અને સૌથી ઓછા વીટો ધરાવતા ઉમેદવાર જીતે છે). જો ગઠબંધન એ સુનિશ્ચિત કરવા માંગે છે કે સી ચૂંટાય છે, તો તેઓએ તેમના મતને એ અને બી વચ્ચે વહેંચવા જોઈએ જેથી તેમને દરેકને મળતી વીટોની સૌથી ઓછી સંખ્યાને મહત્તમ કરી શકાય. જો મતોનું ભારણ કરવામાં આવે, તો સમસ્યાને વિભાજનની સમસ્યામાં ઘટાડી શકાય છે, અને આમ તેને સી. કે. કે. નો ઉપયોગ કરીને અસરકારક રીતે ઉકેલી શકાય છે. સ્કોરિંગ પર આધારિત અન્ય કોઈપણ મતદાનના નિયમ માટે પણ આ જ સાચું છે. નોંધો સંદર્ભો સંખ્યા પાર્ટીશનિંગ નબળા એન. પી.-પૂર્ણ સમસ્યાઓ