N (Насти) алгоритм

Памяти Насти. Памяти дочери.

Что знаем об алгоритмах поиска? Есть граф. Чаще ориентированный. И некое целевое состояние. Фиксированное. А если нет?

Как, например, найти ребенка, который потерялся в лесу? Ведь не только вы его будете искать, но и он вас.

Передвигаться случайно? Да. Но еще лучше выбирать те направления, где меньше всего были. Есть дополнительные признаки, например следы? Отлично. В первую очередь ориентируемся на них. Потерялись следы? Вновь возвращаемся к поиску с учетом только памяти.

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 — ищет в первую очередь по признакам, если таковые имеются.

Разумеется, именно 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(self.maps, self.ban)              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                      for y in range(len(self.maps)):             for x in range(len(self.maps[0])):                 Z.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))                                      Z.neighbor[(y,x)] = n                                  self.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)] = 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 = {}         P.neighbor = {}          self.visit[(self.y, self.x)] = 1         P.neighbor[(self.y, self.x)] = Z.neighbor[(self.y, self.x)]                      def update(self):         self.move()            self.root.after(500, self.update)      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 choice(self, yx):         v = []                  for i in P.neighbor[yx]:              if not yx in self.visit:                 self.visit[yx] = 0             v.append(i)             return random.choice(v)              def move(self):         for i in Z.neighbor[(self.y, self.x)]:             if (self.y, self.x) not in P.neighbor:                 P.neighbor[(self.y, self.x)] = Z.neighbor[(self.y, self.x)]                      y,x = self.choice((self.y, self.x))                  self.show(self.y, self.x, 'white')             self.y = y         self.x = x         self.show(y, x, self.color)                  self.count +=1                           if self.target == Z.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()                   class M(P):     def __init__(self, root, color, node, target, maps, ban):         super().__init__(root, color, node, target, maps, ban)         self.visit[node] += 1              def move(self):         yx = self.choice((self.y, self.x))                  self.show(self.y, self.x, 'white')             self.y = yx[0]         self.x = yx[1]         self.show(yx[0], yx[1], self.color)                  self.count +=1                  if self.target == Z.hierarchy[(self.y, self.x)]:             #J.disable = True             self.top_show()              def choice(self, yx):         v = []                  for i in Z.neighbor[yx]:             if (yx) not in P.neighbor:                 P.neighbor[yx] = Z.neighbor[yx]                          for i in P.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(M):     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 = []                  for i in Z.neighbor[yx]:             if (yx) not in P.neighbor:                 P.neighbor[yx] = Z.neighbor[yx]                          for i in P.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:             v = []                          for i in Z.neighbor[(self.y, self.x)]:                 if (self.y, self.x) not in P.neighbor:                     P.neighbor[(self.y, self.x)] = Z.neighbor[(self.y, self.x)]                              y,x = self.choice((self.y, self.x))                          Z.hierarchy[(self.y, self.x)] = self.target[:-1] + \               str(int(self.target[-1]) - 1) #'4288'             Z.time[(y, x)] = TIME                              self.show(self.y, self.x, 'white')                self.y = y             self.x = x             Z.hierarchy[(self.y, self.x)] = self.target             self.show(y, x, self.color)               #--------- 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()