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

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

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

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

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

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

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

મેઝ જનરેશન માટે ક્રુસ્કલનું અલ્ગોરિધમ કેવી રીતે કાર્ય કરે છે

પગલું 1: પ્રારંભ કરો

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

પગલું 2: દિવાલોને સૉર્ટ કરો

• દિવાલોને શફલ કરો અથવા રેન્ડમલી ક્રમમાં ગોઠવો. જો તમે તેને ક્રુસ્કલના અલ્ગોરિધમ તરીકે અમલમાં મૂકી રહ્યા છો, તો દિવાલોને રેન્ડમ ક્રમમાં ગોઠવો (કારણ કે મેઝ જનરેશન માટે વજનની જરૂર નથી).

પગલું 3: દિવાલો પર પ્રક્રિયા કરો

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

પગલું 4: પૂર્ણ થાય ત્યાં સુધી ચાલુ રાખો

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

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

વધુ વાંચન

જો તમને આ પોસ્ટ ગમી હોય, તો તમને આ સૂચનો પણ ગમશે:

• એલરનું અલ્ગોરિધમ મેઝ જનરેટર
• હન્ટ એન્ડ કિલ મેઝ જનરેટર
• વિલ્સન્સ એલ્ગોરિધમ મેઝ જનરેટર