0

アルゴリズムを理解するためにいくつかの「最大フロー」の問題に取り組みたいのですが、それらをテストするための単純なセットアップとは何かという私の考えは、実装が難しいことが証明されています.

このプロジェクト オイラーの問題を見てみましょう: http://projecteuler.net/problem=83

私がやりたいことは、これらのセルのそれぞれが隣接するすべてのセルに接続されていると仮定し (「+」パターン)、コスト == を使用してすべてのペアの間にパスを作成し、それらの 2 つの間の最大値にすることですmax(cell1, cell2。

したがって、単純な[[s 4],[3 t]]行列は[(s, (0,1), 4), (s, (1,0), 3), ((0,1), t, 3), ((1,0), 4, t)](ノード 1、ノード 2、コスト) + 他の方向に向かうすべてのパスになります。

私がやろうとしていることを説明するもっと簡単な方法があるかもしれませんが、助けていただければ幸いです。

その他の詳細: Python と NumPy を使用しています。

4

1 に答える 1

-1

プロジェクト オイラー問題 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 に答える