Вспоминаем алгоритм Дейкстры
Алгоритм Дейкстры один из наиболее популярных алгоритмов теории графов. Он используется для поиска кратчайшего пути между узлами на ориентированном графе. Мы начнем с исходного узла и известных длин ребер между узлами.
Сначала мы присваиваем значение расстояния от источника всем узлам. Узел s получает значение 0, потому что это источник; остальные получают значения для начала.
Наш интересующий узел это необработанный узел с наименьшим значением (показан серым), то есть s. Сначала мы ослабляем каждую смежную вершину до нашего интересующего узла, обновляя их значения до минимума их текущего значения или значения узла интереса плюс длину соединительного ребра
Узел s теперь завершен (черный), а его соседи a и b приняли новые значения. Новый интересующий узел b, поэтому мы повторяем процесс ослабления соседних узлов b и финализации значения кратчайшего пути для b.
Пройдя через каждый узел, мы в итоге получим график, показывающий кратчайшую длину пути от источника до каждого узла.
Наша финальная диаграмма после запуска алгоритма Дейкстры. Числа в каждом узле представляют кратчайшее возможное расстояние от исходного узла.
Концептуализация изображений лабиринта
Мы можем представить себе изображение как матрицу пикселей. Каждый пиксель (для простоты) имеет значение RGB 0,0,0 (черный) или 255,255,255 (белый). Наша цель создать кратчайший путь, который начинается на белом и не переходит на чёрные границы. Чтобы представить эту цель, мы можем рассматривать каждый пиксель как узел и рисовать ребра между соседними пикселями с длиной ребер, основанной на разнице значений RGB. Мы будем использовать формулу евклидова квадратного расстояния и добавим 0,1, чтобы гарантировать отсутствие длины пути 0 (требование для алгоритма Дейкстры):
Эта формула делает расстояние пересечения через границу лабиринта чрезмерно большим. Как мы видим, кратчайший путь от источника к месту назначения будет четко проходить вокруг барьера, а не через него.
Реализация
Мы можем использовать OpenCV, популярную библиотеку компьютерного зрения для Python, чтобы извлечь значения пикселей и показать наши изображения лабиринта. Давайте также определим координаты нашего начального и конечного местоположений, добавив точки в наш лабиринт
import cv2import matplotlib.pyplot as pltimport numpy as npimg = cv2.imread('maze.png') # read an image from a file usingcv2.circle(img,(5,220), 3, (255,0,0), -1) # add a circle at (5, 220)cv2.circle(img, (25,5), 3, (0,0,255), -1) # add a circle at (5,5)plt.figure(figsize=(7,7))plt.imshow(img) # show the imageplt.show()
Мы создаем класс Vertex, который поможет нам отслеживать координаты. Мы также хотим отслеживать родительский узел, чтобы мы могли восстановить весь путь, как только найдем значения расстояния.
class Vertex: def __init__(self,x_coord,y_coord): self.x=x_coord self.y=y_coord self.d=float('inf') #current distance from source node self.parent_x=None self.parent_y=None self.processed=False self.index_in_queue=None
Нам нужно создать матрицу вершин, представляющую двухмерное расположение пикселей на изображении. Это будет основой для алгоритма Дейкстры. Мы также поддерживаем очередь с минимальной кучей приоритетов для отслеживания необработанных узлов.
def find_shortest_path(img,src,dst): pq=[] #min-heap priority queue imagerows,imagecols=img.shape[0],img.shape[1] matrix = np.full((imagerows, imagecols), None) #access matrix elements by matrix[row][col] #fill matrix with vertices for r in range(imagerows): for c in range(imagecols): matrix[r][c]=Vertex(c,r) matrix[r][c].index_in_queue=len(pq) pq.append(matrix[r][c]) #set source distance value to 0 matrix[source_y][source_x].d=0 #maintain min-heap invariant (minimum d Vertex at list index 0) pq = bubble_up(pq, matrix[source_y][source_x].index_in_queue)
Нам нужно несколько вспомогательных функций, чтобы помочь найти ребра и длину ребер между вершинами:
#Implement euclidean squared distance formuladef get_distance(img,u,v): return 0.1 + (float(img[v][0])-float(img[u][0]))**2+(float(img[v][1])-float(img[u][1]))**2+(float(img[v][2])-float(img[u][2]))**2#Return neighbor directly above, below, right, and leftdef get_neighbors(mat,r,c): shape=mat.shape neighbors=[] #ensure neighbors are within image boundaries if r > 0 and not mat[r-1][c].processed: neighbors.append(mat[r-1][c]) if r < shape[0] - 1 and not mat[r+1][c].processed: neighbors.append(mat[r+1][c]) if c > 0 and not mat[r][c-1].processed: neighbors.append(mat[r][c-1]) if c < shape[1] - 1 and not mat[r][c+1].processed: neighbors.append(mat[r][c+1]) return neighbors
Теперь мы можем реализовать алгоритм Дейкстры и присвоить значения расстояния (d) всем вершинам пикселей в изображении лабиринта:
while len(pq) > 0: u=pq[0] #smallest-value unprocessed node #remove node of interest from the queue pq[0]=pq[-1] pq[0].index_in_queue=0 pq.pop() pq=bubble_down(pq,0) #min-heap function, see source code u.processed=True neighbors = get_neighbors(matrix,u.y,u.x) for v in neighbors: dist=get_distance(img,(u.y,u.x),(v.y,v.x)) if u.d + dist < v.d: v.d = u.d+dist v.parent_x=u.x #keep track of the shortest path v.parent_y=u.y idx=v.index_in_queue pq=bubble_down(pq,idx) pq=bubble_up(pq,idx)
Теперь мы можем вызвать функцию кратчайшего пути и нарисовать решение в нашем лабиринте:
img = cv2.imread('maze.png') # read an image from a file using opencv (cv2) libraryp = find_shortest_path(img, (25,5), (5,220))drawPath(img,p)plt.figure(figsize=(7,7))plt.imshow(img) # show the image on the screen plt.show()
Давайте попробуем другие лабиринты со всего Интернета.
Полный исходный код доступен на GitHub здесь.
Узнайте подробности, как получить востребованную профессию с нуля или Level Up по навыкам и зарплате, пройдя платные онлайн-курсы SkillFactory:
- Курс по Machine Learning (12 недель)
- Обучение профессии Data Science с нуля (12 месяцев)
- Профессия аналитика с любым стартовым уровнем (9 месяцев)
- Курс Python для веб-разработки (9 месяцев)
Читать еще
- Тренды в Data Scienсe 2020
- Data Science умерла. Да здравствует Business Science
- Крутые Data Scientist не тратят время на статистику
- Как стать Data Scientist без онлайн-курсов
- Шпаргалка по сортировке для Data Science
- Data Science для гуманитариев: что такое data
- Data Scienсe на стероидах: знакомство с Decision Intelligence
