1

以下のアルゴリズム (疑似コード) の時間計算量はどれくらいですか? 私はそれを分析するのに苦労しました。これは、別のスレッドで指定された問題の実装です: Algorithm to find max cost path of length N in matrix, from [0,0] to last row。しかし、私はここに来たばかりなので、スレッドにコメントするのに十分なポイントがありません (私は思います)?. 初めての投稿なので、間違っていたらすみません。

アルゴリズムは、メモ化を使用しcache[][][][]ます。初期化中はcache[][][][]-1 で埋められます。

メソッドは で呼び出されmaxPath(0,0,m,DOWN)ます。ここで、m は歩数で、n<=m<=n^2 であり、方向は DOWN=0、LEFT=1、RIGHT=2 として定義されます。

function maxPath(i, j, fuel, direction)
    if i = n OR j = n OR j < 0 OR fuel = 0 then
         return 0;
    end if
    if cache[i][j][f-1][d] != -1 then
         return cache[i][j][f - 1][d];
    end if
    ret := 0
    acc+ = matrix[i][j]
    ret:=max(ret,maxPath(i+1, j, fuel-1, DOWN))
    if f > n - i then . If there is enough steps to move horizontally
        if d = RIGHT or d = DOWN then
            ret:=max(ret,maxPath(i, j+1, fuel-1, RIGHT))
        end if
        if d = LEFT or d = DOWN then
            ret:=max(ret,maxPath(i, j-1, fuel-1, LEFT))
        end if
    end if
    return cache[i,j,fuel-1,direction] = ret + matrix[i][j]
end function
4

1 に答える 1

1

わかりました私はそれを解決し、結果を共有する必要があると考えていました.

G=(V,E) を V={maxPath(i, j, p, d) : すべての可能な i, j, p および d } および E= {uv : u = f(i , j, p, d) および v = f(i', j', p', d') }. G は明らかに DAG (有向非巡回グラフ) である状態のグラフです。次に、メモ化を使用して maxPath を計算できます。

我々は持っています

    n possible values for i
    n possible values for j
    m possible values for fuel (which in worst case is n^2)
    3 possible values for direction

次に、n * n * m * 3 の maxPath のさまざまな関数を呼び出す必要があります。最悪の場合は n^4*3 です。したがって、O(n^4) 個の異なる関数があります。関数の各呼び出しは O(1) 時間で実行されます。グラフは次善の構造を持っているため、各部分問題は元の問題です。したがって、メモ化では、同じ「関数」を 2 回計算する必要がないため、O(n^4) が得られます。

于 2012-10-15T10:47:15.123 に答える