在塔防游戏中，您有一个 NxM 网格，其中包含开始、结束和许多墙。
敌人在不穿过任何墙壁的情况下从头到尾采用最短路径（它们通常不受网格的限制，但为了简单起见，假设它们是。在任何一种情况下，它们都不能穿过对角线“洞”）
问题（至少对于这个问题）是放置多达K 个额外的墙，以最大化敌人必须走的路径。例如，对于 K=14
我的直觉告诉我，如果（正如我希望的那样）我们将其概括为包括在移动到终点之前必须访问的航点，并且可能也没有航点，那么这个问题是 NP 难的。
但是，对于接近最优的解决方案，是否有任何体面的启发式方法？
[编辑]我在这里发布了一个相关的问题。
我提出了一种贪婪的方法，它可能接近最优（但我找不到近似因子）。想法很简单，我们应该封锁迷宫关键位置的细胞。这些地方可以帮助测量迷宫的连通性。我们可以考虑顶点连通性，我们找到断开起点和终点的最小顶点切割：(s,f)。之后，我们删除了一些关键单元格。
要将其转换为图表，请使用双迷宫。在此图上找到最小(s,f)顶点切割。然后我们检查这个切割中的每个顶点。我们删除一个顶点，它的删除会增加所有s,f路径的长度，或者如果它在从 s 到 f 的最小长度路径中。消除一个顶点后，递归重复上述过程k次。
但这有一个问题，这是当我们删除一个顶点时，它会切断从 s 到 f 的任何路径。为了防止这种情况，我们可以将切割节点的权重尽可能高，这意味着首先计算最小 (s,f) 切割，如果切割结果只是一个节点，则对其进行加权并为该顶点设置一个高权重，如 n^3，现在再次计算最小s,f割，之前计算的单割顶点因为等待不属于新割。
但是如果 s,f 之间只有一条路径（经过一些迭代），我们就无法改进它。在这种情况下，我们可以使用正常的贪心算法，例如从不属于任何切割的从 s 到 f 的最短路径之一中删除节点。之后我们可以处理最小顶点切割。
每一步的算法运行时间为：
min-cut + path finding for all nodes in min-cut
O(min cut) + O(n^2)*O(number of nodes in min-cut)
并且因为在非常悲观的情况下，最小切割中的节点数不能大于 O(n^2)，所以算法是 O(k n^4)，但通常不应该超过 O(k n^3) ，因为通常最小切算法主导寻路，所以通常寻路也不需要 O(n^2)。
我猜贪心选择是模拟退火类型算法的一个很好的起点。
PS: minimum vertex cut 与 minimum edge cut类似，max-flow/min-cut 类似的方法可以应用于 minimum vertex cut，只需假设每个顶点为两个顶点，一个 V i，一个 V o，表示输入和输出，也将无向图转换为有向图并不难。
可以很容易地证明（证明让读者作为练习）搜索解决方案就足够了，以便将 K 个封锁中的每一个都放在当前的最小长度路线上。请注意，如果有多个最小长度路线，则必须考虑所有这些路线。原因是，如果您不在当前最小长度路线上设置任何剩余的封锁，那么它不会改变；因此，您可以在搜索期间立即对其进行第一个可用的封锁。这甚至可以加速蛮力搜索。
但是还有更多的优化。您也可以随时决定放置下一个封锁线，使其成为当前最短长度路线上的第一个封锁线，也就是说，如果您将封锁线放置在路线上的第 10 个方格上，那么您将方格标记为 1 ..9 作为“永久开放”，直到您回溯。这再次节省了在回溯搜索期间搜索的指数数量的正方形。
然后，您可以应用启发式方法来减少搜索空间或对其重新排序，例如首先尝试那些最大程度地增加当前最小长度路线长度的封锁位置。然后，您可以在有限的实时时间内运行回溯算法，并选择迄今为止找到的最佳解决方案。
我相信我们可以将包含的最大流形问题简化为布尔可满足性，并通过对这个子问题的任何依赖来显示 NP 完全性。正因为如此，提供的算法 spin_plate是合理的，因为启发式、预计算和机器学习是合理的，如果我们想在这里犯错，诀窍就变成了找到最佳的启发式解决方案。
考虑如下所示的电路板：
..S........
#.#..#..###
...........
...........
..........F
这有许多导致贪婪和门限解决方案失败的问题。如果我们看第二行：
#.#..#..###
我们的逻辑门在基于 0 的二维数组中排序为[row][column]：
[1][4], [1][5], [1][6], [1][7], [1][8]
我们可以将其重新渲染为一个方程以满足该块：
if ([1][9] AND ([1][10] AND [1][11]) AND ([1][12] AND [1][13]):
traversal_cost = INFINITY; longest = False # Infinity does not qualify
除了无穷大作为不可满足的情况外，我们回溯并将其重新呈现为：
if ([1][14] AND ([1][15] AND [1][16]) AND [1][17]:
traversal_cost = 6; longest = True
我们隐藏的布尔关系属于所有这些门。您还可以证明几何证明不能递归分形，因为我们总是可以创建一个N-1宽度或高度正好长的墙，这在所有情况下都代表解决方案的关键部分（因此，分而治之不会帮助你）。
此外，由于不同行之间的扰动很重要：
..S........
#.#........
...#..#....
.......#..#
..........F
我们可以证明，如果没有一套完整的可计算几何恒等式，完整的搜索空间会减少到 N-SAT。
通过扩展，我们还可以证明，当门的数量接近无穷大时，验证和非多项式求解是微不足道的。不出所料，这就是为什么塔防游戏对人类来说仍然如此有趣的原因。显然，更严格的证明是可取的，但这只是一个初步的开始。
请注意，您可以显着减少 n-choose-k 关系中的 n 项。因为我们可以递归地证明每个扰动都必须位于关键路径上，并且因为关键路径总是可以在 O(V+E) 时间内计算（通过一些优化来加快每个扰动的速度），所以您可以显着减少您的以广度优先搜索添加到板上的每个附加塔为代价来搜索空间。
因为我们可以容忍地假设 O(n^k) 作为确定性解决方案，所以启发式方法是合理的。因此，我的建议介于spin_plate的答案和Soravux的答案之间，着眼于适用于该问题的机器学习技术。
第 0 种解决方案：使用可容忍但次优的 AI，其中 spin_plate 提供了两种可用的算法。事实上，这些近似于有多少天真的玩家接近游戏，这对于简单的游戏来说应该足够了，尽管具有高度的可利用性。
一阶解决方案：使用数据库。鉴于问题的表述，您还没有完全证明需要即时计算最佳解决方案。因此，如果我们放宽在没有信息的情况下接近随机棋盘的约束，我们可以简单地预先计算K每个棋盘的所有可容忍的最优值。显然，这只适用于少数板：V!对于每种配置的潜在板状态，我们不能容忍地预先计算所有最优值，因为它V变得非常大。
二阶解决方案：使用机器学习步骤。当你缩小导致非常高的遍历成本的差距时，推动每一步，一直运行直到你的算法收敛或找不到比贪心算法更好的解决方案。此处适用的算法过多，因此我建议您参考经典和文献，以选择在您的程序约束范围内有效的正确算法。
最好的启发式方法可能是由局部状态感知、递归深度优先遍历生成的简单热图，在 O(V^2) 遍历之后按最常见到最不常见的遍历对结果进行排序。通过这个输出贪婪地识别所有瓶颈，并且这样做而不会使路径变得不可能是完全可能的（检查这是 O(V+E)）。
把它们放在一起，我会尝试这些方法的交集，结合热图和关键路径标识。我假设这里有足够的东西来提出一个好的、功能性的几何证明来满足问题的所有约束。
冒着说明显而易见的风险，这是一种算法
1) Find the shortest path
2) Test blocking everything node on that path and see which one results in the longest path
3) Repeat K times
天真地，这将花费 O(K*(V+ E log E)^2) 但您只需重新计算部分路径即可通过一些小工作改进 2。
正如您所提到的，简单地尝试打破路径是很困难的，因为如果大多数中断只是增加 1（或 2）的长度，那么很难找到导致大收益的阻塞点。
如果你在开始和结束之间取最小顶点切割，你会发现整个图形的阻塞点。一种可能的算法是这样的
1) Find the shortest path
2) Find the min-cut of the whole graph
3) Find the maximal contiguous node set that intersects one point on the path, block those.
4) Wash, rinse, repeat
3）是很重要的部分，为什么这个算法也可能表现不佳。你也可以试试
最后一个可能是最有希望的
如果您在整个图上找到一个最小顶点切割，您将找到整个图的阻塞点。
这是一个想法。在您的网格中，将相邻的墙分组为岛屿，并将每个岛屿视为一个图形节点。节点之间的距离是连接它们（阻挡敌人）所需的最小墙数。
在这种情况下，您可以通过阻止最便宜的弧来开始最大化路径长度。
我不知道这是否可行，因为您可以使用您的积分制作新的岛屿。但它可以帮助确定在哪里放置墙壁。
我建议使用修改后的广度优先搜索和 K 长度优先级队列来跟踪每个岛之间的最佳 K 条路径。
对于每一个连接墙壁的岛屿，我会假装它是一盏灯。（一种只能发出水平和垂直光线的特殊灯）
使用光线追踪查看光线可以照射到哪些其他岛屿
说 Island1 (i1) 命中 i2,i3,i4,i5 但没有命中 i6,i7 ..
那么你会有 line(i1,i2), line(i1,i3), line(i1,i4) 和 line(i1,i5)
将所有网格点的距离标记为无穷大。将起点设为 0。
现在从一开始就使用广度优先搜索。每个网格点，将该网格点的距离标记为其邻居的最小距离。
但是..这是问题所在..
每次到达两个岛之间的 line() 上的网格点时，不需要将距离记录为其邻居的最小值，而是需要将其设为长度为 K 的优先级队列。并记录 K 最短路径从任何其他 line() 到该 line()
然后，此优先级队列保持不变，直到您到达下一行（），它汇总了进入该点的所有优先级队列。
您没有表明该算法需要实时性，但我对这个前提可能是错误的。然后，您可以预先计算块位置。
如果您可以事先做到这一点，然后简单地进行 AI构建就像一棵树一样，一个又一个的迷宫，你可以使用遗传算法来减轻你对启发式的需求。您需要加载任何类型的遗传算法框架，从一组不可移动的块（您的地图）和随机放置的可移动块（AI 将放置的块）开始。然后，您通过在可移动块上进行交叉和嬗变来进化种群，然后通过对计算出的最长路径给予更多奖励来评估个体。然后，您只需编写一个资源高效的路径计算器，而无需在代码中使用启发式方法。在你进化的最后一代中，你会选择排名最高的个体，这将是你的解决方案，因此你想要这张地图的方块模式。
事实证明，在理想情况下，遗传算法可以在合理的时间内将您带到局部最大值（或最小值），这可能无法通过在足够大的数据集（即您的情况下足够大的地图）上的分析解决方案来达到。
您还没有说明您将使用哪种语言开发此算法，因此我无法提出可能完全适合您需求的框架。
请注意，如果您的地图是动态的，这意味着地图可能会随着塔防迭代而发生变化，您可能希望避免使用这种技术，因为它可能过于密集而无法在每一波中重新进化一个全新的人口。
我根本不是算法专家，但看着网格让我想知道康威的人生游戏是否可能对此有用。有了合理的初始种子和精心挑选的关于塔的诞生和死亡的规则，您可以在短时间内尝试许多种子及其后代。
您已经对小兵路径的长度进行了衡量，因此您可以相应地选择最佳的。我不知道（如果有的话）它会接近最佳路径，但在解决方案中使用它会是一件有趣的事情。