我正在嘗試GeeksforGeeks 的 A* 大綱。我遵循了灰色框中的大部分步驟，直到我在 dii 和 diii 上遇到了障礙。這是尋路部分：def pathfind(grid): sx, sy = 0, 0 # find start point and end point cood for y in range(len(grid)): for x in range(len(grid[y])): if grid[y][x] == "S": sx = x sy = y elif grid[y][x] == "E": ex = x ey = y opensq = [] closedsq = [] successor = [] #add starting point to closed opensq.append([sx, sy, gcost(sx, sy, sx, sy), hcost(sx, sy, ex, ey)]) grid[sy][sx] = "O" while opensq: # find the node with lowest fcost q = opensq[0] if len(opensq) == 1: pass else: for sq in range(len(opensq)): if sq == len(opensq) - 1: pass else: if q[2] + q[3] < opensq[sq + 1][2] + opensq[sq + 1][3]: pass elif q[2] + q[3] == opensq[sq + 1][2] + opensq[sq + 1][3]: # if f is same, check hcost if q[3] < opensq[sq + 1][3]: pass elif q[3] == opensq[sq + 1][3]: pass else: q = opensq[sq + 1] else: q = opensq[sq + 1] opensq.pop(opensq.index(q)) # pick successors to q successors = [] successors.append([q[0] + 1, q[1], gcost(q[0] + 1, q[1], sx, sy), hcost(q[0] + 1, q[1], ex, ey)]) successors.append([q[0] - 1, q[1], gcost(q[0] - 1, q[1], sx, sy), hcost(q[0] - 1, q[1], ex, ey)]) successors.append([q[0], q[1] + 1, gcost(q[0], q[1] + 1, sx, sy), hcost(q[0], q[1] + 1, ex, ey)]) successors.append([q[0], q[1] - 1, gcost(q[0], q[1] - 1, sx, sy), hcost(q[0], q[1] - 1, ex, ey)])
1 回答
aluckdog
TA貢獻1847條經驗 獲得超7個贊
錯誤發生在以下部分：
for s in successors:
if s[0] == ex and s[1] == ey:
pass
for sq in opensq:
if sq[2] + sq[3] < s[2] + s[3]:
successors.pop(successors.index(s)) # line 1
for sq in closedsq:
if sq[2] + sq[3] < s[2] + s[3]:
successors.pop(successors.index(s)) # line 2
在“第1行”和“第2行”上，可以在循環中的上一個循環中已經彈出successors.index(s)之后調用。然后，發生錯誤。sfor
而且，更重要的是，您的代碼沒有正確執行A* 搜索算法。當您對代碼發表評論時，您應該只檢查“與后繼位置相同的節點”。您可以嘗試使用以下代碼代替上述部分來解決問題。
# Iterate over a copy of the list,
# since we are popping elements in the original list.
for s in list(successors):
if s[0] == ex and s[1] == ey:
pass
for sq in opensq + closedsq:
if sq[0] == s[0] and sq[1] == s[1] and sq[2] + sq[3] <= s[2] + s[3]:
successors.pop(successors.index(s))
break
而且，上面的代碼并不是那么簡潔。你可以看到上面的語句sq[3] == s[3]總是成立，if因為它們是hcost相同的位置。所以，你可以比較sq[2]，s[2]即gcost。（換句話說，因為sq[3] == s[3]持有，你可以只做sq[2] <= s[2]而不是上面的sq[2] + sq[3] <= s[2] + s[3]陳述。）我認為GeeksforGeeks 上if灰色框中描述的 A* 搜索算法不是那么簡潔。
gcost是“從起點移動到網格上給定方格的移動成本，沿著生成的路徑到達那里?！?所以你應該修復你的代碼：
移除gcost功能
修復gcost用于
opensq.append([sx, sy, 0, hcost(sx, sy, ex, ey)])
successors.append([q[0] + 1, q[1], q[2] + 1, hcost(q[0] + 1, q[1], ex, ey)])
successors.append([q[0] - 1, q[1], q[2] + 1, hcost(q[0] - 1, q[1], ex, ey)])
successors.append([q[0], q[1] + 1, q[2] + 1, hcost(q[0], q[1] + 1, ex, ey)])
successors.append([q[0], q[1] - 1, q[2] + 1, hcost(q[0], q[1] - 1, ex, ey)])
通過上述修復，您的代碼似乎可以正常工作。但我認為你仍然可以改進你的代碼。我們可以改進的一件事是分離節點和gcost節點的?，F在opensq在您的代碼中保存節點坐標并保存在一起，如果計算的不同，則可以多次gcost添加一個節點。opensqgcost
你也可以參考Wikipedia 上的 A* 偽代碼。我認為它比您已經提到的GeeksForGeeks更整潔干凈。
你也可以參考Wikipedia 上的 A* 偽代碼。我認為它比您已經提到的GeeksForGeeks更整潔干凈。
關閉列表可以參考維基百科偽代碼后面的“ Remark ” ：
備注：在此偽代碼中，如果一個節點通過一條路徑到達，從 openSet 中刪除，隨后通過一條更便宜的路徑到達，它將再次添加到 openSet。如果啟發式函數是可接受的但不一致，這對于保證返回的路徑是最優的是必不可少的。如果啟發式是一致的，當一個節點從 openSet 中移除時，它的路徑保證是最優的，因此如果再次到達該節點，測試 'tentative_gScore < gScore[neighbor]' 將始終失敗。
GeeksForGeeks 上的封閉列表只有在啟發式函數一致的情況下才是真正封閉的。
添加回答
舉報
0/150
提交
取消