python – 使用meshgrid上两点之间的’n`节点计算最短路径

概述我在网格上定义了以下3D表面： %pylab inlinedef muller_potential(x, y, use_numpy=False): """Muller potential Parameters ---------- x : {float, np.ndarray, or theano symbolic variable} X coordina 我在网格上定义了以下3D表面：

%pylab inlinedef muller_potential(x,y,use_numpy=False):    """Muller potential    Parameters    ----------    x : {float,np.ndarray,or theano symbolic variable}    X coordinate. If you supply an array,x and y need to be the same shape,and the potential will be calculated at each (x,y pair)    y : {float,or theano symbolic variable}    Y coordinate. If you supply an array,y pair)    Returns    -------    potential : {float,or theano symbolic variable}    Potential energy. Will be the same shape as the inputs,x and y.    Reference    ---------    Code adapted from https://cims.nyu.edu/~eve2/ztsMueller.m    """    aa = [-1,-1,-6.5,0.7]    bb = [0,11,0.6]    cc = [-10,-10,0.7]    AA = [-200,-100,-170,15]    XX = [1,-0.5,-1]    YY = [0,0.5,1.5,1]    # use symbolic algebra if you supply symbolic quantitIEs    exp = np.exp    value = 0    for j in range(0,4):        if use_numpy:            value += AA[j] * numpy.exp(aa[j] * (x - XX[j])**2 + bb[j] * (x - XX[j]) * (y - YY[j]) + cc[j] * (y - YY[j])**2)        else: # use sympy            value += AA[j] * sympy.exp(aa[j] * (x - XX[j])**2 + bb[j] * (x - XX[j]) * (y - YY[j]) + cc[j] * (y - YY[j])**2)    return value

其中给出了以下情节：

minx=-1.5maxx=1.2miny=-0.2maxy=2ax=NonegrID_wIDth = max(maxx-minx,maxy-miny) / 50.0xx,yy = np.mgrID[minx : maxx : grID_wIDth,miny : maxy : grID_wIDth]V = muller_potential(xx,yy,use_numpy=True)V = ma.masked_array(V,V>200)contourf(V,40)colorbar();

我编写了以下代码来定义该网格上两点之间的最短路径.我在网格网格的两个相邻点之间使用的度量由(V [e] -V [cc])** 2给出,其中cc为当前单元,e为相邻单元之一.邻居定义为完全连接：包括对角线的所有直接邻居.

def dijkstra(V):    mask = V.mask    visit_mask = mask.copy() # mask visited cells    m = numpy.ones_like(V) * numpy.inf    connectivity = [(i,j) for i in [-1,1] for j in [-1,1] if (not (i == j == 0))]    cc = unravel_index(V.argmin(),m.shape) # 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] ]        tentative_distance = [(V[e]-V[cc])**2 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,Pdef shortestPath(start,end,P):    Path = []    step = end    while 1:        Path.append(step)        if step == start: break        step = P[step]    Path.reverse()    return asarray(Path)D,P = dijkstra(V)path = shortestPath(unravel_index(V.argmin(),V.shape),(40,4),P)

结果如下：

contourf(V,40)plot(path[:,1],path[:,0],'r.-')

路径长度为112：

print path.shape[0]112

我想知道是否可以计算精确长度n的开始和结束之间的最短路径,其中n是给函数赋予的参数.

备注：如果我将使用的度量值从(V [e] -V [cc])** 2更改为V [e] -V [cc],这会增加负距离,我会获得看起来更好的图,因为它通过本地最低预期：

@H_502_48@解决方法 由于我想获得一个合理的路径,即潜在的样本盆,我写了下面的函数.为了完整性,我记得我写的dijkstra函数：

%pylabdef dijkstra(V,start):    mask = V.mask    visit_mask = mask.copy() # mask visited cells    m = numpy.ones_like(V) * numpy.inf    connectivity = [(i,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,Pstart,end = unravel_index(V.argmin(),4)D,P = dijkstra(V,start)def shortestPath(start,P):    Path = []    step = end    while 1:        Path.append(step)        if step == start: break        step = P[step]    Path.reverse()    return asarray(Path)path = shortestPath(start,P)

其中给出了以下情节：

contourf(V,'r.-')colorbar()

然后,extend_path函数背后的基本思想是扩展通过获取路径中最小化潜力的节点的邻居而获得的最短路径.集合记录在扩展过程中已访问过的单元格.

def get_neighbors(cc,V,visited_nodes):    connectivity = [(i,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 neighborsdef 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,visited_nodes)            next_step = path[i_cc+1]            next_neighbors = get_neighbors(next_step,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,250)print len(path),len(path_ext)path_ext = numpy.asarray(path_ext)contourf(V,'w.-')plot(path_ext[:,path_ext[:,'r.-')colorbar()

正如预期的那样,当我增加n时,我首先开始对更深的盆地进行采样,如下所示：

rcParams['figure.figsize'] = 14,8for i_plot,n in enumerate(range(0,250,42)):    path_ext = numpy.asarray(extend_path(V,n))    subplot('23%d'%(i_plot+1))    contourf(V,40)    plot(path_ext[:,'r.-')    Title('%d path steps'%len(path_ext))

总结

以上是内存溢出为你收集整理的python – 使用meshgrid上两点之间的’n`节点计算最短路径全部内容，希望文章能够帮你解决python – 使用meshgrid上两点之间的’n`节点计算最短路径所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。