由于我想获得对势中的盆地进行采样的合理路径，因此我编写了以下函数。为了完整起见，我记得dijkstra我写的函数：
%pylab
def dijkstra(V, start):
mask = V.mask
visit_mask = mask.copy() # mask visited cells
m = numpy.ones_like(V) * numpy.inf
connectivity = [(i,j) for i in [-1, 0, 1] for j in [-1, 0, 1] if (not (i == j == 0))]
cc = start # current_cell
m[cc] = 0
P = {} # dictionary of predecessors
#while (~visit_mask).sum() > 0:
for _ in range(V.size):
#print cc
neighbors = [tuple(e) for e in asarray(cc) - connectivity
if e[0] > 0 and e[1] > 0 and e[0] < V.shape[0] and e[1] < V.shape[1]]
neighbors = [ e for e in neighbors if not visit_mask[e] ]
t.ntative_distance = asarray([V[e]-V[cc] for e in neighbors])
for i,e in enumerate(neighbors):
d = tentative_distance[i] + m[cc]
if d < m[e]:
m[e] = d
P[e] = cc
visit_mask[cc] = True
m_mask = ma.masked_array(m, visit_mask)
cc = unravel_index(m_mask.argmin(), m.shape)
return m, P
start, end = unravel_index(V.argmin(), V.shape), (40,4)
D, P = dijkstra(V, start)
def shortestPath(start, end, P):
Path = []
step = end
while 1:
Path.append(step)
if step == start: break
step = P[step]
Path.reverse()
return asarray(Path)
path = shortestPath(start, end, P)
其中给出了以下情节：
contourf(V, 40)
plot(path[:,1], path[:,0], 'r.-')
colorbar()
然后，背后的基本思想extend_path功能是扩展通过获取路径中使势能最小化的节点的邻居而获得的最短路径。集合保存在扩展过程中已经访问过的单元格的记录。
def get_neighbors(cc, V, visited_nodes):
connectivity = [(i,j) for i in [-1, 0, 1] for j in [-1, 0, 1] if (not (i == j == 0))]
neighbors = [tuple(e) for e in asarray(cc) - connectivity
if e[0] > 0 and e[1] > 0 and e[0] < V.shape[0] and e[1] < V.shape[1]]
neighbors = [ e for e in neighbors if e not in visited_nodes ]
return neighbors
def extend_path(V, path, n):
"""
Extend the given path with n steps
"""
path = [tuple(e) for e in path]
visited_nodes = set()
for _ in range(n):
visited_nodes.update(path)
dist_min = numpy.inf
for i_cc, cc in enumerate(path[:-1]):
neighbors = get_neighbors(cc, V, visited_nodes)
next_step = path[i_cc+1]
next_neighbors = get_neighbors(next_step, V, visited_nodes)
join_neighbors = list(set(neighbors) & set(next_neighbors))
if len(join_neighbors) > 0:
tentative_distance = [ V[e] for e in join_neighbors ]
argmin_dist = argmin(tentative_distance)
if tentative_distance[argmin_dist] < dist_min:
dist_min, new_step, new_step_index = tentative_distance[argmin_dist], join_neighbors[argmin_dist], i_cc+1
path.insert(new_step_index, new_step)
return path
下面是我将最短路径延长 250 步得到的结果：
path_ext = extend_path(V, path, 250)
print len(path), len(path_ext)
path_ext = numpy.asarray(path_ext)
contourf(V, 40)
plot(path[:,1], path[:,0], 'w.-')
plot(path_ext[:,1], path_ext[:,0], 'r.-')
colorbar()
正如预期的那样，当我增加时，我首先开始对更深的盆地进行采样n，如下所示：
rcParams['figure.figsize'] = 14,8
for i_plot, n in enumerate(range(0,250,42)):
path_ext = numpy.asarray(extend_path(V, path, n))
subplot('23%d'%(i_plot+1))
contourf(V, 40)
plot(path_ext[:,1], path_ext[:,0], 'r.-')
title('%d path steps'%len(path_ext))
