algorithm - 二维最近邻搜索

Question

从绿色方 block 开始，我想要一个高效的算法来找到最近的 3 x 3 窗口，没有红色方 block ，只有蓝色方 block 。该算法不需要准确地找到最近的 3 x 3 窗口，但它应该找到靠近绿色方 block 的 3 x 3 全蓝色窗口(假设存在一个)。我考虑将其实现为递归广度优先搜索，但该解决方案将涉及多次重新检查同一个方 block 。发布此消息以查看是否有人知道更有效的解决方案。检查给定正方形的成本是恒定且便宜的，但我想尽可能地减少算法的执行时间(实际应用将涉及在更大的 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;
    }
}

更新:距离度量不是那么重要，但为了简单起见，让我们最小化曼哈顿距离。

这里有一个更好的算法，它不使用递归，并且可以保证找到最接近的解决方案(如果有平局，则找到最接近的解决方案之一)。它需要大于 5 x 5 的网格才能正常工作，但如果您想搜索小于 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
    }
}

Answer 1

一个简单的建议是标记您检查过的所有单元格。这样您就不必多次检查单元格。

递归肯定会比基于迭代的方法花费更多时间，因为它会在您每次进行新调用时创建一个新堆栈。如果您正在尝试找到最接近的那个，请选择 BFS 而不是 DFS。

我还建议对“洪水填充算法”进行快速的互联网研究。