Ответ 1

Какая хорошая проблема!

Как заметил @qwertyman, проблема заключается в нахождении минимальной вершины, отрезанной между "внутренними" ячейками и границей сетки. Хотя вполне возможно, что эта специальная проблема на сетке может иметь более легкое решение, я не думаю, что любое из других решений решит проблему во всех случаях.

Ячейки на квадратных сетках можно увидеть как имеющие до четырех или до восьми соседей (@tobias_k и @hidefromkgb). Если пренебречь существующими (свободными) стеновыми ячейками, то какие типичные заборы будут выглядеть на 4- и 8-сетках:

Не то, чтобы в обоих случаях было еще много минимальных заборов, но эти прямоугольные и восьмиугольные ограничивающие прямоугольники минимальны и легко найти. Кроме того, они представляют собой минимальные заборы с максимальной внутренней площадью.

Есть два осложнения: бесплатные предварительно существующие стеновые ячейки и возможность того, что несколько небольших элементов забора дешевле, чем одна большая ограничивающая коробка.

Оба осложнения хорошо решены в минимальной задаче обрезания вершины; предварительно существующие стеновые ячейки можно просто удалить из графика (и внутренние ячейки могут быть объединены с другими связанными внутренними ячейками, оставив только одну внутреннюю ячейку для каждого связанного компонента внутренних ячеек). К сожалению, минимальные сокращения обычно считаются удалением ребер, а не вершин!

Я сомневаюсь, что любой алгоритм будет проще, чем реализация чистого алгоритма вырезания вершины. Вот с чем мы сталкиваемся:

В этом примере четыре маленьких забора дешевле одного большого, но это зависит от точных пропорций. Мы могли бы начать с одного большого забора и попытаться улучшить его путем деления, например, @LazyMammal, или с ограждением каждого подключенного компонента отдельно, но в любом случае эти ситуации не являются тривиальными.

Это тоже проблематично:

Можно ли использовать большой свободный сегмент забора? Будем ли мы запереть каждое маленькое пятно отдельно? Будем ли мы использовать три средних забора? Независимо от того, начинаем ли мы с большого и разделяем, например, @LazyMammal, или начинаем с отдельных ограничивающих блоков и присоединяем их, эти ситуации, похоже, представляют те же проблемы, что и общие минимальные сокращения.

Если вы в порядке с приближением к оптимальным решениям или можете ограничиться экземплярами в сетках 50 на 50 и можете быстро исключить эти сложности, может быть, что-то легко и быстро? Я не знаю.

Для подключенного множества G внутренних ячеек поиск самого дешевого забора будет работать следующим образом:

• Найдите кратчайший путь "потока" FL пустых ячеек от этой группы до границы.

• Найдите самый дешевый путь "забор" FE вокруг группы, используя все ячейки, не находящиеся ни в G, ни в FL. Попробуйте либо каждую ячейку FL в качестве начальной точки, либо любую ячейку, которая находится как в FL, так и в G gence. Стоимость пустых ячеек равна 1, стоимость стеновых ячеек равна 0, а стоимость внутренних ячеек не в G равна 0. Вам нужно временно разрезать сетку вдоль FL, чтобы убедиться, что FE идет вокруг G.

(Но я не знаю, как заполнить пробелы в группах, чтобы соединить все его ячейки - в присутствии стенных ячеек.)

Так что, может быть, реальная проблема заключается в том, какие внутренние ячейки нужно объединить? Связанные внутренние ячейки должны оставаться на связи, хорошо. Кроме того, если какие-либо минимальные заборы касаются, присоединитесь к их группам. Помимо этого, приблизительные, просто попробуйте разные комбинации?

Я не знаю; Я считаю, что проблема на больших сетках сопряжена с такими же сложностями и сложностью, как и общие проблемы с минимальным разрезом, поэтому, если вам действительно нужна оптимальность, решите их.

Релевантно: https://cstheory.stackexchange.com/questions/2877/ (спасибо qwertyman), https://en.wikipedia.org/wiki/Vertex_separator с другим понятием "минимальных" разделителей.

Ответ 2

Это можно решить как задачу упрощения графика:

• создать график сетки (без диагоналей)
• удалить (удалить) внутренние узлы
• Свернуть (слияние) Настенные узлы
• описать путь по краю графа
• итерация по пути
  • проверьте, имеют ли соседние узлы пути пустой сосед графа (рядом = узлы пути [n.. n + k])
  • проверить, если новое расстояние пути <= существующее расстояние пути (графы счета)
  • проверьте, не будет ли внутри node ярлык (не разрешать)
  • отрегулируйте путь, если выполнены условия
  • удалить (удалить) узлы графа, которые больше не нужны
• остановить, когда путь больше не может быть сокращен

В худшем случае вам нужно пересечь все вершинные узлы в графе несколько раз для каждого ребра. Таким образом, это выглядит как O (V * E) или, другими словами, O (N ^ 2).

Ответ 3

То, что вы, скорее всего, хотите, это двумерный выпуклый корпус.

Я рекомендую так называемый алгоритм подарочной упаковки. Его сложность по времени - O (n²) в худшем случае. Его суть такова:

Без ограничения общности предположим, что в облаке нет трех точек, которые являются коллинеарными.

• Начнем с самой левой точки, так как каждая оболочка над областью конечных точек должна включать по крайней мере одну точку, которая является самой левой (и, учитывая вышеприведенные ограничения, возможно не более двух из них, и оба они принадлежат к корпус).
• Затем мы начинаем с грубой силой указывать такую ​​точку, что все остальные находятся на одном и том же из двух полуплоскостей, в которые начальная плоскость делится на линию, взятую из начальной точки, на ту, которую искали.
• Теперь мы создаем новый исходный текст, а затем повторяем [2-3], пока корпус не будет закрыт.

[NB] помните, что поиск точки, которая является предшественником текущего начального, ни к чему не приводит (например: • ⇌ •), поэтому ее следует пропустить, если нет других точек, кроме этих двух.

Ответ 4

Если самый короткий забор вы имеете в виду тот, который берет минимальное количество "стенных" ячеек, будет работать забор с минимальным охватывающим прямоугольником.

Ответ 5

Для меня это еще вариант выпуклого корпуса. вы должны включить в свой выпуклый корпус все ячейки, которые являются соседями внутри ячейки и которые не являются внутренней ячейкой +, включают в себя ячейки, которые находятся на [начале] и [конце] стены (смежная стена). Тогда важная часть состоит в том, чтобы исключить соседние ячейки, если эти ячейки находятся внутри стены. Чтобы проверить, находится ли ячейка внутри стены, например, (I), вы можете вычислить строку ax + b из p1-p2, а затем используя некоторую проверку разбиения точек по часовой стрелке/против часовой стрелки, а затем дальнейшие настенные точки со своей соседней точкой, чтобы исключить это от поиска. В примере ниже точки соседи с я будут исключены. Таким образом, алгоритм найдет p1- > p2-соединение p1-p2 как прямое.

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

В приведенном ниже примере точки T являются соседними точками

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

после выпуклого корпуса algo вы получите:

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

что означает путь p2 [T1] [T2] [T3] p1, а линии между этими точками дают минимальную обертку. Поскольку вы можете видеть, что каждая стена должна также хранить значение, если какая-либо точка соседа находится внутри формы стены (например, C), эти стены должны быть включены в выпуклый корпус, но те, которые не имеют внутренних соседей, могут использоваться только если расстояние до следующей точки меньше, используя нулевую стоимость существующей стены.. Ну, это немного сложно для быстрого объяснения, но я полагаю, вы можете получить что-то от этого.

EDIT: на этом вычисленном выпуклом вам нужно будет также запустить мин-поток для настройки таких случаев, как:

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

где один из я находится внутри, но min-забор вокруг обоих я без p1 и p2. В algo p1 и p2 будут выбраны, то для всех стенок, которые имеют внутренний I, вам нужно вычислить dist (p1, externalI) + dist (p2, externalI) с dist (internalI, eternalI) и выбрать меньший .externalI тот, который связан с p1 и p2 (может быть одной или двумя внешними точками.)

Ответ 6

OK Я решил проблему, но я не вычислил асимптотическую сложность.

Я сделал это через Dynamic Progamming, где я решил проблему рекурсивно, а также добавил критерии отбора для хорошего ускорения.

Вот рекурсивная постановка задачи:

Найдите наименьший набор фехтования в a, так что нет пути от startArea до border.
Рекурсивная проблема обеспечивается:

• a grid, содержащий естественные, ранее существовавшие стены
• a startArea
• a border определение
• уже существующий набор fences, который был помещен и не может быть удален
• максимальное количество ограждений N

Возвратите следующее:

• Если обнаружено фехтование, верните a List заборов
• Если никаких ограждений не требуется, верните empty list
• Если размер забора должен превышать стены N, верните <invalid> (например, null)

Решение этого утверждения было выполнено с использованием этого наблюдения:

Любое ограждение должно содержать по крайней мере одну стену на оптимальном пути от начальной области до границы (в противном случае этот путь будет действительным и будет использоваться для выхода)

Следовательно, способ решения рекурсивной задачи состоит в следующем:

Инициализировать рекурсивный алгоритм, предоставив:

• Первоначальный мир
• В начало,
• Определение границы (например, ячейка должна находиться на границе сетки)
• Пустой список начальных заборов
• Максимальное количество ограждений, установленных на Positive_Infinity (без ограничений)

Затем recurse следующим образом:

• Создайте кратчайший path от startArea до border без прохождения через существующий fences
• Если ни один путь не ведет к выходу, верните предварительно определенный fences
  • Обоснование: путь заблокирован, существующее ограждение достаточно, не нужно добавлять никаких
• Если предопределенный fences имеет не менее N элементов, верните <invalid>
  • Обоснование: предопределенные заборы недостаточны, поэтому потребуется, по крайней мере, N+1 заборы. Поскольку известно, что существует решение с N ограждениями, нет необходимости исследовать далее
• Инициализировать bestLength как входное максимальное количество ограждений N как
• Инициализировать bestPath как ìnvalid
• Итерации по каждому location вдоль path (исключая ячейки, которые находятся в startArea, которые, как я полагаю, не могут быть обнесены стеной)
  • порождает решение рекурсивной задачи следующим образом:
    • вход grid, содержащий естественные, ранее существовавшие стены
    • вход startArea
    • определение ввода border
    • уже существующий набор fences плюс текущий location
    • максимальное количество заборов bestLength
  • Если решение <invalid>, продолжите повторение
  • Если решение существует
    • Сохраните его как bestPath
    • Обновить bestLength его длину
  • Если длина решения N+1 возвращает его
• Возврат bestPath

В принципе, мы облекаем лучшие пути, как мы их находим. Когда мы наступаем, путь меняется, и мы стягиваем это.

Лучший бит IMO - это механизм отбраковки, аналогичный бета-обрезке.

Анализ грязной сложности (сетка NxN):

• Путь имеет длину N, мы повторяем его длину.
  • Каждая рекурсивная итерация создает путь длины N (обычно это дольше, но я это проигнорирую). Благодаря отбраковке я сделаю эту сложность только log(N)
    • На каждом этапе мы выполняем BFS, поэтому N.log(N)

Общая сложность: N².log(N) ²` (может быть? Я не знаю, что я делаю)

Вот его версия Java:

MinimalFenceSolver.java (основной класс)

Задача построена в 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 enum

public enum CellType {
    WALL, EMPTY
}

GridWorld.java реализация мира, который живет на сетке

Содержит собственную реализацию местоположения. Имеет возможность временно украсить дополнительными ограждениями с помощью подкласса GridWorldWithWall.

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)

Не стесняйтесь прочитывать его, он ванильный 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();
        }
    }

}

Извините за удивительно длинный пост и переработанное решение! Мне просто понравился вопрос, так что я увлекся.