假如时光倒流,如何帮助特朗普赢得大选?-技术圈

引言

近日如火如荼的美国总统大选，让我们看到两位七十多岁的老同志，一个 160 多斤，一个 210 多斤，为了一份工作，耍小聪明，搞窝里斗。

图 1: 两位七十多岁的老同志搞窝里斗

尽管投票结果还在统计中，但根据已经统计的结果，拜登已经赢得了当选下一任总统所需的 270 票。很多媒体已经宣布拜登胜选，二十多个国家领导人也纷纷向拜登表示了祝贺。在选举日之后，特朗普在社交媒体上表示拒绝承认本次大选结果，并质疑某些摇摆州的投票统计结果。同时也向法院提出请求，要求重新统计选票。本次美国总统大选实际上只是特朗普粉和特朗普黑之间的大战，与拜登没什么太大关系。即使把拜登换成吉祥物，可能对大选结果也没多大影响。

图 2: 2020 美国大选状态（美东11月12日）

西班牙《国家报》网站日前刊文称，在本次美国大选中，真正输家不是两位候选人，而是美国的选举制度。美国总统并不是直接由选民普选产生，而是由选民普选叠加赢家通吃的选举人制度产生。选举人制度根据每一州的参众两院人数来确定该州的选举人票数，赢得每一州普选的总统候选人，将获得该州所有的选举人票，最后获得选举人票过半数的候选人当选总统。

图 3: 美国总统的选举过程

美国有 50 个州，每个州设两名参议员，共 100 张选举人票；众议院席位则根据每个州的人口比例设置，共 435 张选举人票；华盛顿特区额外占 3 张选举人票。以上所有选举人票加在一起共 538 张。所以，过半数必须取得 270 张及以上选举人票。目前除内布拉斯加州、缅因州外，选举人都被各州法律规定必须按照该州选民投票结果来投票，即凡赢得该州民众普选的候选人即赢得该州的所有选举人票。选举人制度保证了人口少的小州的选举权益，避免了选举结果完全由人口众多的大州决定的弊端。同时，也避免出现众多小党，导致无候选人过半数等影响政局稳定的不利结果出现。但是，该选举制度可能会使选票获得最多的候选人不能当选总统，也可能会造成某几个州的几千张选票直接影响最终选举走向。在选票的统计工作中，还可能会出现作弊。

问题

假如你是李华，你的好朋友唐纳德特朗普已经输掉了 2020 年总统大选。到目前为止特朗普仅获得了 217 张选举人票，而他的对手拜登已经获得了 290 张选举人票。现在你有一次穿越到大选投票之前的机会，请问你该如何建议你的好朋友特朗普，以尽可能帮助他获得大选？

在美国总统大选过程中，最重要的是争取摇摆州。假设每个摇摆州初始状态都是中立的，只要去开展宣传活动就能获得选票，每个州的选举人票数是不一样的，但是票数越多的州需要花费的时间也越多。本次美国大选中特朗普尚未拿下或已经失败的摇摆州有 10 个，具体如表 1 所示。表的第四列是开展宣传活动并拿下该州所需的天数。

表 1. 尚未拿下或已经失败的摇摆州序号州名票数天数1Arizona512Georgia1633Maine514Michigan1635Minnesota1026Nevada617New Hampshire418North Carolina1539Pennsylvania20410Wisconsin102

特朗普要赢得大选，可以在大选投票前去摇摆州开展或增加竞选宣传活动。考虑到特朗普的年龄较大，并且刚刚从新冠中恢复，特朗普总统最多去其中 5 个州开展宣传活动。请问：

如果你只能穿越到大选投票开始前的半个月，在时间有限的情况下，你该怎么安排行程，让特朗普竞选的胜算更大呢？
你至少需要多少时间才能让特朗普转败为胜？即用最短的时间获得 270 张选票。
请为特朗普总统的专机设计飞行路线，使航线距离尽可能短。特朗普总统的专机从华盛顿出发，最终必须回到华盛顿。

模型

问题一：最大票数

在 15 天内，通过选择不超过 5 个摇摆州开展宣传活动，以获得更多的选票，这是一个典型的整数规划问题。令或（ = 1, 2, , 10）分别表示是否去第个州。目标是获得尽可能多的选票，即每个州的宣传活动都需要一定的天数，而去所有州的总天数不能大于 15 天，因此有约束条件：特朗普总统只能去不超过 5 个州开展宣传活动，因此又有约束条件：综上所述，该问题可表述为以下整数规划问题：其中表示第个州的选举人票数，即表 1 中的第三列。表示在第个州开展宣传活动所需的天数，即表 1 中的第四列。应用 MATLAB 中的 intlinprog 函数可以很方便地求解以上整数规划问题，求解程序见附录。求解结果为如图 4 所示，特朗普应该去序号为 2（Georgia）、4（Michigan）、8（North Carolina）、9（Pennsylvania）和10（Wisconsin）的州，刚好需要 15 天，共计能够多获得 77 票。

图 4: 红色州必去，粉色两州二选一

加上特朗普已经获得的 217 票，已经超过了当选总统所需的 270 张选举人票。需要注意的是，序号为 5（Minnesota）和 10（Wisconsin）的州选票数和所需天数完全一样，因此，也可以将上述最优解中的 Wisconsin 州替换为 Minnesota，对于本问题的选举人票数没有影响。但在考虑第三问的最短路径时则会有区别，稍后讨论。

问题二：最小时间

问题二要求用最少的天数，通过选择不超过 5 个摇摆州开展宣传活动，以获得不少于 270 张的选举人票。目前特朗普已经获得的 217 票，因此只需再获得 53 张选举人票。显然，这也是一个典型的整数规划问题：同样应用 MATLAB 中的 intlinprog 函数，我们求解出结果为求解程序见附录。结果如图 5 所示，特朗普应该去序号为 2（Georgia）、4（Michigan）、6（Nevada）、8（North Carolina）的四个州，共需要 10 天。

图 5: 红色州必去，粉色可换成 1/3 和 10

需要注意的是，本问题也有其它解。North Carolina 州具有 15 票，需要 3 天。可将 North Carolina 州替换为序号为 1（Arizona）和 10（Wisconsin）的两个州或序号为 3（Maine）和 10（Wisconsin）的两个州。这种替换，对于本问题的选举人票数没有影响，但要去的州会增加一个。此外，在考虑第三问的最短路径时，这种替换也会有区别，稍后讨论。

问题三：最短路径

上文已经求得了特朗普应该去哪些摇摆州开展宣传活动。考虑到特朗普的年龄和身体，我们希望对特朗普去往各州的路线进行优化。特朗普总统的专机将从华盛顿特区出发，按照一定的顺序依次访问各州。问题要求我们设计出最短的飞行路线，这是典型的 TSP 问题。假设特朗普只到每个州的首府开展宣传活动。我们用节点表示第州的首府，任意两个州的首府距离可表示为地球表面两点的球面距离：其中为地球半径，和表示第州首府的纬度和经度。

令 = { } 为节点集， = {} 为示边权集，则和构成加权无向图 = ( , )。问题转化为寻找中的 Hamilton 回路，使得的总权最小。若用表示是否经过节点和间的路径：则最小 Hamilton 回路问题可用线性规划的方法描述为这里不需要考虑路径的方向，即不必区分和，只考虑其中一个变量即可，不妨只考虑的情况。只要和间存在边，则 = 1（）。第一个约束条件表示每个节点只有一条出弧和入弧。第二个约束条件表示为 0 或 1 的整数变量。第三个约束条件表示任何顶点集的真子集都不构成回路。第三个约束条件很难在程序中表示出来，在使用整数规划求解时可以用以下方法替代：假设采用整数规划的方式求解得到子圈的顶点集 , , , ，则依次执行以下操作直到只含一个圈，即。

增加个不等式约束：重新用整数规划求解。需要注意的是，上式与第三个约束条件的形式和原理都非常相似。
根据整数规划重新求解出的结果，确定解包含的子圈个数，及个子圈的顶点集 , , , 。

根据以上方法，调用 MATLAB 中的 intlinprog 函数，可以高效地求解 TSP 问题。即使节点规模达到 200，程序也在 1 分钟以内完成计算。我们用以上方法对除了 Alaska 和 Hawaii 外的美国所有州为节点的 TSP 问题进行求解，结果如图 6。

图 6: 以美国各州为节点的TSP问题求解

如果特朗普总统有足够的时间，可以考虑按图 6 所示的路径依次访问各州。

接下来，我们将以上最小 Hamilton 回路的求解方法应用到问题一和问题二中，求解程序见附录。对于问题一，我们已经求得特朗普应该去 Georgia、Michigan、North Carolina、Pennsylvania 和 Wisconsin（或 Minnesota）这五个州。经过计算，将Wisconsin 替换为 Minnesota 后的最短路径更短，结果如图 7 所示。

图 7: 问题一的最短路径

对于问题二，特朗普应该去 Georgia、Michigan、Nevada 和 North Carolina 这四个州。可将 North Carolina 州替换为 Arizona 和 Wisconsin 或 Maine 和 Wisconsin。经过计算，特朗普仅去四个州的路径最短，结果如图 8 所示。

图 8: 问题二的最短路径

结论

本文以美国大选为背景，通过整数规划、图论最短路径算法为特朗普设计了大选投票前最佳的竞选活动行程。结果显示，如果特朗普总统最多只能去 5 个州开展宣传活动，在十五天的时间内，应该从华盛顿特区出发，依照 Minnesota Michigan Pennsylvania North Carolina Georgia 的顺序访问这五个州，最后再回到华盛顿特区，飞行路径总长度为 3317 公里。按照我们的假设，特朗普会因此获得这五个摇摆州的 77 张选举人票，并以 294 票的优异成绩连任总统。如果只想用最短的时间获得 270 张选票连任总统，特朗普至少需要 10 天时间，从华盛顿特区出发，依照 Michigan North Carolina Georgia Nevada 的顺序访问这四个州，最后再回到华盛顿特区，飞行路径总长度为 7880 公里。

附录

点击文章左下角“阅读原文”获取本文 PDF 版和附件。

参考资料

[1]

CNN. Presidential results, 2020: https://edition.cnn.com/election/2020/results/president

[2]

USAGov. Presidential election process, 2020: https://www.usa.gov/election

[3]

Christopher Tao. Using dynamic planning to help trump win the elections, 2020: https://towardsdatascience.com/using-dynamic-planning-to-help-trump-win-the-elections-7b5b34f63961

[4]

MathWorks. Traveling salesman problem, 2020: https://www.mathworks.com/help/optim/ug/travelling-salesman-problem.html

[5]

Cleve Moler. Usa traveling salesman tour, 2018: https://blogs.mathworks.com/cleve/2018/09/17/usa-traveling-salesman-tour