Алгоритм A * в python испытывает проблемы с созданием окончательного пути

Полный теперь рабочий код: https://docs.google.com/document/d/1j1BLe4L735nmXWR0Vnj3TeHumzI5x7Ea5yWJSc5j-8w/edit

Я попытался закодировать алгоритм поиска пути A*, и мне удалось правильно расширить его, используя затраты g и h.

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

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

Я сделал это, используя pygame в python.

Вот соответствующая часть моего кода (большая часть взаимодействия с pygame исключена):

BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
PURPLE = (238, 130, 238)
pygame.init()
width = 1200
hight = 900
startNode = None
endNode = None
SCREEN = pygame.display.set_mode((width, hight), pygame.DOUBLEBUF)

class node:

   def __init__(self, pos, h_cost, g_cost, f_cost, Color):
       self.x = pos[0]
       self.y = pos[1]
       self.parent = None
       self.f_cost = f_cost
       self.g_cost = g_cost
       self.h_cost = h_cost
       self.pos = pos
       self.Color = Color

   def TraceBack(self):
       if self.parent != None:
           self.parent.Color = "BLUE"
           self.parent.TraceBack()

   def calG_cost(self, startNode):
       self.g_cost = math.sqrt((self.x - startNode.x) ** 2 + abs(self.y - startNode.y) ** 2)

   def calH_cost(self,endNode):
       self.h_cost = math.sqrt((self.x - endNode.x) ** 2 + abs(self.y - endNode.y) ** 2)

   def calF_cost(self,endNode,startNode):
       self.calG_cost(startNode)
       self.calH_cost(endNode)
       self.f_cost = self.g_cost + self.h_cost

grid = []

def checkIfDone(endNode):
   x = endNode.x
   y = endNode.y
   if grid[x + 1][y].Color == "PURPLE":
       return True

   if grid[x + 1][y + 1].Color == "PURPLE":
       return True
   if grid[x + 1][y - 1].Color == "PURPLE":
       return True
   if  grid[x - 1][y - 1].Color == "PURPLE":
       return True

   if grid[x - 1][y].Color == "PURPLE":
       return True

   if grid[x - 1][y + 1].Color == "PURPLE":
       return True

   if grid[x][y + 1].Color == "PURPLE":
       return True

   if grid[x][y - 1].Color == "PURPLE":
       return True
   return False



def findLowestFCost():
   lowest = math.inf
   lowestNode = None
   for row in grid:
       for node in row:
           if node.Color == "GREEN" and node.f_cost < lowest:
               lowest = node.f_cost
               lowestNode = node

   return lowestNode

def GenerateGrid():
   for x in range(100):
       grid.append([])
       for y in range(100):
           grid[x].append("")

   for y in range(len(grid[0]) ):
       for x in range(len(grid) ):
           grid[x][y] = node((x, y), 0, 0, 0, "")


def checkFound(parent):
   x = parent.x
   y = parent.y
   try:
       if grid[x + 1][y].Color == "RED": return True

       if grid[x + 1][y + 1].Color == "RED": return True

       if grid[x + 1][y - 1].Color == "RED": return True

       if grid[x - 1][y - 1].Color == "RED": return True

       if grid[x - 1][y].Color == "RED": return True

       if grid[x - 1][y + 1].Color == "RED": return True

       if grid[x][y + 1].Color == "RED": return True

       if grid[x][y - 1].Color == "RED": return True

   except:
       pass


def expandParent(parent):
   x = parent.x
   y = parent.y
   if grid[x + 1][y].Color == "" or grid[x + 1][y].Color == "GREEN":
       grid[x + 1][y].Color = "GREEN"

       if grid[x + 1][y].parent == None:
           grid[x + 1][y].parent = parent

       elif parent.f_cost < grid[x + 1][y].parent.f_cost:
           grid[x + 1][y].parent = parent

   if grid[x + 1][y + 1].Color == "" or grid[x + 1][y + 1].Color == "GREEN":
       grid[x + 1][y + 1].Color = "GREEN"

       if grid[x + 1][y + 1].parent == None:
           grid[x + 1][y + 1].parent = parent

       elif parent.f_cost < grid[x + 1][y + 1].parent.f_cost:
           grid[x + 1][y + 1].parent = parent

   if grid[x + 1][y - 1].Color == "" or grid[x + 1][y - 1].Color == "GREEN":
       grid[x + 1][y - 1].Color = "GREEN"

       if grid[x + 1][y - 1].parent == None:
           grid[x + 1][y - 1].parent = parent

       elif parent.f_cost < grid[x + 1][y - 1].parent.f_cost:
           grid[x + 1][y - 1].parent = parent

   if grid[x - 1][y - 1].Color == "" or grid[x - 1][y - 1].Color == "GREEN":
       grid[x - 1][y - 1].Color = "GREEN"

       if grid[x - 1][y - 1].parent == None:
           grid[x - 1][y - 1].parent = parent

       elif parent.f_cost < grid[x - 1][y - 1].parent.f_cost:
           grid[x - 1][y - 1].parent = parent

   if grid[x - 1][y].Color == "" or grid[x - 1][y].Color == "GREEN":
       grid[x - 1][y].Color = "GREEN"

       if grid[x - 1][y].parent == None:
           grid[x - 1][y].parent = parent

       elif parent.f_cost < grid[x - 1][y].parent.f_cost:
           grid[x - 1][y].parent = parent

   if grid[x - 1][y + 1].Color == "" or grid[x - 1][y + 1].Color == "GREEN":
       grid[x - 1][y + 1].Color = "GREEN"

       if grid[x - 1][y + 1].parent == None:
           grid[x - 1][y + 1].parent = parent

       elif parent.f_cost < grid[x - 1][y + 1].parent.f_cost:
           grid[x - 1][y + 1].parent = parent

   if grid[x][y + 1].Color == "" or grid[x][y + 1].Color == "GREEN":
       grid[x][y + 1].Color = "GREEN"

       if grid[x][y + 1].parent == None:
           grid[x][y + 1].parent = parent

       elif parent.f_cost < grid[x][y + 1].parent.f_cost:
           grid[x][y + 1].parent = parent

   if grid[x][y - 1].Color == "" or grid[x][y - 1].Color == "GREEN":
       grid[x][y - 1].Color = "GREEN"

       if grid[x][y - 1].parent == None:
           grid[x][y - 1].parent = parent

       elif parent.f_cost < grid[x][y - 1].parent.f_cost:
           grid[x][y - 1].parent = parent

   parent.Color = "PURPLE"

Красный — конечный узел, синий — конечный путь, фиолетовый — родительский узел. Я не вижу начальный узел, так как он перезаписывается. Когда-нибудь исправлю:

Алгоритм A * в python испытывает проблемы с созданием окончательного пути

Здесь сработало лучше:

Алгоритм A * в python испытывает проблемы с созданием окончательного пути

Я не вижу кода алгоритма A*. Пожалуйста, предоставьте код, с помощью которого можно воспроизвести проблему. Алгоритм A* гарантирует кратчайший путь, когда эвристическая функция допустима. Поскольку вы не предоставили ни реализацию поиска A*, ни эвристическую функцию, мы не можем сказать вам, почему она у вас не работает.

— 09.04.2023 10:34

Извините, вот ссылка на код Google Docs docs.google.com/document/d/…

— 09.04.2023 11:49

Пожалуйста, не публикуйте ссылку на необходимую информацию для вопроса. Вместо этого включите его в свой вопрос (по крайней мере, необходимый код, а не то, что не имеет отношения к вопросу).

— 09.04.2023 13:08

Хорошо, я добавил это для вас.

— 09.04.2023 15:11

python algorithm path-finding

08.04.2023 17:56

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это

Советы по эффективной веб-разработке с помощью Python

Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.

Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Одна из основных проблем заключается в том, как вы рассчитываете 𝑔-стоимость:

   def calG_cost(self, startNode):
       self.g_cost = math.sqrt((self.x - startNode.x) ** 2 + abs(self.y - startNode.y) ** 2)

Это вычисляет расстояние от начального узла до текущего узла «по прямой», но 𝑔 должен отражать фактический пройденный путь. Как правило, мы не можем знать это только по начальному узлу и текущему узлу. Это должно накапливаться постепенно по мере расширения узлов, а следующий шаг добавляется к стоимости 𝑔.

Другая проблема заключается в том, что findLowestFCost неэффективен: ему нужно посетить каждую ячейку сетки. Алгоритм A* разработан для использования с приоритетной очередью для этой цели.

expandParent имеет очень похожий код, который повторяется несколько раз. Это можно сделать лучше. Поскольку вы уже используете класс Node, почему бы не зарегистрировать соседей каждого узла в атрибуте neighbors. Таким образом, вы можете повторять эту neighbors коллекцию в цикле.

Это то, что я сделал в следующем решении. Обратите внимание, что он текстовый, интеграции с pygame нет.

from heapq import heappop, heappush

DIAGDIST = 2**0.5
# Define meaning of letters
WALL = "#"
START = "y"
END = "r"
NEW = "."
QUEUED = "?"
VISITED = ","
ONPATH = "B"

class Node:
    def __init__(self, pos, *neighbors):
        self.x, self.y = pos
        self.pos = pos
        self.color = NEW
        self.parent = None
        self.f_cost = self.g_cost = float("inf")
        # Define neighbor bi-directional relations 
        self.neighbors = set()
        for neighbor in neighbors:
            if neighbor:
                self.neighbors.add(neighbor)
                neighbor.neighbors.add(self)

    def minDistance(self, other):
        # minimum distance with legal steps when there would be no walls
        dx = abs(self.x - other.x)
        dy = abs(self.y - other.y)
        diag = min(dx, dy)
        straight = max(dx, dy) - diag
        return diag * DIAGDIST + straight

    # Make Node instances comparable; for use by a heap
    def __lt__(self, other):
        return (self.f_cost - other.f_cost or self.x - other.x or self.y - other.y) < 0
    
    def traceBack(self):
        node = self
        while node:
            node.color = ONPATH
            node = node.parent



class Maze:
    def __init__(self, pattern):
        pattern = pattern.replace(" ", "")  # Remove intermediate spaces
        lines = pattern.strip().splitlines()
        row = [None] * len(lines[0])
        self.startNode = self.endNode = None
        self.grid = []
        for x, line in enumerate(lines):
            left = None
            # Create a row of Nodes that are immediately connected to previously created neighbors
            #   Don't create Nodes for Walls.
            row = [left := Node((x, y), left, *row[max(0, y-1):y+2]) if ch != WALL else None 
                   for y, ch in enumerate(line)]
            self.grid.append(row)
            if not self.startNode:
                self.startNode = next((node for node, ch in zip(row, line) if ch == START), None)
            if not self.endNode:
                self.endNode = next((node for node, ch in zip(row, line) if ch == END), None)
    
    def __str__(self):
        return "\n".join([
            " ".join(node.color if node else WALL for node in row)
            for row in self.grid
        ])


    def aStarSearch(self):
        self.startNode.g_cost = 0
        self.startNode.f_cost = self.startNode.minDistance(self.endNode)
        heap = [self.startNode]
        while heap:
            node = heappop(heap)
            if node == self.endNode:  # found target
                node.traceBack()
                # Restore indications of start/end nodes
                self.startNode.color = "y"
                self.endNode.color = "r"
                return
            if node.color != VISITED:
                node.color = VISITED
                for neighbor in node.neighbors:
                    if neighbor.color != VISITED:
                        g_cost = node.g_cost + node.minDistance(neighbor)
                        if g_cost < neighbor.g_cost:
                            h_cost = neighbor.minDistance(self.endNode)
                            neighbor.g_cost = g_cost
                            neighbor.f_cost = g_cost + h_cost
                            neighbor.parent = node
                            neighbor.color = QUEUED
                            heappush(heap, neighbor)
            
            
# Example run (text-based, no pygame)
maze = Maze("""
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . # . . . . . . . . . . . . . . . . . . . . . . . .
. . . . # . . . . . . . . y . . . . . . . . . . . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # # # # # # # # # # # # # # # # # # # # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . . . . . . . . r . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
""")

maze.aStarSearch()
print(maze)

Это выводит:

. . ? ? , , , , , , , , , , , , , , , , , , ? ? . . . . .
. ? ? , , , , , , , , , , , , , , , , , , , , ? ? . . . .
? ? , , , , , , , , , , , , , , , , , , , , , , ? ? . . .
? , , , B B , , , , , , , , , , , , , , , , , , , ? ? . .
? , , B # , B , , , , , , , , , , , , , , , , , , , ? ? .
, , , B # , , B B B B B B y , , , , , , , , , , , , , ? .
, , , B # , , , , , , , , , , , , , , , , , , # , , , ? ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , , ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , , ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , , ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , , ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , , ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , ? ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , ? .
, , , B # # # # # # # # # # # # # # # # # # # # , , ? ? .
, , , B # . . . . . . . . . . . . . . . . . . # , , ? . .
, , , B # . . . . . . . . . . . . . . . . . . # , , ? . .
? , , B # . . . . . . . . . . . . . . . . . . # , ? ? . .
? , , B # . . . . . . . . . . . . . . . . . . # , ? . . .
? , , B # . . . . . . . . . . . . . . . . . . # ? ? . . .
? ? , B # . . . . . . . . . . . . . . . . . . # . . . . .
. ? , B # . . . . . . . . . . . . . . . . . . # . . . . .
. ? ? B # . . . . . . . . . . . . . . . . . . # . . . . .
. . ? B # . . . . . . . . . . . . . . . . . . # . . . . .
. . ? B # ? ? ? ? ? ? ? . . . . . . . . . . . # . . . . .
. . ? ? B B B B B B B r . . . . . . . . . . . . . . . . .
. . . ? ? ? ? ? ? ? ? ? . . . . . . . . . . . . . . . . .

Большое спасибо за эту помощь, я наконец заработал! Вы были правы, это была стоимость g, которая была неправильной. Кроме того, когда я исправлял это, я сделал много улучшений эффективности. Весь новый код находится в документе Google, если вам интересно. Спасибо!

— 09.04.2023 19:27

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

— 09.04.2023 19:41

09.04.2023 15:25