Astar Numpy Gscore error“unhable type:'Numpy.ndarray'”

Question

总的来说，我试图在网格上创建从2到-1的最佳路径。我要改变这些数字的位置，我希望路径能够计算出两点之间的最短距离

到目前为止，我在这一部分遇到了一些问题

def astar(array, start, goal):
    neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
    close_set = set()
    came_from = {}
    gscore = {start:0} 
    fscore = {start:heuristic(start, goal)}
    oheap = []
    heapq.heappush(oheap, (fscore[start], start)) 

我的gscore给了我一个

unhashable type: 'numpy.ndarray'

我还没想好要做什么改变才能使它起作用

当起始点和结束点是坐标时，代码工作。又称作 start = (0,0)，goal = (0,19)

完整代码供参考

import numpy as np
import heapq
import matplotlib.pyplot as plt
from matplotlib.pyplot import figure



##############################################################################
# plot grid
##############################################################################

grid=grid = np.array([
 [2, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1],
 [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0],
 [0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])
# start point and goal
##start = np.any(grid>=2)
##start = grid.argmax()
##print(start)
start = np.where(grid==2)
##goal = np.any(grid<=-1)
##goal = grid.argmin()
##print(goal)
goal = np.where(grid==-1)




##############################################################################
# heuristic function for path scoring
##############################################################################

def heuristic(a, b):
 return np.sqrt((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2)

##############################################################################
# path finding function
##############################################################################

def astar(array, start, goal):
 neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
 close_set = set()
 came_from = {}
 gscore = {start:0} ## start:0
 fscore = {start:heuristic(start, goal)}
 oheap = []
 heapq.heappush(oheap, (fscore[start], start)) 

 while oheap:
     current = heapq.heappop(oheap)[1]
     if current == goal:
         data = []
         while current in came_from:
             data.append(current)
             current = came_from[current]
         return data
     close_set.add(current)
     for i, j in neighbors:
         neighbor = current[0] + i, current[1] + j
         tentative_g_score = gscore[current] + heuristic(current, neighbor)
         if 0 <= neighbor[0] < array.shape[0]:
             if 0 <= neighbor[1] < array.shape[1]:                
                 if array[neighbor[0]][neighbor[1]] == 1:
                     continue
             else:
                 # array bound y walls
                 continue
         else:
             # array bound x walls
             continue

         if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, 0):
             continue

         if  tentative_g_score < gscore.get(neighbor, 0) or neighbor not in [i[1]for i in oheap]:
             came_from[neighbor] = current
             gscore[neighbor] = tentative_g_score
             fscore[neighbor] = tentative_g_score + heuristic(neighbor, goal)
             heapq.heappush(oheap, (fscore[neighbor], neighbor))

 return False
route = astar(grid, start, goal)
route = route + [start]
route = route[::-1]
print(route)

##############################################################################
# plot the path
##############################################################################

#extract x and y coordinates from route list
x_coords = []
y_coords = []
for i in (range(0,len(route))):
 x = route[i][0]
 y = route[i][1]
 x_coords.append(x)
 y_coords.append(y)
# plot map and path
fig, ax = plt.subplots(figsize=(20,20))
ax.imshow(grid, cmap=plt.cm.Dark2)
ax.scatter(start[1],start[0], marker = "*", color = "yellow", s = 200)
ax.scatter(goal[1],goal[0], marker = "*", color = "red", s = 200)
ax.plot(y_coords,x_coords, color = "black")
plt.show()

Answer 1

问题是ndarray是可变的，而dict键必须是不可变的。见Immutable vs Mutable types。 问题是变量“start”。我猜它是ndarray，所以必须将它转换为不可变类型才能用作键。使用以下命令将其转换为元组：

start=tuple（start.tolist（））