1.简介
搜索可以是复杂的，也可以是简单的。 当目标本身和实现目标的方式未知（或仅部分未知）时，机会很重要
该研究文章的目的是比较发现目标为运动（黄色物体）和静止物体的方法。
这些方法：
- 随机搜索（红色物体）
- 带内存的随机搜索（蓝色对象）
- 具有内存和层次结构的随机搜索（绿色对象）
- 搜索第一条路线（紫色对象）
- 搜索一条短途路线（棕色物体）
在图1中，显示了这些对象。 完整的程序代码发布在
github上
2.主要部分
2.1。 P类-随机搜索
构造函数初始化类的属性和变量：主窗口，颜色，y和x坐标，计数器，已访问字典，目标，层次结构字典，邻居字典。 init_3_dict方法填充三个字典。 show方法将单元格绘制为所需的颜色。 update方法更新对象。 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
show方法使用所需颜色绘制具有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)
move方法移动对象。 在变量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()
update方法调用move并且每半秒更新一次。
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类-随机存储器搜索
构造函数调用父类的构造函数，并增加我们要去的字段的单元格的值。 move方法移动对象。 选择方法返回带有存储器的随机搜索算法选择的坐标。
在move方法中，调用choice方法。 否则，他的工作类似于父母的方法。
def move(self): yx = self.choice((self.y, self.x))
选择方法遍历邻居的坐标并将元组添加到列表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存储此变量与目标的匹配数。 如果匹配数r较大，则符合被覆盖。 在这种情况下，来自列表v的元组（坐标，访问次数）被写入列表d。 如果r等于巧合，则在d中从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类-搜索路线并搜索最短路线。
构造函数将结束坐标写入结束变量。 如果short参数为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的变量为true，则该对象停止。
2.6。 功能主体。
创建主窗口。 在目标变量中，编写目标的层次结构名称。 禁止列表包含禁止的单元格的坐标。 在地图列表中，地图本身。 在循环中，我们绘制了一张地图。 创建类对象。 然后我们调用更新函数，该函数将更新对象。
3.结论
对移动目标和静止目标都进行了五次实验。
表1显示最佳算法是最短路径。 第二有效的是具有内存和层次结构的随机搜索。 最糟糕的是随机搜索。
表1.固定目标
在移动目标的情况下，结果是不同的。 最差的算法是最初计算到达目标路线的算法。 在表2中，破折号表示尚未实现目标。 布朗比紫罗兰还差。 更糟糕的是，因为紫罗兰色的轨迹较长（达到移动目标的机会更大）。 搜索移动目标时，最好的算法是具有内存和层次结构的随机搜索。 其次是带有内存的随机搜索。
表2.移动目标
如果不知道目标是否在移动，则最好使用具有内存和层次结构的随机搜索算法，或者仅使用具有内存的随机搜索算法。
4.结论
如果寻找目标时面对不确定性，则随机性很重要。 如果数据分层显示，则搜索会减少。 记忆当然也很有价值。