最优选择算法

Question

我有个大学约会，今天就要到了，我开始紧张了。最近我们讨论了用于算法优化的动态规划，现在我们将实现一个使用动态规划的算法。

任务

因此，我们有一个简单的游戏，我们将编写一个算法，以找到最佳可能的策略，以获得最佳的可能得分(假设双方的游戏优化)。

我们有像4 7 2 3这样的一行数字(请注意，根据任务描述，它并不是固定的，它总是相等的数字计数)。现在每个玩家都会从后面或前面取一个数字。当选择最后一个数字时，每个玩家的数字被相加，每个玩家得到的分数是彼此相减的。结果是玩家1的得分。因此，上述数字的最佳顺序是

P1: 3 -> p2: 4 -> p1: 7 -> p2: 2

所以p1会有3, 7，p2会有4, 2，这会给玩家1带来(3 + 7) - (4 + 2) = 4的最终分数。

在第一个任务中，我们应该简单地实现“一种简单的递归解决这个问题的方法”，其中我只使用了一个很适合自动化测试的极小极大算法。然而，在第二个任务中，我陷入了困境，因为我们现在将使用动态编程技术。我发现的唯一提示是，在任务本身中提到了一个matrix。

到目前为止我所知道的

我们有一个使用这样一个矩阵的单词转换问题的例子，它被称为“两个单词的Edit distance”，这意味着有多少变化(Insertions，Deletions， of )，是否需要将一个单词转换成另一个单词。在这里，两个单词按表或矩阵顺序排列，对于该词的每一个组合，将计算距离。

示例：

W    H    A         T
     | D       | I
     v         v
W         A    N    T

编辑距离为2。您有一个表，其中每个子字符串的编辑距离显示如下：

   ""    W    H    A    T
         1    2    3    4
       
   W 1   0    1    2    3
   
   A 2   1    1    2    3
   
   N 3   2    2    2    3
   
   T 4   3    3    3    2

例如，从WHA到WAN需要两个编辑:插入N和删除H；从WH到WAN也需要两个编辑:替换H->A和插入N等等。这些值是用"OPT“函数计算的，我认为它代表了优化。我还学习了自下而上和自上而下的递归方案，但我不太确定如何将其与我的问题联系起来。

我在想什么

作为提醒，我使用了数字4 7 2 3。

我从上面了解到，我应该尝试创建一个表，其中显示每个可能的结果(就像minimax一样，它将在前面保存)。然后，我创建了一个简单的表，其中我试图包括可能的绘图，可以这样做(我认为这是我的OPT函数)：

         4    7    2    3
       ------------------
a.  4 |  0   -3    2    1
      |
b.  7 |  3    0    5    4
      |
c.  2 | -2   -5    0   -1
      |
d.  3 | -1   -4    1    0

左边的列标记player 1绘图，上面的行标记player 2绘图，然后每个数字表示numberP1 - numberP2。从这个表中，我至少可以读到上面提到的3 -> 4 -> 7 -> 2 (-1 + 5)的最优策略，所以我确信表应该包含所有可能的结果，但我现在不太确定如何从中提取结果。我的想法是开始对行进行迭代，并选择其中数字最高的行，并将其标记为来自p1 (但无论如何都是贪婪的)。然后，p2将搜索此行中最低的数字，并选择特定的条目，这将是转弯。

示例：

p1选择行a. 7 | 3 0 5 4，因为5是表中的最高值。P2现在从该行中选择3，因为它是最低的(0是无效的抽签，因为它是相同的数字，您不能选择两次)，所以第一个回合将是7 -> 4，但是我注意到，由于从一开始就无法访问该7，所以无法进行此绘制。因此，对于每一轮，您只有4种可能性:表的外部数和表后面/前面的表数，因为这些在绘图后是可访问的。因此，在第一个回合中，我只有a.或d.行，p1可以从中选择：

4只剩下p2 7或3，或p1取3，留给p2 4或2

但我真的不知道如何得出结论，我真的坚持住了。

所以我真的很想知道我是在正确的道路上，还是我想得太多了。这是解决这个问题的正确方法吗？

Answer 1

在开始动态规划算法时，首先要写下来的是一个递归关系。

让我们先简化一下这个问题。我们会考虑扑克牌的数量是相等的，我们想要为第一个玩家设计一个最优的策略。一旦我们成功地解决了这个版本的问题，其他的(奇数牌，优化策略为第二位玩家)跟随琐碎。

所以，首先，一个递推关系。让X(i, j)成为玩家1所能期望的最佳得分(当玩家2也是最佳的时候)，当剩余的牌从i^th到j^th的时候。然后，玩家1在玩游戏时所能得到的最好的分数将由X(1, n)来表示。

我们有：

X(i, j) = max(Arr[i] + X(i+1, j), X(i, j-1) + Arr[j]) if j-i % 2 == 1，意思是玩家所能期望的最佳得分是从左边的牌到右边的牌之间的最佳得分。

在另一种情况下，另一位玩家正在玩，所以他将尝试最小化：X(i, j) = min(Arr[i] + X(i+1, j), X(i, j-1) + Arr[j]) if j-i % 2 == 0。

终端的情况是微不足道的：X(i, i) = Arr[i]，意思是当只有一张卡时，我们只是选择它，仅此而已。

现在没有动态规划的算法，这里我们只写递归关系作为递归算法：

function get_value(Arr, i, j) {
    if i == j {
        return Arr[i]
    } else if j - i % 2 == 0 {
        return max(
            Arr[i] + get_value(i+1, j),
            get_value(i, j-1) + Arr[j]
        )
    } else {
        return min(
            Arr[i] + get_value(i+1, j),
            get_value(i, j-1) + Arr[j]
        )
    }
}

这个函数的问题是，对于某些给定的i, j，将有许多冗余的X(i, j)计算。动态规划的本质是存储中间结果，以避免重复计算。

Algo与动态规划(X是初始化与+ inf无处不在。

function get_value(Arr, X, i, j) {
    if X[i][j] != +inf {
        return X[i][j]
    } else if i == j {
        result = Arr[i]
    } else if j - i % 2 == 0 {
        result = max(
            Arr[i] + get_value(i+1, j),
            get_value(i, j-1) + Arr[j]
        )
    } else {
        result = min(
            Arr[i] + get_value(i+1, j),
            get_value(i, j-1) + Arr[j]
        )
    }
    X[i][j] = result
    return result
}

正如您所看到的，上面算法的唯一不同之处在于，我们现在使用2D数组X来存储中间结果。由于第一种算法在O(2^n)中运行，而第二种算法在O(n²)中运行，因此对时间复杂度的影响是巨大的。

Answer 2

动态规划问题一般可以通过自上而下和自下而上两种方式来解决。

自下而上需要构建一个从最简单到最复杂的数据结构。这是很难写的，但它提供了将您知道不再需要的部分数据丢弃的选项。自顶向下需要编写递归函数，然后编写回忆录。因此，自下而上可以更有效，自上而下通常更容易编写。

我会同时展示给你看。天真的做法可以是：

def best_game(numbers):
    if 0 == len(numbers):
        return 0
    else:
        score_l = numbers[0] - best_game(numbers[1:])
        score_r = numbers[-1] - best_game(numbers[0:-1])
        return max(score_l, score_r)

但是我们传递了很多多余的数据。所以让我们稍微重组一下。

def best_game(numbers):
    def _best_game(i, j):
        if j <= i:
            return 0
        else:
            score_l = numbers[i] - _best_game(i+1, j)
            score_r = numbers[j-1] - _best_game(i, j-1)
            return max(score_l, score_r)

    return _best_game(0, len(numbers))

现在我们可以添加一个缓存层来回溯它：

def best_game(numbers):
    seen = {}
    def _best_game(i, j):
        if j <= i:
            return 0
        elif (i, j) not in seen:
            score_l = numbers[i] - _best_game(i+1, j)
            score_r = numbers[j-1] - _best_game(i, j-1)
            seen[(i, j)] = max(score_l, score_r)
        return seen[(i, j)]

    return _best_game(0, len(numbers))

这种方法将是内存和时间O(n^2)。

现在自下而上。

def best_game(numbers):
    # We start with scores for each 0 length game
    # before, after, and between every pair of numbers.
    # There are len(numbers)+1 of these, and all scores
    # are 0.
    scores = [0] * (len(numbers) + 1)
    for i in range(len(numbers)):
        # We will compute scores for all games of length i+1.
        new_scores = []
        for j in range(len(numbers) - i):
            score_l = numbers[j] - scores[j+1]
            score_r = numbers[j+i] - scores[j]
            new_scores.append(max(score_l, score_r))
        # And now we replace scores by new_scores.
        scores = new_scores
    return scores[0]

这同样是O(n^2)时间，但只有O(n)空间。因为在计算完长度为1的游戏后，我可以扔掉长度为0的游戏。长度2的游戏，我可以扔掉长度1的游戏，等等。