Минимальная сумма маршрута через массив numpy

Question

Это вопрос из двух частей.

Часть 1

Учитывая следующий массив Numpy:

foo = array([[22.5, 20. ,  0. , 20. ],
             [24. , 40. ,  0. ,  8. ],
             [ 0. ,  0. , 50. ,  9.9],
             [ 0. ,  0. ,  0. ,  9. ],
             [ 0. ,  0. ,  0. ,  2.5]])

Что такое наиболее эффективный способ (i) найти две минимально возможные суммы значений по столбцам (, принимая во внимание значения ячеек, превышающие только ноль * ), где для каждого столбца используется только одна строка и (ii) отслеживать местоположения индекса массива, посещенные на этом маршруте?

Например, в приведенном выше примере это будет: minimum_bar = 22.5 + 20 + 50 + 2.5 = 95 для индексов [0,0], [0,1], [2,2], [4,3] и next_best_bar = 22.5 + 20 + 50 + 8 = 100.5 для индексов [0,0], [0,1], [2,2], [1,3].

Часть 2

Аналогично Часть 1 , но теперь с ограничением, что сумма строк по строке foo (если эта строка используется в решение) должно быть больше, чем значения в массиве (например, np.array([10, 10, 10, 10, 10]). Другими словами sum(row[0])>array[0]=62.5>10=True, но sum(row[4])>array[4]=2.5>10=False.

В этом случае результат будет: minimum_bar = 22.5 + 20 + 50 + 9.9 = 102.4 at индексы [0,0], [0,1], [2,2], [2,3] и next_best_bar = 22.5 + 20 + 50 + 20 = 112.5 по индексам [0,0], [0,1], [2,2], [0,3].

Мой первоначальный подход заключался в поиске всех возможных маршрутов (комбинаций индексов). используя itertools), но это решение не подходит для больших размеров матрицы (например, mxn=500x500).

Answer 1

Вот одно решение, которое я нашел (надеюсь, я ничего не понял в вашем вопросе)

def minimum_routes(foo):
    assert len(foo) >= 2
    assert np.all(np.any(foo > 0, axis=0))

    foo = foo.astype(float)
    foo[foo <= 0] = np.inf
    foo.sort(0)

    minimum_bar = foo[0]

    next_best_bar = minimum_bar.copy()
    c = np.argmin(np.abs(foo[0] - foo[1]))
    next_best_bar[c] = foo[1, c]

    return minimum_bar, next_best_bar

Давайте проверим это:

foo = np.array([[22.5, 20. ,  0. , 20. ],
                [24. , 40. ,  0. ,  8. ],
                [ 0. ,  0. , 50. ,  9.9],
                [ 0. ,  0. ,  0. ,  9. ],
                [ 0. ,  0. ,  0. ,  2.5]])

# PART 1
minimum_bar, next_best_bar = minimum_routes(foo)
# (array([22.5, 20. , 50. ,  2.5]), array([24. , 20. , 50. ,  2.5]))


# PART 2
constraint = np.array([10, 10, 10, 10, 10])
minimum_bar, next_best_bar = minimum_routes(foo[foo.sum(1) > constraint])
# (array([22.5, 20. , 50. ,  8. ]), array([24., 20., 50.,  8.]))

Чтобы найти индексы:

np.where(foo == minimum_bar)
np.where(foo == next_best_bar)