Non-Disjunct 网格上二维正方形的矩形边缘覆盖
Non-Disjunct Rectangle Edge Covering for 2D Squares on a Grid
尽管标题听起来很复杂，但我的实际问题应该不难建模。但是，我一直无法找到一个好的算法来执行以下操作：
我想用固定数量 n 个矩形覆盖网格上的一组正方形。这些矩形可以重叠，它们只需要覆盖我形状的外边缘。
为什么不Brute-Force？
正方形 m x m 网格上不同矩形的数量为
.
因此 brute-force-approach 必须尝试的组合数在
对于 10 x 10 网格，只有 27,680,640,625 组合74=]3 个矩形。
例子
上面有一些正方形的初始网格可能如下所示：
n = 1：用单个矩形覆盖此形状的最佳方法是：
n = 2: 使用两个矩形可以减少被覆盖的空方块的数量：
（注意中心现在被两个矩形覆盖了）
有效封面
我正在寻找一种解决方案，该解决方案至少覆盖所有属于外边缘的正方形，即所有在网格宽度上共享边缘的填充正方形是一个空正方形。
不属于形状外边缘的所有正方形可能会被覆盖，也可能不会被覆盖，覆盖的矩形可能会相交，也可能不会相交。
目标函数
给定固定数量的覆盖矩形 n，我想覆盖所有填充的方块，但尽量减少覆盖的空方块的数量 在形状之外。这意味着中心的空方块不应计入必须最小化的目标函数（我也可以在应用算法之前填充所有孔而不会产生影响）。
因此，我的示例的目标函数的值为：
n | target function
---|-----------------
1 | 11
2 | 3
附加约束
请注意，原始正方形集可能 未连接 并且 non-connected 子形状的数量甚至可能超过覆盖矩形的数量。
替代说明
为了简化问题，您也可以只处理输入数据的转换版本：
然后目标是覆盖所有蓝色方块，并使用 n 个可能相交的矩形来尽量减少被覆盖的白色方块的数量。
不是一个完整的解决方案，但有一些（optimality-preserving-under-certain-conditions）减少规则：
- 如果您想要一个完全没有白色方块被覆盖的解决方案，那么您可以安全地合并任何相邻的相同行或列对。这是因为对于不包含任何白色方块的较小合并问题的任何有效解决方案都可以通过 "stretching" 以与执行合并相反的顺序跨每条合并线的每个矩形扩展为原始问题的解决方案 -这不会导致任何未覆盖的白色方块被覆盖，任何蓝色方块被覆盖，或改变所需的矩形数量。根据 "curvy" 原始图像的大小，这可以大大减少输入问题的大小。 （即使对于覆盖白色方块的解决方案，您仍然可以应用此策略——但是 "expanded" 解决方案可能会覆盖比原始解决方案更多的白色方块。作为启发式方法仍然有用。）
您可以通过将 already-placed 矩形覆盖的所有单元格（无论它们最初是蓝色还是白色）变为粉红色来表示任何部分解决方案；粉红色单元格是可能被（更多）矩形免费覆盖但不需要覆盖的单元格。如果您正在寻找一个完全没有白色方块被覆盖的解决方案，您可以应用规则 1 的加强形式来缩小实例：您不仅可以像以前一样合并相同的相邻行和列对，您可以先根据以下规则将一些粉红色单元格更改为蓝色，这可能会导致更多合并发生。两个相邻列的规则是：如果第 1 列中的每个白色单元格在第 2 列中也是白色的，反之亦然，那么在包含一个粉色和一个蓝色单元格的每一行中，您可以将粉色单元格更改为蓝色。 （基本原理：某些 non-white-cell-covering 矩形最终必须覆盖蓝色单元格；该矩形也可以拉伸以覆盖粉色单元格，而不覆盖任何新的白色单元格。）示例：
WW WW W
BB BB B
BP --> BB --> B
PP PP P
PB BB B
您永远不需要考虑一个矩形，该矩形是不覆盖任何白色单元格的矩形的真子矩形。
一些进一步的想法：
简单地将图像调整为较小的尺寸，其中新高度是原始高度的整数倍，宽度也类似，并且当且仅当原始图像中相应单元格块中的任何单元格都是蓝色的是蓝色的，应该给出一个很好的近似子问题，它更容易解决。 （如有必要，用白色单元格填充原始图像。）解决这个较小的问题并将解决方案重新扩展到原始大小后，您可以 trim 一些矩形边缘的更多行或列。
我想提出一个不同的问题：
假设你有三个孤立的正方形，有什么可能性：
一个矩形覆盖所有三个
两个矩形，有 3 种可能性覆盖 2 +1
和三个矩形各占一个
所以顺序是Sum_in_choose_i
比您的订单小很多
在任何情况下都是 n 的多项式而不是指数。
然后你可以 trim 写下你的解决方案（顺便说一下，这是相互矛盾的：矩形越少越好，空单元格越少越好，但你可以解决这个问题）
嗯，我还没有想到 P-class 解决方案，但我确实想到这个问题可能是随机解决方案的一个很好的候选者。
值得注意的是，有一个 easily-defined 可行的起点：只需将所有覆盖矩形设置为目标方块边界框的范围即可。
从这个初始状态开始，可以通过缩小覆盖矩形的边界之一并检查所有目标方块是否仍然被覆盖来生成新的有效状态。
此外，任意两个状态之间的路径可能很短（每个矩形可以在O(√n)时间内缩小到合适的尺寸，其中n 是边界框中的方块数），这意味着很容易在搜索中移动 space。尽管这伴随着一些可能的解决方案被返回初始状态的狭窄路径分隔的警告，这意味着重新运行我们将要开发的算法几次可能是好的。
鉴于上述情况，simulated annealing 是解决该问题的可能方法。以下 Python 脚本实现了它：
#!/usr/bin/env python3
import random
import numpy as np
import copy
import math
import scipy
import scipy.optimize
#Generate a grid
class Grid:
def __init__(self,grid_array):
self.grid = np.array(grid_array)
self.width = len(self.grid[0]) #Use inclusive coordinates
self.height = len(self.grid) #Use inclusive coordinates
#Convert into a list of cells
self.cells = {}
for y in range(len(self.grid)):
for x in range(len(self.grid[y])):
self.cells[(x,y)] = self.grid[y][x]
#Find all cells which are border cells (the ones we need covered)
self.borders = []
for c in self.cells:
for dx in [-1,0,1]: #Loop through neighbors
for dy in [-1,0,1]:
n = (c[0]+dx,c[1]+dy) #This is the neighbor
if self.cells[c]==1 and self.cells.get(n, 1)==0: #See if this cell has a neighbor with value 0. Use default return to simplify code
self.borders.append(c)
#Ensure grid contains only valid target cells
self.grid = np.zeros((self.height,self.width))
for b in self.borders:
self.grid[b[1],b[0]] = 1
self.ntarget = np.sum(self.grid)
def copy(self):
return self.grid.copy()
#A state is valid if the bounds of each rectangle are inside the bounding box of
#the target squares and all the target squares are covered.
def ValidState(rects):
#Check bounds
if not (np.all(0<=rects[0::4]) and np.all(rects[0::4]<g.width)): #x
return False
if not (np.all(0<=rects[1::4]) and np.all(rects[1::4]<g.height)): #y
return False
if not (np.all(0<=rects[2::4]) and np.all(rects[2::4]<=g.width)): #w
return False
if not (np.all(0<=rects[3::4]) and np.all(rects[3::4]<=g.height)): #h
return False
fullmask = np.zeros((g.height,g.width))
for r in range(0,len(rects),4):
fullmask[rects[r+1]:rects[r+3],rects[r+0]:rects[r+2]] = 1
return np.sum(fullmask * g.grid)==g.ntarget
#Mutate a randomly chosen bound of a rectangle. Keep trying this until we find a
#mutation that leads to a valid state.
def MutateRects(rects):
current_state = rects.copy()
while True:
rects = current_state.copy()
c = random.randint(0,len(rects)-1)
rects[c] += random.randint(-1,1)
if ValidState(rects):
return rects
#Determine the score of a state. The score is the sum of the number of times
#each empty space is covered by a rectangle. The best solutions will minimize
#this count.
def EvaluateState(rects):
score = 0
invgrid = -(g.grid-1) #Turn zeros into ones, and ones into zeros
for r in range(0,len(rects),4):
mask = np.zeros((g.height,g.width))
mask[rects[r+1]:rects[r+3],rects[r+0]:rects[r+2]] = 1
score += np.sum(mask * invgrid)
return score
#Print the list of rectangles (useful for showing output)
def PrintRects(rects):
for r in range(0,len(rects),4):
mask = np.zeros((g.height,g.width))
mask[rects[r+1]:rects[r+3],rects[r+0]:rects[r+2]] = 1
print(mask)
#Input grid is here
gridi = [[0,0,1,0,0],
[0,1,1,1,0],
[1,1,0,1,1],
[0,1,1,1,0],
[0,1,0,1,0]]
g = Grid(gridi)
#Number of rectangles we wish to solve with
rect_count = 2
#A rectangle is defined as going from (x,y)-(w,h) where (w,h) is an upper bound
#on the array coordinates. This allows efficient manipulation of rectangles as
#numpy arrays
rects = []
for r in range(rect_count):
rects += [0,0,g.width,g.height]
rects = np.array(rects)
#Might want to run a few times since the initial state is something of a
#bottleneck on moving around the search space
sols = []
for i in range(10):
#Use simulated annealing to solve the problem
sols.append(scipy.optimize.basinhopping(
func = EvaluateState,
take_step = MutateRects,
x0 = rects,
disp = True,
niter = 3000
))
#Get a minimum solution and display it
PrintRects(min(sols, key=lambda x: x['lowest_optimization_result']['fun'])['x'])
这是我在上面的示例代码中指定的十个 运行 的算法进度显示，作为迭代次数的函数（我添加了一些抖动，因此您可以看到所有行）：
您会注意到大多数 (8/10) 运行 很早就找到了 8 处的最小值。同样，在 6/10 运行 中找到 5 处的最小值，他们中的大多数很早就这样做了。这表明 运行 许多较短的搜索可能比一些较长的搜索更好。选择适当的长度和 运行 数量将是一个实验问题。
请注意，EvaluateState 为每个 添加点 次空白正方形被矩形覆盖。这会抑制冗余覆盖，而冗余覆盖可能是找到解决方案所必需的，或者可能导致更快地找到解决方案。成本函数包含这种东西是很常见的。试验直接询问您想要什么的成本函数很容易 - 只需将 EvaluateState 替换如下：
#Determine the score of a state. The score is the sum of the number of times
#each empty space is covered by a rectangle. The best solutions will minimize
#this count.
def EvaluateState(rects):
score = 0
invgrid = -(g.grid-1) #Turn zeros into ones, and ones into zeros
mask = np.zeros((g.height,g.width))
for r in range(0,len(rects),4):
mask[rects[r+1]:rects[r+3],rects[r+0]:rects[r+2]] = 1
score += np.sum(mask * invgrid)
return score
在这种情况下使用此成本函数似乎确实会产生更好的结果：
这可能是因为它为可行状态之间的矩形提供了更多的过渡路径。但如果你遇到困难，我会记住其他功能。
尽管标题听起来很复杂，但我的实际问题应该不难建模。但是，我一直无法找到一个好的算法来执行以下操作：
我想用固定数量 n 个矩形覆盖网格上的一组正方形。这些矩形可以重叠，它们只需要覆盖我形状的外边缘。
为什么不Brute-Force？
正方形 m x m 网格上不同矩形的数量为
.
因此 brute-force-approach 必须尝试的组合数在
对于 10 x 10 网格，只有 27,680,640,625 组合74=]3 个矩形。
例子
上面有一些正方形的初始网格可能如下所示：
n = 1：用单个矩形覆盖此形状的最佳方法是：
n = 2: 使用两个矩形可以减少被覆盖的空方块的数量：
（注意中心现在被两个矩形覆盖了）
有效封面
我正在寻找一种解决方案，该解决方案至少覆盖所有属于外边缘的正方形，即所有在网格宽度上共享边缘的填充正方形是一个空正方形。
不属于形状外边缘的所有正方形可能会被覆盖，也可能不会被覆盖，覆盖的矩形可能会相交，也可能不会相交。
目标函数
给定固定数量的覆盖矩形 n，我想覆盖所有填充的方块，但尽量减少覆盖的空方块的数量 在形状之外。这意味着中心的空方块不应计入必须最小化的目标函数（我也可以在应用算法之前填充所有孔而不会产生影响）。
因此，我的示例的目标函数的值为：
n | target function
---|-----------------
1 | 11
2 | 3
附加约束
请注意，原始正方形集可能 未连接 并且 non-connected 子形状的数量甚至可能超过覆盖矩形的数量。
替代说明
为了简化问题，您也可以只处理输入数据的转换版本：
然后目标是覆盖所有蓝色方块，并使用 n 个可能相交的矩形来尽量减少被覆盖的白色方块的数量。
不是一个完整的解决方案，但有一些（optimality-preserving-under-certain-conditions）减少规则：
- 如果您想要一个完全没有白色方块被覆盖的解决方案，那么您可以安全地合并任何相邻的相同行或列对。这是因为对于不包含任何白色方块的较小合并问题的任何有效解决方案都可以通过 "stretching" 以与执行合并相反的顺序跨每条合并线的每个矩形扩展为原始问题的解决方案 -这不会导致任何未覆盖的白色方块被覆盖，任何蓝色方块被覆盖，或改变所需的矩形数量。根据 "curvy" 原始图像的大小，这可以大大减少输入问题的大小。 （即使对于覆盖白色方块的解决方案，您仍然可以应用此策略——但是 "expanded" 解决方案可能会覆盖比原始解决方案更多的白色方块。作为启发式方法仍然有用。）
您可以通过将 already-placed 矩形覆盖的所有单元格（无论它们最初是蓝色还是白色）变为粉红色来表示任何部分解决方案；粉红色单元格是可能被（更多）矩形免费覆盖但不需要覆盖的单元格。如果您正在寻找一个完全没有白色方块被覆盖的解决方案，您可以应用规则 1 的加强形式来缩小实例：您不仅可以像以前一样合并相同的相邻行和列对，您可以先根据以下规则将一些粉红色单元格更改为蓝色，这可能会导致更多合并发生。两个相邻列的规则是：如果第 1 列中的每个白色单元格在第 2 列中也是白色的，反之亦然，那么在包含一个粉色和一个蓝色单元格的每一行中，您可以将粉色单元格更改为蓝色。 （基本原理：某些 non-white-cell-covering 矩形最终必须覆盖蓝色单元格；该矩形也可以拉伸以覆盖粉色单元格，而不覆盖任何新的白色单元格。）示例：
WW WW W BB BB B BP --> BB --> B PP PP P PB BB B您永远不需要考虑一个矩形，该矩形是不覆盖任何白色单元格的矩形的真子矩形。
一些进一步的想法：
简单地将图像调整为较小的尺寸，其中新高度是原始高度的整数倍，宽度也类似，并且当且仅当原始图像中相应单元格块中的任何单元格都是蓝色的是蓝色的，应该给出一个很好的近似子问题，它更容易解决。 （如有必要，用白色单元格填充原始图像。）解决这个较小的问题并将解决方案重新扩展到原始大小后，您可以 trim 一些矩形边缘的更多行或列。
我想提出一个不同的问题：
假设你有三个孤立的正方形，有什么可能性：
一个矩形覆盖所有三个
两个矩形，有 3 种可能性覆盖 2 +1
和三个矩形各占一个
所以顺序是Sum_in_choose_i
比您的订单小很多
在任何情况下都是 n 的多项式而不是指数。
然后你可以 trim 写下你的解决方案（顺便说一下，这是相互矛盾的：矩形越少越好，空单元格越少越好，但你可以解决这个问题）
嗯，我还没有想到 P-class 解决方案，但我确实想到这个问题可能是随机解决方案的一个很好的候选者。
值得注意的是，有一个 easily-defined 可行的起点：只需将所有覆盖矩形设置为目标方块边界框的范围即可。
从这个初始状态开始，可以通过缩小覆盖矩形的边界之一并检查所有目标方块是否仍然被覆盖来生成新的有效状态。
此外，任意两个状态之间的路径可能很短（每个矩形可以在O(√n)时间内缩小到合适的尺寸，其中n 是边界框中的方块数），这意味着很容易在搜索中移动 space。尽管这伴随着一些可能的解决方案被返回初始状态的狭窄路径分隔的警告，这意味着重新运行我们将要开发的算法几次可能是好的。
鉴于上述情况，simulated annealing 是解决该问题的可能方法。以下 Python 脚本实现了它：
#!/usr/bin/env python3
import random
import numpy as np
import copy
import math
import scipy
import scipy.optimize
#Generate a grid
class Grid:
def __init__(self,grid_array):
self.grid = np.array(grid_array)
self.width = len(self.grid[0]) #Use inclusive coordinates
self.height = len(self.grid) #Use inclusive coordinates
#Convert into a list of cells
self.cells = {}
for y in range(len(self.grid)):
for x in range(len(self.grid[y])):
self.cells[(x,y)] = self.grid[y][x]
#Find all cells which are border cells (the ones we need covered)
self.borders = []
for c in self.cells:
for dx in [-1,0,1]: #Loop through neighbors
for dy in [-1,0,1]:
n = (c[0]+dx,c[1]+dy) #This is the neighbor
if self.cells[c]==1 and self.cells.get(n, 1)==0: #See if this cell has a neighbor with value 0. Use default return to simplify code
self.borders.append(c)
#Ensure grid contains only valid target cells
self.grid = np.zeros((self.height,self.width))
for b in self.borders:
self.grid[b[1],b[0]] = 1
self.ntarget = np.sum(self.grid)
def copy(self):
return self.grid.copy()
#A state is valid if the bounds of each rectangle are inside the bounding box of
#the target squares and all the target squares are covered.
def ValidState(rects):
#Check bounds
if not (np.all(0<=rects[0::4]) and np.all(rects[0::4]<g.width)): #x
return False
if not (np.all(0<=rects[1::4]) and np.all(rects[1::4]<g.height)): #y
return False
if not (np.all(0<=rects[2::4]) and np.all(rects[2::4]<=g.width)): #w
return False
if not (np.all(0<=rects[3::4]) and np.all(rects[3::4]<=g.height)): #h
return False
fullmask = np.zeros((g.height,g.width))
for r in range(0,len(rects),4):
fullmask[rects[r+1]:rects[r+3],rects[r+0]:rects[r+2]] = 1
return np.sum(fullmask * g.grid)==g.ntarget
#Mutate a randomly chosen bound of a rectangle. Keep trying this until we find a
#mutation that leads to a valid state.
def MutateRects(rects):
current_state = rects.copy()
while True:
rects = current_state.copy()
c = random.randint(0,len(rects)-1)
rects[c] += random.randint(-1,1)
if ValidState(rects):
return rects
#Determine the score of a state. The score is the sum of the number of times
#each empty space is covered by a rectangle. The best solutions will minimize
#this count.
def EvaluateState(rects):
score = 0
invgrid = -(g.grid-1) #Turn zeros into ones, and ones into zeros
for r in range(0,len(rects),4):
mask = np.zeros((g.height,g.width))
mask[rects[r+1]:rects[r+3],rects[r+0]:rects[r+2]] = 1
score += np.sum(mask * invgrid)
return score
#Print the list of rectangles (useful for showing output)
def PrintRects(rects):
for r in range(0,len(rects),4):
mask = np.zeros((g.height,g.width))
mask[rects[r+1]:rects[r+3],rects[r+0]:rects[r+2]] = 1
print(mask)
#Input grid is here
gridi = [[0,0,1,0,0],
[0,1,1,1,0],
[1,1,0,1,1],
[0,1,1,1,0],
[0,1,0,1,0]]
g = Grid(gridi)
#Number of rectangles we wish to solve with
rect_count = 2
#A rectangle is defined as going from (x,y)-(w,h) where (w,h) is an upper bound
#on the array coordinates. This allows efficient manipulation of rectangles as
#numpy arrays
rects = []
for r in range(rect_count):
rects += [0,0,g.width,g.height]
rects = np.array(rects)
#Might want to run a few times since the initial state is something of a
#bottleneck on moving around the search space
sols = []
for i in range(10):
#Use simulated annealing to solve the problem
sols.append(scipy.optimize.basinhopping(
func = EvaluateState,
take_step = MutateRects,
x0 = rects,
disp = True,
niter = 3000
))
#Get a minimum solution and display it
PrintRects(min(sols, key=lambda x: x['lowest_optimization_result']['fun'])['x'])
这是我在上面的示例代码中指定的十个 运行 的算法进度显示，作为迭代次数的函数（我添加了一些抖动，因此您可以看到所有行）：
您会注意到大多数 (8/10) 运行 很早就找到了 8 处的最小值。同样，在 6/10 运行 中找到 5 处的最小值，他们中的大多数很早就这样做了。这表明 运行 许多较短的搜索可能比一些较长的搜索更好。选择适当的长度和 运行 数量将是一个实验问题。
请注意，EvaluateState 为每个 添加点 次空白正方形被矩形覆盖。这会抑制冗余覆盖，而冗余覆盖可能是找到解决方案所必需的，或者可能导致更快地找到解决方案。成本函数包含这种东西是很常见的。试验直接询问您想要什么的成本函数很容易 - 只需将 EvaluateState 替换如下：
#Determine the score of a state. The score is the sum of the number of times
#each empty space is covered by a rectangle. The best solutions will minimize
#this count.
def EvaluateState(rects):
score = 0
invgrid = -(g.grid-1) #Turn zeros into ones, and ones into zeros
mask = np.zeros((g.height,g.width))
for r in range(0,len(rects),4):
mask[rects[r+1]:rects[r+3],rects[r+0]:rects[r+2]] = 1
score += np.sum(mask * invgrid)
return score
在这种情况下使用此成本函数似乎确实会产生更好的结果：
这可能是因为它为可行状态之间的矩形提供了更多的过渡路径。但如果你遇到困难，我会记住其他功能。