طرق للعثور على الهدف. دور الصدفة

1. مقدمة

يمكن أن يكون البحث معقدًا أو بسيطًا. عندما تكون غير معروفة (أو معروفة جزئياً) بالهدف نفسه وطريقة تحقيقه ، تكون الفرصة مهمة

الهدف من مقالة البحث هو مقارنة طرق البحث عن الهدف بأنه متحرك (كائن أصفر) ، وبدون حراك.

هذه الطرق:

• بحث عشوائي (كائن أحمر)
• بحث عشوائي مع الذاكرة (كائن أزرق)
• بحث عشوائي مع الذاكرة والتسلسل الهرمي (كائن أخضر)
• ابحث عن المسار الأول (كائن أرجواني)
• ابحث عن طريق قصير (كائن بني)

في الشكل 1 ، تظهر هذه الكائنات. رمز البرنامج بالكامل نشر على جيثب

2. الجزء الرئيسي

2.1. الفئة P - البحث العشوائي

يقوم المُنشئ بتهيئة سمات ومتغيرات الفصل: نافذة رئيسية ولون وإحداثيات ص و س ، عداد ، قاموس زار ، هدف ، قاموس هرمي ، قاموس جيران. يملأ الأسلوب 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) 

يتم الإعلان عن وظيفة is_en في طريقة 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 

ترسم طريقة العرض خلية بإحداثيات y ، x باللون المطلوب.

 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) 

تعرض طريقة top_show النتائج.

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

2.2. فئة M - عشوائية ذاكرة البحث

يستدعي المنشئ مُنشئ الفئة الأصل ويزيد من قيمة خلية الحقل الذي نحن بصدده. تحريك طريقة التحرك الكائن. تقوم طريقة الاختيار بإرجاع الإحداثيات التي حددتها خوارزمية البحث العشوائي مع الذاكرة.

في طريقة النقل ، استدعاء طريقة الاختيار. خلاف ذلك ، فإن عمله يشبه طريقة الوالدين.

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

تتكرر طريقة الاختيار على إحداثيات الجيران وتضيف tuples إلى القائمة v. سيكون العنصر الأول من المجموعة هو إحداثيات الجار ، والثاني - كم مرة تم زيارتها. ثم نقوم بالفرز من الصغيرة إلى الكبيرة. نقوم بالفرز بين جميع الصفوف وفي القائمة 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. الفئة N - البحث العشوائي مع الذاكرة والتسلسل الهرمي.

تحدد طريقة الاختيار تلك المجموعات التي تتوافق بشكل وثيق مع الاسم الهرمي للهدف. إذا كانت هذه المطابقة هي نفسها ، فسيتم تحديد الإحداثيات التي كانت الأقل زيارة.

يستدعي المنشئ مُنشئ الأصل ويقوم بتهيئة سمة المصادفة عدد مرات مطابقة حروف الاسم الهرمي مع الهدف.

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

تكتب طريقة الاختيار في الحلقة الاسم الهرمي للإحداثي الحالي للجار. يقوم المتغير r بتخزين عدد مطابقات هذا المتغير مع الهدف. إذا كان عدد التطابقات أكبر ، فيتم استبدال الصدفة. في هذه الحالة ، تتم كتابة tuple (الإحداثيات ، عدد الزيارات) من القائمة v إلى القائمة د. إذا كانت r تساوي مصادفة ، فإننا نضيف t من v.

 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 - ابحث عن طريق وابحث عن أقصر طريق.

يكتب المنشئ إحداثيات النهاية إلى متغير النهاية. إذا كانت المعلمة القصيرة هي False ، فإننا نسميها البحث عن الطريق. خلاف ذلك ، نجد أقصر الطرق.

تضيف طريقة find_path الإحداثيات الحالية إلى المسار. إذا تم الوصول إلى الهدف ، فقم بإرجاع المسار. نحن فرز من خلال جميع الجيران. إذا لم يكن هناك جار في الطريق ، فدعو أنفسنا بشكل متكرر. وحقيقة أن الأسلوب يعود يعود إلى newpath. أول طريق تم العثور عليه سيكون newpath. الفرق بين طريقة 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 هي هدف متحرك.

يتحرك كائن الفئة J مثل الفئة P. إذا كان متغير الفئة J.disable صحيحًا ، فإن الكائن يتوقف.

2.6. الوظيفة الرئيسية.

إنشاء النافذة الرئيسية. في المتغير الهدف ، اكتب الاسم الهرمي للهدف. تحتوي قائمة الحظر على إحداثيات الخلايا المحرمة. في قائمة الخرائط ، الخريطة نفسها. في الحلقة نرسم خريطة. إنشاء كائنات فئة. ثم نسميه وظيفة التحديث ، والتي تقوم بتحديث الكائنات.

3. الاستنتاجات

أجريت خمس تجارب من أجل هدف متحرك ولغاية بلا حراك.

يوضح الجدول 1 أن أفضل خوارزمية هي أقصر طريق. الثاني الأكثر فعالية هو البحث العشوائي مع الذاكرة والتسلسل الهرمي. الأسوأ هو البحث العشوائي.

الجدول 1. الهدف الثابت



في حالة وجود هدف متحرك ، تكون النتائج مختلفة. وكانت أسوأ الخوارزميات هي تلك التي حسبت في البداية الطريق إلى الهدف. في الجدول 2 ، تشير الشرطة إلى أن الهدف لم يتحقق. تبين أن براون كان أسوأ من البنفسجي. والأسوأ من ذلك ، لأن البنفسجي لديه مسار أطول (فرصة لتحقيق هدف متحرك أكبر). أفضل خوارزمية عند البحث عن هدف متحرك هو البحث العشوائي مع الذاكرة والتسلسل الهرمي. في المقام الثاني هو البحث العشوائي مع الذاكرة.

الجدول 2. نقل الهدف



إذا لم يكن معروفًا ما إذا كان الهدف يتحرك أم لا ، فمن الأفضل استخدام خوارزمية البحث العشوائي مع الذاكرة والتسلسل الهرمي أو البحث العشوائي فقط مع الذاكرة.

4. الخلاصة

العشوائية مهمة إذا حدث البحث عن هدف في مواجهة حالة عدم اليقين. يتم تقليل البحث إذا تم تقديم البيانات بشكل هرمي. الذاكرة ، بالطبع ، هي أيضا قيمة.