为什么我的路径与 A Star 算法中的启发式函数的方向相反？
Why is my path moving in the opposite direction of the heuristic functions in A Star Algorithm?
背景
我想实现一个带有 GUI 的 A-Star 算法，供用户输入以设置开始和结束节点，并绘制障碍物。但是，我花了很多时间思考为什么算法不起作用。
问题
路径与结束节点相反，到达矩阵的一角。例如，如果开始：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)
正如用户@Ghoti 所指出的，问题是算法中的一个简单比较错误。使用上面代码中的当前比较语句，始终选择 adjNode 列表中的第一个节点。
if(minNode.f < openList[i].f):
minNode = openList[i]
minIndex = i
相反，翻转不等式来比较另一种方式很简单。一个简单的初等代数错误。正确的比较是：minNode.f > openList[i].f
背景
我想实现一个带有 GUI 的 A-Star 算法，供用户输入以设置开始和结束节点，并绘制障碍物。但是，我花了很多时间思考为什么算法不起作用。
问题
路径与结束节点相反，到达矩阵的一角。例如，如果开始：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)
正如用户@Ghoti 所指出的，问题是算法中的一个简单比较错误。使用上面代码中的当前比较语句，始终选择 adjNode 列表中的第一个节点。
if(minNode.f < openList[i].f):
minNode = openList[i]
minIndex = i
相反，翻转不等式来比较另一种方式很简单。一个简单的初等代数错误。正确的比较是：minNode.f > openList[i].f