Понимание и применение эвристик при разработке алгоритмов
Эвристика - это приближение, которое мы используем, и не гарантируется, что оно будет оптимальным для достижения цели. В этой статье я подробно объясню на простом для понимания примере, как мы можем использовать эвристику для разработки алгоритмов. Поэтому я буду использовать алгоритм A-Star (A *), чтобы объяснить использование и реализацию эвристики на полном примере, который включает кратчайший путь.
Детерминированный подход
Детерминированные подходы гарантированно предоставят оптимальное решение. Например, алгоритм Дейкстры можно рассматривать как детерминированный алгоритм для получения кратчайшего пути между любыми двумя точками в графе с положительными весами ребер.
Алгоритм Дейкстры как детерминированный алгоритм
Алгоритм в его основной форме выглядит следующим образом.
function Dijkstra(Graph, Start)
vertex_set = {}
for each vertex v in Graph
dist[v] = INFINITY
parent[v] = NULL
dist[start] = 0
while vertex_set not empty
u = min dist vertex from vertex_set
remove u from vertex_set
for neighbour v of u
path = dist[u]+length(u,v)
if path < dist[v]
dist[v] = path
parent[v] = u
return parent, dist
Мы видим, что в начале алгоритма никакие сведения о целевом узле не учитываются. Следовательно, мы, по сути, выполняем исчерпывающий поиск кратчайших путей к каждой другой проходимой вершине графа. Представьте, что на графике изображена дорожная сеть вашей страны. Будет ли это масштабироваться до этого уровня? Оптимальная реализация алгоритма Дейкстры для очередей с минимальным приоритетом имеет временную сложность O (| V | + | E | log | V |).
Введение в алгоритм Дейкстры эвристики
Вместо того, чтобы полностью искать всех соседей исходной вершины, мы могли бы также выбрать соседей, которые МОГУТ дать нам более короткий путь к целевая вершина на графике. Слово МОЖЕТ важно, поскольку эвристика часто приводит к неоптимальным результатам.
Как мы можем угадать, может ли конкретный узел привести нас к более короткому пути?
Вот где приходит эвристика. Например, в случае дорожной сети мы можем предположить, что чем ближе выбранный нами перекресток, тем быстрее он может добраться до целевого города. Для этого мы можем использовать легкодоступную информацию GPS для вычисления не элитного, а приблизительного расстояния по воздуху между точками. Хотя это может быть неверно, учитывая, что вы можете видеть повороты и кольцевые развязки, мы можем быть уверены, что общее направление движения должно быть в сторону целевого города.
Сравнивая вышеприведенное предположение, вы можете заметить, что если бы мы выбрали алгоритм Дейкстры, мы также вычислили бы расстояния до целевых узлов, которые нигде не находятся в направлении намеченной цели. Надежная реализация самого известного алгоритма кратчайшего пути с эвристикой называется A * или алгоритм A-Star.
Алгоритм A-Star
Псевдокод будет выглядеть, как показано ниже. Подробнее читайте в wiki.
function AStar(start, end, heuristic=h)
open_set = {start}
closed_set = {}
# distance so far to node
distance = lookup_table(default=INFINITY)
# guess to the end
guess = lookup_table(default=INFINITY)
distance[start] = 0
guess[start] = h(start)
while open_set not empty
current = node with lowest guess from open_set
if current is goal: END
open_set.remove(current)
closed_set.add(current)
for neighbour of current
score = distance[current]+length(current,neighbour)
if score < guess[neighbour]
distance[neighbour] = score
parent[neighbour] = current
guess[neighbour] = distance[neighbour]+h(neighbour)
if neighbour not in closed_set
open_set.add(neighbour)
Уловка в приведенном выше коде заключается в том, что вам нужно сканировать массив, чтобы получить ближайшего соседа к целевому узлу. Однако, если вы будете хранить соседей в минимальной куче, используя расстояние до целевого узла в качестве ключа, вы можете сделать это за O (1) времени. Довольно замечательно, как мы можем улучшить алгоритмы, зная структуры данных (Прочтите эту статью, чтобы узнать больше). Давайте посмотрим на реализацию этого алгоритма на Python.
Реализация A-Star на Python
Я буду использовать следующий импорт в моей реализации алгоритма.
import numpy as np import matplotlib.pyplot as plt # for visualizations import matplotlib.cm as cm # for visualizations from collections import defaultdict import networkx as nx # storing the graph structure import heapq # pythons heap implementation
Я создам класс-оболочку, содержащий вершины (узлы) графа, чтобы я мог сразу использовать их в heapq реализации python. Я отменяю функцию __lt__ оболочки, чтобы heapq использовал свой атрибут val для элементов heappush и heappop. Это val соответствует расстоянию до целевого узла.
class NodeWrap:
def __init__(self, nid, dist_to_end):
self.nid = nid
self.val = dist_to_end
def __lt__(self, other):
return self.val < other.val
Я использую следующий код для отслеживания кратчайшего пути после запуска алгоритма и наличия родителей вершин, которые мы пересекаем.
def trace_path(parent_map, end):
node = end
path = []
while (node in parent_map):
path.append(node)
node = parent_map[node]
return path[::-1]
Реализация графа и матрицы визуализации
Поскольку это сделано в учебных целях, я подумал, что было бы очень интересно посмотреть, как алгоритм работает в реальном времени. Поэтому давайте смоделируем нашу проблему, как показано ниже. Представьте, что у нас есть 2D-ландшафт, и мы хотим попасть в верхний правый угол из нижнего левого угла. У нас есть препятствие на пути, показанное черным.
Я заполняю эту местность с помощью следующего кода. Это простая матрица размером 50x50. Изображение представляет собой матрицу с 3 каналами для RGB. Таким образом, препятствия - это просто индексы с [0, 0, 0].
mat = np.zeros((50, 50, 3), dtype=np.float32)
for x in range(50):
for y in range(50):
mat[x, y, 0] = 0.95
mat[x, y, 1] = 0.95
mat[x, y, 2] = 0.95
g.add_node("{},{}".format(x,y), x=x, y=y)
# end
mat[49, 0, 0] = .0
mat[49, 0, 1] = .0
mat[49, 0, 2] = 0.8
# start
mat[0, 49, 0] = .0
mat[0, 49, 1] = 0.8
mat[0, 49, 2] = .0
for x in range(20, 50):
for y in range(20, 50):
if x>y+5:
mat[x, y, 0] = .0
mat[x, y, 1] = .0
mat[x, y, 2] = .0
for x in range(0, 30):
for y in range(0, 30):
if x<y-5:
mat[x, y, 0] = .0
mat[x, y, 1] = .0
mat[x, y, 2] = .0
for x in range(26, 30):
for y in range(10, 20):
mat[x, y, 0] = .0
mat[x, y, 1] = .0
mat[x, y, 2] = .0
mat_copy = np.copy(mat)
Создание графика NetworkX
Поскольку операции с графами лучше всего выполнять на графах, таких как структура данных с функциями графа, давайте перенесем нашу местность в граф. Каждый пиксель будет узлом / вершиной на нашем графике. Из каждого узла / вершины мы можем пройти во всех 8 направлениях, как ферзь на шахматной доске. В нашем случае ребра существуют, если доступный обратимый сосед не черный.
g = nx.Graph()
def is_black(arr):
return sum(arr) == 0
for x in range(50):
for y in range(50):
xi = g.nodes["{},{}".format(x,y)]['x']
yi = g.nodes["{},{}".format(x,y)]['y']
for xj in range(xi-1, xi+2):
for yj in range(yi-1, yi+2):
if xi==xj and yi==yj or \
xj<0 or yj<0 or \
xj>49 or yj>49:
continue
# if black not a neighbour
if is_black(mat[xi, yi]) \
or is_black(mat[xj, yj]):
continue
g.add_edge("{},{}".format(xi,yi), "{}, \
{}".format(xj,yj))
Реализация алгоритма с контрольными точками
Теперь, когда я подготовил свой график, я хочу реализовать и запустить A-Star. В то же время, когда алгоритм ищет соседей, я хочу сделать снимок исходного 2D-ландшафта для последующей визуализации. Полный код Python для этого выглядит следующим образом. Здесь я использую евклидово расстояние в качестве эвристики расстояния, которое является предположением от любого узла до цели.
def store_image(world, node, i):
global mat
x = world.nodes[node]['x']
y = world.nodes[node]['y']
mat[x, y, 0] = 1
mat[x, y, 1] = .5
mat[x, y, 2] = .0
fig = plt.figure(figsize=(10, 10))
plt.imshow(mat)
plt.axis('off')
plt.savefig("im-{}.png".format(i))
plt.close()
def euclidean_dist(world, node1, node2):
x1 = world.nodes[node1]['x']
x2 = world.nodes[node2]['x']
y1 = world.nodes[node1]['y']
y2 = world.nodes[node2]['y']
return ((x1-x2)**2 + (y1-y2)**2)**.5
def a_star(world, start, end):
stepper = 1
open_set = []
close_set = set()
parent_map = {}
start_node = NodeWrap(start, 0)
heapq.heappush(open_set, start_node)
store_image(world, start, stepper)
stepper += 1
cost_to_reach_node = defaultdict(lambda: float('inf'))
cost_to_reach_node[start] = 0
guess_to_destination = defaultdict(lambda: float('inf'))
guess_to_destination[start] = euclidean_dist(world, start, end)
while len(open_set) > 0:
current = heapq.heappop(open_set)
if current.nid == end:
path = trace_path(parent_map, end)
return path
close_set.add(current.nid)
for neighbor in world.neighbors(current.nid):
tentative_score = cost_to_reach_node[current.nid] + \
euclidean_dist(world, current.nid, neighbor)
if tentative_score < cost_to_reach_node[neighbor]:
parent_map[neighbor] = current.nid
cost_to_reach_node[neighbor] = tentative_score
guess_to_destination[neighbor] =
cost_to_reach_node[neighbor] + \
euclidean_dist(world, neighbor, end)
if neighbor not in close_set:
neighbor_node = NodeWrap(neighbor,
euclidean_dist(world, neighbor, end))
heapq.heappush(open_set, neighbor_node)
store_image(world, neighbor, stepper)
stepper += 1
Мы можем запустить вышеуказанный алгоритм, используя следующий фрагмент бегуна. Обратите внимание, что я использую копию матрицы, поскольку внутри алгоритма мы обновляем исходный объект mat.
path = a_star(g, "49,0", "0,49")
# trace path and visualize on terrain
for node in path:
x = g.nodes[node]['x']
y = g.nodes[node]['y']
mat_copy[x, y, 0] = 1
mat_copy[x, y, 1] = .5
mat_copy[x, y, 2] = .0
fig = plt.figure(figsize=(10, 10))
plt.imshow(mat_copy)
plt.axis('off')
Окончательное выполнение и создание GIF
Красота становится более заметной, когда мы видим, как все происходит в анимации. Поэтому я объединю все созданные мной изображения, чтобы сформировать великолепный GIF. Я использую следующий код для создания GIF из моих снимков.
import imageio
import glob
anim_file = 'out.gif'
with imageio.get_writer(anim_file, mode='I', fps=10) as writer:
filenames = glob.glob('im-*.png')
filenames = sorted(filenames, \
key=lambda x: int(x.replace("im-", "").replace(".png", "")))
last = -1
for i,filename in enumerate(filenames):
frame = 2*(i**0.5)
if round(frame) > round(last):
last = frame
else:
continue
image = imageio.imread(filename)
writer.append_data(image)
image = imageio.imread(filename)
writer.append_data(image)
image = imageio.imread(filename)
writer.append_data(image)
image = imageio.imread(filename)
writer.append_data(image)
После этого у нас будет следующая анимация.
Заключение
Мы ясно видим, что обход происходит в очень узком пространстве поиска. Это значительно ускоряет поиск, и нам не нужно выполнять исчерпывающий поиск по всем узлам.
В гораздо более крупных графах используются такие методы, как маркировка узлов и индексация, так что графу не нужно будет полностью загружаться в оперативную память. Надеюсь, что в будущем напишу больше статей по этой теме. А пока я надеюсь, что вам понравилось читать эту статью. Полную записную книжку можно посмотреть здесь.
