Русский
Русский
English
Статистика
Реклама

Перевод - recovery mode Учебный проект на Python алгоритм Дейкстры, OpenCV и UI ( часть 1)

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

Вспоминаем алгоритм Дейкстры


Алгоритм Дейкстры один из наиболее популярных алгоритмов теории графов. Он используется для поиска кратчайшего пути между узлами на ориентированном графе. Мы начнем с исходного узла и известных длин ребер между узлами.

Сначала мы присваиваем значение расстояния от источника всем узлам. Узел s получает значение 0, потому что это источник; остальные получают значения для начала.

image

Наш интересующий узел это необработанный узел с наименьшим значением (показан серым), то есть s. Сначала мы ослабляем каждую смежную вершину до нашего интересующего узла, обновляя их значения до минимума их текущего значения или значения узла интереса плюс длину соединительного ребра

image

Узел s теперь завершен (черный), а его соседи a и b приняли новые значения. Новый интересующий узел b, поэтому мы повторяем процесс ослабления соседних узлов b и финализации значения кратчайшего пути для b.

image

Пройдя через каждый узел, мы в итоге получим график, показывающий кратчайшую длину пути от источника до каждого узла.

image

image

image

Наша финальная диаграмма после запуска алгоритма Дейкстры. Числа в каждом узле представляют кратчайшее возможное расстояние от исходного узла.

Концептуализация изображений лабиринта


image

Мы можем представить себе изображение как матрицу пикселей. Каждый пиксель (для простоты) имеет значение RGB 0,0,0 (черный) или 255,255,255 (белый). Наша цель создать кратчайший путь, который начинается на белом и не переходит на чёрные границы. Чтобы представить эту цель, мы можем рассматривать каждый пиксель как узел и рисовать ребра между соседними пикселями с длиной ребер, основанной на разнице значений RGB. Мы будем использовать формулу евклидова квадратного расстояния и добавим 0,1, чтобы гарантировать отсутствие длины пути 0 (требование для алгоритма Дейкстры):

image

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

image

Реализация


Мы можем использовать 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()


image


Мы создаем класс 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()


image

image

Давайте попробуем другие лабиринты со всего Интернета.

image

image

image

image

Полный исходный код доступен на GitHub здесь.

image

Узнайте подробности, как получить востребованную профессию с нуля или Level Up по навыкам и зарплате, пройдя платные онлайн-курсы SkillFactory:



Читать еще


Источник: habr.com
К списку статей
Опубликовано: 02.07.2020 20:17:59
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Блог компании skillfactory

Python

Алгоритмы

Программирование

Учебный процесс в it

Учебный процесс

Категории

Последние комментарии

© 2006-2020, personeltest.ru