🏢 👩‍❤️‍💋‍👨 ☄️ भूलभुलैया पथ एल्गोरिथम 🎉 👎🏿 🤞🏼

शुभ दिन, प्रिय समुदाय।

प्रागितिहास

एक ठीक दिन, इंटरनेट के विस्तार में घूमना, एक भूलभुलैया पाया गया। इसके पारित होने और नेटवर्क पर चलने के बारे में जानना दिलचस्प हो गया, मुझे अभी भी एक कार्यशील सॉफ्टवेयर कार्यान्वयन, भूलभुलैया का समाधान नहीं मिला।

यह वास्तव में यह है:

काम का दिन उबाऊ था, मूड उत्कृष्ट था। एक लक्ष्य, साधन और इच्छा उपलब्ध हैं। निष्कर्ष स्पष्ट है, हम पास करेंगे।

कहानी

एक सुविधाजनक समाधान के लिए, आपके पास भूलभुलैया की मौजूदा छवि होनी चाहिए, दो-आयामी सरणी के प्रकार के लिए नेतृत्व करना चाहिए। जिनमें से प्रत्येक तत्व 3 में से एक मान ले सकता है:

const WALL=-1; BLANK=-2; DEADBLOCK=-3;

सबसे पहले, मैं भूलभुलैया की छवि को स्कैन करने के लिए फ़ंक्शन दिखाना चाहता हूं, इसके बाद सरणी में डेटा लिखकर और सरणी से डेटा के आधार पर एक नई छवि उत्पन्न करने का कार्य करता हूं:

छवि स्कैन:

 ... var N:integer=600; LABIRINT:array[0..600,0..600] of integer; ... var bit:TBitmap; i,j:integer; begin bit:=TBitmap.Create; If OpenDialog1.Execute then begin bit.LoadFromFile(OpenDialog1.FileName); for i:=0 to N do for j:=0 to N do if bit.Canvas.Pixels[j,i]=clWhite then LABIRINT[j,i]:=BLANK else LABIRINT[j,i]:=WALL; bit.Free; ... end; end; ...

छवि निर्माण:

 ... var N:integer=600; LABIRINT:array[0..600,0..600] of integer; ... procedure genBitmap; var bit:TBitmap; i,j:Integer; begin bit:=TBitmap.Create; bit.Width:=N+1; bit.Height:=N+1; for i:=0 to N do for j:=0 to N do begin if LABIRINT[i,j]=BLANK then bit.Canvas.Pixels[i,j]:=clWhite // else if LABIRINT[i,j]=WALL then bit.Canvas.Pixels[i,j]:=clBlack else bit.Canvas.Pixels[i,j]:=clRed; end; bit.SaveToFile('tmp.bmp'); bit.Free; end; ...

शुरुआत के लिए, आपको एक मोनोक्रोम बीएमपी के रूप में छवि को फिर से सहेजने की आवश्यकता है, ताकि 2 रंग सफेद या काले हों। यदि आप भूलभुलैया को करीब से देखते हैं, तो इसमें दीवार 2 पिक्सेल मोटी और सड़क 4 पिक्सेल मोटी है। यह दीवार और सड़क की मोटाई 1 पिक्सेल बनाने के लिए आदर्श होगा। ऐसा करने के लिए, छवि को फिर से बनाना आवश्यक है, छवि को 3 में विभाजित करें, अर्थात, चित्र से पिक्सेल के प्रत्येक 2 और 3, पंक्ति और स्तंभ को हटा दें (यह भूलभुलैया की शुद्धता और धैर्य को प्रभावित नहीं करेगा)।

तैयार चित्र:

छवि चौड़ाई और ऊँचाई: 1802 पिक्सेल।

1. हम इमेज स्कैनिंग फंक्शन का उपयोग करते हैं।
2. छवि का पुनर्निर्माण करें:

 ... var N:integer=1801; LABIRINT:array[0..1801,0..1801] of integer; ... procedure rebuildArr2; var i,j:integer; begin for i:=0 to ((N div 3) ) do for j:=0 to ((N div 3) ) do LABIRINT[i,j]:=LABIRINT[i*3,j*3]; N:=N div 3; end; ...

3. पुनर्निर्माण छवि उत्पन्न करें।

प्रक्रिया का परिणाम:

छवि चौड़ाई और ऊँचाई: 601 पिक्सेल।

और इसलिए, हमारे पास वांछित प्रकार के भूलभुलैया की एक छवि है, अब सबसे दिलचस्प है भूलभुलैया को पारित करने के सभी विकल्पों की खोज। हमारे पास क्या है? दर्ज की गई वैल के साथ एक सरणी - दीवार और BLANK - सड़क।

लहर एल्गोरिथ्म का उपयोग करके भूलभुलैया के मार्ग को खोजने का एक असफल प्रयास था। सभी प्रयासों में असफल क्यों, इस एल्गोरिथ्म ने "स्टैक ओवरफ्लो" त्रुटि का नेतृत्व किया। मुझे 100% यकीन है कि इसका उपयोग करके, आप मार्ग पा सकते हैं, लेकिन कुछ और दिलचस्प होने के लिए आने का एक कारण था।

यह विचार तुरंत नहीं आया, पारित होने के कई अहसास थे, जो समय में लगभग 3 मिनट के लिए काम करते थे, जिसके बाद प्रेरणा आई: "क्या होगा यदि आप रास्तों की तलाश नहीं करते हैं, लेकिन पथ जो भूलभुलैया की ओर नहीं जाते हैं और उन्हें मृत सिरों पर चिह्नित करते हैं"।

एल्गोरिथ्म इस प्रकार है:
भूलभुलैया सड़कों के सभी बिंदुओं के साथ एक पुनरावर्ती कार्य करें:
1. यदि हम सड़क पर खड़े होते हैं और हमारे चारों ओर 3 दीवारें होती हैं, तो उस स्थान को चिह्नित करें जहां हम एक मृत अंत के रूप में खड़े हैं, अन्यथा हम फ़ंक्शन से बाहर निकलते हैं;
2. हम उस जगह से गुजरते हैं जो बिंदु नंबर 1 से दीवार नहीं है, और हम बिंदु नंबर 1 को दोहराते हैं;

सॉफ्टवेयर कार्यान्वयन:

 ... var N:integer=600; LABIRINT:array[0..600,0..600] of integer; ... procedure setBlankAsDeadblockRec(x,y:integer); var k:integer; begin k:=0; if LABIRINT[x,y]=blank then begin if LABIRINT[x-1,y]<>BLANK then k:=k+1; if LABIRINT[x,y-1]<>BLANK then k:=k+1; if LABIRINT[x+1,y]<>BLANK then k:=k+1; if LABIRINT[x,y+1]<>BLANK then k:=k+1; if k=4 then LABIRINT[x,y]:=DEADBLOCK; if k=3 then begin LABIRINT[x,y]:=DEADBLOCK; if LABIRINT[x-1,y]=BLANK then setBlankAsDeadblockRec(x-1,y); if LABIRINT[x,y-1]=BLANK then setBlankAsDeadblockRec(x,y-1); if LABIRINT[x+1,y]=BLANK then setBlankAsDeadblockRec(x+1,y); if LABIRINT[x,y+1]=BLANK then setBlankAsDeadblockRec(x,y+1); end; end; end; procedure setDeadblock; var i,j:integer; begin for i:=1 to N-1 do for j:=1 to N-1 do setBlankAsDeadblockRec(i,j); end; ...

निष्कर्ष

मुझे एक "पूर्ण" वर्किंग एल्गोरिथ्म मिला, जिसका उपयोग सभी भूलभुलैया को खोजने के लिए किया जा सकता है। गति में नवीनतम सभी अपेक्षाओं को पार कर गया। मुझे उम्मीद है कि मेरे छोटे से काम से किसी को फायदा होगा या नए विचारों के लिए धक्का लगेगा।

कार्यक्रम कोड और भूलभुलैया का पता लगाया:

 //       . unit Unit1; interface uses Windows, Graphics, Forms, Dialogs, ExtCtrls, StdCtrls, Controls, Classes; const WALL=-1; BLANK=-2; DEADBLOCK=-3; type TForm1 = class(TForm) Button1: TButton; OpenDialog1: TOpenDialog; procedure Button1Click(Sender: TObject); private { Private declarations } public { Public declarations } end; var Form1: TForm1; N:integer=600; LABIRINT:array[0..600,0..600] of integer; implementation {$R *.dfm} procedure genBitmap; var bit:TBitmap; i,j:Integer; begin bit:=TBitmap.Create; bit.Width:=N+1; bit.Height:=N+1; for i:=0 to N do for j:=0 to N do begin if LABIRINT[i,j]=BLANK then bit.Canvas.Pixels[i,j]:=clWhite // else if LABIRINT[i,j]=WALL then bit.Canvas.Pixels[i,j]:=clBlack else bit.Canvas.Pixels[i,j]:=clRed; end; bit.SaveToFile('tmp.bmp'); bit.Free; end; procedure rebuildArr2; var i,j:integer; begin for i:=0 to ((N div 3) ) do for j:=0 to ((N div 3) ) do LABIRINT[i,j]:=LABIRINT[i*3,j*3]; N:=N div 3; end; procedure setBlankAsDeadblockRec(x,y:integer); var k:integer; begin k:=0; if LABIRINT[x,y]=blank then begin if LABIRINT[x-1,y]<>BLANK then k:=k+1; if LABIRINT[x,y-1]<>BLANK then k:=k+1; if LABIRINT[x+1,y]<>BLANK then k:=k+1; if LABIRINT[x,y+1]<>BLANK then k:=k+1; if k=4 then LABIRINT[x,y]:=DEADBLOCK; if k=3 then begin LABIRINT[x,y]:=DEADBLOCK; if LABIRINT[x-1,y]=BLANK then setBlankAsDeadblockRec(x-1,y); if LABIRINT[x,y-1]=BLANK then setBlankAsDeadblockRec(x,y-1); if LABIRINT[x+1,y]=BLANK then setBlankAsDeadblockRec(x+1,y); if LABIRINT[x,y+1]=BLANK then setBlankAsDeadblockRec(x,y+1); end; end; end; procedure setDeadblock; var i,j:integer; begin for i:=1 to N-1 do for j:=1 to N-1 do setBlankAsDeadblockRec(i,j); end; procedure TForm1.Button1Click(Sender: TObject); var bit:TBitmap; i,j:integer; begin bit:=TBitmap.Create; If OpenDialog1.Execute then begin bit.LoadFromFile(OpenDialog1.FileName); for i:=0 to N do for j:=0 to N do if bit.Canvas.Pixels[j,i]=clWhite then LABIRINT[j,i]:=BLANK else LABIRINT[j,i]:=WALL; bit.Free; setDeadblock; genBitmap; end; end; end.

सबसे छोटा रास्ता खोजने के लिए, लहर एल्गोरिथ्म को पाया जाने वाले भूलभुलैया चक्रों पर लागू करने की योजना है। यह सुनना दिलचस्प होगा कि एक बड़े भूलभुलैया में एक रास्ता खोजने के लिए अन्य एल्गोरिदम का क्या उपयोग किया जा सकता है?

भूलभुलैया पथ एल्गोरिथम

प्रागितिहास

कहानी

निष्कर्ष

More articles: