algorithm - pathfinding - Encuentra la cerca más corta que encierra un área en una grilla 2D

pathfinding traduccion

Question

Tengo una cuadrícula 2D de 50 x 50. Las celdas de cuadrícula pueden tener uno de tres estados:

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

Mi configuración inicial es una cuadrícula con algunas celdas (tal vez el 10% de ellas, en su mayoría contiguas) marcadas como "dentro". Aleatoriamente hay algunas células de "pared" también. Las otras celdas están "vacías".

Estoy tratando de encontrar la cerca más corta que pueda construir alrededor de las celdas "internas" para que todas las celdas "internas" estén cercadas (las vallas se construyen cambiando las celdas "vacías" por celdas "de pared"). Si estamos evaluando soluciones, la mejor solución reducirá al mínimo la cantidad de células "vacías" que deben cambiarse a células "de pared".

Más rigurosamente, en la configuración final, existe la restricción de que para cada celda "interna" no hay una ruta al borde de la cuadrícula que no pase a través de una celda de "pared". En mi caso, el movimiento diagonal está permitido.

Supongo que puedo hacer algo inteligente que implique la transformación a distancia, o calcular el esqueleto topológico de la cuadrícula, pero no es inmediatamente obvio para mí. Si este es un problema de optimización clásico, no sé qué términos usar en google.

¿Hay un algoritmo O (n ^ 2) para encontrar la cerca más corta?

EDITAR: No es tan fácil como encontrar el casco convexo de las celdas "internas", porque las celdas de "pared" preexistentes están libres. Imagina un trozo en forma de "C" de una pared preexistente, con todas las celdas "internas" en el interior de la C. La mayoría de las veces, completar la C con celdas de "pared" será más barato que dibujar un casco convexo alrededor de todo las celdas "adentro". Esto es lo que hace que este problema sea difícil.

Answer 1

¡Qué lindo problema!

Como @qwertyman ha notado, el problema es encontrar un corte de vértice mínimo entre las celdas "internas" y el límite de la cuadrícula. Si bien es concebible que este problema especial en una grilla pueda tener una solución más fácil, no creo que ninguna de las otras soluciones resuelva el problema en todos los casos.

Se puede ver que las celdas en cuadrículas cuadradas tienen hasta cuatro o hasta ocho vecinos (@tobias_k y @hidefromkgb). Si no tomamos en cuenta las celdas de pared existentes (libres), esto es lo que las cercas típicas se verán en las cuadrículas de 4 y 8:

No es que en ambos casos, haya muchas más cercas mínimas, pero estas cajas rectangulares y octagonales son mínimas y fáciles de encontrar. Además, son cercas mínimas con un área interior máxima.

Hay dos complicaciones: celdas de pared preexistentes libres, y la posibilidad de que múltiples componentes pequeños de la valla sean más baratos que una caja grande.

Ambas complicaciones están bien resueltas en un problema de corte de vértice mínimo; las celdas de pared preexistentes pueden simplemente eliminarse del gráfico (y las celdas internas pueden fusionarse con otras celdas internas conectadas, dejando solo una celda interna para cada componente conectado de las celdas internas). Desafortunadamente, los cortes mínimos generalmente se consideran remoción de bordes en lugar de vértices.

Dudo que cualquier algoritmo sea más fácil que implementar un algoritmo de corte de vertice limpio. Esto es a lo que nos enfrentamos:

En este ejemplo, cuatro vallas pequeñas son más baratas que una grande, pero eso depende de las proporciones exactas. Podríamos comenzar con una valla grande e intentar mejorarla por división, como lo hace @LazyMammal, o con esgrima cada componente conectado por separado, pero en cualquier caso, estas situaciones no son triviales.

Este también es problemático:

¿Usaremos el segmento grande de valla libre? ¿Debemos cercar cada punto por separado? ¿Usaremos tres vallas medianas? No importa si estamos comenzando a lo grande y dividiéndonos, como lo hace @LazyMammal, o comenzamos con recuadros delimitadores individuales y nos unimos a ellos, estas situaciones parecen presentar los mismos problemas que los cortes mínimos generales están resolviendo.

Si está de acuerdo con las aproximaciones a soluciones óptimas, o tal vez se limita a instancias en cuadrículas de 50 por 50 y puede descartar rápidamente estas complicaciones, ¿tal vez hay algo fácil y rápido? No lo sé.

Para un conjunto conectado G de celdas internas, encontrar una valla más barata funcionaría así:

• Encuentre una ruta FL de flujo más corta de celdas vacías desde ese grupo hasta el límite.

• Encuentre una ruta FE de "valla" más barata alrededor del grupo usando todas las celdas que no estén en G o FL. Pruebe cada celda en FL como punto de partida, o cualquier celda que esté tanto en FL como en la valla de G. El costo de las celdas vacías es 1, el costo de las celdas de pared es 0 y el costo de las celdas internas que no están en G es 0. Tendrás que cortar temporalmente la cuadrícula a lo largo de FL para asegurarte de que FE recorra G.

(Pero no sé cómo llenar las lagunas en un grupo para conectar todas sus células, en presencia de células de pared).

Entonces, ¿quizás el verdadero problema es qué células internas unir entre sí? Las celdas internas conectadas deben permanecer conectadas, bien. Además, si toca alguna cerca mínima, únete a sus grupos. Aparte de eso, aproxima con solo probar diferentes combinaciones?

No lo sé; Creo que el problema en las grillas grandes presenta las mismas complicaciones y complejidad que los problemas generales de corte mínimo, por lo que si realmente necesitas la optimización, resuélvelos.

Relevante: https://cstheory.stackexchange.com/questions/2877/ (gracias qwertyman), https://en.wikipedia.org/wiki/Vertex_separator con una noción diferente de separadores "mínimos".

Answer 2

De acuerdo, resolví el problema, pero no he calculado la complejidad asintótica.

Lo hice a través de Dynamic Progamming, donde definí el problema recursivamente y también agregué un criterio de eliminación para una buena aceleración.

Aquí está la declaración del problema recursivo:

Encuentra el conjunto de cercado más pequeño de forma que no haya camino desde un startArea de startArea hasta un border .
El problema recursivo se proporciona con:

• una grid contiene paredes naturales preexistentes
• un startArea
• una definición de Border
• un conjunto preexistente de fences que se colocaron y no se pueden quitar
• un número máximo de cercas N

Devuelve lo siguiente:

• Si se encuentra una cerca, devuelva una List de las vallas
• Si no se requieren vallas, devuelva una empty list
• Si el tamaño de la cerca debe superar N paredes, devuelva <invalid> (por ejemplo, null )

La solución a esta declaración se hizo usando esta observación:

Cualquier cercado debe contener al menos una pared en la ruta óptima desde el área de inicio hasta el borde (de lo contrario, esa ruta sería válida y se usaría para escapar)

Por lo tanto, una forma de resolver el enunciado recursivo del problema es la siguiente:

Inicialice el algoritmo recursivo proporcionando:

• El mundo inicial
• The startArea,
• La definición del borde (por ejemplo, la celda debe estar en la frontera de la cuadrícula)
• Una lista vacía de vallas iniciales
• Un número máximo de vallas establecido en Positive_Infinity (sin restricción)

Luego recurse de la siguiente manera:

• Genere la path más corta desde startArea hasta el border sin pasar por fences existentes
• Si no hay camino que conduzca a la salida, devuelva las fences predefinidas
  • Justificación : el camino está bloqueado, el cercado existente es suficiente, no es necesario agregar ningún
• Si las fences predefinidas tienen al menos N elementos, devuelve <invalid>
  • Justificación : las vallas predefinidas son insuficientes, por lo que se necesitarían al menos N+1 vallas. Como se sabe que existe una solución con N vallas, no es necesario investigar más a fondo
• Inicialice bestLength como la entrada número máximo de vallas N como
• Inicialice bestPath como " ìnvalid
• Iterar sobre cada location largo de la path (excluyendo las celdas que están en el área de startArea , que supongo que no se pueden startArea )
  • generar una solución al problema recursivo de la siguiente manera:
    • la grid entrada contiene paredes naturales preexistentes
    • la entrada startArea
    • la definición de Border entrada
    • el conjunto preexistente de fences más la location actual
    • el número máximo de cercas bestLength
  • Si la solución es <invalid> , continúe la iteración
  • Si la solución existe
    • Guárdelo como bestPath
    • Actualiza bestLength su longitud
  • Si la longitud de la solución es N+1 devuélvala
• Return bestPath

Básicamente, estamos cerrando los mejores caminos a medida que los encontramos. A medida que avanzamos, el camino cambia y lo bloqueamos.

El mejor IMO es el mecanismo de eliminación selectiva, similar a una beta-pruning .

Análisis de complejidad sucia (la grilla es NxN):

• La ruta tiene una longitud N , estamos iterando sobre su longitud.
  • Cada iteración recursiva crea una ruta de longitud N (normalmente es más larga, pero lo ignoraré). Gracias a la eliminación, voy a hacer esto una complejidad de log(N) solamente
    • En cada paso estamos realizando BFS, por lo que N.log(N)

Complejidad total: N².log (N) ²` (¿quizás? No sé lo que estoy haciendo)

Aquí hay una versión de Java:

MinimalFenceSolver.java (clase principal)

El problema se construye en general , y se resuelven static métodos 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 
    }
}

Interfaz World.java para una definición mundial

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);

}

Interfaz Location.java

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

CellType.java enum

public enum CellType {
    WALL, EMPTY
}

GridWorld.java una implementación de un mundo que vive en una red

Contiene su propia implementación de Ubicación. Tiene la capacidad de ser decorado temporalmente con vallas adicionales usando la subclase 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 (Interfaz)

Esta es una interfaz con exceso de fluidez en caso de que quiera probar otros solucionadores, si logra hacer una buena heurística para el borde, a-Star puede usarse aquí

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 (El solucionador típico de BFS)

Siéntase libre de omitir la lectura, es dijkstra vainilla, pero implementa mi intrincada interfaz 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();
        }
    }

}

Perdón por la increíblemente larga publicación y solución sobre ingeniería. Me encantó tanto la Pregunta que me dejé llevar.

Answer 3

Esto se puede resolver como un problema de simplificación de gráficos:

1. crea un gráfico de la grilla (sin diagonales)
2. eliminar (eliminar) nodos internos
3. colapsar (fusionar) Nodos de pared
4. describir un camino alrededor del borde del gráfico
5. iterar a lo largo de la ruta
   • compruebe si los nodos de ruta cercanos comparten un vecino de gráfico vacío (cercano = nodos de ruta [n .. n + k])
   • compruebe si hay una nueva distancia de trayectoria <= distancia de trayectoria existente (bordes de conteo)
   • verificar si el nodo Inside se va a quedar varado por un atajo (no permitir)
   • ajustar la ruta si se cumplen las condiciones
   • eliminar (eliminar) nodos gráficos que ya no son necesarios
6. detener cuando el camino no puede ser reducido más

En el peor de los casos, debe atravesar todos los nodos de los vértices en el gráfico varias veces para cada borde. Entonces parece que O (V * E) o en otras palabras O (N ^ 2).

Answer 4

Lo que probablemente quiera es un casco convexo bidimensional .

Yo recomendaría el llamado algoritmo de envoltura de regalos . Su complejidad temporal es O (n²) en el peor de los casos. Su esencia es la siguiente.

Sin pérdida de generalidad, asumamos que no hay 3 puntos en la nube que sean colineales.

1. Comenzamos con un punto más a la izquierda, ya que cada casco sobre una nube de puntos finita debe incluir al menos un punto que está más a la izquierda (y, teniendo en cuenta las restricciones anteriores, no más de dos son posibles, y ambos pertenecen al casco).
2. Entonces comenzamos a usar la fuerza bruta en tal punto que el resto está en el mismo plano de los dos semiplanos, en el cual el plano inicial está dividido por una línea trazada desde el punto inicial al que se busca.
3. Ahora hacemos que el encontrado sea una nueva inicial, y luego repetimos [2-3] hasta que el casco se cierre.

[NB] tenga en cuenta que encontrar un punto que es un predecesor de la inicial actual no lo lleva a ninguna parte (como esto: • ⇌ •), por lo que debe omitirse, a menos que no haya más puntos que estos dos.

Answer 5

Para mí, sigue siendo una variante de casco convexo. debe incluir en su casco convexo todas las celdas que sean vecinas de la celda interna y que no sean una celda interna + incluir celdas que estén al [principio] y [fin] de una pared (muro contiguo). Entonces parte importante es excluir las células vecinas si esas células están dentro de una pared. Para verificar si la celda está dentro de una C con forma de pared, por ejemplo (I) puede calcular una línea ax + b desde p1 - p2, luego usando un tipo de partición puntual, en sentido horario / antihorario y luego puntos de pared adicionales con su vecino. de la búsqueda. En el siguiente ejemplo, los puntos vecinos a I serán excluidos. Por lo tanto, el algoritmo encontrará la conexión p1-> p2 p1-p2 como directa.

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

En el siguiente ejemplo, los puntos T son puntos vecinos

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

después del casco convexo algo obtendrás:

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

eso significa que una ruta p2 [T1] [T2] [T3] p1 y las líneas entre esos puntos le dan un ajuste mínimo. Como puede ver, cada pared tiene que almacenar también un valor si cualquier punto adyacente está DENTRO de una forma de muro (como C), esas paredes deben incluirse en un casco convexo, pero las que no tienen vecinos internos solo se pueden usar si la distancia al siguiente punto es más pequeña usando la pared existente de costo cero ... Bueno, es un poco complicado para una explicación rápida, pero supongo que puedes obtener algo de eso ...

EDITAR: en esa convexa computada deberá ejecutar también flujo mínimo para afinar casos como:

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

donde uno de I está dentro, pero la valla de min está alrededor de ambos I sin p1 ni p2. En algo p1 y p2 se seleccionará, luego para todas las paredes que tengan I interno, debe calcular dist (p1, externalI) + dist (p2, externalI) con dist (internalI, eternalI) y elegir la más pequeña ...externalI es el conectado a p1 y p2 (podría ser uno o dos puntos externos ...)

Answer 6

Si con la valla más corta se refiere a una celda que requiere un número mínimo de celdas de "pared", la valla con un rectángulo mínimo de cerramiento funcionará.