时间戳

首页 > 解决方案 > 通过numpy数组的最小总和路由

python - 通过numpy数组的最小总和路由

问题描述

这是一个两部分的问题。

第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 = 95at indices[0,0], [0,1], [2,2], [4,3]和next_best_bar = 22.5 + 20 + 50 + 8 = 100.5at indices [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.4at indices[0,0], [0,1], [2,2], [2,3]和next_best_bar = 22.5 + 20 + 50 + 20 = 112.5at indices [0,0], [0,1], [2,2], [0,3]。

我最初的方法是找到所有可能的路线（使用 的索引组合itertools），但是这个解决方案不能很好地适应大矩阵大小（例如，mxn=500x500）。

标签： pythonalgorithmnumpymath

解决方案

这是我想出的一个解决方案（希望我没有误解你的问题）

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)

推荐阅读