1. Введение

Поиск может быть как сложным, так и простым. Когда не известна (или только частично известна) как сама цель, так и способ её достижения, случайность важна

Целью исследования статьи будет сравнение способов нахождения цели как подвижной (жёлтый объект), так и неподвижной.

Эти способы:

• Случайный поиск (красный объект)
• Случайный поиск с памятью (синий объект)
• Случайный поиск с памятью и иерархией (зелёный объект)
• Поиск первого маршрута (фиолетовый объект)
• Поиск короткого маршрута (коричневый объект)

На рис.1 эти объекты показаны. Полностью код программы выложен на github

2. Основная часть

2.1. Класс P – случайный поиск

Конструктор инициализирует атрибуты и переменные класса: главное окно, цвет, координату по y и x, счётчик, словарь посещённых, цель, словарь иерархии, словарь соседей. Метод init_3_dict заполняет три словаря. Метод show закрашивает клетку в нужный цвет. Метод update обновляет объект. Метод top_show создаёт окно верхнего уровня и показывает сколько шагов сделано до цели.

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]
        P.target = target
        self.count = 0
        
        self.visit = {}
        P.hierarchy = {}
        P.neighbor = {}
        
        self.init_3_dict(maps, ban)

В методе init_3_dict объявляется функция is_en, которая проверяет, чтобы координата не была забанина и не выходила за рамки карты.

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

В цикле в словарь посещённых с ключом координата записываем начальное значение ноль. В словарь иерархии с таким же ключом записываем иерархическое имя этой координаты. Потом заполняем словарь соседей, вызывая функцию is_en.

for y in range(len(maps)):
            for x in range(len(maps[0])):
                self.visit[(y,x)] = 0
                P.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))
                    
                P.neighbor[(y,x)] = n

Метод show закрашивает клетку с координатами y,x в нужный цвет.

def show(self, y, x, color):
        lb = Label(text=" ", background = color)
        lb.configure(text=P.hierarchy[(y,x)] )
        lb.grid(row=self.y, column=self.x, ipadx=10, ipady=5, padx=1, pady=1)

Метод move передвигает объект. В переменные y, x записываем координату соседа, которая выбрана случайно из списка соседей. Потом перерисовываем с новыми координатами.

Увеличиваем счётчик. Проверяем достигнута ли цель. Если цель достигнута, то в переменную класса J.disable записываем верно. Вызываем метод top_show().

def move(self):
        v = []
        for i in P.neighbor[(self.y, self.x)]:
            v.append(i)    
        y,x = random.choice(v)
        
        self.show(self.y, self.x, 'white')    
        self.y = y
        self.x = x
        self.show(y, x, self.color)
        
        self.count +=1
        
        if P.target == P.hierarchy[(self.y, self.x)]:
            J.disable = True
            self.top_show()

Метод update вызывает move и обновляет через каждые пол секунды.

def update(self):
        self.move()   
        self.root.after(500, self.update)

Метод top_show выводит результаты.

def top_show(self):
        top = Toplevel()
        lbt = Label(top, text=self.color + " = " + str(self.count))
        lbt.pack()
        top.mainloop()

2.2. Класс М – случайный поиск с памятью

Конструктор вызывает конструктор класса родителя и увеличивает значение той клетки поля, куда идём. Метод move передвигает объект. Метод choice возвращает координату, которую выбрал алгоритм случайного поиска с памятью.

В методе move вызываем метод choice. В остальном его работа аналогична методу родителя.

def move(self):
        yx = self.choice((self.y, self.x))

Метод choice перебирает координаты соседей и добавляет в список v кортежи. Первым элементом кортежа будет координата соседа, вторым — сколько раз она была посещена. Потом сортируем от маленького до большого. Перебираем все кортежи и в списке v оставляем только те, которые встречались столько раз, сколько записано в первом кортеже. Случайно выбираем любой из них.

def choice(self, yx):
        v = []
        for i in P.neighbor[yx]:
            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]

2.3. Класс N – случайный поиск с памятью и иерархией.

Метод choice отбирает те кортежи, которые больше всего совпадают с иерархическим именем цели. Если это совпадение одинаково, то отбираются те координаты, которые меньше всего были посещены.

Конструктор вызывает конструктор родителя и инициализирует атрибут coincidence количество посимвольных совпадений иерархического имени с целью.

def __init__(self, root, color, node, target, maps, ban):
        super().__init__(root, color, node, target, maps, ban)
        self.coincidence = 0

Метод choice в цикле записывает иерархическое имя текущей координаты соседа. Переменная r хранит количество совпадений этой переменной c целью. Если количество совпадений r больше, то coincidence перезаписывается. В этом случае в список d записывается кортеж (координаты, количество посещений) из списка v. Если же r равно coincidence, то в d добавляем кортеж из v.

def choice(self, yx):
        v = []
        for i in P.neighbor[yx]:
            v.append((i, self.visit[i]))
             
        d = []
        for l in v:
            c = P.hierarchy[l[0]]
            
            r = 0
            for i in range(len(P.target)):
                if c[i] == P.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]   

2.4. Класс К – поиск маршрута и поиск самого короткого маршрута.

Конструктор в переменную end записывает координаты цели. Если параметр short равен False, то вызываем поиск маршрута. Иначе находим самый короткий маршрут.

Метод find_path в маршрут добавляет текущую координату. Если цель достигнута, тогда возвращает маршрут. Перебираем всех соседей. Если соседа нет в path, тогда рекурсивно вызываем себя. И то, что метод возвращает, записываем в newpath. Первым найденным маршрутом будет newpath. Отличие метода find_short_path в том, что, если длина newpath больше или равна длине shortest, тогда shortest перезаписывается.

def find_path(self, node, end, path=[]):
        path = path + [node]
        if node == end:
            return path
            
        for v in P.neighbor[node]:
            if v not in path:
                newpath = self.find_path(v, end, path)
                if newpath: 
                    return newpath

2.5. Класс J – подвижная цель.

Объект класса J передвигается как класс P. Если переменная класса J.disable равна верно, то объект останавливается.

2.6. Функция main.

Создаём главное окно. В переменную target записываем иерархическое имя цели. В список ban записаны координаты запретных клеток. В списке maps – сама карта. В цикле рисуем карту. Создаём объекты класса. Потом вызываем функцию update, которая обновляет объекты.

3. Выводы

Были проведены пять экспериментов как для подвижной цели, так и для неподвижной.

Из таблицы 1 видно, что самый лучший алгоритм – самый короткий маршрут. Второй по эффективности — это случайный поиск с памятью и иерархией. Худший – случайный поиск.

Таблица 1. Неподвижная цель



В случае подвижной цели результаты иные. Худшими стали те алгоритмы, которые изначально рассчитывали маршрут до цели. В таблице 2 прочерк означает, что цель не достигнута. Brown оказался хуже, чем Violet. Хуже, поскольку у Violet траектория длиньше (шанс встретить подвижную цель больше). Самый лучший алгоритм при поиске подвижной цели — случайный поиск с памятью и иерархией. На втором месте — случайный поиск с памятью.

Таблица 2. Подвижная цель



Если неизвестно подвижна ли цель или нет, то лучше использовать алгоритм случайный поиск с памятью и иерархией либо просто случайный поиск с памятью.

4. Заключение

Случайность важна, если поиск цели происходит в условиях неизвестности. Поиск сокращается, если данные представлены иерархично. Память, разумеется, тоже ценна.