Mixed Chinese postman problem
મિશ્ર ચાઇનીઝ પોસ્ટમેન પ્રોબ્લેમ (એમ. સી. પી. પી. અથવા એમ. સી. પી.) એ શિરોબિંદુઓ V ના સમૂહ સાથે ગ્રાફના સૌથી ટૂંકા પરિભ્રમણની શોધ છે, હકારાત્મક તર્કસંગત વજન સાથે દિશાહીન ધાર E નો સમૂહ અને હકારાત્મક તર્કસંગત વજન સાથે નિર્દેશિત ચાપ A નો સમૂહ છે જે દરેક ધાર અથવા ચાપને ઓછામાં ઓછા એક વાર ઓછામાં ઓછા ખર્ચે આવરી લે છે. પાપદિમિત્રીઉ દ્વારા આ સમસ્યા એન. પી.-પૂર્ણ હોવાનું સાબિત થયું છે. મિશ્ર ચાઇનીઝ પોસ્ટમેન સમસ્યા ઘણીવાર બરફની ખેડ જેવી ચાપ માર્ગની સમસ્યાઓમાં ઊભી થાય છે, જ્યાં કેટલીક શેરીઓ બંને દિશામાં પસાર થવા માટે ખૂબ જ સાંકડી હોય છે જ્યારે અન્ય શેરીઓ દ્વિદિશ હોય છે અને બંને દિશામાં ખેડ કરી શકાય છે. ગ્રાફ મજબૂત રીતે જોડાયેલ છે કે કેમ તેની ચકાસણી કરીને મિશ્ર ગ્રાફમાં કોઈપણ કદની પોસ્ટમેન ટૂર છે કે કેમ તે તપાસવું સરળ છે. સમસ્યા એ છે કે એન. પી. મુશ્કેલ છે જો આપણે પોસ્ટમેન પ્રવાસને દરેક કમાનને બરાબર એક વાર પાર કરવા માટે પ્રતિબંધિત કરીએ અથવા જો આપણે તેને દરેક ધારને બરાબર એક વાર પાર કરવા માટે પ્રતિબંધિત કરીએ, જેમ કે ઝારાગોઝા માર્ટિનેઝે સાબિત કર્યું છે. ગાણિતિક વ્યાખ્યા ગાણિતિક વ્યાખ્યા છેઃ ઇનપુટઃ દરેક ધારની કિંમત અને મહત્તમ કિંમત સાથે મજબૂત રીતે જોડાયેલ, મિશ્ર આલેખ. પ્રશ્નઃ શું કોઈ (નિર્દેશિત) પ્રવાસ છે જે દરેક ધાર અને દરેક કમાનને ઓછામાં ઓછી એક વારમાં પાર કરે છે અને તેમાં સૌથી વધુ ખર્ચ થાય છે? કોમ્પ્યુટેશનલ જટિલતા મિશ્ર ચાઇનીઝ પોસ્ટમેન સમસ્યાને ઉકેલવામાં મુખ્ય મુશ્કેલી એ છે કે જ્યારે આપણને આપણા પ્રવાસ માટે ચુસ્ત બજેટ આપવામાં આવે છે અને આપણે દરેક ધારને માત્ર એક જ વાર પાર કરી શકીએ છીએ ત્યારે (દિશાહીન) ધાર માટે દિશાઓ પસંદ કરવામાં આવે છે. પછી આપણે દિશા નિર્દેશિત યુલરિયન આલેખ મેળવવા માટે ધારને દિશા આપવી પડશે અને કેટલીક વધુ કમાનો ઉમેરવી પડશે, એટલે કે દરેક શિરોબિંદુને સંતુલિત કરવું પડશે. જો એક શિરોબિંદુ પર બહુવિધ ધાર હોય, તો દરેક ધારની યોગ્ય દિશા નક્કી કરવી સરળ કાર્ય નથી. ગણિતશાસ્ત્રી પાપાડિમિટ્રિયુએ વધુ પ્રતિબંધો સાથે આ સમસ્યાનું વિશ્લેષણ કર્યું; "મિશ્ર ચિની પોસ્ટમેન એન. પી.-પૂર્ણ છે, ભલે ઇનપુટ ગ્રાફ સમતલીય હોય, દરેક શિરોબિંદુ મહત્તમ ત્રણ ડિગ્રી ધરાવે છે, અને દરેક ધાર અને ચાપની કિંમત એક હોય છે". યુલરિયન આલેખ મિશ્ર ચિની પોસ્ટમેન સમસ્યાને ઉકેલવા માટે અલ્ગોરિધમ બનાવવા માટે મિશ્ર આલેખ યુલરિયન છે કે કેમ તે તપાસવાની પ્રક્રિયા મહત્વપૂર્ણ છે. યુલરિયન ચક્ર માટે મિશ્ર આલેખ G ની ડિગ્રી સરખી હોવી જોઈએ, પરંતુ આ પૂરતું નથી. અંદાજ મિશ્ર ચાઇનીઝ પોસ્ટમેન એન. પી.-હાર્ડ છે તે હકીકત બહુપદી સમય અલ્ગોરિધમ્સની શોધ તરફ દોરી ગઈ છે જે વાજબી થ્રેશોલ્ડ સુધી મહત્તમ ઉકેલ સુધી પહોંચે છે. ફ્રેડરિકસને 3/2 ના પરિબળ સાથે એક પદ્ધતિ વિકસાવી જે સમતલીય આલેખ પર લાગુ કરી શકાય, અને રાઘવચારી અને વીરાસામીએ એક એવી પદ્ધતિ શોધી કાઢી જે સમતલીય હોવી જરૂરી નથી. જો કે, બહુપદી સમય ડેડહેડિંગની કિંમત શોધી શકતો નથી, શેરીઓ સુધી પહોંચવા માટે બરફના હળને જેટલો સમય લાગે છે તે હલ કરશે અથવા શેરીઓ સુધી પહોંચવા માટે શેરી સફાઈ કરનાર તે સાફ કરશે. ઔપચારિક વ્યાખ્યા શિરોબિંદુ સમૂહ સાથે મજબૂત રીતે જોડાયેલા મિશ્ર આલેખ અને ધાર સમૂહ, ચાપ સમૂહ અને દરેક માટે બિન-નકારાત્મક ખર્ચને ધ્યાનમાં રાખીને, એમ. સી. પી. પી. માં દરેક કડીમાંથી ઓછામાં ઓછી એક વાર પસાર થતી લઘુતમ-કિંમતની મુલાકાત શોધવાનો સમાવેશ થાય છે. આપેલ,, બરાબર એક અંતિમ બિંદુ સાથે ધારનો સમૂહ સૂચવે છે, અને. શિરોબિંદુને જોતાં, (ઇન્ડીગ્રી) એ દાખલ થતી કમાનોની સંખ્યા સૂચવે છે, (આઉટ ડિગ્રી) એ છોડતી કમાનોની સંખ્યા છે, અને (ડિગ્રી) એ તેની સાથે જોડાયેલી કડીઓની સંખ્યા છે. તેની નોંધ લો. મિશ્ર આલેખ કહેવામાં આવે છે, જો તેના તમામ શિરોબિંદુઓ સમ ડિગ્રી ધરાવતા હોય તો પણ, તેને સમપ્રમાણ કહેવામાં આવે છે જો દરેક શિરોબિંદુ માટે, અને તેને સંતુલિત કહેવામાં આવે છે જો, શિરોબિંદુઓના કોઈપણ સબસેટને જોતાં, ચાપની સંખ્યા વચ્ચેનો તફાવત, અને ચાપની સંખ્યા વચ્ચેનો તફાવત, જોડાતી દિશાહીન ધારની સંખ્યા કરતા વધારે ન હોય અને,. તે એક જાણીતી હકીકત છે કે મિશ્ર આલેખ યુલરિયન છે જો અને માત્ર ત્યારે જ જો તે સમ અને સંતુલિત હોય. નોંધ લો કે જો સમ અને સમપ્રમાણ હોય, તો G પણ સંતુલિત (અને યુલરિયન) છે. વધુમાં, જો સમ હોય, તો બહુપદી સમયમાં બરાબર ઉકેલી શકાય છે. એમ. સી. પી. પી. અલ્ગોરિધમ પણ સમાન અને મજબૂત રીતે જોડાયેલા મિશ્ર આલેખને જોતાં, ચાલો સમાન ખર્ચ સાથે અને તેની અંદરની ધારને અવ્યવસ્થિત રીતે દિશા સોંપીને મેળવેલા ચાપનો સમૂહ બનીએ. નિર્દેશિત આલેખમાં દરેક શિરોબિંદુ i માટે ગણતરી કરો. સાથેનો શિરોબિંદુ પુરવઠાની માંગ સાથે સ્રોત (સિંક) તરીકે ગણવામાં આવશે. નોંધ લો કે સમ આલેખની જેમ, તમામ પુરવઠો અને માંગણીઓ સમ સંખ્યાઓ છે (શૂન્યને સમ સંખ્યા ગણવામાં આવે છે). ચાલો તે અનુરૂપ ધારની કિંમતમાં અને તેની સાથે વિરુદ્ધ દિશામાં કમાનોનો સમૂહ હોઈએ, અને શૂન્ય કિંમતે સમાંતર કમાનોનો સમૂહ હોઈએ. તમામ શિરોબિંદુઓની માંગને સંતોષવા માટે, આલેખમાં લઘુતમ ખર્ચ પ્રવાહની સમસ્યાનું સમાધાન કરો, જેમાં દરેક ચાપમાં અનંત ક્ષમતા હોય છે અને દરેક ચાપમાં ક્ષમતા 2 હોય છે. ચાલો શ્રેષ્ઠ પ્રવાહ બનીએ. દરેક કમાન માટેઃ જો, પછી અનુરૂપ ધારને થી તરફ દિશા આપો (પગલું 1 માં સંકળાયેલ ધારને સોંપેલ દિશા, થી, ખોટી હતી); જો, તો પછી G માં અનુરૂપ ધારને દિશા આપો (આ કિસ્સામાં, પગલું 1 માં દિશા "જમણી" હતી). નોંધ લો કે કેસ અશક્ય છે, કારણ કે ચાપમાંથી પસાર થતા તમામ પ્રવાહ મૂલ્યો સમ સંખ્યાઓ છે. દરેક કમાનની નકલો ઉમેરીને વૃદ્ધિ કરો. પરિણામી આલેખ સમ અને સપ્રમાણ છે. હ્યુરિસ્ટિક અલ્ગોરિધમ્સ જ્યારે મિશ્ર ગ્રાફ સમ ન હોય અને બધા નોડ્સમાં સમ ડિગ્રી ન હોય, ત્યારે ગ્રાફને સમ ગ્રાફમાં રૂપાંતરિત કરી શકાય છે. ચાલો એક મિશ્ર આલેખ બનીએ જે મજબૂત રીતે જોડાયેલ છે. ચાપ દિશાઓને અવગણીને વિચિત્ર ડિગ્રી નોડ્સ શોધો અને ન્યૂનતમ-ખર્ચ મેળ મેળવો. સમ આલેખ પેદા કરવા માટે ન્યૂનતમ કિંમત મેળ ખાતી ધાર સાથે આલેખમાં વધારો કરો. આલેખ સમ છે પરંતુ સપ્રમાણ નથી અને યુલરિયન મિશ્ર આલેખ સમ અને સપ્રમાણ છે. સમપ્રમાણ આલેખ મેળવવા માટે લઘુતમ ખર્ચ પ્રવાહ સમસ્યાનું સમાધાન કરો જે સમ ન પણ હોઈ શકે. અંતિમ તબક્કામાં સપ્રમાણ આલેખને સમાન બનાવવાનો સમાવેશ થાય છે. વિષમ ડિગ્રી નોડ્સને લેબલ કરો. ચાપ સમૂહમાં રેખાઓ અને ધાર સમૂહમાં રેખાઓ વચ્ચે વૈકલ્પિક એવા ચક્ર શોધો જે અંદરના બિંદુઓ પર શરૂ થાય છે અને સમાપ્ત થાય છે. અંદરની કમાનોને દિશાહીન ધાર તરીકે ગણવી જોઈએ, નિર્દેશિત કમાન તરીકે નહીં. આનુવંશિક અલ્ગોરિધમ હુઆ જિઆંગ એટ દ્વારા પ્રકાશિત એક પેપર. એ. એલ. એ વસ્તી પર કામ કરીને મિશ્ર ચાઇનીઝ પોસ્ટમેન સમસ્યાને ઉકેલવા માટે આનુવંશિક અલ્ગોરિધમ બહાર પાડ્યું. એમ. સી. પી. પી. માટે અન્ય અંદાજિત અલ્ગોરિધમ્સની સરખામણીમાં અલ્ગોરિધમે સારું પ્રદર્શન કર્યું. આ પણ જુઓ કેપેસિટેડ આર્ક રાઉટીંગ સમસ્યા સંદર્ભો આલેખ સિદ્ધાંતમાં કોમ્પ્યુટેશનલ સમસ્યાઓ