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

点击上方“小白学视觉”，选择加"星标"或“置顶”

重磅干货，第一时间送达

免责声明：本文仅以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 GeorgiaThere are 2 days left. We should not go to North CarolinaThere are 2 days left. We should go to ArizonaThere are 2 days left. We should not go to FloridaThere are 2 days left. We should not go to WisconsinThere are 2 days left. We should not go to PennsylvaniaThere are 1 days left. We should not go to GeorgiaThere are 1 days left. We should not go to North CarolinaThere are 1 days left. We should not go to ArizonaThere are 1 days left. We should not go to FloridaThere are 1 days left. We should not go to WisconsinThere are 1 days left. We should not go to GeorgiaThere 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. 简单比较

我不应该只谈论动态计划的效率。让我显示一些证据。

这是递归函数的经过时间。

这是动态规划解决方案之一。

在这种情况下，动态规划的速度大约要快10倍。如果我们有更多节点和更多可能性的问题，差异将是巨大的。

04. 总结

在本文中，我提出了一个问题，即在有限的几天内优化选举促销活动。我们可以很容易地使用递归函数解决问题，但是事实证明，它效率不高，因为有太多次要计算的子问题。

动态计划不是使用“自上而下”的方法（递归），而是使用“自下而上”的方法解决了问题。它从最小的子问题开始，并确保每个步骤都能在当前条件下提供优化的结果，因此下一步将建立在当前步骤的基础上。因此，它没有重复的计算，并且算法复杂度要小得多。

05. 开个小玩笑

当小伙伴们告诉特朗普我们可以用10天的时间获得56张选举人票时，他似乎很高兴。

他问你：“好吧。那我们的行程呢？我们应该去哪些州。”

您：“嗯，目前我没有这些信息。让我调整代码...”

特朗普：“不。我来做相信我。没有人比我更了解Python！”

交流群

欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~