时间戳

首页 > 解决方案 > 需要帮助破解python中的A*（A星）算法

python - 需要帮助破解python中的A*（A星）算法

问题描述

import math
import heapq

class Node:
    def __init__(self, location, parent, pathCost, goalLocation):
        self.location = location
        self.parent = parent
        self.g = pathCost
        if not isinstance(parent, Node):
            self.pathValue = pathCost
        else:
            self.pathValue = parent.g + pathCost
        self.h = math.sqrt((location[0] - goalLocation[0]) ** 2 + (location[1] - goalLocation[1]) ** 2)
        self.f = self.g + self.h

    def __eq__(self, other):
        if self.f == other.f:
            return True
        else:
            return False

    def __lt__(self, other):
        if self.f <= other.f:
            return True
        else:
            return False

    def __str__(self):
        return "Location: [" + str(self.location[0]) + "," + str(self.location[1]) + "] | MoveValue:" + str(self.g)

    def __repr__(self):
        return "Location: [" + str(self.location[0]) + "," + str(self.location[1]) + "] | MoveValue:" + str(self.g)

def getNeighbors(location, grid):
    neighbors = []
    if location[1] != 0 and grid[location[1] - 1][location[0]] != 0:
        neighbors.append([location[0], location[1] - 1])
    if location[0] != 0 and grid[location[1]][location[0] - 1] != 0:
        neighbors.append([location[0] - 1, location[1]])
    if location[1] != len(grid[0]) - 1 and grid[location[1] + 1][location[0]] != 0:
        neighbors.append([location[0], location[1] + 1])
    if location[0] != len(grid[0]) - 1 and grid[location[1]][location[0] + 1] != 0:
        neighbors.append([location[0] + 1, location[1]])
    return neighbors

def expandNode(node, grid, clist, olist, goalLocation):
    neighbors = getNeighbors(node.location, grid)
    #print(neighbors)
    for n in neighbors:
        child = Node(n, node, grid[n[1]][n[0]], goalLocation)
        if child in olist:
            if child.g < node.g:
                heapq.heappush(olist, child)
            if child in clist:
                clist.remove(child)
        elif not child in clist:
            heapq.heappush(olist, child)

grid = [[0, 2, 1, 3], #the top right is [3,0] the starting location
        [1, 1, 1, 0],
        [0, 4, 1, 3],
        [1, 1, 1, 1]] #the bottom left is [0,3] the goal location

goalLocation = [0, 3]
startLocation = [3, 0]

firstNode = Node(startLocation, 0, grid[startLocation[1]][startLocation[0]], goalLocation)
olist, clist = [], []
heapq.heappush(olist, firstNode)

for i in range(6):
    node = heapq.heappop(olist)
    print(node)
    print(str(i) + "| Open list: " + str(olist))
    print(str(i) + "| Closed list: " + str(clist))
    if node.location == goalLocation:
        print("Found Goal")
        break
    clist.append(node)
    expandNode(node, grid, clist, olist, goalLocation)

我一直在尝试在 python 中创建一个可以遍历二维列表的简单版本的 A* 算法。我相信算法本身是有效的，但由于某种原因，它不会为我的网格中的位置 [2, 2] 创建 Node 对象。因此，可能无法找到最佳解决方案。如果有人可以看到我遗漏的逻辑错误，或者可以指出算法不正确的原因。

目前，它打印出：

Location: [3,0] | MoveValue:3
0| Open list: []
0| Closed list: []
Location: [2,0] | MoveValue:1
1| Open list: []
1| Closed list: [Location: [3,0] | MoveValue:3]
Location: [2,1] | MoveValue:1
2| Open list: [Location: [1,0] | MoveValue:2]
2| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1]
Location: [1,1] | MoveValue:1
3| Open list: [Location: [1,0] | MoveValue:2]
3| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1, Location: [2,1] | MoveValue:1]s
Location: [0,1] | MoveValue:1
4| Open list: [Location: [1,0] | MoveValue:2, Location: [1,2] | MoveValue:4]
4| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1, Location: [2,1] | MoveValue:1, Location: [1,1] | MoveValue:1]
Location: [1,0] | MoveValue:2
5| Open list: [Location: [1,2] | MoveValue:4]
5| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1, Location: [2,1] | MoveValue:1, Location: [1,1] | MoveValue:1, Location: [0,1] | MoveValue:1]

标签： pythonalgorithma-star

解决方案

代码和算法存在几个问题，我将尝试从最严重到最不严重的顺序列出它们：

  1. self.h = math.sqrt((location[0] - goalLocation[0]) ** 2 + (location[1] - goalLocation[1]) ** 2)- 这是大多数问题的原因。要使 A* 搜索产生正确的输出，您的启发式算法h需要是可容许的，这意味着它永远不会高估达到目标的成本。您的成本函数是顶点权重的总和，因此列表索引上的欧几里德距离不是可接受的启发式方法。您可以设置h为 0（这将导致 A* 成为 Dijkstra 算法）或找到图形的特殊属性以获得一致的启发式。

child = Node(n, node, grid[n[1]][n[0]], goalLocation)
if child in olist:

这里的主要问题是相等测试和in语句。首先，节点的相等性（用于成员资格测试）应该基于图坐标，而不是现在的距离。您可能需要将元组传递(f_value, node)到最小堆中，而不是以__eq__一种搞乱区分测试的方式进行定义。此外，使用 aset而不是列表，否则 A* 的运行时间会变得更糟。

  1. for i in range(6):应该是while olist；目前尚不清楚为什么探索的最大节点数硬编码为 6。
  2. 中的第四个 if 语句getNeighbors应该以 开头if location[0] != len(grid) - 1，尽管一旦矩阵不是正方形并且得到IndexError. 我还将再次建议找到一种方法来避免索引顺序与 Python 的默认顺序相反，因为这些类型的细微错误变得更加常见且更难捕获。
  3. 我不熟悉A*您尝试实现的版本或您正在使用的参考，但我会仔细检查循环是否expandNode与该参考匹配。我不确定封闭列表的目的是什么，或者这些条件背后的逻辑，所以我无法评论它们的正确性。

推荐阅读