ક્રુસ્કલનું અલ્ગોરિધમ મેઝ જનરેટર

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

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

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

ક્રુસ્કલના અલ્ગોરિધમ વિશે

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

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

ભુલભુલામણી પેઢી માટે ક્રુસ્કલનું અલ્ગોરિધમ કેવી રીતે કાર્ય કરે છે

પગલું ૧ઃ પ્રારંભ કરો

• ભુલભુલામણીમાં દરેક કોષને એક અલગ સમૂહ (એક અનન્ય ઘટક) તરીકે ગણો.
• નજીકના કોષો વચ્ચેની તમામ દિવાલોને સંભવિત ધાર તરીકે સૂચિબદ્ધ કરો.

સ્ટેપ ૨ઃ દિવાલોને સોર્ટ કરો

• દીવાલોને બદલી નાખો અથવા અવ્યવસ્થિત રીતે ઓર્ડર કરો. જો તેને સાચા ક્રુસ્કલના અલ્ગોરિધમ તરીકે અમલમાં મૂકવામાં આવે, તો દિવાલોને રેન્ડમ ક્રમમાં ગોઠવો (કારણ કે ભુલભુલામણી પેઢીને વજનની જરૂર હોતી નથી).

સ્ટેપ ૩ઃ પ્રોસેસ વોલ્સ

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

પગલું ૪ઃ પૂર્ણ ન થાય ત્યાં સુધી ચાલુ રાખો.

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

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