4

正の整数のNxN行列があり、選択した要素の合計が最小化されるように、各行と列から正確に1つの要素を選択するように求められた場合、どのように解決できますか？

動的計画法についてだと思います。O(n!)私はメモ化を使用して時間を最小限に抑えようとしました：

    Dictionary<byte[,], int>[] memo = new Dictionary<byte[,], int>[17];

    int rec(byte[,] arr)
    {
        if (arr.Length == 1) return arr[0, 0];
        int opt = find(arr);
        if (opt != -1) return opt;
        opt = 1 << 25;
        for (int i = 0; i < arr.GetLength(1); ++i)
            opt = Math.Min(opt, arr[0, i] + rec(divide(arr, i)));
        add(arr, opt);
        return opt;
    }

これにより、現在の行列の行0から要素が選択され、次に行列が分割され、それ自体が再帰的に呼び出されて部分行列が解決されます。関数divideは、選択された要素に従って現在の行列を分割します。その場合、部分行列のサイズは（N-1）x（N-1）になります。関数findはで線形探索を実行しmemo[n]、addに解を追加しますが、memo[n]各行列を他の行列と比較するため、これは遅すぎます。

いくつかの機能強化はありますか？より高速なDPアルゴリズムはありますか？どんな助けでも大歓迎です

例

1     2     3    4

8     7     6    5

9     11    10   12

13    14    16   15

最適なソリューション：1 + 5 + 10 + 14

手順：

7   6  5

11 10 12

14 16 15

11 10

14 16

14
4

1 に答える 1

3

これは実際には割り当ての問題です。これは、他の方法の中でも、ハンガリーのアルゴリズムを使用して多項式時間で解くことができます。

于 2012-12-25T23:21:04.287 に答える