Способы нахождения цели. Роль случайности

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. Заключение

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