लक्ष्य खोजने के तरीके। मौका की भूमिका

1. परिचय

खोज या तो जटिल या सरल हो सकती है। जब लक्ष्य (या केवल आंशिक रूप से ज्ञात) दोनों ही लक्ष्य और इसे प्राप्त करने का तरीका नहीं है, तो मौका महत्वपूर्ण है

अनुसंधान लेख का उद्देश्य लक्ष्य को खोजने के तरीकों की तुलना चलती (पीली वस्तु), और गतिहीन के रूप में करना है।

ये तरीके:

• यादृच्छिक खोज (लाल वस्तु)
• स्मृति के साथ यादृच्छिक खोज (नीली वस्तु)
• स्मृति और पदानुक्रम (हरी वस्तु) के साथ यादृच्छिक खोज
• पहला मार्ग खोजें (बैंगनी वस्तु)
• एक छोटा मार्ग खोजें (भूरी वस्तु)

चित्र 1 में, इन वस्तुओं को दिखाया गया है। पूरी तरह से प्रोग्राम कोड गिथब पर पोस्ट किया गया

2. मुख्य भाग

2.1। कक्षा पी - यादृच्छिक खोज

कंस्ट्रक्टर वर्ग विशेषताओं और चर को आरंभीकृत करता है: मुख्य विंडो, रंग, y और x समन्वय, काउंटर, विज़िट किए गए शब्दकोश, लक्ष्य, पदानुक्रम शब्दकोश, पड़ोसी शब्दकोश। Init_3_dict पद्धति तीन शब्दकोशों को आबाद करती है। शो विधि सेल को वांछित रंग में पेंट करती है। अपडेट विधि ऑब्जेक्ट को अपडेट करती है। Top_show विधि एक शीर्ष-स्तरीय विंडो बनाता है और दिखाता है कि लक्ष्य के लिए कितने चरण हैं।

class P(): def __init__(self, root, color, node, target, maps, ban): self.root = root self.color = color self.y = node[0] self.x = node[1] P.target = target self.count = 0 self.visit = {} P.hierarchy = {} P.neighbor = {} self.init_3_dict(maps, ban) 

In__ फ़ंक्शन को init_3_dict पद्धति में घोषित किया गया है, जो यह जांचता है कि समन्वय प्रतिबंधित नहीं है और नक्शे से परे नहीं जाता है।

 def init_3_dict(self, maps, ban): def is_en(yx): if yx[0] < 0 or yx[0] > len(maps)-1: return if yx[1] < 0 or yx[1] > len(maps[0])-1: return if yx in ban: return return True 

एक चक्र में, समन्वय कुंजी के साथ गए शब्दकोश में, प्रारंभिक मूल्य शून्य लिखें। एक ही कुंजी के साथ पदानुक्रम शब्दकोश में, इस समन्वय के पदानुक्रमित नाम लिखें। फिर हम is_en फ़ंक्शन को कॉल करके पड़ोसियों के शब्दकोश में भरते हैं।

 for y in range(len(maps)): for x in range(len(maps[0])): self.visit[(y,x)] = 0 P.hierarchy[(y,x)] = maps[y][x] n = [] if is_en((y-1,x)): n.append((y-1,x)) if is_en((y+1,x)): n.append((y+1,x)) if is_en((y,x-1)): n.append((y,x-1)) if is_en((y,x+1)): n.append((y,x+1)) P.neighbor[(y,x)] = n 

शो विधि वाई के साथ एक सेल पेंट करता है, एक्स वांछित रंग में समन्वय करता है।

 def show(self, y, x, color): lb = Label(text=" ", background = color) lb.configure(text=P.hierarchy[(y,x)] ) lb.grid(row=self.y, column=self.x, ipadx=10, ipady=5, padx=1, pady=1) 

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

हम काउंटर बढ़ाते हैं। यदि लक्ष्य प्राप्त हो गया है तो जाँच करें। यदि लक्ष्य प्राप्त किया जाता है, तो कक्षा J.disable के चर में हम सही ढंग से लिखते हैं। हम top_show () विधि कहते हैं।

 def move(self): v = [] for i in P.neighbor[(self.y, self.x)]: v.append(i) y,x = random.choice(v) self.show(self.y, self.x, 'white') self.y = y self.x = x self.show(y, x, self.color) self.count +=1 if P.target == P.hierarchy[(self.y, self.x)]: J.disable = True self.top_show() 

अपडेट विधि कॉल चाल और अद्यतन हर आधे सेकंड में।

 def update(self): self.move() self.root.after(500, self.update) 

शीर्ष_शो विधि परिणाम प्रदर्शित करती है।

 def top_show(self): top = Toplevel() lbt = Label(top, text=self.color + " = " + str(self.count)) lbt.pack() top.mainloop() 

2.2। क्लास एम - रैंडम मेमोरी सर्च

कंस्ट्रक्टर, पैरेंट क्लास के कंस्ट्रक्टर को कॉल करता है और जिस क्षेत्र में हम जा रहे हैं, उस सेल की वैल्यू बढ़ाता है। चाल विधि वस्तु को आगे बढ़ाती है। चुनाव विधि उस समन्वय को लौटाती है जिसे स्मृति के साथ यादृच्छिक खोज एल्गोरिदम ने चुना है।

चाल विधि में, पसंद विधि को कॉल करें। अन्यथा, उसका काम माता-पिता की विधि के समान है।

 def move(self): yx = self.choice((self.y, self.x)) 

पसंद की विधि पड़ोसियों के निर्देशांक पर पुनरावृत्त होती है और सूची v में tuples को जोड़ती है। टपल का पहला तत्व पड़ोसी का समन्वय होगा, दूसरा - इसे कितनी बार देखा गया है। फिर हम छोटे से बड़े तक छँटते हैं। हम सभी tuples के माध्यम से सॉर्ट करते हैं और सूची v में हम केवल उन्हीं को छोड़ते हैं जो पहली बार ट्यूपल में दर्ज किए गए थे। बेतरतीब ढंग से उनमें से किसी का चयन करें।

 def choice(self, yx): v = [] for i in P.neighbor[yx]: v.append((i, self.visit[i])) v.sort(key = lambda x: x[1], reverse = False) v = [i for i in v if v[0][1] == i[1]] v = random.choice(v) self.visit[v[0]] += 1 return v[0] 

2.3। कक्षा एन - स्मृति और पदानुक्रम के साथ यादृच्छिक खोज।

पसंद विधि उन टुपल्स का चयन करती है जो लक्ष्य के पदानुक्रमित नाम से सबसे अधिक निकटता से मेल खाते हैं। यदि यह मैच समान है, तो कम से कम जाने वाले निर्देशांक चुने गए हैं।

कंस्ट्रक्टर माता-पिता के कंस्ट्रक्टर को कॉल करता है और संयोग को प्रारंभिक करता है लक्ष्य के साथ पदानुक्रमित नाम के चरित्र मिलानों की संख्या।

 def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) self.coincidence = 0 

लूप में पसंद विधि पड़ोसी के वर्तमान समन्वय के पदानुक्रमित नाम लिखती है। वेरिएबल आर इस वेरिएबल के मैचों की संख्या को लक्ष्य के साथ स्टोर करता है। यदि माच r की संख्या अधिक है, तो संयोग ओवरराइट किया जाता है। इस स्थिति में, सूची v से tuple (निर्देशांक, विज़िट की संख्या) सूची d पर लिखी जाती है। यदि r संयोग के बराबर है, तो d में हम v से एक tuple जोड़ते हैं।

 def choice(self, yx): v = [] for i in P.neighbor[yx]: v.append((i, self.visit[i])) d = [] for l in v: c = P.hierarchy[l[0]] r = 0 for i in range(len(P.target)): if c[i] == P.target[i]: r +=1 else: break if r > self.coincidence: self.coincidence = r d = [l] if r == self.coincidence: d.append(l) if d: v = d v.sort(key = lambda x: x[1], reverse = False) v = [i for i in v if v[0][1] == i[1]] v = random.choice(v) self.visit[v[0]] += 1 return v[0] 

2.4। कक्षा K - एक मार्ग की खोज करें और सबसे छोटे मार्ग की खोज करें।

कंस्ट्रक्टर अंत चर के लिए अंत निर्देशांक लिखता है। यदि छोटा पैरामीटर गलत है, तो हम मार्ग खोज कहते हैं। अन्यथा, हम सबसे छोटा मार्ग पाते हैं।

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

 def find_path(self, node, end, path=[]): path = path + [node] if node == end: return path for v in P.neighbor[node]: if v not in path: newpath = self.find_path(v, end, path) if newpath: return newpath 

2.5। कक्षा जे एक चलती लक्ष्य है।

क्लास J का ऑब्जेक्ट क्लास P की तरह चलता है। यदि क्लास J.disable का वेरिएबल सही है, तो ऑब्जेक्ट बंद हो जाता है।

2.6। मुख्य कार्य।

मुख्य विंडो बनाएँ। लक्ष्य चर में, लक्ष्य के पदानुक्रमित नाम लिखें। प्रतिबंध सूची में निषिद्ध कोशिकाओं के निर्देशांक शामिल हैं। नक्शे की सूची में, नक्शा ही। लूप में हम एक नक्शा बनाते हैं। क्लास ऑब्जेक्ट बनाएँ। फिर हम अपडेट फ़ंक्शन को कॉल करते हैं, जो ऑब्जेक्ट्स को अपडेट करता है।

3. निष्कर्ष

गतिमान लक्ष्य के लिए और गतिहीन दोनों के लिए पाँच प्रयोग किए गए।

तालिका 1 से पता चलता है कि सबसे अच्छा एल्गोरिथ्म सबसे छोटा मार्ग है। दूसरी सबसे प्रभावी स्मृति और पदानुक्रम के साथ एक यादृच्छिक खोज है। सबसे खराब यादृच्छिक खोज है।

तालिका 1. निश्चित लक्ष्य



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

तालिका 2. लक्ष्य निर्धारण



यदि यह ज्ञात नहीं है कि लक्ष्य बढ़ रहा है या नहीं, तो स्मृति और पदानुक्रम के साथ यादृच्छिक खोज एल्गोरिथ्म या स्मृति के साथ यादृच्छिक खोज का उपयोग करना बेहतर है।

4. निष्कर्ष

यदि अनिश्चितता की स्थिति में लक्ष्य की तलाश होती है तो यादृच्छिकता महत्वपूर्ण है। यदि डेटा पदानुक्रम में प्रस्तुत किया जाता है तो खोज कम हो जाती है। स्मृति, निश्चित रूप से, मूल्यवान है।