પુનરાવર્તિત બેકટ્રેકર મેઝ જનરેટર

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

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

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

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

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

તે કેવી રીતે કામ કરે છે

આ અલ્ગોરિધમ સ્ટેક-આધારિત ડેપ્થ-ફર્સ્ટ સર્ચ અભિગમનો ઉપયોગ કરીને કાર્ય કરે છે. અહીં સ્ટેપ-બાય-સ્ટેપ બ્રેકડાઉન છે:

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

આ અલ્ગોરિધમ વિશે એક રસપ્રદ વાત એ છે કે તે મેઝ જનરેટર અને મેઝ સોલ્વર બંને તરીકે કામ કરે છે. જો તમે તેને પહેલાથી જ જનરેટ થયેલા મેઝ પર ચલાવો છો અને નક્કી કરેલા અંતિમ બિંદુ પર પહોંચતા જ બંધ કરી દો છો, તો સ્ટેકમાં મેઝનો ઉકેલ હશે.

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

વધુ વાંચન

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

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