如何为 a* 算法的路径中的所有值添加无穷大

Question

我正在遵循这个伪代码，尝试使用 python 中的 a* 算法找到迷宫的最佳路径。

迷宫将会是这样的。这是一个二维数组，您只能在 x 是墙的零处导航： 你有一个入口和一个出口。

xxx0xx
xx00x0
xx0000
xxxx0x

我最大的问题是理解如何设置无穷大来计算距离成本。

看着伪代码，我虽然在做这样的事情。但是当我尝试获取下一个元素

g_score = {dist: float("inf") for dist in range(len(array))}

伪代码的无穷大值时，它给了我错误：

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
    // The set of discovered nodes that may need to be (re-)expanded.
    // Initially, only the start node is known.
    // This is usually implemented as a min-heap or priority queue rather than a hash-set.
    openSet := {start}

    // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start
    // to n currently known.
    cameFrom := an empty map

    // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
    // how short a path from start to finish can be if it goes through n.
    fScore := map with default value of Infinity
    fScore[start] := h(start)

    while openSet is not empty
        // This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        for each neighbor of current
            // d(current,neighbor) is the weight of the edge from current to neighbor
            // tentative_gScore is the distance from start to the neighbor through current
            tentative_gScore := gScore[current] + d(current, neighbor)
            if tentative_gScore < gScore[neighbor]
                // This path to neighbor is better than any previous one. Record it!
                cameFrom[neighbor] := current
                gScore[neighbor] := tentative_gScore
                fScore[neighbor] := tentative_gScore + h(neighbor)
                if neighbor not in openSet
                    openSet.add(neighbor)

    // Open set is empty but goal was never reached
    return failure

我的代码：我仍然需要添加轨道父部分

def a_star(a, start, goal):
        dir = [[0,1],[-1,0],[0,-1],[1,0]] #up, right, left, down.

        #setting all vertices to infinity
        g_dist = {dist: float("inf") for dist in range(len(a))}
        total_dist = {dist: float("inf") for dist in range(len(a))}
        
        g_dist[start] = 0
        total_dist[start] = heuristic(start,goal)

        queue = PriorityQueue()
        queue.put(start)

        while queue:
                currVertice = queue.get()
          
                if currVertice == goal:
                        return True
                for d in dir:
                        newVertice = (currVertice[0] + d[0],  currVertice[1] + d[1])
            #IsValid: checking if is out of bounds or if is a wall
                        if isValid(newVertice[0], newVertice[1]):
                                temp_g_dist = g_dist[currVertice] + 1
                                temp_total_dist = temp_g_dist + heuristic(newVertice,goal)
                                
                                if temp_total_dist < total_dist[newVertice]:
                                        g_dist[newVertice] = temp_g_dist
                                        total_dist[newVertice] = temp_total_dist
                                        queue.put(newVertice)
        return False

Answer 1

我的问题实际上是我将无穷大值设置为节点距离的方式。我通过以下方式将距离创建为地图来修复代码：

g_dist = {(p,x): float("inf") for p in range(len(a)) for x in range(len(a[p]))}

total_dist = {(p,x): float("inf") for p in range(len(a)) for x in range(len(a[p]))}

“a”是保存迷宫的二维数组。