找到包围二维网格上某个区域的最短栅栏

Question

我有一个 50 x 50 的二维网格。网格单元格可以具有以下三种状态之一：

1: "inside"
2: "empty"
3: "wall"

我的初始配置是一个网格，其中有一些单元格（可能是其中的 10%，大部分是连续的）标记为 "inside"。随机也有一些 "wall" 个单元格。其他单元格是 "empty".

我正在尝试找到 最短的栅栏 我可以围绕 "inside" 个单元格进行构建，以便所有 "inside" 个单元格都被围起来（栅栏是通过将 "empty" 个单元格更改为 "wall" 个单元格来构建）。如果我们对解决方案进行评分，最佳解决方案将最大限度地减少需要更改为"wall"个单元格的"empty"个单元格的数量。

更严格地说，在最终配置中，有一个约束，即对于每个 "inside" 单元格，没有不通过 "wall" 单元格的到网格边缘的路径。在我的例子中，允许对角线移动。

我猜我可以做一些巧妙的事情，包括距离变换，或计算网格的拓扑骨架，但对我来说不是很明显。如果这是一个经典的优化问题，我不知道google。

有没有找到最短栅栏的O(n^2)算法？

编辑：这不像找到 "inside" 单元格的凸包那么容易，因为预先存在的 "wall" 单元格是免费的。想象一个 "C" 形的既有墙块，所有 "inside" 个单元格都在 C 的内部。大多数情况下，用 "wall" 个单元格完成 C 会比在所有 "inside" 个单元格周围绘制一个凸包。这就是使这个问题变得困难的原因。

Answer 1

您最可能想要的是 2-dimensional convex hull。

我推荐所谓的gift-wrapping algorithm。在最坏的情况下，它的时间复杂度是 O(n²)。其要点如下。

不失一般性，我们假设云中没有共线的 3 个点。

我们从最左边的点开始，因为有限点云上的每个外壳都必须至少包含一个最左边的点（并且，考虑到上述限制，其中不超过两个是可能的，它们都属于到船体）。
然后我们开始暴力破解这样的点，其余的点都在两个半平面的同一个上，初始平面被从初始点到搜索点的连线分割成两个半平面。
现在我们将找到的一个作为新的首字母，然后重复[2-3]直到外壳闭合。

[N.B.] 请记住，找到一个当前初始点的前导点会让你无处可去（像这样：•⇌•），所以应该跳过它，除非有除了这两个就没有别的了。

Answer 2

如果您所说的最短栅栏是指占用最少 "wall" 个单元格的栅栏，则具有最小封闭矩形的栅栏将起作用。

Answer 3

对我来说，它仍然是一个凸包变体。您必须在凸包中包含与内部单元格相邻且不是内部单元格的所有单元格+包括位于墙（连续墙）[开始]和[结束]处的单元格。然后重要的部分是排除相邻的单元格，如果这些单元格在墙内。例如，要检查单元格是否位于 C 形墙内（I），您可以从 p1--p2 计算 ax+b 线，然后使用一种点划分检查 clockwise/counterclockwise，然后使用相邻点进一步计算墙点将其从搜索中排除。在下面的示例中，指向我的邻居将被排除在外。因此算法将直接找到 p1->p2 连接 p1-p2。

...[.p1]
. I 
. I 
...[.p2]

在下面的例子中T点是相邻点

               TTT
...[.p1]       TIT
. I            TTT
. I 
...[.p2]

经过凸包算法你会得到：

               [T3]
...[.p1]        I[T2]
. I            [T1] 
. I 
...[.p2]

这意味着路径 p2[T1][T2][T3]p1 和这些点之间的线为您提供了最小的环绕。如您所见，如果任何 I 邻居点位于墙形状内部（如 C），则每面墙也必须存储一个值，这些墙必须包含在凸包中，但没有内部邻居的那些只能使用如果使用零成本现有墙到下一个点的距离更小。那么快速解释有点复杂，但我想你可以从中得到一些东西。

编辑：在计算出的凸面上，您还必须运行最小流量来调整以下情况：

...........[.]
.
.
. 
.
.         
.
.         I  I
.
.
.
.
.
. 
...........[.]

其中一个我在里面，但我周围有最小栅栏，没有涉及 p1 和 p2。在算法中 p1 和 p2 将被选中，然后对于所有具有内部 I 的墙，您必须使用 dist(internalI,eternalI) 计算 dist(p1,externalI)+dist(p2,externalI) 并选择较小的一个..externalI 是连接到 p1 和 p2 的那个（可以是一个或两个外部点..）

Answer 4

这可以作为图形简化问题解决：

创建网格图（无对角线）
移除（删除）内部节点
折叠（合并）墙节点
描述围绕图形边缘的路径
沿路径迭代
- 检查附近的路径节点是否共享一个空图邻居（附近=路径节点[n .. n+k]）
- 检查新路径距离是否 <= 现有路径距离（计数边）
- 检查内部节点是否会被快捷方式搁浅（不允许）
- 满足条件调整路径
- 移除（删除）不再需要的图节点
当路径不能再收缩时停止

最坏的情况是你必须为每条边遍历图中的所有顶点节点几次。所以它看起来像 O(V * E) 或者换句话说 O(N^2).

Answer 5

多么好的问题！

正如@qwertyman 所注意到的，问题是在 "inner" 单元格和网格边界之间找到最小顶点切割。虽然可以想象网格上的这个特殊问题可能有更简单的解决方案，但我认为其他任何解决方案都无法解决所有情况。

方形网格上的单元格最多可以看作有四个或最多八个邻居（@tobias_k 和@hidefromkgb）。如果我们忽略现有的（免费的）墙单元，这是 4 和 8 网格上典型栅栏的样子：

并不是说在这两种情况下，都有更多的最小栅栏，但是这些矩形和八角形边界框都是最小的并且很容易找到。此外，它们是具有最大内部面积的最小栅栏。

有两个问题：免费的预先存在的墙单元，以及多个小栅栏组件可能比一个大边界框便宜。

这两种复杂情况都在最小顶点切割问题中得到了很好的解决；可以从图中删除预先存在的壁单元（并且内部单元可以与其他连接的内部单元合并，内部单元的每个连接组件只留下一个内部单元）。不幸的是，最小切割通常被认为是去除边而不是顶点！

我怀疑任何算法都会比实现干净的顶点切割算法更容易。这是我们面临的问题：

在这个例子中，四个小栅栏比一个大栅栏便宜，但这取决于确切的比例。我们可以从一个大栅栏开始，然后尝试通过划分来改进它，就像@LazyMammal 所做的那样，或者分别对每个连接的组件进行栅栏，但无论哪种情况，这些情况都不是微不足道的。

这个也有问题：

我们可以使用大的免费围栏段吗？我们应该把每个小点分开围起来吗？我们要用三个中型栅栏吗？无论我们是像@LazyMammal 那样从大开始划分，还是从单独的边界框开始并加入它们，这些情况似乎都提出了一般最小削减正在解决的相同问题。

如果您对最佳解决方案的近似值没有问题，或者可能将自己限制在 50×50 网格上的实例并且可以快速排除这些复杂情况，也许有一些简单快捷的方法？我不知道。

对于已连接 组 G 的内部单元格，找到最便宜的栅栏会像这样工作：

找到从该组到边界的空单元格的最短 "flow" 路径 FL。
使用不在 G 或 FL 中的所有单元在组周围找到最便宜的 "fence" 路径 FE。尝试将 FL 中的每个单元格作为起点，或者尝试将 FL 和 G 的栅栏中的任何单元格作为起点。空单元格的成本为 1，壁单元格的成本为 0，不在 G 中的内部单元格的成本为 0。您必须临时沿着 FL 切割网格以确保 FE 围绕 G.

（但我不知道如何填充组中的空隙以连接其所有单元 - 在存在壁单元的情况下。）

所以也许真正的问题是将哪些内部单元格围起来？连接的内部细胞必须保持连接，好吧。此外，如果有任何最小的围栏接触，请加入他们的小组。除此之外，仅通过尝试不同的组合来近似？

我不知道；我相信大网格上的问题与一般的最小切割问题具有相同的复杂性和复杂性 - 所以如果你真的需要最优性，请解决这些问题。

相关：https://cstheory.stackexchange.com/questions/2877/ (thanks qwertyman), https://en.wikipedia.org/wiki/Vertex_separator 具有不同的 "minimal" 分隔符概念。

Answer 6

好的我解决了这个问题，但是我还没有计算渐近复杂度。

我通过 Dynamic Progamming 做到了这一点，我在其中递归地定义了问题，并且还添加了剔除标准以获得良好的加速。

递归问题陈述如下：

Find the smallest fencing set in a such that there is no path from a startArea to a border.
The recursive problem is provided with:

a grid containing natural, pre-existing walls

a startArea

a Border definition

a pre-existing set of fences that were placed and cannot be removed

a maximum number of fences N

Return the following:

If a fencing is found, return a List of the fences

If no fences are required, return an empty list

If the fence size must exceed N walls, return <invalid> (e.g. null)

此语句的解决方案是使用此观察完成的：

Any fencing should contain at least one wall on the optimal path from the start area to the border (Otherwise, that path would be valid and be used to escape)

因此，解决递归问题语句的方法如下：

通过提供初始化递归算法：

初始世界
起始区域，
边界定义（例如单元格必须在网格的边界上）
初始围栏的空列表
围栏的最大数量设置为Positive_Infinity（无限制）

然后递归如下：

生成从startArea到border最短的path而不经过现有的fences
如果没有路径通向出口，return预定义的fences
- 原理: 路径被阻塞，已有的fencing就足够了，不用加任何
如果预定义的 fences 至少有 N 个元素，return <invalid>
- 基本原理：预定义的栅栏不够用，所以至少需要N+1栅栏。由于已知存在 N 个围栏的解决方案，因此无需进一步调查
初始化bestLength为输入最大栅栏数N为
初始化bestPath为ìnvalid
沿 path 遍历每个 location（不包括 startArea 中的单元格，我认为这些单元格不能被隔离）
- 生成递归问题的解如下：
  - 输入 grid 包含自然的、预先存在的墙
  - 输入startArea
  - 输入Border定义
  - 已有的fences加上现在的location
  - 最大栅栏数bestLength
- 如果解是<invalid>，继续迭代
- 如果解存在
  - 存储为bestPath
  - 更新bestLength它的长度
- 如果解长度是N+1return就
ReturnbestPath

基本上，我们会在找到最佳路径时将它们围起来。当我们靠墙前进时，路径会改变，我们会靠墙。

IMO 最好的一点是剔除机制，类似于 beta-pruning。

脏复杂度分析（网格为NxN）：

路径的长度为 N，我们正在对其长度进行迭代。
- 每次递归迭代都会创建一条长度为 N 的路径（通常它会更长，但我会忽略它）。由于剔除，我将使它的复杂度仅为 log(N)
  - 我们在每一步都执行 BFS，因此 N.log(N)

总复杂度：N².log(N)²`（也许？我不知道我在做什么）

这是它的 Java 版本：

`MinimalFenceSolver.java`（主要class）

问题在main中构建，解决的是static方法

public class MinimalFenceSolver {

    public static final Predicate<Location> borderDetector = loc -> ((GridWorld.GridLocation)loc).isBorder();

    public static void main(String[] argc){
        GridWorld world = new GridWorld(10, 10, 0);

        // Find best fence
        List<Location> startArea = new ArrayList<>();
        startArea.add(world.at(5, 4));
        findBestFence(world, startArea);
    }

    private static List<Location> findBestFence(GridWorld world, List<Location> startArea) {
         List<Location> bestFence = findBestFenceRec(world, startArea, new ArrayList<>(), Integer.MAX_VALUE);
        return bestFence;
    }

    private static List<Location> findBestFenceRec(GridWorld world, List<Location> startArea, List<Location> fencePrefix, int bestLengthYet) {
        List<Location> bestFence = null;
        int bestLength = bestLengthYet;

        // Iterate
        World fencedWorld = world.withWall(fencePrefix);
        Path shortestPath = EscapePathfinder.begin(fencedWorld).setStart(startArea).setEnd(borderDetector).solve();
        if(!shortestPath.exists()){
            return fencePrefix;
        }

        if(fencePrefix.size() >= bestLength){
            return null; // Culling
        }

        for (Location loc : shortestPath.fullPath()) {
            if(!fencePrefix.contains(loc) && !startArea.contains(loc)){
                List<Location> newfence = new ArrayList<>(fencePrefix);
                newfence.add(loc);
                List<Location> bestChild = findBestFenceRec(world, startArea, newfence, bestLength);
                if(bestChild != null){
                    if(bestFence == null || bestChild.size() < bestLength) {
                        bestFence = bestChild;
                        bestLength = bestChild.size();
                    }
                }
            }
        }

        return bestFence; // null if no fence found 
    }
}

`World.java` 世界定义界面

public interface World {

     Location at(int i, int j);

     /**
      * Removes walled Locations in the input, return the result
      * @param neighbours (untouched)
      * @return a List of Locations, none of which has any wall in it
      */
    List<Location> noWalls(List<Location> neighbours);

}

`Location.java` 界面

public interface Location {
     CellType getType();
     List<Location> neighbours();
}

`CellType.java`枚举

public enum CellType {
    WALL, EMPTY
}

`GridWorld.java` 生活在网格上的世界的实现

包含自己的 Location 实现。可以使用 GridWorldWithWall subclass.

临时装饰额外的栅栏

public class GridWorld implements World{

    private final GridLocation[][] world;
    final int nx;
    final int ny;

    public GridWorld(int nx, int ny, long seed){
        this.nx = nx;
        this.ny = ny;
        Random rand = new Random(seed);
        world = new GridLocation[nx][ny];
        for(int i=0; i<nx; i++){
            for(int j=0; j<ny; j++){
                CellType locationType = rand.nextBoolean() ? CellType.EMPTY: CellType.WALL;
                world[i][j] = new GridLocation(locationType, i, j);
            }
        }
    }

    public GridLocation at(int i, int j){
        return world[(i+nx) % nx][(j+ny) % ny];
    }

    public String toString(){
        StringBuilder builder = new StringBuilder();
        for(int i=0; i<nx; i++){
            for(int j=0; j<ny; j++){
                builder.append(world[i][j].type == CellType.WALL ? "#" : ".");
            }
            builder.append("\n");
        }
        return builder.toString();
    }

    private static final int[][] offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public class GridLocation implements Location{

        private final CellType type;
        private final int i;
        private final int j;

        public GridLocation(CellType type, int i, int j) {
            super();
            this.type = type;
            this.i = i;
            this.j = j;
        }

        @Override
        public CellType getType() {
            return type;
        }

        @Override
        public List<Location> neighbours() {
            List<Location> result = new ArrayList<>();
            for(int[] offset: offsets){
                result.add(GridWorld.this.at(i + offset[0], j + offset[1]));
            }
            return result;
        }

        public boolean isBorder(){
            return i==0 || j==0 || i==nx-1 || j==ny-1;
        }

        public String toString(){
            return (type == CellType.WALL ? "#" : ".") + "(" + i + ", " + j + ")";
        }

        public boolean equals(Object obj){
            if(!(obj instanceof GridLocation)){
                return false;
            } else {
                GridLocation other = (GridLocation) obj;
                return other.i == this.i && other.j == this.j;
            }
        }
    }

    @Override
    public List<Location> noWalls(List<Location> neighbours) {
        return neighbours.stream().filter(cell -> cell.getType()!=CellType.WALL).collect(Collectors.toList());
    }

    public World withWall(List<Location> walls) {
        return new GridWorldWithWall(walls);
    }

    private class GridWorldWithWall implements World {

        public List<Location> walls;

        public GridWorldWithWall(List<Location> walls) {
            this.walls = walls;
        }

        @Override
        public Location at(int i, int j) {
            return new LocationWithWalls(GridWorld.this.at(i, j));
        }

        @Override
        public List<Location> noWalls(List<Location> neighbours) {
            List<Location> noWalls = GridWorld.this.noWalls(neighbours);
            noWalls.removeAll(walls);
            return noWalls;
        }

        private class LocationWithWalls implements Location{
            private final GridLocation location;
            public LocationWithWalls(GridLocation location) {
                this.location = location;
            }

            @Override
            public CellType getType() {
                if(GridWorldWithWall.this.walls.contains(location)) {
                    return CellType.WALL;
                }
                return location.getType();
            }

            @Override
            public List<Location> neighbours() {
                List<Location> neighbours = location.neighbours();
                neighbours().removeAll(walls);
                return neighbours;
            }

        }
    }
}

`Pathfinder.java`（界面）

如果您想尝试其他解算器，这是一个矫枉过正的流畅界面，如果您设法对边界进行良好的启发，可以在此处使用 a-Star

public interface Pathfinder {

    public static interface PathStartSetter {

        PathEndSetter setStart(Iterator<? extends Location> startSupplier, Predicate<Location> startTester);

        default PathEndSetter setStart(final Location start){
            return setStart(
                new Iterator<Location>() {

                    boolean provided = false;

                    @Override
                    public boolean hasNext() {
                        return !provided;
                    }

                    @Override
                    public Location next() {
                        if(provided){
                            return null;
                        } else {
                            provided = true;
                            return start;
                        }
                    }
                },
                loc -> loc.equals(start)
            );
        }

        default PathEndSetter setStart(final List<Location> start){
            return setStart(start.iterator(),
                loc -> start.contains(loc)
            );
        }

    }

    public static interface PathEndSetter{

        public PathSolver setEnd(Predicate<Location> endTester);


        default PathSolver setEnd(final Location end){
            return setEnd(loc -> loc.equals(end));
        }

        default PathSolver setEnd(final List<Location> end){
            return setEnd(loc -> end.contains(loc));
        }
    }

    public static interface PathSolver{
        public Path solve();
    }

    public static interface Path{
        List<Location> fullPath();
        Location pathAt(int step);
        public boolean exists();
    }

    public static class NoPath implements Path {

        @Override
        public List<Location> fullPath() {
            return null;
        }

        @Override
        public Location pathAt(int step) {
            return null;
        }

        @Override
        public boolean exists() {
            return false;
        }

    }
}

`Dijkstra.java`（典型的 BFS 求解器）

请跳过阅读它，它是 vanilla dijkstra，但它确实实现了我复杂的 Pathfinder 接口

public class Dijkstra implements Pathfinder{

    public static DijkstraStartSetter begin(World world) {
        return new DijkstraStartSetter(world);
    }

    public static class DijkstraStartSetter implements PathStartSetter {
        private final World world;
        public DijkstraStartSetter(World world) {
            this.world = world;
        }

        public DijkstraEndSetter setStart(Iterator<? extends Location> startSupplier, Predicate<Location> startTester) {
            return new DijkstraEndSetter(world, startSupplier, startTester);
        }
    }

    public static class DijkstraEndSetter implements PathEndSetter{

        private final World world;
        private final Iterator<? extends Location> startSupplier;
        private final Predicate<Location> startTester;

        public DijkstraEndSetter(World world, Iterator<? extends Location> startSupplier, Predicate<Location> startTester) {
            this.world = world;
            this.startSupplier = startSupplier;
            this.startTester = startTester;
        }

        public DijkstraSolver setEnd(Location end){
            return new DijkstraSolver(world, startSupplier, startTester, end);
        }

        public DijkstraSolver setEnd(Predicate<Location> endTester){
            return new DijkstraSolver(world, startSupplier, startTester, null);
        }
    }

    public static class DijkstraSolver implements PathSolver{

        private final World world;
        private final Iterator<? extends Location> startSupplier;
        private final Predicate<Location> startTester;
        private final Location end;

        public DijkstraSolver(World world, Iterator<? extends Location> startSupplier, Predicate<Location> startTester, Location end) {
            this.world = world;
            this.startSupplier = startSupplier;
            this.startTester = startTester;
            this.end = end;
        }

        public Path solve(){
            Queue<Location> open = new LinkedList<>();
            List<Location> closed = new ArrayList<>();
            Map<Location, Location> parents = new HashMap<>();
            while (startSupplier.hasNext()) {
                open.add(startSupplier.next());
            }
            while(!open.isEmpty()){
                Location current = open.remove();
                closed.add(current);
                List<Location> neighbours = world.noWalls(current.neighbours());
                for (Location n : neighbours) {
                    if(open.contains(n) || closed.contains(n)) {
                        continue;
                    }
                    open.add(n);
                    parents.put(n, current);
                    if(n == end){
                        return makePath(parents);
                    }
                }
            }
            return new NoPath();
        }

        private Path makePath(Map<Location, Location> parents) {
            StandardPathBuilder path = StandardPath.begin();
            Location current = end;
            while(!startTester.test(current)){
                path.add(current);
                current = parents.get(current);
            }
            path.add(current);
            return path.buildReverse();
        }
    }

}

很抱歉 post 和过度设计的解决方案！我非常喜欢这个问题，以至于我被带走了。

找到包围二维网格上某个区域的最短栅栏

Find the shortest fence that encloses an area on a 2D grid

algorithm

optimization

graph-algorithm

path-finding

topology

递归问题陈述如下：

此语句的解决方案是使用此观察完成的：

`MinimalFenceSolver.java`（主要class）

`World.java` 世界定义界面

`Location.java` 界面

`CellType.java`枚举

`GridWorld.java` 生活在网格上的世界的实现

`Pathfinder.java`（界面）

`Dijkstra.java`（典型的 BFS 求解器）

找到包围二维网格上某个区域的最短栅栏

Find the shortest fence that encloses an area on a 2D grid

algorithm

optimization

graph-algorithm

path-finding

topology

递归问题陈述如下：

此语句的解决方案是使用此观察完成的：

MinimalFenceSolver.java（主要class）

World.java 世界定义界面

Location.java 界面

CellType.java枚举

GridWorld.java 生活在网格上的世界的实现

Pathfinder.java（界面）

Dijkstra.java（典型的 BFS 求解器）

`MinimalFenceSolver.java`（主要class）

`World.java` 世界定义界面

`Location.java` 界面

`CellType.java`枚举

`GridWorld.java` 生活在网格上的世界的实现

`Pathfinder.java`（界面）

`Dijkstra.java`（典型的 BFS 求解器）