0

我想研究一些“最大流量”问题来理解算法，但我认为测试它们的简单设置的概念很难实现。

看看这个 Project Euler 问题：http ://projecteuler.net/problem=83

我想要做的是假设每个单元格都连接到其所有相邻单元格（“+”模式），然后在每对之间创建一条路径，成本 == 到它们两者之间的最大值，即max(cell1, cell2：）

因此，一个简单的[[s 4],[3 t]]矩阵将变为[(s, (0,1), 4), (s, (1,0), 3), ((0,1), t, 3), ((1,0), 4, t)](node1, node2, cost) + 所有在另一个方向上的路径。

也许有一种更简单的方法来描述我正在尝试做的事情，但我将不胜感激。

其他细节：我正在使用 Python 和 NumPy。

4

1 回答 1

-1

这是计算 Project Euler 问题 83 边缘的 ipython 笔记本代码。我对矩阵中的每个元素使用索引，而不是 2D 坐标。

In [1]:

#load the data
import numpy as np
from StringIO import StringIO
data = StringIO("""131  673 234 103 18
201 96  342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37  331""")
m = np.loadtxt(data, dtype=int)
m

Out[1]:

array([[131, 673, 234, 103,  18],
       [201,  96, 342, 965, 150],
       [630, 803, 746, 422, 111],
       [537, 699, 497, 121, 956],
       [805, 732, 524,  37, 331]])

In [2]:

# give every element an index
idx = np.arange(m.size).reshape(m.shape)
idx

Out[2]:

array([[ 0,  1,  2,  3,  4],
       [ 5,  6,  7,  8,  9],
       [10, 11, 12, 13, 14],
       [15, 16, 17, 18, 19],
       [20, 21, 22, 23, 24]])

In [3]:

# create edges
left_edges = np.concatenate([idx[:, :-1, None], idx[:, 1:, None], m[:, 1:, None]], axis=2).reshape(-1, 3)
right_edges = np.concatenate([idx[:, 1:, None], idx[:, :-1, None], m[:, :-1, None]], axis=2).reshape(-1, 3)
down_edges = np.concatenate([idx[:-1, :, None], idx[1:, :, None], m[1:, :, None]], axis=2).reshape(-1, 3)
up_edges = np.concatenate([idx[1:, :, None], idx[:-1, :, None], m[:-1, :, None]], axis=2).reshape(-1, 3)
edges = np.vstack((left_edges, right_edges, down_edges, up_edges))
edges

Out[3]:

array([[  0,   1, 673],
       [  1,   2, 234],
       [  2,   3, 103],
       [  3,   4,  18],
       [  5,   6,  96],
       [  6,   7, 342],
       [  7,   8, 965],
       [  8,   9, 150],
       [ 10,  11, 803],
       [ 11,  12, 746],
       [ 12,  13, 422],
       [ 13,  14, 111],
       [ 15,  16, 699],
       [ 16,  17, 497],
       [ 17,  18, 121],
       [ 18,  19, 956],
       [ 20,  21, 732],
       [ 21,  22, 524],
       [ 22,  23,  37],
       [ 23,  24, 331],
       [  1,   0, 131],
       [  2,   1, 673],
       [  3,   2, 234],
       [  4,   3, 103],
       [  6,   5, 201],
       [  7,   6,  96],
       [  8,   7, 342],
       [  9,   8, 965],
       [ 11,  10, 630],
       [ 12,  11, 803],
       [ 13,  12, 746],
       [ 14,  13, 422],
       [ 16,  15, 537],
       [ 17,  16, 699],
       [ 18,  17, 497],
       [ 19,  18, 121],
       [ 21,  20, 805],
       [ 22,  21, 732],
       [ 23,  22, 524],
       [ 24,  23,  37],
       [  0,   5, 201],
       [  1,   6,  96],
       [  2,   7, 342],
       [  3,   8, 965],
       [  4,   9, 150],
       [  5,  10, 630],
       [  6,  11, 803],
       [  7,  12, 746],
       [  8,  13, 422],
       [  9,  14, 111],
       [ 10,  15, 537],
       [ 11,  16, 699],
       [ 12,  17, 497],
       [ 13,  18, 121],
       [ 14,  19, 956],
       [ 15,  20, 805],
       [ 16,  21, 732],
       [ 17,  22, 524],
       [ 18,  23,  37],
       [ 19,  24, 331],
       [  5,   0, 131],
       [  6,   1, 673],
       [  7,   2, 234],
       [  8,   3, 103],
       [  9,   4,  18],
       [ 10,   5, 201],
       [ 11,   6,  96],
       [ 12,   7, 342],
       [ 13,   8, 965],
       [ 14,   9, 150],
       [ 15,  10, 630],
       [ 16,  11, 803],
       [ 17,  12, 746],
       [ 18,  13, 422],
       [ 19,  14, 111],
       [ 20,  15, 537],
       [ 21,  16, 699],
       [ 22,  17, 497],
       [ 23,  18, 121],
       [ 24,  19, 956]])

然后您可以通过以下方式转换edges为稀疏矩阵scipy.sparse.coo_matrix

于 2013-02-26T02:13:53.713 回答