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