రికర్సివ్ బ్యాక్‌ట్రాకర్ మేజ్ జనరేటర్

రికర్సివ్ బ్యాక్‌ట్రాకర్ అల్గోరిథం నిజానికి ఒక సాధారణ ప్రయోజన లోతు-మొదటి శోధన. మేజ్ జనరేషన్ కోసం ఉపయోగించినప్పుడు, యాదృచ్ఛికంగా మార్గాన్ని ఎంచుకోవడానికి ఇది కొద్దిగా సవరించబడింది, అయితే వాస్తవ శోధన ప్రయోజనాల కోసం ఉపయోగించినట్లయితే, సాధారణంగా ప్రతి స్థాయిని సరళ క్రమంలో శోధిస్తుంది. ఇది పొడవైన, వైండింగ్ కారిడార్లు మరియు చాలా పొడవైన, ట్విస్టింగ్ సొల్యూషన్‌తో మేజ్‌లను ఉత్పత్తి చేస్తుంది.

పరిపూర్ణ మేజ్ అంటే ఒక మేజ్, దీనిలో మేజ్‌లోని ఏ బిందువు నుండి మరొక బిందువుకు అయినా ఒకే మార్గం ఉంటుంది. అంటే మీరు వృత్తాలుగా తిరగలేరు, కానీ మీరు తరచుగా డెడ్ ఎండ్‌లను ఎదుర్కొంటారు, దీనివల్ల మీరు తిరిగి వెనక్కి వెళ్ళవలసి వస్తుంది.

ఇక్కడ రూపొందించబడిన మేజ్ మ్యాప్‌లు ఎటువంటి ప్రారంభ మరియు ముగింపు స్థానాలు లేకుండా డిఫాల్ట్ వెర్షన్‌ను కలిగి ఉంటాయి, కాబట్టి మీరు వాటిని మీరే నిర్ణయించుకోవచ్చు: మేజ్‌లోని ఏ పాయింట్ నుండి ఏదైనా ఇతర పాయింట్‌కి పరిష్కారం ఉంటుంది. మీకు ప్రేరణ కావాలంటే, మీరు సూచించిన ప్రారంభ మరియు ముగింపు స్థానాన్ని ప్రారంభించవచ్చు - మరియు రెండింటి మధ్య పరిష్కారాన్ని కూడా చూడవచ్చు.

రికర్సివ్ బ్యాక్‌ట్రాకర్ అల్గోరిథం అనేది పరిపూర్ణ మేజ్‌లను (లూప్‌లు లేకుండా మరియు ఏదైనా రెండు పాయింట్ల మధ్య ఒకే మార్గం లేకుండా మేజ్‌లు) రూపొందించడానికి లోతు-మొదటి శోధన పద్ధతి. ఇది సరళమైనది, సమర్థవంతమైనది మరియు పొడవైన, వైండింగ్ కారిడార్‌లతో దృశ్యపరంగా ఆకర్షణీయమైన మేజ్‌లను ఉత్పత్తి చేస్తుంది.

దాని పేరు ఉన్నప్పటికీ, దీనిని రికర్షన్ ఉపయోగించి అమలు చేయవలసిన అవసరం లేదు. ఇది తరచుగా LIFO క్యూ (అంటే స్టాక్) ఉపయోగించి పునరుక్తి విధానంలో అమలు చేయబడుతుంది. చాలా పెద్ద మేజ్‌ల కోసం, రికర్షన్‌ను ఉపయోగించడం వల్ల ప్రోగ్రామింగ్ భాష మరియు అందుబాటులో ఉన్న మెమరీని బట్టి కాల్ స్టాక్ ఓవర్‌ఫ్లో వచ్చే అవకాశం ఉంది. LIFO క్యూను పెద్ద మొత్తంలో డేటాను నిర్వహించడానికి మరింత సులభంగా స్వీకరించవచ్చు, అందుబాటులో ఉన్న మెమరీ సరిపోకపోతే డిస్క్‌లో లేదా డేటాబేస్‌లో క్యూను ఉంచడం కూడా చేయవచ్చు.

అది ఎలా పని చేస్తుంది

ఈ అల్గోరిథం స్టాక్-ఆధారిత డెప్త్-ఫస్ట్ సెర్చ్ విధానాన్ని ఉపయోగించి పనిచేస్తుంది. దశలవారీగా బ్రేక్‌డౌన్ ఇక్కడ ఉంది:

1. ప్రారంభ గడిని ఎంచుకుని, దానిని సందర్శించినట్లుగా గుర్తించండి.
2. సందర్శించని సెల్‌లు ఉన్నప్పటికీ: సందర్శించని పొరుగు సెల్‌లను చూడండి. కనీసం ఒక సందర్శించని పొరుగు వ్యక్తి ఉంటే: యాదృచ్ఛికంగా సందర్శించని పొరుగువారిలో ఒకదాన్ని ఎంచుకోండి. ప్రస్తుత సెల్ మరియు ఎంచుకున్న పొరుగువారి మధ్య గోడను తీసివేయండి. ఎంచుకున్న పొరుగువారికి తరలించి, దానిని సందర్శించినట్లు గుర్తించండి. ప్రస్తుత సెల్‌ను స్టాక్‌పైకి నెట్టండి. సందర్శించని పొరుగువారు ఎవరూ లేకుంటే: స్టాక్ నుండి చివరి సెల్‌ను పాప్ చేయడం ద్వారా బ్యాక్‌ట్రాక్ చేయండి.
3. స్టాక్ ఖాళీ అయ్యే వరకు ఈ ప్రక్రియను కొనసాగించండి.

ఈ అల్గోరిథం గురించి ఒక ఆసక్తికరమైన విషయం ఏమిటంటే ఇది మేజ్ జనరేటర్‌గా మరియు మేజ్ సాల్వర్‌గా పనిచేస్తుంది. మీరు ఇప్పటికే జనరేట్ చేయబడిన మేజ్‌పై దీన్ని అమలు చేసి, మీరు నిర్ణయించిన ముగింపు బిందువును చేరుకున్నప్పుడు ఆపివేసినట్లయితే, స్టాక్ మేజ్‌కు పరిష్కారాన్ని కలిగి ఉంటుంది.

నిజానికి ఈ సైట్‌లో ఈ అల్గోరిథం యొక్క రెండు వెర్షన్‌లు నా దగ్గర ఉన్నాయి: ఈ పేజీలో మేజ్‌లను రూపొందించడానికి LIFO క్యూ ఆధారితమైనది మరియు మేజ్‌లను పరిష్కరించడానికి రికర్షన్ ఆధారితమైనది, అలాగే ఇతర అల్గోరిథంల ద్వారా రూపొందించబడిన మేజ్‌లు (సొల్యూషన్‌లతో కూడిన మ్యాప్‌లను ఈ విధంగా తయారు చేస్తారు). రెండు వేర్వేరు వెర్షన్‌లను కలిగి ఉండటం కేవలం క్రీడల కోసం మాత్రమే ఎందుకంటే నేను ఒక మేధావిని కాబట్టి అది ఆసక్తికరంగా ఉంటుంది, రెండింటికీ ఒకటి పని చేసి ఉండవచ్చు ;-)

మరింత చదవడానికి

మీరు ఈ పోస్ట్‌ను ఆస్వాదించినట్లయితే, మీరు ఈ సూచనలను కూడా ఇష్టపడవచ్చు:

• ఎలర్ల యొక్క అల్గోరిథం మేజి జనరేటర్
• విల్సన్ అల్గోరిథం మేజ్ జనరేటర్
• పెరుగుతున్న ట్రీ అల్గోరిథం మేజ్ జనరేటర్