एक ओलंपियाड समस्या को पार करते हुए, हम लेबिरिंथ और उनके पारित होने की पीढ़ी के घुमावदार गलियारों के साथ जाएंगे, और हम यह भी देखेंगे कि जूलिया भाषा में इसके छद्म कोड पर एल्गोरिदम सीमाओं के कार्यान्वयन की सादगी है।

कार्य

भूलभुलैया 10 से 10 से 10 का एक चेकर वर्ग है, कुछ कोशिकाओं में बाधाएं हैं, और एक सेल में एक निकास है। रोबोट इस तरह के चक्रव्यूह में है और 4 कमांड को पूरा कर सकता है: एक सेल को नीचे, ऊपर, दाएं या बाएं घुमाएं। यदि रोबोट भूलभुलैया की सीमाओं से परे जाने या एक बाधा के साथ पिंजरे में जाने की कोशिश करता है, तो यह जगह में रहता है। यदि रोबोट निकास में प्रवेश करता है, तो यह भूलभुलैया से बाहर निकलता है और आगे के आदेशों की अनदेखी करता है। रोबोट के लिए एक प्रोग्राम लिखें, जिसे निष्पादित करते हुए रोबोट किसी भी मामले में बाहर निकलता है, भले ही वह सेल जिसमें वह शुरुआत में स्थित था। कार्यक्रम में 1000 से अधिक टीम नहीं होनी चाहिए।

इनपुट प्रारूप

कोई प्रविष्टि नहीं है। आपको निर्दिष्ट एक विशिष्ट स्थिति के लिए एक कार्यक्रम लिखने की आवश्यकता है
भूलभुलैया।
भूलभुलैया का संस्करण जिसे आप कॉपी कर सकते हैं। 0 - मुक्त सेल, 1 - बाधा, x -
रास्ता निकालना।

0011010011 0100001000 0110x00000 0010000100 0000111000 0000100100 0000010010 0100101010 0011001010 1000011000

आउटपुट स्वरूप

एक लाइन जिसमें U, D, R, L की लंबाई 1000 से अधिक नहीं है

ट्रेनिंग

जो लोग जूलिया में ग्राफिक्स के साथ काम नहीं करते थे उन्हें पैकेज डाउनलोड करने की आवश्यकता होती है

 using Pkg Pkg.add("Plots") Pkg.add("Colors") Pkg.add("Images") Pkg.build("Images") #

यह जुपिटर में काम करने के लिए सबसे सुविधाजनक है, क्योंकि चित्रों को काम के दौरान सीधे प्रदर्शित किया जाएगा। यहां आप स्थापना के बारे में, साथ ही शुरुआती लोगों के लिए एक परिचय और कार्यों के बारे में जान सकते हैं।

हमारे कार्य की स्थिति में प्रतिलिपि के लिए भूलभुलैया का एक संस्करण है

 S0 = "0011010011 0100001000 0110x00000 0010000100 0000111000 0000100100 0000010010 0100101010 0011001010 1000011000"

भूलभुलैया को आकर्षित करने के लिए, आपको एक मैट्रिक्स बनाने की आवश्यकता है। चूंकि हम मैन्युअल रूप से स्थान नहीं बनाना चाहते हैं, इसलिए हम लाइन के साथ काम करेंगे:

 S1 = prod(s-> s*' ', '['*S0*']') # prod(fun, arr)    arr #     fun #  julia  *   "[ 0 0 1 1 0 1 0 0 1 1 \n 0 1 0 0 0 0 1 0 0 0 \n 0 1 1 0 x 0 0 0 0 0 \n 0 0 1 0 0 0 0 1 0 0 \n 0 0 0 0 1 1 1 0 0 0 \n 0 0 0 0 1 0 0 1 0 0 \n 0 0 0 0 0 1 0 0 1 0 \n 0 1 0 0 1 0 1 0 1 0 \n 0 0 1 1 0 0 1 0 1 0 \n 1 0 0 0 0 1 1 0 0 0 ] "

एक नंबर के साथ अजीब अक्षर x को बदलना और स्ट्रिंग को पार्स करना, हमें एक भूलभुलैया मैट्रिक्स मिलता है जो हमारे भूलभुलैया को परिभाषित करता है। फिर, अधिक सुविधा के लिए, लोगों को शून्य में बदलें, और शून्य को लोगों को, और एक दीवार पर भूलभुलैया को संलग्न करें:

 S2 = replace(S1, 'x'=>'9') M0 = S2 |> Meta.parse |> eval m,n = size(M0) M1 = replace(M0, 1=>0, 0=>1) M = zeros(Int64,m+2,n+2) for i in 2:m+1, j in 2:n+1 M[i,j] = M1[i-1,j-1] end M # Maze map matrix 12×12 Array{Int64,2}: 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 0 1 9 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0

मैट्रिक्स में

 length(M) 144

कोशिकाएं और उनसे

 sum(M)-9 70

जिस पर आप चल सकते हैं, वह है - संभावित शुरुआती स्थिति। आप दो-आयामी हिस्टोग्राम का निर्माण करके परिणाम प्रदर्शित कर सकते हैं

 using Plots heatmap(M, yaxis = :flip) # flip -

समाधान सत्यापन

सबसे पहले, आपको उन प्रक्रियाओं को काम करने की आवश्यकता है जो प्रस्तावित समाधान की शुद्धता को सत्यापित करेंगे। बिंदुओं और निर्देशांक की शब्दावली का उपयोग करने के लिए मिश्रित प्रकार Point निर्धारित करें:

 mutable struct Point x::Int64 # vertical y::Int64 # horisont Point(x, y) = new(x, y) end

और अब आपको यह जानने की ज़रूरत है कि आदेशों के अनुक्रम का अनुवाद कैसे किया जाए जो कोड में रोबोट के लिए समझ में आता है।

यह विचार काफी सरल है: एक प्रारंभिक समन्वय है, एक रेखा एक एल्गोरिथ्म के साथ आती है जो बताती है कि कैसे चलना है। हम एक चिट्ठी लेते हैं और देखते हैं कि पड़ोसी की कौन सी कोशिकाओं को आगे बढ़ना है। वर्तमान समन्वय के लिए हम इस सेल में संग्रहीत मूल्य को जोड़ते हैं। यही है, अगर शून्य (दीवार) है, तो हम कहीं भी स्थानांतरित नहीं हुए हैं, अन्यथा हमने आवश्यक दिशा में एक छोटा कदम उठाया है।

मेटाप्रोग्रामिंग की शक्ति का उपयोग करते हुए, आप आने वाले अनुक्रम को भारी, समान कोड के साथ बदल सकते हैं और इसे निष्पादित कर सकते हैं

 S = "RRLDUURULDDRDDRRRUUU" S1 = replace(S , "R"=>"c.y+=M[cx, c.y+1];") S1 = replace(S1, "L"=>"cy-=M[cx, cy-1];") S1 = replace(S1, "U"=>"c.x+=M[c.x+1, cy];") S1 = replace(S1, "D"=>"cx-=M[cx-1, cy];") #  - start point Sp = eval( Meta.parse(S1) )

लेकिन इस पद्धति में कई असुविधाएं हैं, इसलिए, हम शास्त्रीय सशर्त ऑपरेटरों का उपयोग करेंगे। वैसे, यह तथ्य कि आउटपुट को संख्या 9 से दर्शाया गया है, एक छोटी सी चाल है: प्रत्येक सेल की जांच नहीं करने के लिए, और क्या यह रास्ता है, हम एक विशिष्ट सेल में संग्रहीत मान जोड़कर आंदोलन शुरू करते हैं। जब रोबोट निकास पर कदम रखता है, तो एक जानबूझकर बड़ी संख्या को उसके समन्वय में जोड़ा जाता है, जैसे कि रोबोट सरणी की सीमाओं से परे उड़ता है, जिसे ब्लॉक का उपयोग करके त्रुटि के रूप में पकड़ा जा सकता है:

 try #     catch #       end

इस प्रकार, हम एक फ़ंक्शन लागू करते हैं जो यह जांच करेगा कि क्या स्ट्रिंग स्ट्रिंग से कमांड निष्पादित c रोबोट बिंदु c से शुरू होने वाले निकास तक पहुंचता है:

 function isexit(str, c) scatter!([cy],[cx]) try for s in str if s == 'R' c.y+=M[cx, c.y+1]; elseif s == 'L' cy-=M[cx, cy-1]; elseif s == 'U' c.x+=M[c.x+1, cy]; elseif s == 'D' cx-=M[cx-1, cy]; else println("Error! Use only R, L, U, D") end end catch return true end return false end

आइए एक फ़ंक्शन इकट्ठा करें जो सभी शुरुआती पदों पर पुनरावृत्ति करेगा

 function test(Str) k = 0 for i in 2:m+1, j in 2:n+1 if M[i,j] == 1 c = Point(i, j) a = isexit(S,c) if a k +=1 #println(a) end end end println(k, " test completed from ", sum(M)-9) end

आदेशों की जाँच करें:

 S = "RRRLDUUURRRUUURRRRLLLRRUULDDDDRRRRDDDRRRUUU" heatmap(M, yaxis = :flip) test(S) # 10 test completed from 70 plot!(legend = false)

सभी शुरुआती बिंदुओं का परीक्षण किया गया था, और केवल 10 ने बाहर निकलने का नेतृत्व किया। प्रत्येक बिंदु से निकास के लिए मार्गों का निर्माण करना आवश्यक है।

पीढ़ियों की पीढ़ी और मार्ग में गोता लगाने से पहले, हम अपने परिणामों को बचाएंगे। हम Images.jl पैकेज का उपयोग करेंगे जो छवि प्रसंस्करण (एक अच्छा उदाहरण ) के क्षेत्र में कई संभावनाएं प्रदान करता है। उनका एक सहायक उपकरण Colors.jl पैकेज है, जो जूलिया के रंगों के साथ काम करने की क्षमता का विस्तार करता है।

 using Images clrs(x) = x==9 ? RGB(1.,0.5,0) : RGB(x,x,x) maze = clrs.(M) # maze = Gray.(maze) # save("D:/dat/maze12x12.png", maze)

गहराई खोज

हैबर पर एक लेख से विचार को लागू किया।
विचार सरल है: दीवारों का एक ग्रिड बनाएं

 M = 10 N = 10 A = [ i&j&1 for i in 0:N, j in 0:M ] # isodd(i) & isodd(j) & 1 Gray.(A) # from Images.jl

फिर, के माध्यम से लूपिंग, हम मार्ग और शाखाओं के माध्यम से तोड़ते हैं। हम एक समारोह को परिभाषित करते हैं जो पड़ोसी गैर-अधिकृत क्षेत्रों को ढूंढता है (हम उन्हें एक पदनाम के अनुसार कहेंगे), और इनमें से एक पड़ोसी को लौटाते हैं (यदि कोई पड़ोसी पड़ोसी नहीं हैं, तो यह एक फ्लैग-पॉइंट लौटाता है):

 function neighbours2(A,p, n, m) nbrs = [Point(px, p.y+2), # up Point(px, py-2), # down Point(px-2, py), # left Point(p.x+2, py)] # right goal = [] for a in nbrs if 0<ax<=n && 0<ay<=m && A[ax,ay]==2 push!(goal, a) end end length(goal) != 0 ? rand(goal) : Point(-1,-1) end

हम इस तरह से दीवारों को तोड़ देंगे:

 function breakwall(A, newp,oldp) #  : x = (newp.x + oldp.x) >> 1 #   y = (newp.y + oldp.y) >> 1 A[x,y] = 1 end

एल्गोरिथ्म

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

कार्यक्रम कोड

 function amazeng(n, m) M = [ 2(i&j&1) for i in 0:n, j in 0:m ]; p = Point(2,2) #   lifo = [] #   push!(lifo, p) #i = 0 while length(lifo) != 0 #     M[px,py] = 1 #     np = neighbours2(M, p, n, m) # new point #    -   if np.x == np.y == -1 p = pop!(lifo) else push!(lifo, p) breakwall(M, np, p) p = np #i+=1 #maze = Gray.(M/2) #save("D:/dat/maze$i.png", maze) end end M[1,2] = 1 #  M[n,m+1] = 1 #  Gray.(M) end

 lbrnt = amazeng(36, 48) # save("D:/dat/maze111.png", lbrnt)

पथ खोज एल्गोरिथम:

प्रारंभिक सेल को वर्तमान बनाएं और इसे विज़िट के रूप में चिह्नित करें।
जब तक कोई हल नहीं मिल जाता
1. यदि वर्तमान सेल ने "पड़ोसी" की परिकल्पना की है
1. स्टैक पर वर्तमान सेल को पुश करें
2. पड़ोसी से एक यादृच्छिक सेल का चयन करें
3. चयनित सेल को चालू करें और इसे चिह्नित के रूप में चिह्नित करें।
2. अन्यथा, यदि स्टैक खाली नहीं है
1. स्टैक से पिंजरे को खींचो
2. इसे चालू करें
3. अन्यथा, कोई रास्ता नहीं है।

हम इसके विपरीत और एक कोशिका के दायरे में पड़ोसियों की तलाश कर रहे हैं, और एक के माध्यम से नहीं:

 function neighbours1(A, p, n, m) nbrs = [Point(px, p.y+1), # up Point(px, py-1), # down Point(px-1, py), # left Point(p.x+1, py)] # right goal = [] for a in nbrs if 0<ax<=n && 0<ay<=m && A[ax,ay]==1 push!(goal, a) end end length(goal) != 0 ? rand(goal) : Point(0,0) end

मार्ग और असफल प्रयासों को ड्राइंग के साथ भूलभुलैया पास करने के लिए एक एल्गोरिथ्म को परिभाषित करें

 function amazeng(img, start, exit) M = Float64.(channelview(img)) n, m = size(M) p = start M[exit.x,exit.y] = 1 lifo = [] push!(lifo, p) while px != exit.x || py != exit.y M[px,py] = 0.4 np = neighbours1(M, p, n, m) if np.x == np.y == 0 M[px,py] = 0.75 p = pop!(lifo) #  -  ,    #      else push!(lifo, p) p = np end end Gray.(M) end

जैसा कि कुछ ने देखा है, एक फ़ंक्शन भी कहा जाता है, जैसे कि एल्गोरिदम उत्पन्न (एकाधिक शेड्यूलिंग)। जब आप इसे दो नंबरों के साथ कॉल करते हैं, तो यह भूलभुलैया के निर्माण की विधि का काम करेगा, लेकिन अगर आप इसे इमेज और दो बिंदुओं (इनपुट और आउटपुट के निर्देशांक) को एक तर्क के रूप में निर्दिष्ट करके कहते हैं, तो आउटपुट पर हमें भूलभुलैया के साथ एक छवि मिलती है।

 img0 = load("D:/dat/maze111.png") amazeng(img0)

चलो हमारे भूलभुलैया पर प्रयास करें:

 img0 = load("D:/dat/maze12x12.png") n, m = size(img0) amazeng(img0, Point(11,9), Point(4,6) )

यहां तक कि अगर आप फ़ंक्शन को संशोधित करते हैं ताकि मार्ग याद किया जाता है, तो एल्गोरिथ्म अभी भी खुले स्थानों के कारण अप्रभावी साबित होता है। लेकिन माज़े महान निकलते हैं।

प्राइम का रैंडमाइज्ड अल्गोरिथम

जैसे ही आप लेबिरिंथ आकर्षित करना शुरू करते हैं, आप बंद नहीं करेंगे। चलो एक और दिलचस्प एल्गोरिथ्म करते हैं :

दीवारों से भरे ग्रिड से शुरू करें।
एक सेल का चयन करें, इसे भूलभुलैया के भाग के रूप में चिह्नित करें। सेल की दीवारों को दीवार की सूची में जोड़ें।
जबकि सूची में दीवारें हैं:
- सूची से एक यादृच्छिक दीवार चुनें। यदि केवल दो कोशिकाओं में से एक जिसे दीवार के शेयरों का दौरा किया जाता है, तो:
  - दीवार को एक मार्ग बनाएं और भूलभुलैया के हिस्से के रूप में परिकल्पित सेल को चिह्नित करें।
  - दीवार की सूची में आसन्न सेल दीवारों को जोड़ें।
- दीवार को सूची से हटा दें।

कोड

 neighbors(p::Point) = [Point(px, p.y+1), # up Point(px, py-1), # down Point(px-1, py), # left Point(p.x+1, py)] # right function newalls!(walls, p, maze, n, m) nbrs = neighbors(p) for a in nbrs if 1<ax<n-1 && 1<ay<m-1 && !maze[ax,ay] push!(walls, a) #       . end end end function breakwall!(p, maze, n, m) nbrs = neighbors(p) #       if sum( a-> maze[ax,ay], nbrs) == 1 for a in nbrs if maze[ax,ay] # true =  px == ax ? nx = px : px>ax ? nx = p.x+1 : nx = px-1 py == ay ? ny = py : py>ay ? ny = p.y+1 : ny = py-1 maze[px,py] = true #   maze[nx,ny] = true px = nx py = ny return true end end else return false end end function prim(n, m) M = falses(n,m); #    p = Point(2, 2) M[px,py] = true walls = [] newalls!(walls, p, M, n, m) while length(walls) != 0 p = splice!( walls, rand(1:length(walls)) ) if breakwall!(p, M, n, m) newalls!(walls, p, M, n, m) end end M end

 primaze = prim(19,19); Gray.(primaze)

यह अधिक शाखा और कोई कम भयानक नहीं है, खासकर विधानसभा प्रक्रिया।

और अब हम सबसे छोटा मार्ग खोजने के लिए सबसे आम एल्गोरिथम लागू करते हैं:

विधि ए *

2 शीर्ष सूची बनाई गई हैं - लंबित और पहले से ही समीक्षा की गई। लंबित लोगों के लिए एक शुरुआत बिंदु जोड़ा जाता है, अब तक की समीक्षा की सूची खाली है।
प्रत्येक बिंदु के लिए गणना की जाती है $ज$ - बिंदु से लक्ष्य तक अनुमानित दूरी।
विचार के लिए बिंदुओं की सूची से, सबसे छोटी के साथ बिंदु $ज$ । उसे रहने दो $X$ ।
अगर $X$ - लक्ष्य, फिर हमें मार्ग मिला।
हम ढोते हैं $X$ लंबित सूची से पहले से ही समीक्षा की सूची में।
प्रत्येक आसन्न बिंदु के लिए (इस पड़ोसी बिंदु को निरूपित करें ), निम्नलिखित करें:
- अगर $य$ पहले से ही समीक्षा में - इसे छोड़ें।
- अगर $य$ प्रतीक्षा सूची में अभी तक नहीं - इसे वहां जोड़ें।
यदि विचार के लिए अंकों की सूची खाली है, लेकिन हम लक्ष्य तक नहीं पहुंचे हैं, तो मार्ग मौजूद नहीं है।

शुरू करने के लिए, हम "बिंदु" वर्ग को परिभाषित करते हैं जो यह जानेगा कि यह लक्ष्य से कितनी दूर है:

 mutable struct Point_h x::Int64 # horisont y::Int64 # vertical h::Float64 Point_h(x, y) = new(x, y, 0.) end

अब हम संरचना के लिए एक तुलना ऑपरेशन को परिभाषित करते हैं, एक सरणी में एक तत्व की उपस्थिति स्थापित करने के लिए एक विधि, साथ ही एक तत्व को हटाने का कार्य, बिंदुओं और लिस्टिंग पड़ोसियों के बीच की दूरी का पता लगाना:

दूर ले जाया गया

 import Base: in, == ==(a::Point_h, b::Point_h) = ax==bx && ay==by function in(p::Point_h, Arr::Array{Point_h,1}) for a in Arr if a == p return true end end return false end function splicemin!(Arr)#::Array{Point_h,1} i = argmin( [ah for a in Arr] ) splice!(Arr, i) end dista(u,v) = hypot(vx-ux, vy-uy) # <=> sqrt( (vx-ux)^2 + (vy-uy)^2 ) neighbors(p::Point_h) = [Point_h(px, p.y+1), # up Point_h(px, py-1), # down Point_h(px-1, py), # left Point_h(p.x+1, py)] # right

हमेशा की तरह, अस्पष्ट ऑपरेटरों को कमांड का उपयोग करके स्पष्ट किया जा सकता है ? जैसे ?splice ?argmin

और, वास्तव में, विधि ए * ही

कोड

 function astar(M, start, final) #   -       isgood(p) = 1<px<n && 1<py<m && M[px,py] != 0 n, m = size(M) #       start.h = dista(start,final) closed = [] opened = [] push!(opened, start) while length(opened) != 0 X = splicemin!(opened) if X in closed continue end if X == final break end push!(closed, X) nbrs = neighbors(X) ygrex = filter(isgood, nbrs) for Y in ygrex if Y in closed continue else Yh = dista(Y, final) push!(opened, Y) end end end #    closed # return end

हम चित्र को भूलभुलैया के साथ लोड करते हैं और इसे एक मैट्रिक्स के रूप में प्रस्तुत करते हैं:

 img0 = load("D:/dat/maze0.png") mazematrix = Float64.(channelview(img0))

और हम एक मनमाना बिंदु से बाहर निकलने के लिए एक मार्ग का निर्माण करते हैं:

 s = Point_h(11,9) # start f = Point_h(4,6) # finish M = copy(mazematrix) route = astar(M, s, f) i = 1 for c in route #   M[cx,cy] = 0.7 #save("D:/dat/Astar$i.png", M) i+=1 end Gray.(M)

सभी पदों की एक खोज इस प्रकार है:

देखा कि एजेंट ~~प्रेट~~ हमेशा बाहर निकलने के पक्ष में जाता है और अक्सर मृत सिरों में बदल जाता है, जो अनावश्यक कदमों को जन्म देता है, और पूरे मार्ग को याद किया जाता है। यह ए * एल्गोरिथ्म के थोड़ा अधिक जटिल संस्करण से बचा जाता है।

2 शीर्ष सूची बनाई गई हैं - लंबित और पहले से ही समीक्षा की गई। लंबित लोगों के लिए एक शुरुआत बिंदु जोड़ा जाता है, अब तक की समीक्षा की सूची खाली है।
प्रत्येक बिंदु के लिए गणना की जाती है $F = G + H$ । $जी$ - शुरू से बिंदु तक की दूरी, $ज$ - बिंदु से लक्ष्य तक अनुमानित दूरी। प्रत्येक बिंदु उस बिंदु का लिंक भी संग्रहीत करता है जहां से वह आया था।
विचार के लिए बिंदुओं की सूची से, सबसे छोटी के साथ बिंदु $एफ$ । उसे रहने दो $X$ ।
अगर $X$ - लक्ष्य, फिर हमें मार्ग मिला।
हम ढोते हैं $X$ लंबित सूची से पहले से ही समीक्षा की सूची में।
प्रत्येक आसन्न बिंदु के लिए (इस पड़ोसी बिंदु को निरूपित करें ), निम्नलिखित करें:
- अगर $य$ पहले से ही समीक्षा में - इसे छोड़ें।
- अगर $य$ प्रतीक्षा सूची में अभी तक नहीं है - इसे वहां जोड़ें, लिंक को याद रखना $X$ और गणना की जा रही है $Y.G$ (यह है $X.G$ + से दूरी $X$ को $य$ ) और $Y.H$ ।
- अगर, हालांकि, $य$ विचार के लिए सूची में - यदि जाँच करें $X.G$ + से दूरी $X$ को $य$ $<Y.G$ तो हम मुद्दे पर आए $य$ कम रास्ता, जगह $Y.G$ पर $X.G$ + से दूरी $X$ को $य$ , और जिस बिंदु से वे आए थे $य$ पर $X$ ।
यदि विचार के लिए अंकों की सूची खाली है, लेकिन हम लक्ष्य तक नहीं पहुंचे हैं, तो मार्ग मौजूद नहीं है।

लेकिन अनावश्यक कदमों के साथ, हमारा विकल्प कार्य की बाधा के भीतर अच्छी तरह से है, इसलिए कार्यक्रमों को संशोधित करना आपका होमवर्क होगा।

ओलंपियाड के अंत तक, कुछ भी नहीं बचा था, लेकिन हमें अभी भी यह जानने की ज़रूरत है कि हमारे एल्गोरिदम के परिणामों का अनुवाद "RRLUUDL..." आदेशों में कैसे किया "RRLUUDL..."

और इन सभी के बाद माज़ के माध्यम से चलता है, हम मान सकते हैं कि समाधान बहुत सरल है। वास्तव में, एक साधारण विकल्प अभी भी शुरू होता है, लेकिन मैं वास्तव में सुंदर चीजें बनाना चाहता था ।

यदि हम अपने कलाकार को एक खुले क्षेत्र में रखते हैं और यादृच्छिक रूप से पहल करते हैं, तो वह अपने शुरुआती स्थान के पास संकोच करेगा। लेकिन दीवारों की शुरूआत के साथ, कुछ दिशाएं फीकी पड़ने लगेंगी, स्वतंत्रता की डिग्री कम हो जाएगी, और एक ही इनपुट डेटा के साथ, एजेंट अधिक दूरी तय करेगा।

यहाँ एक भूलभुलैया से रोबोट को बचाने के लिए उपयुक्तता के लिए जाँच टीमों का हमारा संस्करण है:

कोड

 M = [ 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 0 1 9 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0] mutable struct Point # point x::Int64 # vertical y::Int64 # horisont Point(x, y) = new(x, y) end function isexit(str, c) try for s in str if s == 'R' c.y+=M[cx, c.y+1]; elseif s == 'L' cy-=M[cx, cy-1]; elseif s == 'U' c.x+=M[c.x+1, cy]; elseif s == 'D' cx-=M[cx-1, cy]; else println("Error! Use only R, L, U, D") end end catch return true end return false end function test(Str) k = 0 n, m = 10,10 for i in 2:m+1, j in 2:n+1 if M[i,j] == 1 c = Point(i, j) a = isexit(S,c) if a k +=1 #println(a) end end end println(k, " test completed from ", sum(M)-9) end

अब जब तक कि आप सभी आरंभिक पदों के लिए काम न कर लें, तब तक यादृच्छिक लाइनें उत्पन्न करना पर्याप्त है:

 using Random S = randstring("RLUD",200) "RDRRRDLRLUULURUDUUDLLLLLULLUDRRURDLDLULLRLUUUDURUUUULRUDUURUUDLRLLULRLUDRRLRRULLDULRRRRULRLLDULRLDRUDURDRUUDUUDDDDDLURRRRDRDURRRDDLLDUURRRLDRUDLRLLRDDRLRRRDDLLLRUURDRLURDLLUULLLLUURLLULUDULDDLDLLRLDUD" test(S) 41 test completed from 70

इसके अलावा, परीक्षण के बारे में परेशान नहीं करना संभव था। यह कार्य को पढ़ने और अधिकतम स्वीकार्य स्थिति के साथ एक यादृच्छिक स्ट्रिंग उत्पन्न करने के लिए पर्याप्त था:

 for i in 1:20 S = randstring("RLUD",1000) test(S) end 70 test completed from 70 70 test completed from 70 70 test completed from 70 70 test completed from 70 55 test completed from 70# 65 test completed from 70# 70 test completed from 70 70 test completed from 70 38 test completed from 70# 70 test completed from 70 70 test completed from 70 56 test completed from 70# 70 test completed from 70 70 test completed from 70 70 test completed from 70 16 test completed from 70# 70 test completed from 70 24 test completed from 70# 70 test completed from 70 70 test completed from 70

यानी 70% की संभावना के साथ, लाइन परीक्षणों को पारित करेगी।

वह सब है। मैं स्पष्ट समाधान के लिए पाठक को एक सफल यादृच्छिकता, धैर्य और अंतर्ज्ञान की कामना करता हूं।

जिज्ञासु के लिए - विषय को गहरा करने के लिए लिंक:

भूलभुलैया में जूलिया

कार्य

इनपुट प्रारूप

आउटपुट स्वरूप

ट्रेनिंग

समाधान सत्यापन

गहराई खोज

एल्गोरिथ्म

पथ खोज एल्गोरिथम:

प्राइम का रैंडमाइज्ड अल्गोरिथम

विधि ए *

More articles: