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. Заключение
Случайность важна, если поиск цели происходит в условиях неизвестности. Поиск сокращается, если данные представлены иерархично. Память, разумеется, тоже ценна.
