| 123456789101112131415161718192021222324 |
- 哈密尔顿回路：
- 假设初始时有 A 、 B 两位玩家，他们分别位于两个孤岛上。玩家 B 有非常多的地面兵力，但没有空中单位，并且已有资源为 0 ，而且还没有任何经济来源。他只能坐等玩家 A 来攻打他。玩家 A 一开始则完全没有兵力，但他有不少可以生产作战单位的建筑，也有一定的经济来源，理论上有获胜的希望。地图上还有第三个孤岛，孤岛周边放满 B 的对空防御，玩家 A 即使派遣空中部队也无法进入该孤岛。
- 初始时，玩家 A 的资源刚好够造一个农民，玩家 A 还需要收集额外的 x 个单位的资源才足以消灭玩家 B 。但是，玩家 A 的所有可采集资源都在第三个孤岛上。这个孤岛上有 n 个采矿点，每个采矿点都配备有一个基地，以及 x/n 个单位的矿石资源。每个采矿点也都还预先配备了一个农民，只不过这个农民被矿石围在里面出不来了。采矿点与采矿点之间靠一些小路连接，每条路上都有玩家 B 的防御塔，保证一个农民走过去必死无疑，但是两个农民走过去恰好能活一个。
- 游戏开始后，玩家 A 唯一获胜的途径便是，在某个采矿点建造一个农民，采完这个采矿点的矿，把被困的农民救出来，然后选择某条小路走到下一个采矿点（途中死掉一个农民），继续采矿并解救农民，以此类推，直到走遍每一个采矿点，采完所有的矿。很容易看到，玩家 A 相当于要解决一个 Hamilton 路的问题（注意，即使平面图的 Hamilton 路问题也是 NP-complete 的）。因此，星际争霸是 NP-hard 的。
- 最小点集覆盖：
- 基本思想是每条边转成一玩家 A 的士兵, 每个顶点有一玩家 B 的基地
- 玩家 A 只能坐以待毙, 玩家 B 则刚好有生产 k 个军队的资源，从某个顶点生产的军队只能杀掉与它相邻的边上的士兵
- TSP问题：
- N个矿区，每个矿区都有若干矿和一个基地，有一个兵营
- 一开始的资源刚好够造一个农民，人口限制只能再造一个单位
- 对手有且只有刚好可以打败两个农民但是打不过一个农民+一个士兵的兵力，所以对手在一开始就全力往你这边冲来，且会在T时间后到达
- 背包问题：
- B坐以待毙，A有M架运输机和足够的农民，A还需一定资源才能打败B
- 所有的资源分布在N个孤岛，上每个孤岛上都有一个A的基地和B的若干防空塔，进入第i个孤岛会被消灭Ai架运输机，岛上有Bi的资源
- 子集问题：
- A有一架运输机，一架战斗机和一个步兵，B位于一个长条形孤岛，AB间有一定距离
- B是人族，没有资源，有很多大小不一的建筑（一开始都是飞行状态）
- B唯一的求和的办法是用建筑填满孤岛，使A的步兵无法降落
|
