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()
        
    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()