我在网上找到了这个算法的实现,它很管用.它搜索从一个点开始到达另一个点的最佳路径.以下是代码:

from pyamaze import maze,agent,textLabel
from queue import PriorityQueue
def h(cell1,cell2):
    x1,y1=cell1
    x2,y2=cell2

    return abs(x1-x2) + abs(y1-y2)
def aStar(m):
    start=(m.rows,m.cols)
    g_score={cell:float('inf') for cell in m.grid}
    g_score[start]=0
    f_score={cell:float('inf') for cell in m.grid}
    f_score[start]=h(start,(1,1))

    open=PriorityQueue()
    open.put((h(start,(1,1)),h(start,(1,1)),start))
    aPath={}
    while not open.empty():
        currCell=open.get()[2]
        if currCell==(1,1):
            break
        for d in 'ESNW':
            if m.maze_map[currCell][d]==True:
                if d=='E':
                    childCell=(currCell[0],currCell[1]+1)
                if d=='W':
                    childCell=(currCell[0],currCell[1]-1)
                if d=='N':
                    childCell=(currCell[0]-1,currCell[1])
                if d=='S':
                    childCell=(currCell[0]+1,currCell[1])

                temp_g_score=g_score[currCell]+1
                temp_f_score=temp_g_score+h(childCell,(1,1))

                if temp_f_score < f_score[childCell]:
                    g_score[childCell]= temp_g_score
                    f_score[childCell]= temp_f_score
                    open.put((temp_f_score,h(childCell,(1,1)),childCell))
                    aPath[childCell]=currCell
    fwdPath={}
    cell=(1,1)
    while cell!=start:
        fwdPath[aPath[cell]]=cell
        cell=aPath[cell]
    return fwdPath

if __name__=='__main__':
    m=maze(5,5)
    m.CreateMaze()
    path=aStar(m)

    a=agent(m,footprints=True)
    m.tracePath({a:path})
    l=textLabel(m,'A Star Path Length',len(path)+1)

    m.run()

我对这个代码的问题是,为什么他只使用一个队列?优先级队列是开放队列,但为什么他不使用关闭队列呢?因为我在许多伪代码中都找到了这两个伪代码,并且它通常用于某种条件,例如在这个伪代码中

OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): ⁽²⁾
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

推荐答案

首先,CLOSED不是一个队列,而是一个集合:要么有 node 在其中,要么没有(没有优先级或其他顺序).

这一组实际上被第一个脚本中使用的infinity所取代.通过使用无穷大进行初始化,您可以指示尚未访问相应的 node .通过测试OPEN或CLOSED中的成员资格,可以在第二个脚本中找到相同的"未访问"概念.不同之处在于,当当前计算的路径开销小于已知的路径开销时,第二个脚本"取消访问"一个 node ,而第一个脚本直接进行判断--依靠的是所有开销都小于无穷大的事实.

所以最后都是一样的.

Python相关问答推荐

从不规则形状区域返回使用openCV跟踪的对象的着陆位置

单击cookie按钮,但结果不一致

取相框中一列的第二位数字

如何使用函数正确索引收件箱?

将numpy数组与空数组相加

除了Python之外,可以替代bare?

单击Python中的复选框后抓取数据

过载功能是否包含Support Int而不是Support Int?

Pandas 在时间序列中设定频率

Polars LazyFrame在收集后未返回指定的模式顺序

如何在Python中将returns.context. DeliverresContext与Deliverc函数一起使用?

沿着数组中的轴计算真实条目

通过Selenium从页面获取所有H2元素

如何让Flask 中的请求标签发挥作用

Python库:可选地支持numpy类型,而不依赖于numpy

如何在python polars中停止otherate(),当使用when()表达式时?

如果条件不满足,我如何获得掩码的第一个索引并获得None?

如何从需要点击/切换的网页中提取表格?

* 动态地 * 修饰Python中的递归函数

如何使用两个关键函数来排序一个多索引框架?