最低成本路径/最低成本路径
最低成本路径/最低成本路径
提问于 2019-02-02 01:38:42
我目前正在使用skimage.graph的一个库和route_through_array函数来获取成本图中从一点到另一点的最低成本路径。问题是我有多个起始点和多个结束点，这导致了数千次迭代。我目前正在用两个for循环来修复这个问题。下面的代码只是一个示例：
img=np.random.rand(400,400)
img=img.astype(dtype=int)
indices=[]
costs=[]
start=[[1,1],[2,2],[3,3],[4,5],[6,17]]
end=[[301,201],[300,300],[305,305],[304,328],[336,317]]
for i in range(len(start)):
for j in range(len(end)):
index, weight = route_through_array(img, start[i],end[j])
indices.append(index)
costs.append(weight)根据我对documentation的理解，该函数接受许多端点，但我不知道如何在函数中传递它们。有什么想法吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-02-02 14:04:16
通过直接与CythonCython类进行交互，这应该可以更有效地实现。skimage.graph.MCP方便的包装器route_through_array还不够通用。假设我正确地理解了您的问题，那么您正在寻找的基本上是MCP.find_costs()方法。
你的代码看起来会像这样(忽略导入)
img = np.random.rand(400,400)
img = img.astype(dtype=int)
starts = [[1,1], [2,2], [3,3], [4,5], [6,17]]
ends = [[301,201], [300,300], [305,305], [304,328], [336,317]]
# Pass full set of start and end points to `MCP.find_costs`
from skimage.graph import MCP
m = MCP(img)
cost_array, tracebacks_array = m.find_costs(starts, ends)
# Transpose `ends` so can be used to index in NumPy
ends_idx = tuple(np.asarray(ends).T.tolist())
costs = cost_array[ends_idx]
# Compute exact minimum cost path to each endpoint
tracebacks = [m.traceback(end) for end in ends]请注意，原始输出cost_array实际上是一个与img形状相同的完全密集数组，它只有在需要端点的地方才具有有限的值。这种方法的唯一可能问题是，来自多个起点的最小路径是否收敛到相同的终点。通过上面的代码，您将只获得这些收敛路径中较低的一个的完整回溯。
回溯步骤仍然有一个循环。这可能可以通过使用tracebacks_array并与`m.offsets交互来消除，这也将消除上面提到的模糊性。但是，如果您只想要最小成本和最佳路径，则可以省略此循环-只需使用argmin找到最小成本，然后跟踪该单个端点(或几个端点，如果多个端点都是最低的话)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54484510
复制相关文章
相似问题
腾讯云开发者
