行インデックスと列インデックスを一度使用して行列の値の最小の和を求めよう

Question

したがって、行列内の最小値を次のようにして見つけたいと思います。

 [[ 1000. 930. 940. 740.] 
     [ 1000. 1000. 990. 670.] 
    M1= [ 1000. 1000. 1000. 680.] 
     [ 1000. 1000. 1000. 1000.]] 

2つのマトリックス値の合計は、インデックスが0,1,2,3に一度使用されるように選択する必要があります。しかし、行列の値の合計も最小限に抑える必要があります。

この場合、解はM1[2][3]とM1[0][1]になります。 間違っているのはM1[2][3]とM1[1][3]です。これは合計が低くなりますが、一意のインデックス番号は含まれません。

解決策はNxN行列に対して機能するはずです.Nは偶数です。だから8×8行列のために、私は4つの要素を探したい。そのようにインデックス番号。 0,1,2,3,4,5,6,7は一度使用されます。したがって、4つの行列値。 もう1つの制約は、マトリックスが上部の円周行列にintrestの値のみを含むことです。したがって、行列要素は1000であり、これらの要素は最小合計を見つける際に無視することができます。

ハンガリーのアルゴリズムを変更しようとしましたが、これは成功しませんでした。 誰かが私の望むアルゴリズムを知っていますか？おそらく私が悪用する可能性のあるPythonパッケージ

または、私はこの行列を約200X200要素で最大限にしなければならないスマートな解決法を持っています。

Answer 1

おそらく最速ではない解決策がありますが、うまくいく可能性があります。あなたは、グラフをこのように構築することができ

：

• グラフが含まれている（N×N + 1）であろう源となり行列のインデックスと新しいものを表す頂点、

• ソースは、それぞれが表すインデックスの値に等しい距離で他のすべての頂点に接続されます。

• この場合、各頂点（ソースを除く）を移動可能な他のすべての頂点に接続する必要があります（たとえば、M1 [1] [2]はM1 [0] [3] M1 [1] [3]）。任意の頂点から頂点Vまでの距離は、行列内のVの値に対応する。

あなたはこのグラフを構築した後、あなたは（Kあなたが、たとえば、あなたの例のような4×4の行列で2を検討する可能性マトリックス」インデックスの数である）の手順をKその上を歩く必要があります。

ステップごとに、スタック内に2つのハッシュを格納しています（既に使用されているすべての行を格納し、2番目はすでに使用されているすべての列を格納します）。に。

いつも頂点に入るので、ハッシュ（理論的にはO（1）チェック）を使ってその中に留まることが可能かどうかをチェックし、可能であればその値を現在の合計に加えます。 （スタックに格納されている）前の位置に移動し、現在の頂点に入ったときに追加したウェイトを削除します。

また、グローバル変数を保存して、常にKステップを歩き、現在の合計がグローバルな合計よりも小さいかどうかをチェックし、そうであればそれを変更する必要があります。

可能な限り歩いた後、グローバルな合計があなたの答えになります。

希望します。