生成一个塔防御迷宫（最长的迷宫与有限的墙壁） – 近乎最佳的启发式？
在一个塔防游戏中，你有一个NxM网格，有一个开始，一个完成和一些墙。
敌人从起点到终点都走最短的路，而不经过任何的墙（它们通常不会被限制在网格中，但是为了简单起见，我们假设它们是无论如何都不能穿过对angular的“洞”）
问题（至less对于这个问题）是放置K个额外的墙壁，以最大化敌人必须采取的path。 例如，对于K = 14
我的直觉告诉我，如果（正如我所希望的那样）这个问题是NP难的，我们把这个问题推广到包括在到达终点之前必须访问的路点，也可能没有路点。
但是， 有没有什么像样的启发式algorithm可以接近最优解？
[编辑]我在这里发布了一个相关的问题。
它可以很容易地显示（certificate让读者作为一个练习），足以search解决scheme，使每个K封锁都放在当前的最小长度路线上。 请注意，如果有多个最小长度的路由，那么他们都必须考虑。 原因是如果你不在当前的最小长度路线上放置任何剩余的封锁，那么它不会改变; 因此您可以在search过程中立即将第一个可用的封锁。 这甚至可以加速search。
但是还有更多的优化。 你也可以总是决定把下一个封锁放在当前最小长度路线上的第一个封锁，也就是说，如果你把封锁放在路线的第10个方格上，那么你就把方块标记为1 .9作为“永久开放”，直到你回溯。 这再次节省了在回溯search期间search的指数数量的正方形。
然后，您可以应用启发法来减lesssearch空间或对其进行重新sorting，例如，首先尝试那些增加当前最小长度路线长度的封锁布局。 然后，您可以运行有限的实时回溯algorithm，并select迄今为止find的最佳解决scheme。
我提出了一个贪婪的方法，它可能接近最优（但我找不到近似因子）。 想法很简单，我们应该阻止在迷宫的关键地方的细胞。 这些地方可以帮助测量迷宫的连通性。 我们可以考虑顶点的连通性，并且我们find最小的顶点切割，它将开始和结束断开： （s，f） 。 之后，我们删除一些关键细胞。
把它变成graphics，采取迷宫的双重。 在此图上查找最小（s，f）顶点切割。 然后我们检查这个切割中的每个顶点。 我们删除一个顶点，它的删除增加了所有s，fpath的长度，或者如果它在从s到f的最小长度path中。 消除一个顶点后，recursion地重复上述过程k时间。
但有一个问题，这是当我们删除一个顶点，切割任何path从f到f。 为了防止这种情况，我们可以尽可能的加权切割节点，意思是先计算最小（s，f）切割，如果切割结果只是一个节点，则对其进行加权并设置一个高度为n ^ 3的权重计算以前计算中的最小s，f切，单切顶点由于等待而不属于新切。
但是，如果s，f之间只有一条path（经过一些迭代），我们不能改进它。 在这种情况下，我们可以使用正常的贪婪algorithm，例如从s到f中不属于任何剪切的最短path中的一个删除节点。 之后我们可以处理最小的顶点切割。
每一步运行时间的algorithm是：
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），所以该algorithm为O（k n ^ 4），但通常不会超过O（k n ^ 3） ，因为通常min-cutalgorithm支配path寻找，通常path寻找也不需要O（n ^ 2）。
我猜贪婪select是模拟退火algorithm的一个很好的起点。
PS：最小顶点切割类似于最小切割边缘 ， 类似的方法，如最大stream/最小切割可以应用于最小顶点切割 ， 假设每个顶点为两个顶点 ， 一个V i ， 一个V o ， 意味着input和输出 ， 也将无向图转换为有向图不难。
我相信我们可以将包含的最大stream形问题减less到布尔可满足性，并通过对这个子问题的任何依赖来显示NP完全性。 正因为如此， spin_plate提供的algorithm是合理的，因为启发式algorithm， 预计算和机器学习是合理的 ，如果我们希望在这里前进，我们的诀窍就是find最好的启发式解决scheme。
考虑一下如下的棋盘：
..S........ #.#..#..### ........... ........... ..........F
这有许多问题导致贪婪和门禁解决scheme失败。 如果我们看第二行：
#.#..#..###
我们的逻辑门在基于0的二维数组中sorting为[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
而我们隐藏的布尔关系属于所有这些门。 你也可以certificate，几何certificate不能recursion分形，因为我们总是可以创build一个正好是N-1宽度或高度的墙，这在所有情况下都是解决scheme的关键部分（因此，帮助你）。
此外，由于不同行的扰动是显着的：
..S........ #.#........ ...#..#.... .......#..# ..........F
我们可以certificate，如果没有一套完整的可计算的几何身份标识，完整的search空间会自动减less到N-SAT。
通过扩展，我们还可以certificate，当门数接近无穷大时，这是微不足道的validation和非多项式解决。 毫不奇怪，这就是为什么塔防游戏对于人类来说仍然非常有趣。 显然，一个更严格的certificate是可取的，但这是一个骨架的开始。
请注意，您可以显着减lessnselect-k关系中的n项。 因为我们可以recursion地显示每个扰动必须位于关键path上，并且因为关键path总是可以在O（V + E）时间内计算（通过几次优化来加速每个扰动），所以可以显着减lesssearch空间的代价是广度优先search添加到电路板的每个附加塔。
因为我们可以容忍地假定O（n ^ k）为确定性的解决scheme，所以启发式方法是合理的。 因此，我的build议就落在了spin_plate 的答案和Soravux 的答案之间，并且着眼于适用于这个问题的机器学习技术。
第0个解决scheme：使用一个可容忍的但是次优的AI，其中spinning_plate提供了两个可用的algorithm。 事实上，这些大概有多less个天真的玩家靠近这个游戏，而这对于简单的游戏来说应该是足够的，尽pipe具有高度的可利用性。
一阶解决scheme：使用数据库。 考虑到问题的表述，您还没有完全certificate需要即时计算最佳解决scheme。 因此，如果我们放松接近无信息板的约束，我们可以简单地预先计算每块板所有K的最优值。 显然，这只适用于less数几个板子：用V! 对于每个configuration的潜在的电路板状态，当V变得非常大时，我们不能容忍地预先计算所有的最佳值。
二阶解决scheme：使用机器学习步骤。 促进每一步，因为你缩小了差距，导致非常高的遍历成本，运行直到你的algorithm收敛或没有更多的最佳解决scheme比贪婪。 在这里可以使用过多的algorithm，所以我build议追逐经典和文献来select正确的，在你的程序的限制范围内工作。
最好的启发式可能是由本地状态感知的recursion深度优先遍历生成的一个简单的热图 ，在O（V ^ 2）遍历之后，将结果按大部分sorting到最不常见的遍历。 通过这个输出进行贪婪地识别所有的瓶颈，并且这样做不会使path不可能完全是可能的（检查这是O（V + E））。
把它放在一起，我会尝试这些方法的交集，结合热图和关键path标识。 我想这里有足够的东西来提出一个好的，function的几何certificate，满足所有的问题约束。
说明明显的风险，这里有一个algorithm
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），但是只需重新计算部分path，你可以稍加改进2。
正如你所提到的，简单地试图打破这条道路是困难的，因为如果大多数断裂只是增加1（或2）的长度，就很难find导致巨大收益的阻塞点。
如果您在开始和结束之间采取最小的顶点切割 ，您将find整个graphics的阻塞点。 一个可能的algorithm是这样的
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）是很大的一部分，为什么这个algorithm也可能performance不佳。 你也可以试试
- 与其他现有块连接的最小节点集。
- 查找顶点切割中的所有连续顶点的分组，testing它们中的每一个以获得第一个algorithm的最长path
最后一个可能是最有希望的
如果在整个图中find最小顶点，那么您将find整个图的瓶颈点。
这是一个想法。 在您的网格中，将相邻的墙壁分组成岛屿，并将每个岛屿视为graphics节点。 节点之间的距离是连接它们所需要的最less数量的墙（阻挡敌人）。
在这种情况下，您可以通过阻止最便宜的弧开始最大化path长度。
我不知道这是否会奏效，因为你可以用你的观点来制造新的岛屿。 但它可以帮助找出墙壁的位置。
我build议使用带有K长度优先级队列的修改后宽度优先search来跟踪每个岛之间的最佳Kpath。
我会为每个连接墙的岛屿假装它是一个光。 （只能发出水平和垂直光线的特殊光线）
使用光线跟踪来查看光线可以击中的其他岛屿
说Island1（i1）击中i2，i3，i4，i5，但不击中i6，i7 ..
那么你会有行（i1，i2），行（i1，i3），行（i1，i4）和行（i1，i5）
将所有网格点的距离标记为无穷大。 将起点设置为0。
现在就从头开始使用广度优先search。 每个网格点，将该网格点的距离标记为其邻居的最小距离。
但是..这是抓住..
每次到达两个岛屿之间的一条线（）上的一个网格点，而不是将距离logging为其邻居的最小值，而是将其作为长度为K的优先级队列。loggingK个最短path从任何其他行（）s到该行（）
然后，这个优先级队列保持不变，直到到达下一行（），在那里它聚合了进入该点的所有优先级问题。
你还没有显示这个algorithm需要实时，但我可能是错误的这个预算。 然后，您可以预先计算块的位置。
如果你事先能做到这一点，然后简单地让人工智能build立迷宫岩石，就好像它是一种树木一样，你可以使用遗传algorithm来减轻你对启发式的需求。 您将需要加载任何种类的遗传algorithm框架，从不可移动块（您的地图）和随机放置的可移动块（AI将放置的块）开始。 然后，通过在可移动块上进行交叉和变换来演变人口，然后通过对计算的最长path给予更多奖励来评估个体。 那么你只需要编写一个资源有效的path计算器，而不需要在代码中启发式。 在你进化的最后一代，你会select排名最高的个人，这将是你的解决scheme，因此你想要的地图块模式。
遗传algorithm被certificate在理想的情况下，在合理的时间内把你带到一个局部最大值（或最小值），这对于一个足够大的数据集（即在你的情况下足够大的地图）的分析解决scheme来说是不可能达到的。
你没有说明你将要开发这种algorithm的语言，所以我不能提出完全适合你的需求的框架。
请注意，如果你的地图是dynamic的，这意味着地图可能会改变塔防迭代，你可能想要避免这种技术，因为它可能太密集，不能在每个波浪重新发展一个新的人口。
我根本不是一个algorithm专家，但是看网格让我怀疑康威的生活游戏是否可能对此有用。 用合理的初始种子和精心挑选的塔楼生死规则，你可以在很短的时间内尝试许多种子和后代。
你已经有了一定程度的适应性，因此你可以select最好的一个。 我不知道如何（如果有的话）这将近似最好的path，但在解决scheme中使用它将是一件有趣的事情。
