从绿色方块开始，我想要一个有效的算法来找到最近的3 x 3窗口，没有红色方块，只有蓝色方块 . 该算法不需要找到最接近的3 x 3窗口，但它应该找到靠近绿色方块的3 x 3全蓝窗口（假设存在一个） . 我考虑将其实现为递归广度优先搜索，但该解决方案将涉及多次重新检查同一个方块 . 发布此信息以查看是否有人知道更有效的解决方案 . 检查给定方块的成本是恒定且廉价的，但我希望尽可能地减少算法的执行时间（实际应用这将涉及在更大的2D搜索中找到3x3“清除”/全蓝窗口区域） .
这是一个示例解决方案，但我不认为它是最佳的 . 它实际上是一个深度优先搜索，我将不得不重组以转换为广度优先，但我需要更多地思考如何做到这一点（一种方法是使每个点成为扩展到相邻点的对象，然后在这些点上多次迭代给孩子，在允许这些孩子生成更多孩子之前访问这些孩子） . 重点是，我认为这是一种更有效和更常见的方法，所以我试图避免重新发明轮子 .
public class Search2D {
private TreeSet<Point> centerpointscheckedsofar;
private Point Search(Point centerpoint) {
if(centerpointscheckedsofar.contains(centerpoint)) {
return null;
}
if(isWithinBounds(centerpoint)) {
if(checkCenterPoint(centerpoint)) {
centerpointscheckedsofar.add(centerpoint);
return null;
}
Point result = Search(getPoint(-1, -1, centerpoint));
if(result != null) return result;
result = Search(getPoint(-1, 0, centerpoint));
if(result != null) return result;
result = Search(getPoint(-1, 1, centerpoint));
if(result != null) return result;
result = Search(getPoint(0, -1, centerpoint));
if(result != null) return result;
result = Search(getPoint(0, 1, centerpoint));
if(result != null) return result;
result = Search(getPoint(1, -1, centerpoint));
if(result != null) return result;
result = Search(getPoint(1, 0, centerpoint));
if(result != null) return result;
result = Search(getPoint(1, 1, centerpoint));
if(result != null) return result;
}
return null;
}
private Point getPoint(int x, int y, Point centerpoint) {
return new Point(centerpoint.x + x, centerpoint.y + y);
}
private boolean checkCenterPoint(Point centerpoint) {
//check here to see if point is valid
return false;
}
private boolean isWithinBounds(Point startPoint) {
//check here to see if point and all neighboring points of 3 x 3 window falls within bounds
return false;
}
}
UPDATE: 距离测量并不重要，但为简单起见，让我们最小化曼哈顿距离 .
这是一个更好的算法，它不使用递归，并且可以保证找到最接近的解决方案（如果存在平局，则可以找到最接近的解决方案之一） . 它需要一个大于5 x 5的网格才能正常工作，但是如果你想搜索一个小于它的网格，可能会有一个更有效的算法可以使用 . 假设最低x-index为0，最低y-index也为0 .
import java.awt.Point;
public class Search2D_v2 {
private boolean[][] bitgrid;
public Search2D_v2() {
bitgrid = new boolean[20][20];
}
public Point search(int centerx, int centery, int maxx, int maxy, int maxsearchsteps) {
//check starting point first, if it works, we're done
if(checkPoint(centerx, centery)) {
return new Point(centerx, centery);
}
int westbound = centerx-1;
boolean keepgoingwest = true;
int eastbound = centerx+1;
boolean keepgoingeast = true;
int southbound = centery-1;
boolean keepgoingsouth = true;
int northbound = centery+1;
boolean keepgoingnorth = true;
//stay within bounds, may move initial search square by 1 east and 1 west
if(westbound <= 0) {
eastbound = 3;
westbound = 1;
}
if(eastbound >= maxx) {
eastbound = maxx - 1;
westbound = maxx - 3;
}
if(southbound == 0) {
northbound = 3;
southbound = 1;
}
if(northbound == maxy) {
northbound = maxy - 1;
southbound = maxy - 3;
}
//always search boundary, we've already searched inside the boundary on previous iterations, expand boundary by 1 step / square for each iteration
for(int i = 0; i < maxsearchsteps && (keepgoingwest || keepgoingeast || keepgoingsouth || keepgoingnorth); i++) {
//search top row
if(keepgoingnorth) { //if we have already hit the north bound, stop searching the top row
for(int x = westbound; x <= eastbound; x++) {
if(checkPoint(x, northbound)) {
return new Point(x, northbound);
}
}
}
//search bottom row
if(keepgoingsouth) {
for(int x = westbound; x <= eastbound; x++) {
if(checkPoint(x, southbound)) {
return new Point(x, southbound);
}
}
}
//search westbound
if(keepgoingwest) {
for(int y = southbound; y <= northbound; y++) {
if(checkPoint(westbound, northbound)) {
return new Point(westbound, y);
}
}
}
//search eastbound
if(keepgoingeast) {
for(int y = southbound; y <= northbound; y++) {
if(checkPoint(eastbound, northbound)) {
return new Point(eastbound, y);
}
}
}
//expand search area by one square on each side
if(westbound - 2 >= 0) {
westbound--;
}
else {
keepgoingwest = false;
}
if(eastbound + 2 <= maxx) {
eastbound++;
}
else {
keepgoingeast = false;
}
if(southbound - 2 >= 0) {
southbound--;
}
else {
keepgoingsouth = false;
}
if(northbound + 2 <= maxy) {
northbound++;
}
else {
keepgoingnorth = false;
}
}
return null; //failed to find a point
}
private boolean checkPoint(int centerx, int centery) {
return !bitgrid[centerx][centery] && //center
!bitgrid[centerx-1][centery-1] && //left lower
!bitgrid[centerx-1][centery] && //left middle
!bitgrid[centerx-1][centery+1] && //left upper
!bitgrid[centerx][centery-1] && //middle lower
!bitgrid[centerx][centery+1] && //middle upper
!bitgrid[centerx+1][centery-1] && //right lower
!bitgrid[centerx+1][centery] && //right middle
!bitgrid[centerx+1][centery+1]; //right upper
}
}
4 回答
一个简单的建议是标记您检查过的所有单元格 . 这样您就不必多次检查单元格 .
递归肯定比基于迭代的方法花费更多的时间，因为每次进行新的调用时它都会创建一个新的堆栈 . 如果您正在尝试找到最接近的一个，则更喜欢BFS而不是DFS .
我还建议对“洪水填充算法”进行快速的互联网研究 .
你可以从你的起始像素向外螺旋 . 每当遇到未经检查的像素p时，请检查p周围的3x3环境 .
对于环境中的每个红色像素r，设置r的3x3环境进行检查 .
如果环境中没有红色像素，则找到解决方案 .
你想要在更一般意义上找到的是一种阵列的形态滤波器 .
我们可以将过滤器定义为3x3滑动窗口，该窗口将窗口的中心设置为窗口内数组元素的总和 . 设蓝色方块用1表示，红色方块用0表示 .
在这种情况下，您正在尝试找到总和值为9的最近元素 .
请注意，解决此问题的一种方法是在阵列中滑动3x3窗口，以便覆盖所有可能的位置 . 在这种情况下，您将看到9 * width * height元素 . 然后，您可以使用广度优先搜索最多宽度*高度检查找到最近的总和值9 . 因此，算法的幼稚时间与10 宽高度成正比
您可以通过确保过滤器只需要查看每个焦点单元格的一个值而不是9来减少这种情况 . 为此，生成summed-area table . 现在你的时间与2 宽高度成正比 .
求和区域表的示例
你可以更快地做到这一点 . 每次找到值9时，将其与当时绿色单元格的位置进行比较 . 如果大多数单元格不是9s，则会缩短与宽度*高度成比例的时间 .
亨斯利等人 . （2005）的论文Fast Summed-Area Table Generation and its Applications解释了如何使用图形硬件在O（log n）时间内生成求和区域表 . 所以's possible to really reduce run-times on this. Nehab et al. (2011)'篇论文GPU-efficient recursive filtering and summed-area tables也可能有用（source code）：他们的工作表明，对于像你这样的小窗口，直接方法可能是最有效的 .
我认为最简单的方法是使用略微修改的广度优先搜索 .
如果我们谈论曼哈顿距离，那么每个广场将有最多4个邻居 . 在每一步，我们检查邻居的数量是否等于3（第四个邻居是我们来自的正方形） . 如果是这样，我们检查对角线 . 否则 - 继续搜索 .