在矩阵中获得相邻 1 的最小翻转次数
Minimum number of flips to get adjacent 1's in a matrix
Given a binary matrix (values of 0 or 1), adjacent entries of 1 denote “hills”. Also, given some number k, find the minimum number of 0's you need to “flip” to 1 in order to form a hill of at least size k.
编辑：为澄清起见，相邻是指左右上下的邻域。对角线 不 算作相邻。例如，
[0 1
0 1]
是一座大小为 2 的山，
[0 1
1 0]
定义 2 个大小为 1 的山，
[0 1
1 1]
定义 1 个大小为 3 的山，并且
[1 1
1 1]
定义 1 个 4 号山。
还要说明一下，大小是由相邻的 1 斑点形成的面积定义的。
我最初的解决方案是将每个现有的山丘转换为图形的节点，并将成本作为到每个其他节点的最小路径。然后，执行 DFS（或类似算法）以找到最小成本。
如果选择某些路径会降低另一条边的成本，并且解决这个问题的解决方案（我能想到的）太接近于蛮力解决方案，那么这会失败。
一座山由1的四个序列组成：
右序列由r'bits'组成，上序列有u位，依此类推。
大小为 k 的山是 k= 1 + r + l + u + d（1 个中心 + 序列），其中每个值是 0 <= v < k.
问题是组合问题。对于每个单元格，应测试满足前一个关系的所有可能的 {r,l,u,d} 组合。
在单元格中测试组合时，必须计算组合的每个值中现有1的数量，而不是"flip"。这也将提前跳过一些其他组合。
您的问题与rectilinear Steiner tree problem密切相关。
一个 Steiner tree connects a set of points together using line segments, minimising the total length of the line segments. The line segments can meet in arbitrary places, not necessarily at points in the set (so it is not the same thing as a minimum spanning tree)。例如，在等边三角形的角上给定三个点，欧氏斯坦纳树通过在中间相遇来连接它们：
直线 Steiner 树是相同的，只是您最小化总距离 Manhattan distance 而不是总欧几里得距离。
在您的问题中，您不是使用长度由欧氏距离测量的线段连接山丘，而是通过添加像素来连接山丘。连接数组中的两个单元格需要翻转的 0 的总数等于这两个单元格之间的曼哈顿距离减 1。
直线斯坦纳树问题 is known to be NP-complete，即使仅限于具有整数坐标的点。你的问题是一个概括，除了两个区别：
- 测量曼哈顿距离时的"minus 1"部分。我怀疑这种细微差别是否足以使问题变得更复杂 class，尽管我没有证据给你。
- 整数点的坐标受矩阵大小的限制（正如 Albert Hendriks 在评论中指出的那样）。这确实很重要——这意味着 pseudo-polynomial time 对于直线斯坦纳树问题将是您问题的多项式时间。
这意味着你的问题可能是也可能不是 NP-hard，这取决于直线 Steiner 树问题是否是 weakly NP-complete or strongly NP-complete。我无法在文献中找到明确的答案，除了学术文献之外，没有太多关于这个问题的信息。据我所知，至少似乎没有已知的伪多项式时间算法。
鉴于此，您最有可能的选择是某种 backtracking search for an exact solution, or applying a heuristic to get a "good enough" solution. One possible heuristic as described by Wikipedia is to compute a rectilinear minimum spanning tree and then try to improve on the RMST using an iterative improvement method。 RMST 本身给出了一个在真正最优值的 1.5 常数因子内的解决方案。
Given a binary matrix (values of 0 or 1), adjacent entries of 1 denote “hills”. Also, given some number
k, find the minimum number of 0's you need to “flip” to 1 in order to form a hill of at least sizek.
编辑：为澄清起见，相邻是指左右上下的邻域。对角线 不 算作相邻。例如，
[0 1
0 1]
是一座大小为 2 的山，
[0 1
1 0]
定义 2 个大小为 1 的山，
[0 1
1 1]
定义 1 个大小为 3 的山，并且
[1 1
1 1]
定义 1 个 4 号山。
还要说明一下，大小是由相邻的 1 斑点形成的面积定义的。
我最初的解决方案是将每个现有的山丘转换为图形的节点，并将成本作为到每个其他节点的最小路径。然后，执行 DFS（或类似算法）以找到最小成本。
如果选择某些路径会降低另一条边的成本，并且解决这个问题的解决方案（我能想到的）太接近于蛮力解决方案，那么这会失败。
一座山由1的四个序列组成：
右序列由r'bits'组成，上序列有u位，依此类推。
大小为 k 的山是 k= 1 + r + l + u + d（1 个中心 + 序列），其中每个值是 0 <= v < k.
问题是组合问题。对于每个单元格，应测试满足前一个关系的所有可能的 {r,l,u,d} 组合。
在单元格中测试组合时，必须计算组合的每个值中现有1的数量，而不是"flip"。这也将提前跳过一些其他组合。
您的问题与rectilinear Steiner tree problem密切相关。
一个 Steiner tree connects a set of points together using line segments, minimising the total length of the line segments. The line segments can meet in arbitrary places, not necessarily at points in the set (so it is not the same thing as a minimum spanning tree)。例如，在等边三角形的角上给定三个点，欧氏斯坦纳树通过在中间相遇来连接它们：
直线 Steiner 树是相同的，只是您最小化总距离 Manhattan distance 而不是总欧几里得距离。
在您的问题中，您不是使用长度由欧氏距离测量的线段连接山丘，而是通过添加像素来连接山丘。连接数组中的两个单元格需要翻转的 0 的总数等于这两个单元格之间的曼哈顿距离减 1。
直线斯坦纳树问题 is known to be NP-complete，即使仅限于具有整数坐标的点。你的问题是一个概括，除了两个区别：
- 测量曼哈顿距离时的"minus 1"部分。我怀疑这种细微差别是否足以使问题变得更复杂 class，尽管我没有证据给你。
- 整数点的坐标受矩阵大小的限制（正如 Albert Hendriks 在评论中指出的那样）。这确实很重要——这意味着 pseudo-polynomial time 对于直线斯坦纳树问题将是您问题的多项式时间。
这意味着你的问题可能是也可能不是 NP-hard，这取决于直线 Steiner 树问题是否是 weakly NP-complete or strongly NP-complete。我无法在文献中找到明确的答案，除了学术文献之外，没有太多关于这个问题的信息。据我所知，至少似乎没有已知的伪多项式时间算法。
鉴于此，您最有可能的选择是某种 backtracking search for an exact solution, or applying a heuristic to get a "good enough" solution. One possible heuristic as described by Wikipedia is to compute a rectilinear minimum spanning tree and then try to improve on the RMST using an iterative improvement method。 RMST 本身给出了一个在真正最优值的 1.5 常数因子内的解决方案。