哪吒机器人提醒：
提醒：Matrix67: My Blog
【标题】经典证明：星际争霸是NP-hard的
【摘要】 今天看到这里给出了一个“星际争霸是 np-hard 问题”的一个证明。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 np-hard 的。当然，考虑到即时战略游戏的复杂性，这个结论并不出人意料；真正有趣的，则是如何巧妙地利用游戏中的元素，构造出极其精巧的初始局面，从而转化成某个已知的 np-complete 问题。下面是原文中给出的证明。这个证明有没有什么漏洞？你还能想到哪些别的证明方法？欢迎在下面留言一同分享。 假设初始时有 a 、 b 两位玩家，他们分别位于两个孤岛上。玩家 b 有非常多的地面兵力，但没有空中单位，并且已有资源为 0 ，而且还没有任何经济来源。他只能坐等玩家 a 来攻打他。玩家 a 一开始则完全没有兵力，但他有不少可以生产作战单位的建筑，也有一定的经济来源，理论上有获胜的希望。地图上还有第三个孤岛，孤岛周边放满 b 的对空防御，玩家 a 即使派遣空中部队也无法进入该孤岛。 初始时，玩家 a 的资源刚好够造一个农民，玩家 a 还需要收集额外的 x 个单位的资源才足以消灭玩家... (01-28 10:43)
手机哪吒网 m.iNezha.com 有人网