用运用动态规划，帮助特朗普赢得选举

小白学视觉

发布于 2020-12-07 11:25:51

3340

发布于 2020-12-07 11:25:51

免责声明：本文仅以2020年美国大选为背景展示一种计算机编程思维方式，且本文中使用的所有数据均由假设构成。

好吧，其实开始写这篇文章的时候，乔·拜登已经获得了胜利。现在想象以下假设我们被聘为特朗普大选团队的成员，假设我们还有10天的投票时间。大家都知道，最重要的是争取摇摆状态，我们从Wikipedia得到了被认为是2020年美国大选的11个摇摆州。

我们首先需要对数据进行整理，并将所有摇摆州州、选举人票数以及在该州中需要花费的天数放到一个词典中。

states_dict = [
    {'name': 'Maine', 'votes': 5, 'days': 1},
    {'name': 'Nevada', 'votes': 6, 'days': 1},
    {'name': 'Minnesota', 'votes': 10, 'days': 2},
    {'name': 'New Hampshire', 'votes': 4, 'days': 1},
    {'name': 'Michigan', 'votes': 16, 'days': 3},
    {'name': 'Pennsylvania', 'votes': 20, 'days': 4},
    {'name': 'Wisconsin', 'votes': 10, 'days': 2},
    {'name': 'Florida', 'votes': 29, 'days': 5},
    {'name': 'Arizona', 'votes': 11, 'days': 2},
    {'name': 'North Carolina', 'votes': 15, 'days': 3},
    {'name': 'Georgia', 'votes': 16, 'days': 3},
]

问题是特朗普在最近10天最多能得到多少张选举人票，要在那些州开展工作？将所有红色州的选票加在一起，便可以估算出特朗普最终将获得多少张选举人票。

有几种解决问题的方法。最直观的方法可能是递归函数，但它绝对不是最佳解决方案。在本文中，我们将提供递归解决方案和动态计划解决方案，并给出解释以说明为什么动态计划比前者更高级。

01. 递归解决方案

递归解决方案的想法相对简单。也就是说，对于每个州，我们都有两个选择-执行或不执行。如果我们选择进入该州，那么总票数=该州的票数+剩下的几天从其他州获得的最高选票。代码如下：

def max_vote_recursive(states, days_left, index):
    # Terminating conditions
    if len(states) == 0 or index >= len(states) or days_left <= 0:
        return 0
# If we have enough days, go to this state
    votes_if_go = 0
    if states[index]['days'] <= days_left:
        votes_if_go = states[index]['votes'] + max_vote_recursive(states, days_left - states[index]['days'], index + 1)
# If we don't go to this state
    votes_if_not_go = max_vote_recursive(states, days_left, index + 1)
    return max(votes_if_go, votes_if_not_go)

我们运行该函数，结果显示56个选举人票。为什么我说这个递归函数不够有效？先让我们看看将最后一个return语句return max(votes_if_go, votes_if_not_go)更改为以下代码段会怎样。

if votes_if_go > votes_if_not_go:
        print(f'There are {days_left} days left. We should go to {states[index]["name"]}')
        return votes_if_go
    else:
        print(f'There are {days_left} days left. We should not go to {states[index]["name"]}')
        return votes_if_not_go

递归的每一步都会判断剩余的天数和当前状态。更改后，通过再次运行该函数，我们的输出如下。

There are 2 days left. We should not go to Georgia
There are 2 days left. We should not go to North Carolina
There are 2 days left. We should go to Arizona
There are 2 days left. We should not go to Florida
There are 2 days left. We should not go to Wisconsin
There are 2 days left. We should not go to Pennsylvania
There are 1 days left. We should not go to Georgia
There are 1 days left. We should not go to North Carolina
There are 1 days left. We should not go to Arizona
There are 1 days left. We should not go to Florida
There are 1 days left. We should not go to Wisconsin
There are 1 days left. We should not go to Georgia
There are 1 days left. We should not go to North Carolina
...

请注意，在这些最初的几行中，我们已经可以找到重复的输出There are 1 days left. We should not go to Georgia。然我们来看看有多少重复的输出。排序结果如下：

('There are 1 days left. We should not go to Georgia', 74),
('There are 2 days left. We should not go to Georgia', 63),
('There are 3 days left. We should go to Georgia', 51),
('There are 1 days left. We should not go to North Carolina', 45),
('There are 2 days left. We should not go to North Carolina', 41),
('There are 4 days left. We should go to Georgia', 40),
('There are 3 days left. We should not go to North Carolina', 35),
('There are 4 days left. We should not go to North Carolina', 29),
('There are 5 days left. We should go to Georgia', 28),
('There are 1 days left. We should not go to Arizona', 24),
('There are 2 days left. We should go to Arizona', 23),
('There are 5 days left. We should not go to North Carolina', 22),
('There are 3 days left. We should not go to Arizona', 21),
('There are 6 days left. We should go to Georgia', 19),
('There are 4 days left. We should not go to Arizona', 18),
('There are 3 days left. We should not go to Florida', 16),
('There are 6 days left. We should go to North Carolina', 16),
('There are 2 days left. We should not go to Florida', 15),
('There are 4 days left. We should not go to Florida', 15),
('There are 5 days left. We should go to Arizona', 14),
('There are 1 days left. We should not go to Florida', 13),
('There are 5 days left. We should go to Florida', 13),
('There are 7 days left. We should go to Georgia', 12),
('There are 6 days left. We should not go to Arizona', 11),
('There are 6 days left. We should not go to Florida', 11),
('There are 7 days left. We should go to North Carolina', 11),
...

很明显，某些“子问题”已经重复了很多次。例如“还剩1天，我们可以/可以去佐治亚州吗？”这个子问题被“计算”了74次。幸亏我们只有11个摇摆州。如果将这种问题转移到另一个域，大量的节点、重复计算子问题的递归函数的缺点可能会导致问题无法解决。

02. 动态计划解决方案

大家都知道知道递归函数实际上是“自上而下”的解决方案。相反，动态计划是指以“自下而上”的结构解决问题的方法。具有以下特点：

要解决的问题必须分为子问题。
在自下而上的推理过程中，我们必须确保在给定条件下，每个步骤（子问题）均已全局优化。

让我们先看一下代码。

def max_vote_dynamic_planning(states, total_days):
    dp_matrix = [[0 for days_left in range(total_days + 1)] for index in range(len(states) + 1)]
for index in range(1, len(states) + 1):
        for days_left in range(1, total_days + 1):
            if states[index-1]['days'] <= days_left:  # If we have enough days left
                votes_if_go = dp_matrix[index-1][days_left - states[index-1]['days']] + states[index-1]['votes']
                votes_if_not_go = dp_matrix[index-1][days_left]
                # Save the maximum votes into cache
                dp_matrix[index][days_left] = max(votes_if_go, votes_if_not_go)
            else:  # We don't have any days left
                dp_matrix[index][days_left] = dp_matrix[index-1][days_left]
    
    return dp_matrix[-1][-1]
max_vote_dynamic_planning(states_dict, 10)

计算如下，我们可以获得的最多选举人票数是最后一个值56。

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5],
 [0, 6, 11, 11, 11, 11, 11, 11, 11, 11, 11],
 [0, 6, 11, 16, 21, 21, 21, 21, 21, 21, 21],
 [0, 6, 11, 16, 21, 25, 25, 25, 25, 25, 25],
 [0, 6, 11, 16, 22, 27, 32, 37, 41, 41, 41],
 [0, 6, 11, 16, 22, 27, 32, 37, 42, 47, 52],
 [0, 6, 11, 16, 22, 27, 32, 37, 42, 47, 52],
 [0, 6, 11, 16, 22, 29, 35, 40, 45, 51, 56],
 [0, 6, 11, 17, 22, 29, 35, 40, 46, 51, 56],
 [0, 6, 11, 17, 22, 29, 35, 40, 46, 51, 56],
 [0, 6, 11, 17, 22, 29, 35, 40, 46, 51, 56]]

在这的思想如下：

初始化一个二维矩阵，该二维矩阵使用状态数作为行、天数作为列。
从剩余天数为1（索引= 1）开始搜索。
如果我们转到当前州，应该将该州的选举人票数与剩余天数所能获得的最高票数相加。剩余天数应为当前剩余天数减去当前状态下我们需要提升的天数。

关于这一点，让我们假设正在计算第二个州，内华达州，并且只剩下2天了。如果我们选择去内华达州，我们将获得6张选举人票。这将花费1天的时间，因此我们还有1天的时间。1天的时间内，最多可以在缅因州获得5票。因此，此步骤的优化结果是11票。如果我们选择不进入当前状态，那么我们应该仅使用针对先前状态已经优化的最高票数。举一个例子，说明动态计划如何知道何时不应该进入状态。假设我们正在计算明尼苏达州，并且还有2天。如果我们选择去明尼苏达州，我们将获得10 票。但是，此后，我们还有2–2 = 0天。另一方面，如果我们选择不前往明尼苏达州，则还有2天的时间，而我们从前两个州可获得的最高票数是11。

因此，随着for循环的进行，对于每个单个循环，我们都可以确保到目前为止它已被优化。这就是为什么您可以看到矩阵在水平和垂直方向上都进行排序的原因。因此，全局优化数应位于右下角，即56。

03. 简单比较