将弓箭手放在墙上

Question

我有一个矩阵(0和1),代表城墙和周围环境.

我的任务是将n弓箭手以某种方式放在墙上,以便尽可能多地覆盖环境.有两个规则:

1:每个射手的射程都是1 - 这意味着他只能射击相邻的瓷砖(每个瓷砖有8个邻居),这些不是墙壁(这支军队禁止友军火力!).

2:如果发生这种情况,那么多个弓箭手可以在同一个瓦片上射击,那个瓦片只计为一个.

我正在努力为此找到有效的解决方案 - 部分是因为我不知道,如果在多项式时间内存在任何问题.有没有？

我猜第一步是使用BFS算法对矩阵上的每个瓦片进行评级,但我不知道如何用第二个规则有效地解决它.蛮力解决方案非常简单 - 对每个位置进行评级,然后尝试所有这些,这将是非常非常无效的 - 我认为O(|可能的位置| ^ n),这是不好的.

简单的例子:

灰色的瓷砖代表墙壁.瓷砖内的数字表示放置在该瓷砖上的射手的覆盖范围.可以肯定的是,我添加了橙色,代表了位于瓷砖b2上的弓箭手的覆盖范围.最后的信息 - 正确的解决方案是b2和b6,覆盖率为14.它不能是b2和b4,因为它们只覆盖了11个区块.

Answer 1

我没有看到如何在保证多项式时间内解决问题,但您可以将问题表达为整数线性程序,可以使用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]).

例如,假设这是地图(.周围的地方和#城堡墙),并且想要放置两个弓箭手.

....
.###
....

然后我们有这个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]