私は次のような再帰関係を持っています:
E( i, j ) = A[ i ] + A[ j ] + E( i+1, j-1 ) + E( i+2, j ) + E( i, j-2 ) ; もし i != j
E( i, j ) = A[ i ] ; if( i == j )
E( i, j ) = 0 ; i < 0 または j < 0
A[ i ] 1 <= i <= N の場合。単純な整数配列です。
O（N ^ 2）よりも時間の複雑さでE（1、N）を解きたいです。この再帰式の閉形式式や、E(1, N) の値を計算する巧妙な方法を見つけられるのではないかと考えていました。
どんなヒントでも大歓迎です、
よろしくお願いします。
編集：
実際の問題は次のとおりです。
あなたの再帰関係について：
E(1,N) には E(2,..) と E(3,..) が必要であり、さらに高い "i 」など。
ここで、用語を再配置して、最高の「i」を分離した E 項を作成します (一般に、再帰関係に関する良い考えは、特定のインデックス (最高、最低、最高) を分離するためにさまざまな配置を検討することです。真ん中、...):
E(i+2,j) = E(i,j) - E(i,j-2) - E(i+1,j-1) - A(i) - A(j)
次に、すべての i を 2 だけ下にシフトします (単に式を書き直すだけです)。
E(i,j) = E(i-2,j) - E(i-2,j-2) - E(i-1,j-1) - A(i-2) - A(j)。
次に、探している {i=1, j=N} については、次のようになります。
E(1,N) = E(-1,N) - E(-1,N-2) - E(0,N-1) - A(-1) - A(N) = -A(N) 、他のすべての項がゼロであるためです。
(もちろん、E(i,j) と A(i) は i=0 / j=0 に対してゼロであると仮定します。NEGATIVE インデックスに対してのみゼロ値を指定し、ゼロインデックス)。
次に、根本的なケースの (編集された) 説明について - A が使い果たされるまで、左または右から任意に A から順番に 2 人のプレーヤーが参加します。
前の結果から、結果 -A(N) を考えると、あなたの再帰関係が根底にあるゲームを説明している可能性は低いと思います... したがって、その再帰関係は脇に置いておきます (とにかく i=1 で解決されます)。どのような関係を導出できるか、ゲーム自体を見てみましょう。
[編集後に続く]
これまでのところ、閉じた形式でキャストできるもの、つまりある種の再帰関係を処理するよりも高速なものは思いつきませんでした。したがって、当分の間、計算に適した方法でゲームを説明する方法を書き留めておきましょう。
次の数量を定義します。
X(i,k) を、ターン #k (両方のプレイヤーからのターンを数えます) の終わりにアイテム #i (配列 A 内) がまだ存在する (つまり、まだどのプレイヤーにも取られていない) 確率であるとします。もちろん、k はゲーム内で 1 から N まで実行され、i も同様です。検証の目的で、X(i,N) はすべての i に対してゼロでなければならないことに注意してください。ゲームの終了時には、すべての要素が取得されています。
「通常の」範囲外の X(i,k) の値が (式の評価で) 必要な場合は、次のように評価します。
X(i,k)=1 for {1<=i<=N; k=0}: initially all elements in A are still there.
X(i,k)=0 whenever i<1 or i>N: no elements ever exist outside the (original) range of A.
次に、T(i,k) をターン #k で要素 #i が (任意のプレイヤーによって) 取られる確率とします。これは、0.5 * それが (現在) 一番左の要素である確率であり、これは前のターンの最後に要素 #(i-1) が存在しないと言うのと同じで、プラス 0.5 * それが一番左である確率です。これは、前のターンの最後に要素 #(i+1) が存在しないことを意味し、そのすべてに要素 #i 自体が最初のターンに存在する確率を掛ける必要があります。場所：
T(i,k) = X(i,k-1) * ( (1-X(i-1,k-1)) + (1-X(i+1,k-1)) ) / 2
要素 #i がターン #k の後も存在する確率 X(i,k) は、前のターンの最後に存在していた確率から、ターン #k で取得される確率を引いたものです。
X(i,k) = X(i,k-1) - T(i,k)
要素 #i がプレーヤー #1 と一緒になる確率は、T(i,k) のすべてのターン k の合計ですが、HIS ターンのみをカウントします。その数量を P(i,1) で表しましょう。ここで、1 はプレーヤー #1 を表します。
P(i,1) = sum{ k=1,3,...: T(i,k) }
同様に、プレーヤー #2 の場合:
P(i,2) = sum{ k=2,4,...: T(i,k) }
プレーヤー #1 の予想されるスコアは、合計 S(1) です。
S(1) = sum( i=1..N: P(i,1)*A(i) }, and likewise for player #2: S(2) = sum( i=1..N: P(i,2)*A(i) }
上記の式を見ると、時間に関して O(N2) メソッドを回避する方法がわかりません。合計を実行し続け、不要になった古い「要素ごと」のデータを破棄する可能性があるため、メモリ使用量は O(N) になる可能性があります。それを考えると - 過度に長い配列 A を処理していないと仮定すると - プレイヤーは生き残れません! - O(n2) 時間パフォーマンスは、実際にはそのような問題にはなりません。
int N = sizeof(A);
// note on the code below: we'll use i as an integer running over the elements in A, and k running over the turns that players make.
// while in human parlance we would have them (both) run from 1 to N, the zero-based arrays of C++ make it more convenient to let them
// run from 0 to N-1.
// initialize the running totals P(i), the accumulated (over turns) probabilities that element #i winds up with player #1.
// if we ever need the same for player #2, it's values are of course 1-P (that is: at the end of the game).
double* P = new double[N];
for (int i=0; i<N; i++)
{
P[i] = 0; // before we start, there's little chance that player #1 has already taken any element.
}
// initialize the existence-array for the elements.
int* X = new int[N];
for (int i=0; i<N; i++)
{
X[i] = 1; // initially all elements exist, i.e. have not yet been taken by any player.
}
// declare an array for processing the probabilities that elements are taken at a particular turn.
double* T = new double[N];
// iterate over the turns.
for (int k=0; k<N; k++)
{
// for each element, calculate the probability that it is taken NOW.
// the current values of X - the existence array - refer to the (end of the) previous turn.
for (int i=0; i<N; i++)
{
// note: take care of the boundaries i=0 and i=N-1.
if (i == 0)
{
T[i] = X[i] * ( 2 - X[i+1] ) / 2;
}
else if (i == N-1)
{
T[i] = X[i] * ( 2 - X[i-1] ) / 2;
}
else
{
T[i] = X[i] * ( 2 - X[i-1] - X[i+1] ) / 2;
}
} // element i
// with the take-probabilities for this turn in place, update P - only at odd turns (i.e. k=even): P is for player #1 only.
if (k % 2 == 0)
{
for (int i=0; i<N; i++)
{
P[i] += T[i];
}
}
// finally - in this turn - update the existence array.
for (int i=0; i<N; i++)
{
X[i] -= T[i];
}
} // turn k
// result: calculate the expected score for player #1.
double score = 0;
for (int i=0; i<N; i++)
{
score += P[i] * A[i];
}
--
確率は等しいので、これは単なるカウントの問題です。
k^番目のターンで A[j] をピックする確率を計算できますか?