我有一个矩阵(分别为0和1)，代表城堡的城墙及其周围环境。
我的任务是以某种方式将n弓箭手放在墙上，使他们尽可能地覆盖周围的环境。有两个规则:
1 :每个弓箭手的射程均为1-也就是说，他只能在相邻的地砖(每个地砖有8个邻居)上射击，而该地不是墙(这支军队禁止友好射击!)。
2 :如果发生这种情况，则多个弓箭手可以在同一块地上射击，该地块仅算作一个。
我正在努力寻找有效的解决方案-部分原因是我不知道多项式时间是否存在。 有吗？
我想第一步是使用BFS算法对矩阵上的每个图块进行评分，但是我不知道如何用第二条规则有效地解决它。蛮力解决方案非常简单-给每个位置评分，然后尝试所有位置，这将是非常无效的-我认为O(|可能的位置| ^ n)不好。
简单示例:
灰色瓷砖代表墙壁。磁贴中的数字表示放置在该磁贴上的弓箭手的覆盖范围。可以肯定的是，我添加了橙色的那些，它们代表了站在b2上的弓箭手的覆盖范围。最后一个信息-对此的正确解决方案是b2和b6，覆盖范围为14。它不能是b2和b4，因为它们仅覆盖11个图块。
最佳答案
我看不到如何在保证的多项式时间内解决问题，但是您可以将问题表达为整数线性程序，可以使用ILP求解器(例如GLPK)来解决。
令c[i]为0-1整数变量，周围的每平方代表一个整数。这些将代表该广场是否至少被一个弓箭手覆盖。
令a[i]为0-1整数变量，城堡墙的每平方一个。这些将代表弓箭手是否站在这个广场上。
最多必须有n弓箭手:sum(a[i] for i in castle walls) <= n
如果没有相邻的弓箭手，则c[i]必须为零:sum(a[j] for j castle wall adjacent to i) >= c[i]
优化目标是最大化sum(c[i])。
例如，假设这是 map (其周围是.和#城堡墙)，并且想要放置两个弓箭手。
....
.###
....
然后我们有这个ILP问题，其中所有变量都是0-1整数变量。
maximize (
c[0,0] + c[0,1] + c[0,2] + c[0,3]
+ c[1,0]
+ c[2,0] + c[2,1] + c[2,2] + c[2,3])
such that:
a[1,1] + a[1,2] + a[1,3] <= 2
c[0,0] <= a[1,1]
c[0,1] <= a[1,1] + a[1,2]
c[0,2] <= a[1,1] + a[1,2] + a[1,3]
c[0,3] <= a[1,2] + a[1,3]
c[1,0] <= a[1,1]
c[2,0] <= a[1,1]
c[2,1] <= a[1,1] + a[1,2]
c[2,2] <= a[1,1] + a[1,2] + a[1,3]
c[2,3] <= a[1,2] + a[1,3]
关于algorithm - 将弓箭手放在墙上，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36833838/