Памяти Насти. Памяти дочери.
Что знаем об алгоритмах поиска? Есть граф. Чаще ориентированный. И некое целевое состояние. Фиксированное. А если нет?
Как, например, найти ребенка, который потерялся в лесу? Ведь не только вы его будете искать, но и он вас.
Передвигаться случайно? Да. Но еще лучше выбирать те направления, где меньше всего были. Есть дополнительные признаки, например следы? Отлично. В первую очередь ориентируемся на них. Потерялись следы? Вновь возвращаемся к поиску с учетом только памяти.
while True: if есть совпадение по признакам: #N выбрать направление с более точным совпадением else: if количество посещений по направлениям разное: #M выбрать менее посещаемое направление else: #P выбрать случайное направление
Что значит выбор с более точным совпадением признаков? Пусть есть соседние состояния {12*, 11*, 14*, 212, 213, 221, 225}. Если целью является состояние 218, то наибольшее совпадение будет либо с 212, либо с 213. Если допустить, что 213 посещалось меньшее число раз, то выбор будет сделан в пользу этого состояния.
Чтобы приблизить к реальности, признаки, которые оставляет после себя подвижный объект, имеют свой срок жизни TIME. Хорошо, если они уникальны. Если же нет, то алгоритм может оставаться в ложной области значительное время.
Сама идея такого поиска - слегка переработанный вариант (код + комментарий кода Насти). Может ошибаюсь, но такой реализации не встречал, как и не встречал самого алгоритма.
Попробуем оценить эффективность кода. Было проведено 10 испытаний как для объекта J(P), так и для объекта J(M). Здесь желтый объект J - подвижное целевое состояние. P - использует только случайный поиск. M - метод поиска, который использует информацию о количестве посещений соседних состояний. N - ищет в первую очередь по признакам, если таковые имеются.
J(P) | J(M) | ||||||
P | M | N | P | M | N | ||
1 | >50 | 31 | 7 | 20 | 17 | 9 | |
2 | >50 | 43 | 15 | 18 | 38 | 38 | |
3 | 32 | 12 | 25 | >50 | 36 | 18 | |
4 | 40 | 34 | 8 | >50 | 50 | 5 | |
5 | >50 | 13 | 12 | 13 | 6 | 6 | |
6 | 39 | 8 | 23 | 24 | 24 | 15 | |
7 | >50 | 14 | 7 | >50 | 37 | 11 | |
8 | >50 | 29 | 13 | 29 | 8 | 8 | |
9 | 10 | 7 | 13 | 17 | 26 | 9 | |
10 | 27 | 21 | 9 | 15 | 9 | 8 | |
Среднее до цели | 39.8 | 21.2 | 13.2 | 28.6 | 25.1 | 12.7 |
Разумеется, именно N в выигрыше в большинстве случаев. Существенна разница для поиска методом P. Объясняется тем, что цель J(M) в сравнении с целью J(P) охватывает больше площади, поэтому и встретиться с P имеет большую вероятность.
from tkinter import * import random TIME = 10 class Z(): def __init__(self, root, maps, ban): self.root = root self.maps = maps self.ban = ban Z.time = {} Z.hierarchy = {} Z.neighbor = {} self.init_3_dict() def init_3_dict(self): def is_en(yx): if yx[0] < 0 or yx[0] > len(self.maps)-1: return if yx[1] < 0 or yx[1] > len(self.maps[0])-1: return if yx in self.ban: return return True for y in range(len(self.maps)): for x in range(len(self.maps[0])): Z.hierarchy[(y,x)] = self.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)) Z.neighbor[(y,x)] = n Z.time[(y,x)] = 0 if (y, x) in self.ban: lb = Label(text=" ", background = 'black') lb.configure(text=self.maps[y][x]) else: lb = Label(text=" ", background = 'white') lb.configure(text=self.maps[y][x]) lb.grid(row=y, column=x, ipadx=10, ipady=5, padx=1, pady=1) self.update() def update(self): for y in range(len(self.maps)): for x in range(len(self.maps[0])): if Z.time[(y,x)]: Z.time[(y,x)] -=1 else: Z.hierarchy[(y,x)] = self.maps[y][x] if not (y, x) in self.ban: lb = Label(text=" ", background = 'white') lb.configure(text=Z.hierarchy[(y,x)]) lb.grid(row=y, column=x, ipadx=10, ipady=5, padx=1, pady=1) self.root.after(500, self.update) 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] self.target = target self.count = 0 self.visit = {} self.neighbor = {} def show(self, y, x, color): lb = Label(text=" ", background = color) lb.configure(text=Z.hierarchy[(y,x)] ) lb.grid(row=self.y, column=self.x, ipadx=10, ipady=5, padx=1, pady=1) def add_neighbor(self): self.neighbor[(self.y, self.x)] = Z.neighbor[(self.y, self.x)] def choice(self, yx): self.add_neighbor() return random.choice((self.neighbor[yx])) def move(self): yx = self.choice((self.y, self.x)) self.redraw(yx) self.count +=1 if self.target == Z.hierarchy[(self.y, self.x)]: #J.disable = True self.top_show() def redraw(self, yx): self.show(self.y, self.x, 'white') self.y = yx[0] self.x = yx[1] self.show(yx[0], yx[1], self.color) 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() class M(P): def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) def choice(self, yx): v = [] self.add_neighbor() for i in self.neighbor[yx]: if not i in self.visit: self.visit[i] = 0 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] class N(P): def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) self.coincidence = 0 def choice(self, yx): v = [] self.add_neighbor() for i in self.neighbor[yx]: if not i in self.visit: self.visit[i] = 0 v.append((i, self.visit[i])) d = [] for l in v: c = Z.hierarchy[l[0]] r = 0 for i in range(len(self.target)): if c[i] == self.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] class J(M): #J(P) or J(M) def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) J.disable = False def move(self): if not J.disable: yx = self.choice((self.y, self.x)) Z.hierarchy[(self.y, self.x)] = self.target[:-1] + \ str(int(self.target[-1]) - 1) #'4288' Z.time[(yx[0], yx[1])] = TIME self.redraw(yx) Z.hierarchy[(self.y, self.x)] = self.target #--------- main ---------# if __name__ == "__main__": root = Tk() target = ('4289') ban=[(1,1), (1,2), (2,3), (5,5)] ''' maps = [ ["011", "012", "013", "211", "212", "201"], ["014", "015", "021", "213", "214", "202"], ["022", "023", "024", "215", "216", "203"], ["025", "026", "027", "213", "204", "205"], ["101", "102", "103", "121", "122", "123"], ["104", "105", "106", "124", "125", "126"] ] ''' maps = [ ["0111", "0121", "0132", "2112", "2121", "2013", "2011"], ["0141", "0152", "0211", "2132", "2143", "2021", "2013"], ["0221", "0231", "0242", "2151", "2162", "2031", "2033"], ["0252", "0262", "0271", "2131", "2041", "2052", "2032"], ["1011", "1022", "1032", "1212", "1231", "1231", "1233"], ["1042", "1053", "1062", "1241", "1233", "1262", "1261"], ["1041", "1052", "1064", "1245", "1255", "1266", "1264"], ] def update(): z1.update() p1.update() m1.update() n1.update() j1.update() z1 = Z(root, maps, ban) p1 = P(root, 'red', (1,0), target, z1.maps, z1.ban) m1 = M(root, 'blue', (1,0), target, z1.maps, z1.ban) n1 = N(root, 'green', (1,0), target, z1.maps, z1.ban) j1 = J(root, 'yellow', (4,4), target, z1.maps, z1.ban) root.after(500, update) root.mainloop()
Как только цель J найдена, будет найден кратчайший маршрут (если он существует) до стартовой позиции. Маршрут может быть не оптимальным, поскольку P,M,N не всегда будут иметь данные о всей карте. Ниже модификация кода с добавлением класса К.
from tkinter import * import random TIME = 10 class Z(): def __init__(self, root, maps, ban): self.root = root self.maps = maps self.ban = ban Z.time = {} Z.hierarchy = {} Z.neighbor = {} self.init_3_dict() def init_3_dict(self): def is_en(yx): if yx[0] < 0 or yx[0] > len(self.maps)-1: return if yx[1] < 0 or yx[1] > len(self.maps[0])-1: return if yx in self.ban: return return True for y in range(len(self.maps)): for x in range(len(self.maps[0])): Z.hierarchy[(y,x)] = self.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)) Z.neighbor[(y,x)] = n Z.time[(y,x)] = 0 if (y, x) in self.ban: lb = Label(text=" ", background = 'black') lb.configure(text=self.maps[y][x]) else: lb = Label(text=" ", background = 'white') lb.configure(text=self.maps[y][x]) lb.grid(row=y, column=x, ipadx=10, ipady=5, padx=1, pady=1) self.update() def update(self): for y in range(len(self.maps)): for x in range(len(self.maps[0])): if Z.time[(y,x)]: Z.time[(y,x)] -=1 else: Z.hierarchy[(y,x)] = self.maps[y][x] if not (y, x) in self.ban: lb = Label(text=" ", background = 'white') lb.configure(text=Z.hierarchy[(y,x)]) lb.grid(row=y, column=x, ipadx=10, ipady=5, padx=1, pady=1) self.root.after(500, self.update) class K(): shortest = [] def initK(self): global shortest shortest = [None]*len(self.neighbor)**2 self.find_short_path((self.y, self.x), self.node) return shortest def find_short_path(self, node, end, path=[]): global shortest path = path + [node] if node == end: return path for v in self.neighbor[node]: if v not in path and v in self.neighbor: newpath = self.find_short_path(v, end, path) if newpath: #print("newpath =", newpath) if len(newpath) <= len(shortest): shortest = newpath class P(K): def __init__(self, root, color, node, target, maps, ban): self.root = root self.color = color self.y = node[0] self.x = node[1] self.node = node self.target = target self.count = 0 self.visit = {} self.neighbor = {} def show(self, y, x, color): lb = Label(text=" ", background = color) lb.configure(text=Z.hierarchy[(y,x)] ) lb.grid(row=self.y, column=self.x, ipadx=10, ipady=5, padx=1, pady=1) def add_neighbor(self): self.neighbor[(self.y, self.x)] = Z.neighbor[(self.y, self.x)] def choice(self, yx): self.add_neighbor() return random.choice((self.neighbor[yx])) def move(self): yx = self.choice((self.y, self.x)) self.redraw(yx) self.count +=1 if self.target == Z.hierarchy[(self.y, self.x)]: #J.disable = True self.add_neighbor() self.top_show() def redraw(self, yx): self.show(self.y, self.x, 'white') self.y = yx[0] self.x = yx[1] self.show(yx[0], yx[1], self.color) def update(self): self.move() self.root.after(500, self.update) def top_show(self): top = Toplevel() shortest = self.initK() short = ": srortest = " + ", ".join(map(str, shortest)) #lbt = Label(top, text=self.color + " = " + str(self.count) + short) print(self.color, "=", self.count, short, "\n") lbt = Label(top, text=self.color + " = " + str(self.count)) lbt.pack() top.mainloop() class M(P): def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) def choice(self, yx): v = [] self.add_neighbor() for i in self.neighbor[yx]: if not i in self.visit: self.visit[i] = 0 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] class N(P): def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) self.coincidence = 0 def choice(self, yx): v = [] self.add_neighbor() for i in self.neighbor[yx]: if not i in self.visit: self.visit[i] = 0 v.append((i, self.visit[i])) d = [] for l in v: c = Z.hierarchy[l[0]] r = 0 for i in range(len(self.target)): if c[i] == self.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] class J(P): #J(P) or J(M) def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) J.disable = False def move(self): if not J.disable: yx = self.choice((self.y, self.x)) Z.hierarchy[(self.y, self.x)] = self.target[:-1] + \ str(int(self.target[-1]) - 1) #'4288' Z.time[(yx[0], yx[1])] = TIME self.redraw(yx) Z.hierarchy[(self.y, self.x)] = self.target #--------- main ---------# if __name__ == "__main__": root = Tk() target = ('4289') ban=[(1,1), (1,2), (2,3), (5,5)] ''' maps = [ ["011", "012", "013", "211", "212", "201"], ["014", "015", "021", "213", "214", "202"], ["022", "023", "024", "215", "216", "203"], ["025", "026", "027", "213", "204", "205"], ["101", "102", "103", "121", "122", "123"], ["104", "105", "106", "124", "125", "126"] ] ''' maps = [ ["0111", "0121", "0132", "2112", "2121", "2013", "2011"], ["0141", "0152", "0211", "2132", "2143", "2021", "2013"], ["0221", "0231", "0242", "2151", "2162", "2031", "2033"], ["0252", "0262", "0271", "2131", "2041", "2052", "2032"], ["1011", "1022", "1032", "1212", "1231", "1231", "1233"], ["1042", "1053", "1062", "1241", "1233", "1262", "1261"], ["1041", "1052", "1064", "1245", "1255", "1266", "1264"], ] def update(): for i in all_update: i.update() z1 = Z(root, maps, ban) p1 = P(root, 'red', (1,0), target, z1.maps, z1.ban) m1 = M(root, 'blue', (1,0), target, z1.maps, z1.ban) n1 = N(root, 'green', (1,0), target, z1.maps, z1.ban) j1 = J(root, 'yellow', (4,4), target, z1.maps, z1.ban) all_update = [z1, p1, m1, n1, j1] root.after(500, update) root.mainloop()
