为什么我的路径与星形算法中的启发式函数方向相反？

Question

背景

我想实现一个A-Star算法，使用GUI进行用户输入，以设置开始和结束节点，并绘制障碍物。然而，我花了很多时间思考为什么算法不起作用

发行

路径与结束节点的方向相反，并到达矩阵的角点。例如，如果开始：2,2和结束：8,8，则路径将映射到原点：0,0，反之亦然

故障排除

我已经检查了我可能认为出错的所有领域，甚至参考了一篇媒体文章的源代码：A-Star Algorithm by Nicholas Swift

• 欧几里德距离不是负的
• 相邻节点不在边界之外
• 其他较小的故障排除

图中的障碍尚未实现，因为我试图在增加激励问题的复杂性之前获得正确映射的路径

我根本看不出我错在哪里。我来自Java背景，因此可能有一些基本的Python语法让我不知所措，让一切都崩溃了。如有任何建议，将不胜感激

源代码：

class Node:
    def __init__(self,x,y,nodeType):
        self.xPos = int(x)
        self.yPos = int(y)
        self.nodeType = str(nodeType)

        self.h = 0
        self.g = 0
        self.f = 0
    
    def __eq__(self,node):
        if((self.xPos == node.xPos) and (self.yPos == node.yPos)):
            return True
        else:
            return False
    
    def __str__(self):
        return "(" + str(self.xPos) + "," + str(self.yPos) + "," + self.nodeType + ")"




class Graph:
    def __init__(self,size,startX,startY,endX,endY):
        self.graph = [[Node(x,y,"open") for y in range(size)] for x in range(size)]
        self.graph[startX][startY].nodeType = "start"
        self.graph[endX][endY].nodeType = "end"
        self.startNode = self.graph[startX][startY]
        self.endNode = self.graph[endX][endY]
    
    def displayGraph(self):
        for x in range(len(self.graph)):
            for y in range(len(self.graph[x])):
                print(self.graph[x][y],end=" ")
            print("")

    def getAdj(self,node):
        adjNodes = []
        x = int(node.xPos)
        y = int(node.yPos)
        if(self.inRange(x,y+1)):
            adjNodes.append(self.graph[x][y+1])
        if(self.inRange(x+1,y+1)):
            adjNodes.append(self.graph[x+1][y+1])
        if(self.inRange(x+1,y)):
            adjNodes.append(self.graph[x+1][y])
        if(self.inRange(x+1,y-1)):
            adjNodes.append(self.graph[x+1][y-1])
        if(self.inRange(x,y-1)):
            adjNodes.append(self.graph[x][y-1])
        if(self.inRange(x-1,y-1)):
            adjNodes.append(self.graph[x-1][y-1])
        if(self.inRange(x-1,y)):
            adjNodes.append(self.graph[x-1][y])
        if(self.inRange(x-1,y+1)):
            adjNodes.append(self.graph[x-1][y+1])

        for node in adjNodes:
            print(node,end=" ")
        print("")

        return adjNodes

    
    def inRange(self,x,y):
        if(x > -1 and x < len(self.graph) and y > - 1 and y < len(self.graph[0])):
            return True
        else:
            return False
    
    def findShortestPath(self):
        openList = []
        closedList = []

        openList.append(self.startNode)
        count = 0

        while(len(openList) > 0):

            minNode = openList[0]
            minIndex = 0
            for i in range(len(openList)):
                if(minNode.f < openList[i].f):
                    minNode = openList[i]
                    minIndex = i
            
            openList.pop(minIndex)
            closedList.append(minNode)

            if(minNode == self.endNode):

                """
                Taken from article
                path = []
                current = minNode
                while current is not None:
                    path.append(current.position)
                    current = current.parent
                return path[::-1] # Return reversed path
                """
                return closedList


            adjNodes = self.getAdj(minNode)

            for node in adjNodes:
                
                for closedNode in closedList:
                    if(node == closedNode):
                        continue

                node.g = minNode.g + 1
                node.h = ((node.xPos - self.endNode.xPos)**2) + ((node.yPos - self.endNode.yPos)**2)
                node.f = node.h + node.g

                for openNode in openList:
                    if((node == openNode) and (node.g > openNode.g)):
                        continue
                
                openList.append(node)



class Driver:
    size = int(input("Enter the size of the graph: "))
    startX = int(input("Enter the x value of the start node: "))
    startY = int(input("Enter the y value of the start node: "))
    endX = int(input("Enter the x value of the end node: "))
    endY = int(input("Enter the y value of the end node: "))

    graph = Graph(size,startX,startY,endX,endY)
    graph.displayGraph()
    graph.findShortestPath()

循环在20次迭代时停止时的输出

Enter the size of the graph: 10
Enter the x value of the start node: 2
Enter the y value of the start node: 2
Enter the x value of the end node: 9
Enter the y value of the end node: 9
(0,0,open) (0,1,open) (0,2,open) (0,3,open) (0,4,open) (0,5,open) (0,6,open) (0,7,open) (0,8,open) (0,9,open) 
(1,0,open) (1,1,open) (1,2,open) (1,3,open) (1,4,open) (1,5,open) (1,6,open) (1,7,open) (1,8,open) (1,9,open) 
(2,0,open) (2,1,open) (2,2,start) (2,3,open) (2,4,open) (2,5,open) (2,6,open) (2,7,open) (2,8,open) (2,9,open) 
(3,0,open) (3,1,open) (3,2,open) (3,3,open) (3,4,open) (3,5,open) (3,6,open) (3,7,open) (3,8,open) (3,9,open) 
(4,0,open) (4,1,open) (4,2,open) (4,3,open) (4,4,open) (4,5,open) (4,6,open) (4,7,open) (4,8,open) (4,9,open) 
(5,0,open) (5,1,open) (5,2,open) (5,3,open) (5,4,open) (5,5,open) (5,6,open) (5,7,open) (5,8,open) (5,9,open) 
(6,0,open) (6,1,open) (6,2,open) (6,3,open) (6,4,open) (6,5,open) (6,6,open) (6,7,open) (6,8,open) (6,9,open) 
(7,0,open) (7,1,open) (7,2,open) (7,3,open) (7,4,open) (7,5,open) (7,6,open) (7,7,open) (7,8,open) (7,9,open) 
(8,0,open) (8,1,open) (8,2,open) (8,3,open) (8,4,open) (8,5,open) (8,6,open) (8,7,open) (8,8,open) (8,9,open) 
(9,0,open) (9,1,open) (9,2,open) (9,3,open) (9,4,open) (9,5,open) (9,6,open) (9,7,open) (9,8,open) (9,9,end) 

(2,3,open)
(3,3,open)
(3,2,open)
(3,1,open)
(2,1,open)
(1,1,open)
(1,2,open)
(1,3,open)

(1,2,open)
(2,2,start)
(2,1,open)
(2,0,open)
(1,0,open)
(0,0,open)
(0,1,open)
(0,2,open)

(0,1,open)
(1,1,open)
(1,0,open)

(1,1,open)
(2,1,open)
(2,0,open)
(0,0,open)
(0,1,open)

(0,1,open)
(1,1,open)
(1,0,open)

(0,2,open)
(1,2,open)
(1,1,open)
(1,0,open)
(0,0,open)

(0,1,open)
(1,1,open)
(1,0,open)

(0,2,open)
(1,2,open)
(1,1,open)
(1,0,open)
(0,0,open)

(0,1,open)
(1,1,open)
(1,0,open)

(1,1,open)
(2,1,open)
(2,0,open)
(0,0,open)
(0,1,open)

(0,1,open)
(1,1,open)
(1,0,open)

(0,2,open)
(1,2,open)
(1,1,open)
(1,0,open)
(0,0,open)

(0,1,open)
(1,1,open)
(1,0,open)

(0,2,open)
(1,2,open)
(1,1,open)
(1,0,open)
(0,0,open)

(0,1,open)
(1,1,open)
(1,0,open)

(1,1,open)
(2,1,open)
(2,0,open)
(0,0,open)
(0,1,open)

(0,1,open)
(1,1,open)
(1,0,open)

(1,1,open)
(2,1,open)
(2,0,open)
(0,0,open)
(0,1,open)

(0,1,open)
(1,1,open)
(1,0,open)

(0,2,open)
(1,2,open)
(1,1,open)
(1,0,open)
(0,0,open)

Answer 1

正如user@Ghoti所指出的，问题在于算法中存在一个简单的比较错误。如果代码中的当前比较语句位于adjNode列表中的第一个节点之上，则始终选中该节点

if(minNode.f < openList[i].f):
    minNode = openList[i]
    minIndex = i

相反，它很简单，只需翻转不平等性，以另一种方式进行比较。一个简单的初等代数错误。正确的比较应该是：minNode.f > openList[i].f