Путь минимальной стоимости / путь наименьшей стоимости - PullRequest
Новая
       74

Путь минимальной стоимости / путь наименьшей стоимости

0 голосов
/ 01 февраля 2019

В настоящее время я использую библиотеку из skimage.graph и функцию route_through_array, чтобы получить путь с наименьшей стоимостью из одной точки в другую на карте затрат.Проблема в том, что у меня есть несколько начальных точек и несколько конечных точек, что приводит к тысячам итераций.Это я исправляю в настоящее время с двумя циклами.Следующий код является просто иллюстрацией: 

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)

Из того, что я понимаю из документации , функция принимает много конечных точек, но я не знаю, как передать их в функцию.Есть идеи?

1 Ответ

0 голосов
/ 02 февраля 2019

Это должно быть возможно гораздо эффективнее, напрямую взаимодействуя с классом skimage.graph.MCP Cython.Удобная оболочка 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 и проследите эту единственную конечную точку (или несколько конечных точек, если несколько связаны для наименьшего) назад.

...