3

私はプログラムを書いています：

たとえば、入力は 5 ( 5 だけではない可能性があります) の数字で、配列内のデータを読み取ります: 1, 2, 3, 4, 5。この配列からいくつかの要素 ( first または last ではない) を選択できます (例: 3)。その後、配列内のこの数値を削除し、sum(最初は 0 です) に、左から先に掛けた値と最初から先に- を加算します。正しい要素 (2*4この場合は を意味します)。結果の配列は1, 2, 4, 5であり、要素の数が 2 になるまで何度も繰り返します (1 and 5これらの数値を削除できないのとまったく同じです)。

例: (ここで、A、B、C、D は 1 と 2、2 と 3 などの数字のペアです。)

 A B C D
1 2 3 4 5

要素を削除する (および sum に左右の乗算を追加する) 順序には、6 つの可能な組み合わせがあります。

A (B (C D))
A ((B C) D)
(A B) (C D)
(A (B C)) D
((A B) C) D
A (B (C D))

目標は最小額を見つけることです！解決には 2 つの方法があります。巧妙なアルゴリズムを使用するか、すべての組み合わせに対して再帰を使用してから最小のものを選択します。そのような再帰を書く方法、どこから書き始めるか (またはおそらくいくつかの巧妙なアルゴリズム) のヒントを教えてください。TNX

4

1 に答える 1

8

再帰的なバックトラッキングソリューションはかなり単純です（擬似コード）：

def solve (list): 
    if list.length == 2:
        return 0
    ans = INFINITY
    for each interior element:
        remove element from list
        ans = min(ans, leftelement * rightelement + solve(list))
        place element back in original position in list
    return ans

ただし、このアルゴリズムは、実行時間が階乗であるため、重要なデータセットを処理するのに十分な速度ではありません(O(n!))。再帰的ソリューションを最適化する通常の方法は、動的計画法です。サブステートを考えてみましょう。

dp[a][b]: minimum cost to reduce array[a .. b] to two elements on the edge
          (array[a] and array[b])

基本ケースはdp[i][i + 1], i = {0 .. size - 1)（2つの隣接する要素）です。削除する内部要素がないため、このサブステートは0に設定されます。

のその他すべての場合dp[a][b]、の間にインデックスが付けられた内部要素を削除することでb - a >= 2分割できます。要素iでサブ配列を分割すると、コストはです。各サブステートのコストを最小限に抑えたいので、考えられるすべての分割要素に対してこれらの値の最小値を取ります。最終的な答えは単純です。array[a .. b][a + 1, b - 1]dp[a][i] + dp[i][b] + array[a] * array[b]dp[0][size - 1]

サブステートがあり、それぞれが考慮すべき分割要素O(n^2)の平均を持っているため、合計実行時間は3次であり、妥当な時間内に中小規模のデータセットに対して実行する必要があります。O(n)(O(n ^ 3))

于 2012-11-27T18:13:52.403 に答える