1

我有一个递归关系，它是这样的：

E( i, j ) = A[ i ] + A[ j ] + E( i+1, j-1 ) + E( i+2, j ) + E( i, j-2 ) ; 如果我！= j

E( 我, j ) = A[ 我 ] ; 如果（ i == j ）

E（ i, j ） = 0 ; 如果 i < 0 或 j < 0

A[ i ] 1 <= i <= N; 是简单的整数数组。

我想解决 E(1, N) 的时间复杂度比 O(N^2) 更好。我想知道我们是否可以为这种递归找到一些封闭形式的公式，或者可能是一种计算 E(1, N) 值的聪明方法？

欢迎任何提示，
在此先感谢。

编辑：
实际问题是这样的：

  1. 我们有一个数组 A[]，2 个玩家轮流玩这个游戏。
  2. 玩家可以以 0.5 的概率选择最左边或最右边的数字并将其添加到他的分数中（如果数组中剩下一个元素，他将简单地选择该数字并结束游戏）。
  3. 问题是找到 Player1 将达到的预期分数。
4

2 回答 2

3

关于您的重复关系：

这似乎有些困难，因为文章表明，对于 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 筋疲力尽：

从之前的结果来看，我认为您的递归关系不太可能描述潜在的游戏，给定结果 -A(N)... 因此，将这种递归关系放在一边（对于 i=1 无论如何它都已解决）。看看游戏本身，我们可能会得出什么关系。

[编辑后继续]

到目前为止，我还没有想出可以以封闭形式进行转换的东西，即比处理某种递归关系更快的东西。因此，目前，让我们写下我们如何以适合计算的方式描述游戏。

定义以下数量：

令 X(i,k) 为在第 #k 回合结束时项目#i（在数组 A 中）仍然存在（即尚未被任何玩家拿走）的概率（计算两个玩家的回合数）。当然，k 在我们的游戏中从 1 运行到 N，i 也是如此。出于验证目的，我们可能会注意到，对于所有 i，X(i,N) 必须为零：在游戏结束时，所有元素都已被取走。

如果我们可能需要（在公式评估中）“正常”范围之外的任何 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) 在 PREVIOUS 回合结束时不存在，加上 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];
}

--

于 2012-10-06T13:21:35.390 回答
-1

由于概率相等，这只是一个计数问题。

你能算出在第 k^th 回合选择 A[j] 的机会吗？

于 2012-10-06T17:30:26.893 回答