પેરામીટરાઇઝ્ડ અલ્ગોરિધમ્સ સાથે NP-હાર્ડ સમસ્યાઓ કેવી રીતે ઉકેલવી

સંશોધન કાર્ય કદાચ અમારી તાલીમનો સૌથી રસપ્રદ ભાગ છે. યુનિવર્સિટીમાં હોવા છતાં તમારી પસંદ કરેલી દિશામાં તમારી જાતને અજમાવવાનો વિચાર છે. ઉદાહરણ તરીકે, સૉફ્ટવેર એન્જિનિયરિંગ અને મશીન લર્નિંગના ક્ષેત્રોના વિદ્યાર્થીઓ ઘણીવાર કંપનીઓમાં સંશોધન કરવા જાય છે (મુખ્યત્વે જેટબ્રેન્સ અથવા યાન્ડેક્સ, પરંતુ માત્ર નહીં).

આ પોસ્ટમાં હું કમ્પ્યુટર સાયન્સમાં મારા પ્રોજેક્ટ વિશે વાત કરીશ. મારા કાર્યના ભાગ રૂપે, મેં સૌથી પ્રખ્યાત NP-હાર્ડ સમસ્યાઓમાંથી એકને ઉકેલવા માટેના અભિગમોનો અભ્યાસ કર્યો અને વ્યવહારમાં મૂક્યો: શિરોબિંદુ આવરી સમસ્યા.

આજકાલ, એનપી-હાર્ડ સમસ્યાઓ માટે એક રસપ્રદ અભિગમ ખૂબ જ ઝડપથી વિકસિત થઈ રહ્યો છે - પેરામીટરાઇઝ્ડ અલ્ગોરિધમ્સ. હું તમને ઝડપી બનાવવાનો પ્રયત્ન કરીશ, તમને કેટલાક સરળ પેરામીટરાઇઝ્ડ અલ્ગોરિધમ્સ કહીશ અને એક શક્તિશાળી પદ્ધતિનું વર્ણન કરીશ જેણે મને ઘણી મદદ કરી. મેં PACE ચેલેન્જ સ્પર્ધામાં મારા પરિણામો રજૂ કર્યા: ઓપન ટેસ્ટના પરિણામો અનુસાર, મારું સોલ્યુશન ત્રીજું સ્થાન લે છે, અને અંતિમ પરિણામો 1 જુલાઈના રોજ જાણવામાં આવશે.

મારા વિશે

મારું નામ વેસિલી અલ્ફેરોવ છે, હું હવે નેશનલ રિસર્ચ યુનિવર્સિટી હાયર સ્કૂલ ઑફ ઇકોનોમિક્સ - સેન્ટ પીટર્સબર્ગમાં મારું ત્રીજું વર્ષ પૂરું કરી રહ્યો છું. મને મારા શાળાના દિવસોથી એલ્ગોરિધમ્સમાં રસ છે, જ્યારે મેં મોસ્કો શાળા નંબર 179 માં અભ્યાસ કર્યો અને કમ્પ્યુટર સાયન્સ ઓલિમ્પિયાડ્સમાં સફળતાપૂર્વક ભાગ લીધો.

પરિમાણિત અલ્ગોરિધમ્સમાં નિષ્ણાતોની મર્યાદિત સંખ્યામાં બારમાં પ્રવેશ કરે છે...

પુસ્તકમાંથી લીધેલું ઉદાહરણ "પેરામીટરાઇઝ્ડ અલ્ગોરિધમ્સ"

કલ્પના કરો કે તમે નાના શહેરમાં બાર સિક્યુરિટી ગાર્ડ છો. દર શુક્રવારે, અડધું શહેર તમારા બાર પર આરામ કરવા માટે આવે છે, જે તમને ઘણી મુશ્કેલી આપે છે: ઝઘડાને રોકવા માટે તમારે તોફાની ગ્રાહકોને બારની બહાર ફેંકી દેવાની જરૂર છે. આખરે, તમે કંટાળી જાઓ છો અને નિવારક પગલાં લેવાનું નક્કી કરો છો.

તમારું શહેર નાનું હોવાથી, તમે બરાબર જાણો છો કે આશ્રયદાતાઓની કઈ જોડી જો તેઓ એક સાથે બારમાં સમાપ્ત થાય તો તેઓ લડશે. શું તમારી પાસે યાદી છે n જે લોકો આજે રાત્રે બારમાં આવશે. તમે કોઈને પણ લડાઈમાં પડ્યા વિના કેટલાક નગરજનોને બારમાંથી બહાર રાખવાનું નક્કી કરો છો. તે જ સમયે, તમારા બોસ નફો ગુમાવવા માંગતા નથી અને જો તમે તેનાથી વધુ ન થવા દો તો નાખુશ થશે k માનવ.

કમનસીબે, તમારી સામેની સમસ્યા ક્લાસિક NP-હાર્ડ સમસ્યા છે. તમે તેણીને આ રીતે જાણો છો શિરોબિંદુ કવર, અથવા શિરોબિંદુ આવરી સમસ્યા તરીકે. આવી સમસ્યાઓ માટે, સામાન્ય કિસ્સામાં, ત્યાં કોઈ અલ્ગોરિધમ્સ નથી જે સ્વીકાર્ય સમયે કાર્ય કરે છે. ચોક્કસ કહીએ તો, અપ્રમાણિત અને તદ્દન મજબૂત પૂર્વધારણા ETH (ઘાતાંકીય સમયની પૂર્વધારણા) કહે છે કે આ સમસ્યા સમયસર ઉકેલી શકાતી નથી. , એટલે કે, તમે સંપૂર્ણ શોધ કરતાં વધુ સારી રીતે કંઈપણ વિચારી શકતા નથી. ઉદાહરણ તરીકે, ચાલો કહીએ કે કોઈ તમારા બારમાં આવવાનું છે એન = 1000 માનવ. પછી સંપૂર્ણ શોધ થશે વિકલ્પો કે જે લગભગ છે - ઉન્મત્ત રકમ. સદનસીબે, તમારા મેનેજમેન્ટે તમને એક મર્યાદા આપી છે કે = 10, તેથી તમારે પુનરાવર્તિત કરવાની જરૂર છે તે સંયોજનોની સંખ્યા ઘણી ઓછી છે: દસ ઘટકોના ઉપગણોની સંખ્યા છે . આ વધુ સારું છે, પરંતુ તે હજુ પણ શક્તિશાળી ક્લસ્ટર પર પણ એક દિવસમાં ગણવામાં આવશે નહીં.

બારના મુલાકાતીઓ વચ્ચેના તણાવપૂર્ણ સંબંધોની આ ગોઠવણીમાં લડાઈની શક્યતાને દૂર કરવા માટે, તમારે બોબ, ડેનિયલ અને ફેડરને બહાર રાખવાની જરૂર છે. એવો કોઈ ઉકેલ નથી કે જેમાં માત્ર બે જ રહી જાય.

શું આનો અર્થ એ છે કે દરેકને અંદર આવવા દેવાનો સમય આવી ગયો છે? ચાલો અન્ય વિકલ્પો ધ્યાનમાં લઈએ. સારું, ઉદાહરણ તરીકે, તમે ફક્ત તે જ લોકોને પ્રવેશ આપી શકતા નથી કે જેઓ ખૂબ મોટી સંખ્યામાં લોકો સાથે લડવાની સંભાવના ધરાવે છે. જો કોઈ વ્યક્તિ સાથે ઓછામાં ઓછું લડી શકે k+1 અન્ય વ્યક્તિ, તો પછી તમે ચોક્કસપણે તેને અંદર ન દો - અન્યથા તમારે દરેકને બહાર રાખવું પડશે k+1 નગરજનો, જેની સાથે તે લડી શકે છે, જે ચોક્કસપણે નેતૃત્વને અસ્વસ્થ કરશે.

તમે આ સિદ્ધાંત મુજબ તમે કરી શકો તે દરેકને ફેંકી દો. પછી દરેક જણ તેનાથી વધુ સાથે લડી શકશે નહીં k લોકો તેમને બહાર ફેંકી દે છે k માણસ, તમે તેનાથી વધુ કંઇ રોકી શકતા નથી તકરાર આનો અર્થ એ છે કે જો ત્યાં કરતાં વધુ છે જો કોઈ વ્યક્તિ ઓછામાં ઓછા એક સંઘર્ષમાં સામેલ હોય, તો તમે ચોક્કસપણે તે બધાને રોકી શકતા નથી. કારણ કે, અલબત્ત, તમે ચોક્કસપણે સંપૂર્ણપણે બિન-વિરોધાભાસી લોકોને આવવા દો છો, તમારે બેસો લોકોમાંથી દસના કદના તમામ સબસેટમાંથી પસાર થવાની જરૂર છે. ત્યાં લગભગ છે , અને ઑપરેશનની આ સંખ્યા ક્લસ્ટર પર પહેલેથી જ ગોઠવી શકાય છે.

જો તમે એવી વ્યક્તિઓને સુરક્ષિત રીતે લઈ શકો કે જેમની પાસે બિલકુલ સંઘર્ષ નથી, તો પછી ફક્ત એક જ સંઘર્ષમાં ભાગ લેનારાઓ વિશે શું? વાસ્તવમાં, તેઓને તેમના પ્રતિસ્પર્ધી પર દરવાજો બંધ કરીને પણ પ્રવેશ આપી શકાય છે. ખરેખર, જો એલિસ ફક્ત બોબ સાથે સંઘર્ષમાં હોય, તો જો આપણે એલિસને તેમાંથી બેમાંથી બહાર જવા દઈએ, તો આપણે ગુમાવીશું નહીં: બોબને અન્ય તકરાર હોઈ શકે છે, પરંતુ એલિસ પાસે ચોક્કસપણે તે નથી. તદુપરાંત, અમને બંનેને અંદર ન આવવા દેવાનો કોઈ અર્થ નથી. આવા ઓપરેશન્સ પછી ત્યાં કોઈ વધુ રહેતું નથી વણઉકેલ્યા ભાવિ સાથે મહેમાનો: અમારી પાસે ફક્ત છે તકરાર, દરેક બે સહભાગીઓ સાથે અને દરેક ઓછામાં ઓછા બેમાં સામેલ છે. તેથી જે બાકી રહે છે તે સૉર્ટ કરવાનું છે વિકલ્પો, જેને લેપટોપ પર અડધો દિવસ સરળતાથી ગણી શકાય.

હકીકતમાં, સરળ તર્ક સાથે તમે વધુ આકર્ષક પરિસ્થિતિઓ પ્રાપ્ત કરી શકો છો. નોંધ કરો કે અમારે ચોક્કસપણે તમામ વિવાદોને ઉકેલવાની જરૂર છે, એટલે કે, દરેક વિરોધાભાસી જોડીમાંથી, ઓછામાં ઓછી એક વ્યક્તિ પસંદ કરો જેને અમે અંદર આવવા દઈશું નહીં. ચાલો નીચેના અલ્ગોરિધમનો વિચાર કરીએ: કોઈપણ સંઘર્ષ લો, જેમાંથી આપણે એક સહભાગીને દૂર કરીએ છીએ અને બાકીના ભાગમાંથી પુનરાવર્તિત રીતે શરૂ કરીએ છીએ, પછી બીજાને દૂર કરીએ છીએ અને પુનરાવર્તિત રીતે શરૂ કરીએ છીએ. આપણે દરેક પગલે કોઈને બહાર ફેંકીએ છીએ, તેથી આવા અલ્ગોરિધમનું રિકર્ઝન ટ્રી એ ઊંડાણનું દ્વિસંગી વૃક્ષ છે. k, તેથી કુલમાં અલ્ગોરિધમ કામ કરે છે જ્યાં n શિરોબિંદુઓની સંખ્યા છે, અને m - પાંસળીની સંખ્યા. અમારા ઉદાહરણમાં, આ લગભગ દસ મિલિયન છે, જે ફક્ત લેપટોપ પર જ નહીં, પણ મોબાઇલ ફોન પર પણ વિભાજિત સેકન્ડમાં ગણી શકાય છે.

ઉપરોક્ત ઉદાહરણ એક ઉદાહરણ છે પેરામીટરાઇઝ્ડ અલ્ગોરિધમ. પેરામીટરાઇઝ્ડ એલ્ગોરિધમ એ એલ્ગોરિધમ છે જે સમયસર ચાલે છે f(k) પોલી(n)જ્યાં p - બહુપદી, f એક મનસ્વી ગણિત કાર્ય છે, અને k - કેટલાક પરિમાણ, જે, સંભવતઃ, સમસ્યાના કદ કરતાં ઘણું નાનું હશે.

આ અલ્ગોરિધમ પહેલાંના તમામ તર્ક એક ઉદાહરણ આપે છે કર્નલાઇઝેશન પેરામીટરાઇઝ્ડ અલ્ગોરિધમ્સ બનાવવા માટેની સામાન્ય તકનીકોમાંની એક છે. કર્નલાઇઝેશન એ પેરામીટરના ફંક્શન દ્વારા મર્યાદિત મૂલ્યમાં સમસ્યાના કદમાં ઘટાડો છે. પરિણામી સમસ્યાને ઘણીવાર કર્નલ કહેવામાં આવે છે. આમ, શિરોબિંદુઓની ડિગ્રી વિશે સરળ તર્ક દ્વારા, અમે શિરોબિંદુ કવર સમસ્યા માટે એક ચતુર્ભુજ કર્નલ મેળવી, જવાબના કદ દ્વારા પરિમાણિત. આ કાર્ય માટે તમે અન્ય સેટિંગ્સ પસંદ કરી શકો છો (જેમ કે વર્ટેક્સ કવર એબોવ એલપી), પરંતુ આ તે સેટિંગ છે જેની અમે ચર્ચા કરીશું.

પેસ ચેલેન્જ

સ્પર્ધા PACE ચેલેન્જ (The Parameterized Algorithms and Computational Experiments Challenge) નો જન્મ 2015 માં પરિમાણિત અલ્ગોરિધમ્સ અને કોમ્પ્યુટેશનલ સમસ્યાઓ ઉકેલવા માટે વ્યવહારમાં ઉપયોગમાં લેવાતા અભિગમો વચ્ચે જોડાણ સ્થાપિત કરવા માટે થયો હતો. પ્રથમ ત્રણ સ્પર્ધાઓ ગ્રાફની ઝાડની પહોળાઈ શોધવા માટે સમર્પિત હતી (ઝાડની પહોળાઈ, સ્ટીનર વૃક્ષ (સ્ટીનર વૃક્ષ(પ્રતિસાદ શિરોબિંદુ સેટ). આ વર્ષે, એક સમસ્યા કે જેમાં તમે તમારો હાથ અજમાવી શકો તે ઉપર વર્ણવેલ શિરોબિંદુ આવરી સમસ્યા હતી.

આ સ્પર્ધા દર વર્ષે લોકપ્રિયતા મેળવી રહી છે. જો તમે પ્રારંભિક ડેટા પર વિશ્વાસ કરો છો, તો આ વર્ષે 24 ટીમોએ એકલા શિરોબિંદુ આવરી સમસ્યાને ઉકેલવા માટે સ્પર્ધામાં ભાગ લીધો હતો. તે નોંધવું યોગ્ય છે કે સ્પર્ધા કેટલાક કલાકો અથવા એક અઠવાડિયા સુધી નહીં, પરંતુ કેટલાક મહિનાઓ સુધી ચાલે છે. ટીમોને સાહિત્યનો અભ્યાસ કરવાની તક મળે છે, પોતાના મૂળ વિચાર સાથે આવે છે અને તેને અમલમાં મૂકવાનો પ્રયાસ કરે છે. સારમાં, આ સ્પર્ધા એક સંશોધન પ્રોજેક્ટ છે. કોન્ફરન્સ સાથે જોડાણમાં સૌથી વધુ અસરકારક ઉકેલો અને વિજેતાઓને પુરસ્કાર આપવા માટેના વિચારો રાખવામાં આવશે આઈ.પી.ઈ.સી. યુરોપમાં સૌથી મોટી વાર્ષિક અલ્ગોરિધમિક મીટિંગના ભાગરૂપે (પેરામીટરાઇઝ્ડ એન્ડ એક્ઝેક્ટ કોમ્પ્યુટેશન પર ઇન્ટરનેશનલ સિમ્પોસિયમ) ALGO. સ્પર્ધા વિશે વધુ વિગતવાર માહિતી અહીં મળી શકે છે સાઇટ, અને પાછલા વર્ષોના પરિણામો આવેલા છે અહીં.

સોલ્યુશન ડાયાગ્રામ

શિરોબિંદુ આવરી સમસ્યાને ઉકેલવા માટે, મેં પેરામીટરાઇઝ્ડ અલ્ગોરિધમ્સનો ઉપયોગ કરવાનો પ્રયાસ કર્યો. તેઓ સામાન્ય રીતે બે ભાગો ધરાવે છે: સરળીકરણ નિયમો (જે આદર્શ રીતે કર્નલાઇઝેશન તરફ દોરી જાય છે) અને વિભાજન નિયમો. સરળીકરણ નિયમો બહુપદી સમયમાં ઇનપુટની પ્રીપ્રોસેસિંગ છે. આવા નિયમો લાગુ કરવાનો ઉદ્દેશ્ય સમસ્યાને સમકક્ષ નાની સમસ્યામાં ઘટાડવાનો છે. સરળીકરણ નિયમો એ અલ્ગોરિધમનો સૌથી ખર્ચાળ ભાગ છે, અને આ ભાગને લાગુ કરવાથી કુલ ચાલવાનો સમય મળે છે. સરળ બહુપદી સમયને બદલે. અમારા કિસ્સામાં, વિભાજન નિયમો એ હકીકત પર આધારિત છે કે દરેક શિરોબિંદુ માટે તમારે તેને અથવા તેના પાડોશીને જવાબ તરીકે લેવાની જરૂર છે.

સામાન્ય યોજના આ છે: અમે સરળીકરણ નિયમો લાગુ કરીએ છીએ, પછી અમે કેટલાક શિરોબિંદુ પસંદ કરીએ છીએ, અને બે પુનરાવર્તિત કૉલ્સ કરીએ છીએ: પ્રથમ અમે તેને પ્રતિસાદમાં લઈએ છીએ, અને બીજામાં આપણે તેના બધા પડોશીઓ લઈએ છીએ. જેને આપણે આ શિરોબિંદુ સાથે વિભાજન (બ્રાન્ચિંગ) કહીએ છીએ.

આગામી ફકરામાં આ યોજનામાં બરાબર એક ઉમેરો કરવામાં આવશે.

વિભાજન (બ્રંચિંગ) નિયમો માટેના વિચારો

ચાલો ચર્ચા કરીએ કે શિરોબિંદુ કેવી રીતે પસંદ કરવું જેની સાથે વિભાજન થશે.
મુખ્ય વિચાર એલ્ગોરિધમિક અર્થમાં ખૂબ જ લોભી છે: ચાલો મહત્તમ ડિગ્રીનો શિરોબિંદુ લઈએ અને તેની સાથે વિભાજીત કરીએ. શા માટે તે વધુ સારું લાગે છે? કારણ કે પુનરાવર્તિત કૉલની બીજી શાખામાં આપણે આ રીતે ઘણા બધા શિરોબિંદુઓ દૂર કરીશું. તમે બાકી રહેલા નાના ગ્રાફ પર ગણતરી કરી શકો છો અને અમે તેના પર ઝડપથી કામ કરી શકીએ છીએ.

આ અભિગમ, પહેલેથી જ ચર્ચા કરેલ સરળ કર્નલાઇઝેશન તકનીકો સાથે, પોતાને સારી રીતે બતાવે છે અને કદમાં કેટલાંક હજાર શિરોબિંદુઓના કેટલાક પરીક્ષણોને હલ કરે છે. પરંતુ, ઉદાહરણ તરીકે, તે ક્યુબિક આલેખ માટે સારી રીતે કામ કરતું નથી (એટલે ​​​​કે, આલેખ જેની દરેક શિરોબિંદુની ડિગ્રી ત્રણ છે).
એકદમ સરળ વિચાર પર આધારિત બીજો વિચાર છે: જો ગ્રાફ ડિસ્કનેક્ટ થઈ ગયો હોય, તો તેના કનેક્ટેડ ઘટકો પરની સમસ્યાને અંતે જવાબોને જોડીને સ્વતંત્ર રીતે ઉકેલી શકાય છે. આ, માર્ગ દ્વારા, યોજનામાં એક નાનો વચનબદ્ધ ફેરફાર છે, જે નોંધપાત્ર રીતે ઉકેલને ઝડપી બનાવશે: અગાઉ, આ કિસ્સામાં, અમે ઘટકોના પ્રતિસાદોની ગણતરી માટે સમયના ઉત્પાદન માટે કામ કર્યું હતું, પરંતુ હવે અમે તેના માટે કામ કરીએ છીએ. રકમ. અને બ્રાન્ચિંગને ઝડપી બનાવવા માટે, તમારે કનેક્ટેડ ગ્રાફને ડિસ્કનેક્ટ કરેલામાં ફેરવવાની જરૂર છે.

તે કેવી રીતે કરવું? જો ગ્રાફમાં કોઈ ઉચ્ચારણ બિંદુ છે, તો તમારે તેના પર લડવાની જરૂર છે. એક ઉચ્ચારણ બિંદુ એ શિરોબિંદુ છે જેમ કે જ્યારે દૂર કરવામાં આવે છે, ત્યારે ગ્રાફ તેની કનેક્ટિવિટી ગુમાવે છે. રેખીય સમયમાં ક્લાસિકલ અલ્ગોરિધમનો ઉપયોગ કરીને ગ્રાફમાંના તમામ જંકશન પોઈન્ટ શોધી શકાય છે. આ અભિગમ નોંધપાત્ર રીતે બ્રાન્ચિંગને વેગ આપે છે.

જ્યારે પસંદ કરેલ કોઈપણ શિરોબિંદુઓ દૂર કરવામાં આવે છે, ત્યારે ગ્રાફ કનેક્ટેડ ઘટકોમાં વિભાજિત થશે.

અમે આ કરીશું, પરંતુ અમને વધુ જોઈએ છે. ઉદાહરણ તરીકે, ગ્રાફમાં નાના શિરોબિંદુ કાપો જુઓ અને તેમાંથી શિરોબિંદુઓ સાથે વિભાજિત કરો. ન્યૂનતમ વૈશ્વિક શિરોબિંદુ કટ શોધવા માટે હું જાણું છું તે સૌથી કાર્યક્ષમ રીત એ છે કે ગોમોરી-હુ વૃક્ષનો ઉપયોગ કરવો, જે ઘન સમયમાં બાંધવામાં આવે છે. PACE ચેલેન્જમાં, લાક્ષણિક ગ્રાફનું કદ હજારો શિરોબિંદુઓનું છે. આ સ્થિતિમાં, રિકર્ઝન ટ્રીના દરેક શિરોબિંદુ પર અબજો ઓપરેશન કરવાની જરૂર છે. તે તારણ આપે છે કે ફાળવેલ સમયમાં સમસ્યા હલ કરવી ફક્ત અશક્ય છે.

ચાલો ઉકેલને ઑપ્ટિમાઇઝ કરવાનો પ્રયાસ કરીએ. શિરોબિંદુઓની જોડી વચ્ચે લઘુત્તમ શિરોબિંદુ કાપવામાં આવેલ કોઈપણ અલ્ગોરિધમ દ્વારા શોધી શકાય છે જે મહત્તમ પ્રવાહનું નિર્માણ કરે છે. તમે તેને આવા નેટવર્ક પર મૂકી શકો છો ડિનિટ્ઝ એલ્ગોરિધમ, વ્યવહારમાં તે ખૂબ જ ઝડપથી કામ કરે છે. મને શંકા છે કે ઓપરેટિંગ સમય માટે અંદાજ સાબિત કરવાનું સૈદ્ધાંતિક રીતે શક્ય છે , જે પહેલેથી જ તદ્દન સ્વીકાર્ય છે.

મેં રેન્ડમ શિરોબિંદુઓની જોડી વચ્ચેના કાપને જોવા અને સૌથી સંતુલિત એક લેવા માટે ઘણી વખત પ્રયાસ કર્યો. કમનસીબે, આનાથી ઓપન PACE ચેલેન્જ પરીક્ષણમાં નબળા પરિણામો આવ્યા. મેં તેની તુલના અલ્ગોરિધમ સાથે કરી છે જે મહત્તમ ડિગ્રીના શિરોબિંદુઓને વિભાજિત કરે છે, તેમને વંશની ઊંડાઈ પર મર્યાદા સાથે ચલાવે છે. આ રીતે કટ શોધવાનો પ્રયાસ કરતા અલ્ગોરિધમ મોટા ગ્રાફ પાછળ છોડી જાય છે. આ તે હકીકતને કારણે છે કે કટ ખૂબ જ અસંતુલિત હોવાનું બહાર આવ્યું છે: 5-10 શિરોબિંદુઓ દૂર કર્યા પછી, ફક્ત 15-20 જ વિભાજિત કરવાનું શક્ય હતું.

તે નોંધવું યોગ્ય છે કે સૈદ્ધાંતિક રીતે સૌથી ઝડપી અલ્ગોરિધમ્સ વિશેના લેખો વિભાજન માટે શિરોબિંદુઓ પસંદ કરવા માટે વધુ અદ્યતન તકનીકોનો ઉપયોગ કરે છે. આવી તકનીકોમાં ખૂબ જ જટિલ અમલીકરણ હોય છે અને સમય અને મેમરીની દ્રષ્ટિએ ઘણી વખત નબળી કામગીરી હોય છે. હું પ્રેક્ટિસ માટે તદ્દન સ્વીકાર્ય છે તે ઓળખવામાં અસમર્થ હતો.

સરળીકરણ નિયમો કેવી રીતે લાગુ કરવા

અમારી પાસે કર્નલાઇઝેશન માટે પહેલાથી જ વિચારો છે. ચાલો હું તમને યાદ કરાવું:

1. જો ત્યાં એક અલગ શિરોબિંદુ હોય, તો તેને કાઢી નાખો.
2. જો ડિગ્રી 1 નો શિરોબિંદુ હોય, તો તેને દૂર કરો અને તેના પડોશીને જવાબમાં લો.
3. જો ત્યાં ઓછામાં ઓછું ડિગ્રીનું શિરોબિંદુ હોય k+1, પાછું લો.

પ્રથમ બે સાથે બધું સ્પષ્ટ છે, ત્રીજા સાથે એક યુક્તિ છે. જો બાર વિશેની હાસ્યની સમસ્યામાં અમને ની ઉપરની મર્યાદા આપવામાં આવી હતી k, તો પછી PACE ચેલેન્જમાં તમારે ન્યૂનતમ કદનું શિરોબિંદુ કવર શોધવાની જરૂર છે. આ શોધ સમસ્યાઓનું નિર્ણય સમસ્યાઓમાં એક લાક્ષણિક રૂપાંતર છે; ઘણીવાર બે પ્રકારની સમસ્યાઓ વચ્ચે કોઈ તફાવત નથી. વ્યવહારમાં, જો આપણે શિરોબિંદુને આવરી લેતી સમસ્યા માટે સોલ્વર લખી રહ્યા છીએ, તો તેમાં તફાવત હોઈ શકે છે. ઉદાહરણ તરીકે, ત્રીજા મુદ્દાની જેમ.

અમલીકરણના દૃષ્ટિકોણથી, આગળ વધવાની બે રીત છે. પ્રથમ અભિગમને પુનરાવર્તિત ઊંડાણ કહેવામાં આવે છે. તે નીચે મુજબ છે: અમે નીચેની કેટલીક વાજબી મર્યાદાઓ સાથે જવાબની શરૂઆત કરી શકીએ છીએ, અને પછી આ અવરોધ કરતાં પુનરાવર્તિતતામાં નીચે ગયા વિના, ઉપરથી જવાબ પર અવરોધ તરીકે આ અવરોધનો ઉપયોગ કરીને અમારું અલ્ગોરિધમ ચલાવી શકીએ છીએ. જો અમને કોઈ જવાબ મળ્યો હોય, તો તે શ્રેષ્ઠ હોવાની ખાતરી આપવામાં આવે છે, અન્યથા અમે આ મર્યાદાને એકથી વધારીને ફરી શરૂ કરી શકીએ છીએ.

બીજો અભિગમ એ છે કે કેટલાક વર્તમાન શ્રેષ્ઠ જવાબો સંગ્રહિત કરવા અને નાના જવાબની શોધ કરવી, જ્યારે મળે ત્યારે આ પરિમાણ બદલવું k શોધમાં બિનજરૂરી શાખાઓને વધુ કાપવા માટે.

રાત્રિના ઘણા પ્રયોગો કર્યા પછી, મેં આ બે પદ્ધતિઓના સંયોજન પર સમાધાન કર્યું: પ્રથમ, હું શોધ ઊંડાઈ પર અમુક પ્રકારની મર્યાદા સાથે મારું અલ્ગોરિધમ ચલાવું છું (તેને પસંદ કરવું જેથી તે મુખ્ય ઉકેલની તુલનામાં નજીવો સમય લે) અને શ્રેષ્ઠ ઉપયોગ કરે છે. જવાબની ઉપલી મર્યાદા તરીકે સોલ્યુશન મળ્યું - એટલે કે, સમાન વસ્તુ માટે k.

ડિગ્રી 2 ના શિરોબિંદુઓ

અમે ડિગ્રી 0 અને 1 ના શિરોબિંદુઓ સાથે વ્યવહાર કર્યો છે. તે તારણ આપે છે કે આ ડિગ્રી 2 ના શિરોબિંદુઓ સાથે કરી શકાય છે, પરંતુ આને ગ્રાફમાંથી વધુ જટિલ કામગીરીની જરૂર પડશે.

આને સમજાવવા માટે, આપણે કોઈક રીતે શિરોબિંદુઓને નિયુક્ત કરવાની જરૂર છે. ચાલો ડિગ્રી 2 ના શિરોબિંદુને શિરોબિંદુ કહીએ v, અને તેના પડોશીઓ - શિરોબિંદુઓ x и y. આગળ આપણી પાસે બે કેસ હશે.

1. જ્યારે x и y - પડોશીઓ. પછી તમે જવાબ આપી શકો છો x и yઅને v કાઢી નાખો. ખરેખર, આ ત્રિકોણમાંથી ઓછામાં ઓછા બે શિરોબિંદુઓ બદલામાં લેવાની જરૂર છે, અને જો આપણે લઈશું તો આપણે ચોક્કસપણે ગુમાવીશું નહીં x и y: તેઓ કદાચ અન્ય પડોશીઓ છે, અને v તેઓ અહીં નથી.
2. જ્યારે x и y - પડોશીઓ નહીં. પછી એવું કહેવામાં આવે છે કે ત્રણેય શિરોબિંદુઓ એકમાં ગુંદર કરી શકાય છે. વિચાર એ છે કે આ કિસ્સામાં એક શ્રેષ્ઠ જવાબ છે, જેમાં આપણે ક્યાં તો લઈએ છીએ v, અથવા બંને શિરોબિંદુઓ x и y. તદુપરાંત, પ્રથમ કિસ્સામાં આપણે બધા પડોશીઓને જવાબમાં લેવા પડશે x и y, પરંતુ બીજામાં તે જરૂરી નથી. આ તે કિસ્સાઓને બરાબર અનુરૂપ છે જ્યારે આપણે પ્રતિભાવમાં ગુંદર ધરાવતા શિરોબિંદુને લેતા નથી અને જ્યારે આપણે કરીએ છીએ. તે માત્ર એ નોંધવા માટે રહે છે કે બંને કિસ્સાઓમાં આવા ઓપરેશનનો પ્રતિસાદ એકથી ઓછો થાય છે.

તે નોંધવું યોગ્ય છે કે આ અભિગમ વાજબી રેખીય સમયમાં ચોક્કસ રીતે અમલમાં મૂકવો ખૂબ મુશ્કેલ છે. ગ્લુઇંગ શિરોબિંદુઓ એક જટિલ કામગીરી છે; તમારે પડોશીઓની સૂચિની નકલ કરવાની જરૂર છે. જો આ બેદરકારીપૂર્વક કરવામાં આવે છે, તો તમે અસમપ્રમાણ રીતે સબઓપ્ટીમલ રનિંગ ટાઇમ સાથે સમાપ્ત થઈ શકો છો (ઉદાહરણ તરીકે, જો તમે દરેક ગ્લુઇંગ પછી ઘણી ધારની નકલ કરો છો). હું ડિગ્રી 2 ના શિરોબિંદુઓમાંથી સમગ્ર માર્ગો શોધવા અને વિશિષ્ટ કેસોના સમૂહનું વિશ્લેષણ કરવા પર સ્થાયી થયો, જેમ કે આવા શિરોબિંદુઓમાંથી ચક્ર અથવા એક સિવાયના તમામ શિરોબિંદુઓમાંથી.

વધુમાં, તે જરૂરી છે કે આ ઑપરેશન ઉલટાવી શકાય તેવું હોવું જોઈએ, જેથી રિકર્ઝનમાંથી પાછા ફરીએ ત્યારે અમે ગ્રાફને તેના મૂળ સ્વરૂપમાં પુનઃસ્થાપિત કરીએ. આ સુનિશ્ચિત કરવા માટે, મેં મર્જ કરેલા શિરોબિંદુઓની ધારની સૂચિને સાફ કરી ન હતી, અને પછી મને ખબર હતી કે કઈ કિનારીઓ ક્યાં જવાની જરૂર છે. ગ્રાફના આ અમલીકરણ માટે પણ ચોકસાઈની જરૂર છે, પરંતુ તે વાજબી રેખીય સમય પૂરો પાડે છે. અને હજારો કિનારીઓના આલેખ માટે, તે પ્રોસેસર કેશમાં બંધબેસે છે, જે ઝડપમાં મહાન ફાયદા આપે છે.

લીનિયર કર્નલ

છેલ્લે, કર્નલનો સૌથી રસપ્રદ ભાગ.

શરૂ કરવા માટે, યાદ કરો કે દ્વિપક્ષીય ગ્રાફમાં લઘુત્તમ શિરોબિંદુ આવરણનો ઉપયોગ કરીને શોધી શકાય છે . આ કરવા માટે તમારે અલ્ગોરિધમનો ઉપયોગ કરવાની જરૂર છે હોપક્રોફ્ટ-કાર્પ ત્યાં મહત્તમ મેળ શોધવા માટે, અને પછી પ્રમેયનો ઉપયોગ કરો કોનિગ-એગરવારી.

રેખીય કર્નલનો વિચાર આ છે: પ્રથમ આપણે ગ્રાફને વિભાજિત કરીએ છીએ, એટલે કે, દરેક શિરોબિંદુને બદલે v ચાલો બે શિખરો ઉમેરીએ и , અને દરેક ધારને બદલે u - વી ચાલો બે પાંસળી ઉમેરીએ и . પરિણામી ગ્રાફ દ્વિપક્ષીય હશે. ચાલો તેમાં લઘુત્તમ શિરોબિંદુ કવર શોધીએ. મૂળ ગ્રાફના કેટલાક શિરોબિંદુઓ ત્યાં બે વાર મળશે, કેટલાક માત્ર એક જ વાર અને કેટલાક ક્યારેય નહીં. નેમહાઉઝર-ટ્રોટર પ્રમેય જણાવે છે કે આ કિસ્સામાં તમે શિરોબિંદુઓને દૂર કરી શકો છો જે એકવાર પણ અથડાયા નથી અને બે વાર અથડાયા હોય તેને પાછા લઈ શકે છે. તદુપરાંત, તેણી કહે છે કે બાકીના શિરોબિંદુઓમાંથી (જે એકવાર હિટ થાય છે) તમારે ઓછામાં ઓછા અડધા જવાબ તરીકે લેવાની જરૂર છે.

અમે હમણાં જ શીખ્યા છે કે તેનાથી વધુ છોડવું નહીં 2k શિખરો ખરેખર, જો બાકીનો જવાબ તમામ શિરોબિંદુઓનો ઓછામાં ઓછો અડધો હોય, તો કુલ શિરોબિંદુઓ કરતાં વધુ કોઈ શિરોબિંદુઓ નથી 2k.

અહીં હું એક નાનું પગલું આગળ લઈ શક્યો. તે સ્પષ્ટ છે કે આ રીતે બાંધવામાં આવેલ કર્નલ દ્વિપક્ષીય ગ્રાફમાં આપણે કયા પ્રકારનું ન્યૂનતમ શિરોબિંદુ આવરણ લીધું છે તેના પર આધાર રાખે છે. હું એક લેવા માંગુ છું જેથી બાકીના શિરોબિંદુઓની સંખ્યા ન્યૂનતમ હોય. પહેલાં, તેઓ ફક્ત સમયસર આ કરવા સક્ષમ હતા . હું તે સમયે આ અલ્ગોરિધમના અમલીકરણ સાથે આવ્યો હતો , આમ, આ કોરને દરેક શાખાના તબક્કામાં હજારો શિરોબિંદુઓના ગ્રાફમાં શોધી શકાય છે.

પરિણામ

પ્રેક્ટિસ બતાવે છે કે મારું સોલ્યુશન કેટલાક સો શિરોબિંદુઓ અને હજારો કિનારીઓના પરીક્ષણો પર સારી રીતે કાર્ય કરે છે. આવા પરીક્ષણોમાં એવી અપેક્ષા રાખવી તદ્દન શક્ય છે કે અડધા કલાકમાં ઉકેલ મળી જશે. સ્વીકાર્ય સમયે જવાબ શોધવાની સંભાવના, સૈદ્ધાંતિક રીતે, જો ગ્રાફમાં ઉચ્ચ ડિગ્રીના શિરોબિંદુઓની પૂરતી મોટી સંખ્યા હોય, ઉદાહરણ તરીકે, ડિગ્રી 10 અને તેથી વધુ હોય તો વધે છે.

સ્પર્ધામાં ભાગ લેવા માટે, ઉકેલો મોકલવાના હતા optil.io. ત્યાં પ્રસ્તુત માહિતી દ્વારા અભિપ્રાય હસ્તાક્ષર, ઓપન ટેસ્ટમાં મારું સોલ્યુશન બીજાથી મોટા ગેપ સાથે વીસમાંથી ત્રીજા ક્રમે છે. સંપૂર્ણ પ્રમાણિક બનવા માટે, તે સંપૂર્ણપણે સ્પષ્ટ નથી કે સ્પર્ધામાં જ ઉકેલોનું મૂલ્યાંકન કેવી રીતે કરવામાં આવશે: ઉદાહરણ તરીકે, મારું સોલ્યુશન ચોથા સ્થાને સોલ્યુશન કરતાં ઓછા પરીક્ષણો પાસ કરે છે, પરંતુ જેઓ પાસ થાય છે તેના પર તે ઝડપથી કાર્ય કરે છે.

બંધ પરીક્ષણોના પરિણામો XNUMXલી જુલાઈના રોજ જાણવા મળશે.

સોર્સ: www.habr.com