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

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

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

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

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()
        
    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 = {}

        self.visit[(self.y, self.x)] = 1
        self.neighbor[(self.y, self.x)] = Z.neighbor[(self.y, self.x)]
     

    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):
        for i in Z.neighbor[(self.y, self.x)]:
            if (self.y, self.x) not in self.neighbor:
                self.neighbor[(self.y, self.x)] = Z.neighbor[(self.y, self.x)]
        
    def choice(self, yx):
        v = []
        self.add_neighbor()
        
        for i in self.neighbor[yx]: 
            if not yx in self.visit:
                self.visit[yx] = 0
            v.append(i)  
              
        return random.choice((v))
        
    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)
        self.visit[node] += 1
   
    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(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 = []
        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()