algorithm - programming - develop artificial intelligence

Hora punta-Cómo resolver el juego

Question

Hora pico
si no estás familiarizado con él, el juego consiste en una colección de autos de diferentes tamaños, configurados horizontal o verticalmente, en una grilla NxM que tiene una única salida.
Cada automóvil puede moverse hacia adelante o hacia atrás en las direcciones en las que se encuentra, siempre que otro automóvil no lo esté bloqueando. Nunca puedes cambiar la dirección de un automóvil.
Hay un auto especial, generalmente es el rojo. Está ubicado en la misma fila que la salida, y el objetivo del juego es encontrar una serie de movimientos (un movimiento - mover un carro N pasos hacia atrás o hacia adelante) que permitirán que el auto rojo salga del laberinto .

He estado tratando de pensar cómo resolver este problema computacionalmente, y realmente no puedo pensar en ninguna buena solución.
Se me ocurrieron algunos:

1. Retroceder. Esto es bastante simple: recursividad y alguna recursión más hasta que encuentres la respuesta. Sin embargo, cada automóvil se puede mover de diferentes maneras, y en cada estado del juego se pueden mover algunos coches, y el árbol de juego resultante será ENORME.
2. Algún tipo de algoritmo de restricción que tendrá en cuenta lo que se debe mover, y trabajar de forma recursiva de alguna manera. Esta es una idea muy aproximada, pero es una idea.
3. Gráficos? ¿Modela el juego como un gráfico y aplica algún tipo de variación en un algoritmo de coloreo para resolver dependencias? De nuevo, esta es una idea muy aproximada.
4. Un amigo sugirió algoritmos genéticos. Esto es posible pero no fácil. No puedo pensar en una buena forma de hacer una función de evaluación, y sin eso no tenemos nada.

Entonces, la pregunta es: ¿cómo crear un programa que tome una grilla y el diseño del vehículo, y emite una serie de pasos necesarios para sacar el carro rojo?

Subtemas:

1. Encontrar alguna solución.
2. Encontrar una solución óptima (cantidad mínima de movimientos)
3. Evaluar qué tan bueno es un estado actual

Ejemplo: ¿Cómo puedes mover los autos en esta configuración, para que el auto rojo pueda "salir" del laberinto a través de la salida a la derecha?
http://scienceblogs.com/ethicsandscience/upload/2006/12/RushHour.jpg

Answer 1

Acabo de terminar de escribir mi implementación y experimentar con ella. Estoy de acuerdo con polygenelubricants que el espacio de estado es realmente pequeño para el juego clásico (tablero 6x6). Sin embargo, probé una implementación de búsqueda inteligente (búsqueda A * ). Tenía curiosidad por la reducción del espacio de estado explorado en comparación con un BFS simple.

Un algoritmo * se puede ver como una generalización de la búsqueda BFS. La decisión de qué camino explorar a continuación está determinada por un puntaje que combina tanto la longitud del camino (es decir, el número de movimientos) como un límite inferior en el recuento de movimientos restantes. La forma en que elegí calcular esto último, es obtener la distancia del auto rojo desde la salida, y luego agregar 1 por cada vehículo en el camino, ya que tiene que moverse al menos una vez para despejar el camino. Cuando reemplazo el cálculo del límite inferior con una constante 0, obtengo un comportamiento BFS regular.

Después de inspeccionar cuatro acertijos de esta lista , descubrí que la búsqueda A * explora en promedio un 16% menos de estados que una BFS normal.

Answer 2

Aquí está mi respuesta. Resuelve el gran acertijo en menos de 6 segundos.

Utiliza una primera búsqueda de amplitud (BFS). El truco es buscar un diseño de tablero que haya visto antes en búsquedas anteriores y abortar esa secuencia. Debido a BFS, si has visto ese diseño antes de que hayas llegado a él de una manera más corta, deja que esa secuencia siga intentándolo en lugar de esta más larga.

#!perl

# Program by Rodos rodos at haywood dot org

use Storable qw(dclone);
use Data::Dumper;

print "Lets play Rush Hour! /n";


# Lets define our current game state as a grid where each car is a different letter.
# Our special car is a marked with the specific letter T
# The boarder is a * and the gloal point on the edge is an @.
# The grid must be the same witdh and height 
# You can use a . to mark an empty space

# Grand Master
@startingGrid = (
 [''*'',''*'',''*'',''*'',''*'',''*'',''*'',''*''],
 [''*'',''.'',''.'',''A'',''O'',''O'',''O'',''*''],
 [''*'',''.'',''.'',''A'',''.'',''B'',''.'',''*''],
 [''*'',''.'',''T'',''T'',''C'',''B'',''.'',''@''],
 [''*'',''D'',''D'',''E'',''C'',''.'',''P'',''*''],
 [''*'',''.'',''F'',''E'',''G'',''G'',''P'',''*''],
 [''*'',''.'',''F'',''Q'',''Q'',''Q'',''P'',''*''],
 [''*'',''*'',''*'',''*'',''*'',''*'',''*'',''*'']
);

# Now lets print out our grid board so we can see what it looks like.
# We will go through each row and then each column.
# As we do this we will record the list of cars (letters) we see into a hash

print "Here is your board./n";

&printGrid(/@startingGrid);

# Lets find the cars on the board and the direction they are sitting

for $row (0 .. $#startingGrid) {
    for $col (0 .. $#{$startingGrid[$row]} ) {

        # Make spot the value of the bit on the grid we are looking at
        $spot = $startingGrid[$row][$col];

        # Lets record any cars we see into a "hash" of valid cars.
        # If the splot is a non-character we will ignore it cars are only characters
        unless ($spot =~ //W/) {

            # We will record the direction of the car as the value of the hash key.
            # If the location above or below our spot is the same then the car must be vertical.
            # If its not vertical we mark as it as horizonal as it can''t be anything else!

            if ($startingGrid[$row-1][$col] eq $spot || $startingGrid[$row+1] eq $spot) {
                $cars{$spot} = ''|'';
            } else {
                $cars{$spot} = ''-'';
            }
        }
    }
}

# Okay we should have printed our grid and worked out the unique cars
# Lets print out our list of cars in order

print "/nI have determined that you have used the following cars on your grid board./n";
foreach $car (sort keys %cars) {
    print " $car$cars{$car}";
}
print "/n/n";

end;

&tryMoves();

end;

# Here are our subroutines for things that we want to do over and over again or things we might do once but for 
# clatiry we want to keep the main line of logic clear

sub tryMoves {

    # Okay, this is the hard work. Take the grid we have been given. For each car see what moves are possible
    # and try each in turn on a new grid. We will do a shallow breadth first search (BFS) rather than depth first. 
    # The BFS is achieved by throwing new sequences onto the end of a stack. You then keep pulling sequnces
    # from the front of the stack. Each time you get a new item of the stack you have to rebuild the grid to what
    # it looks like at that point based on the previous moves, this takes more CPU but does not consume as much
    # memory as saving all of the grid representations.

    my (@moveQueue);
    my (@thisMove);
    push @moveQueue, /@thisMove;

    # Whlst there are moves on the queue process them                
    while ($sequence = shift @moveQueue) { 

        # We have to make a current view of the grid based on the moves that got us here

        $currentGrid = dclone(/@startingGrid);
        foreach $step (@{ $sequence }) {
            $step =~ /(/w)-(/w)(/d)/;
            $car = $1; $dir = $2; $repeat = $3;

            foreach (1 .. $repeat) {
                &moveCarRight($car, $currentGrid) if $dir eq ''R'';
                &moveCarLeft($car,  $currentGrid) if $dir eq ''L'';
                &moveCarUp($car,    $currentGrid) if $dir eq ''U'';
                &moveCarDown($car,  $currentGrid) if $dir eq ''D'';
            }
        }

        # Lets see what are the moves that we can do from here.

        my (@moves);

        foreach $car (sort keys %cars) {
            if ($cars{$car} eq "-") {
                $l = &canGoLeft($car,$currentGrid);
                push @moves, "$car-L$l" if ($l);
                $l = &canGoRight($car,$currentGrid);
                push @moves, "$car-R$l" if ($l);
            } else {
                $l = &canGoUp($car,$currentGrid);
                push @moves, "$car-U$l" if ($l);
                $l = &canGoDown($car,$currentGrid);
                push @moves, "$car-D$l" if ($l);
            }
        }

        # Try each of the moves, if it solves the puzzle we are done. Otherwise take the new 
        # list of moves and throw it on the stack

        foreach $step (@moves) {

            $step =~ /(/w)-(/w)(/d)/;
            $car = $1; $dir = $2; $repeat = $3;

            my $newGrid = dclone($currentGrid);

            foreach (1 .. $repeat) {
                &moveCarRight($car, $newGrid) if $dir eq ''R'';
                &moveCarLeft($car, $newGrid) if $dir eq ''L'';
                &moveCarUp($car, $newGrid) if $dir eq ''U'';
                &moveCarDown($car, $newGrid) if $dir eq ''D'';
            }

            if (&isItSolved($newGrid)) {
                print sprintf("Solution in %d moves :/n", (scalar @{ $sequence }) + 1);
                print join ",", @{ $sequence };
                print ",$car-$dir$repeat/n";
                return;
            } else {

                # That did not create a solution, before we push this for further sequencing we want to see if this
                # pattern has been encountered before. If it has there is no point trying more variations as we already
                # have a sequence that gets here and it might have been shorter, thanks to our BFS

                if (!&seen($newGrid)) {
                    # Um, looks like it was not solved, lets throw this grid on the queue for another attempt
                    my (@thisSteps) = @{ $sequence };
                    push @thisSteps, "$car-$dir$repeat";
                    push @moveQueue, /@thisSteps;
                }
            }            
        }
    }
}    

sub isItSolved {

    my ($grid) = shift;

    my ($row, $col);
    my $stringVersion;

    foreach $row (@$grid) {
        $stringVersion .= join "",@$row;
    }

    # We know we have solve the grid lock when the T is next to the @, because that means the taxi is at the door
    if ($stringVersion =~ //T/@/) {
        return 1;
    }
    return 0;
}    

sub seen {

    my ($grid) = shift;

    my ($row, $col);
    my $stringVersion;

    foreach $row (@$grid) {
        $stringVersion .= join "",@$row;
    }

    # Have we seen this before?
    if ($seen{$stringVersion}) {
        return 1;
    }
    $seen{$stringVersion} = 1;
    return 0;
}    

sub canGoDown {

    my ($car) = shift;

    return 0 if $cars{$car} eq "-";

    my ($grid) = shift;

    my ($row, $col);


    for ($row = $#{$grid}; $row >= 0; --$row) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[++$row][$col] eq ".") {
                    ++$l;
                }
                return $l;
            }
        }
    }
    return 0;
}

sub canGoUp {

    my ($car) = shift;

    return 0 if $cars{$car} eq "-";

    my ($grid) = shift;

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[--$row][$col] eq ".") {
                    ++$l;
                } 
                return $l;
            }
        }
    }
    return 0;
}

sub canGoRight {

    my ($car) = shift;

    return 0 if $cars{$car} eq "|";

    my ($grid) = shift;

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for ($col = $#{$grid->[$row]}; $col >= 0; --$col ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[$row][++$col] eq ".") {
                    ++$l;
                } 
                return $l;
            }
        }
    }
    return 0;
}

sub canGoLeft {

    my ($car) = shift;

    return 0 if $cars{$car} eq "|";

    my ($grid) = shift;

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                # See how many we can move
                $l = 0;
                while ($grid->[$row][--$col] eq ".") {
                    ++$l;
                } 
                return $l;
            }
        }
    }
    return 0;
}

sub moveCarLeft {

    # Move the named car to the left of the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving left requires sweeping left to right.

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only horizontal cards can move left
    die "Opps, tried to move a vertical car $car left" if $cars{$car} eq "|";

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car left into an occupied spot/n" if $grid->[$row][$col-1] ne ".";
                $grid->[$row][$col-1] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}

sub moveCarRight {

    # Move the named car to the right of the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving right requires sweeping right to left (backwards).

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only horizontal cards can move right
    die "Opps, tried to move a vertical car $car right" if $cars{$car} eq "|";

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for ($col = $#{$grid->[$row]}; $col >= 0; --$col ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car right into an occupied spot/n" if $grid->[$row][$col+1] ne ".";
                $grid->[$row][$col+1] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}


sub moveCarUp {

    # Move the named car up in the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving right requires sweeping top down.

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only vertical cards can move up
    die "Opps, tried to move a horizontal car $car up" if $cars{$car} eq "-";

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car up into an occupied spot/n" if $grid->[$row-1][$col] ne ".";
                $grid->[$row-1][$col] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}

sub moveCarDown {

    # Move the named car down in the passed grid. Care must be taken with the algoritm
    # to not move part of the car and then come across it again on the same pass and move it again 
    # so moving right requires sweeping upwards from the bottom.

    # We need to know which car you want to move and the reference to the grid you want to move it on
    my ($car) = shift;
    my ($grid) = shift;

    # Only vertical cards can move up
    die "Opps, tried to move a horizontal car $car down" if $cars{$car} eq "-";

    my ($row, $col);    

    for ($row = $#{$grid}; $row >=0; --$row) {
        for $col (0 .. $#{$grid->[$row]} ) {
            if ($grid->[$row][$col] eq $car) {
                die "Tried to move car $car down into an occupied spot/n" if $grid->[$row+1][$col] ne ".";
                $grid->[$row+1][$col] = $car;
                $grid->[$row][$col] = ".";
            }
        }
    }
}

sub printGrid {

    # Print out a representation of a grid

    my ($grid) = shift; # This is a reference to an array of arrays whch is passed as the argument

    my ($row, $col);

    for $row (0 .. $#{$grid}) {
        for $col (0 .. $#{$grid->[$row]} ) {
                print $grid->[$row][$col], " ";
        }
        print "/n";
    }
}

Answer 3

Creo que la recursividad es una mala idea, a menos que realice un seguimiento de lo que ya ha visitado; podrías terminar recurriendo infinitamente moviendo un automóvil de un lado a otro.

Tal vez este sea un buen comienzo: represente y almacene cada estado de la tabla como un gráfico no dirigido. Luego, para cada movimiento posible, verifique los estados pasados ​​para asegurarse de que no está golpeando nuevamente el mismo estado.

Ahora haga otro gráfico no dirigido donde los nodos representan los estados y los bordes representan la capacidad de pasar de un estado a otro mediante el movimiento de un automóvil. Explore estados hasta que uno de ellos sea una solución. Luego siga los bordes hacia el principio para descubrir un camino de movimiento.

Answer 4

Deberías recurse (tu solución de "retroceso"). Esta es probablemente la única forma de resolver acertijos como este; la pregunta es cómo hacerlo rápido.

Como ha notado, el espacio de búsqueda será grande, pero no demasiado grande, si tiene una placa de tamaño razonable. Por ejemplo, ha dibujado una cuadrícula de 6x6 con 12 autos. Suponiendo que cada uno es un automóvil de tamaño 2, eso da 5 espacios / por lo que a lo sumo 5 ^ 12 = 244,140,625 posiciones potenciales. Esto incluso cabe en un entero de 32 bits. De modo que una posibilidad es asignar una gran matriz, una ranura por posición potencial, y usar memoria para asegurarse de no repetir una posición.

Lo siguiente a tener en cuenta es que la mayoría de esas posiciones "potenciales" no son, de hecho, posibles (implicarían la superposición de autos). Por lo tanto, use una tabla hash para realizar un seguimiento de cada posición que ha visitado. Esto tendrá una pequeña sobrecarga de memoria por entrada, pero probablemente será más eficiente en cuanto a espacio que la solución de "gran conjunto". Sin embargo, demorará un poco más para cada acceso de entrada.

Como dice el documento del MIT en la respuesta de @ Daniel , el problema es que PSPACE está completo, lo que significa que muchos de los trucos utilizados para reducir la complejidad de los problemas NP probablemente no se puedan utilizar.

Dicho esto, cualquiera de las dos soluciones anteriores para el problema de posición repetida debería funcionar para redes pequeñas. Todo estará determinado por cuán grande es el problema y cuánta memoria tiene su computadora; pero el ejemplo que muestra no debe ser ningún problema, incluso para una computadora de escritorio ordinaria.

Answer 5

Escribí un solucionador de sudoku. Si bien los detalles son completamente diferentes, creo que el problema general es similar. Por un lado, tratar de hacer heurística inteligente en un solucionador de sudoku es mucho más lento que una solución de fuerza bruta. Probar cada movimiento, con algunos heurísticos simples y sin duplicados es el camino a seguir. Es un poco más difícil verificar los estados duplicados de la placa en la hora punta, pero no mucho.

Si miras el tablero en tu muestra, solo hay 4 movimientos válidos. En un momento dado, solo habrá algunos movimientos válidos.

En cada nivel de recursión, copie el estado del tablero y pruebe cada movimiento válido en el tablero. Para cada cuadrado vacío, mueva cada automóvil que pueda en ese cuadrado. Si el nuevo estado de la placa no se encuentra en la lista del historial, recurse a otro nivel. Por lista de historial, me refiero a dar a cada nivel de recursión acceso a cada placa que condujo a ese estado, probablemente en una lista vinculada. Use hash para descartar rápidamente estados desiguales.

La clave para esto es tener un estado de placa simple que pueda copiarse y modificarse fácilmente. Probablemente una matriz con un int por cuadrado que indique qué coche cubre ese cuadrado, si lo hay. Entonces solo necesitas iterar a través de los cuadrados y descubrir movimientos legales. Un movimiento legal significa cuadrados vacíos entre el cuadrado de prueba y un automóvil orientado hacia él.

Al igual que con sudoku, la peor opción posible sería un algoritmo genético.

Answer 6

Para la Hora punta clásica, este problema es muy manejable con una primera búsqueda de ancho simple. La configuración inicial más difícil de reclamar requiere 93 movimientos para resolver, con un total de solo 24132 configuraciones alcanzables. Incluso un ingenioso algoritmo de búsqueda implementado ingeniosamente puede explorar todo el espacio de búsqueda en menos de 1 segundo incluso en una máquina modesta.

Referencias

• Wikipedia / Hora punta (juego de mesa)
• Configuraciones iniciales de hora punta : se dice que son los problemas "más difíciles"
• Fuente de Solver en ideone.com - con salida para la entrada "más difícil"

El solucionador de Java

Aquí está el código fuente completo de un solucionador exhaustivo de búsqueda de ancho, escrito en estilo C.

import java.util.*;

public class RushHour {
    // classic Rush Hour parameters
    static final int N = 6;
    static final int M = 6;
    static final int GOAL_R = 2;
    static final int GOAL_C = 5;

    // the transcription of the 93 moves, total 24132 configurations problem
    // from http://cs.ulb.ac.be/~fservais/rushhour/index.php?window_size=20&offset=0
    static final String INITIAL =   "333BCC" +
                                    "B22BCC" +
                                    "B.XXCC" +
                                    "22B..." +
                                    ".BB.22" +
                                    ".B2222";

    static final String HORZS = "23X";  // horizontal-sliding cars
    static final String VERTS = "BC";   // vertical-sliding cars
    static final String LONGS = "3C";   // length 3 cars
    static final String SHORTS = "2BX"; // length 2 cars
    static final char GOAL_CAR = ''X'';
    static final char EMPTY = ''.'';      // empty space, movable into
    static final char VOID = ''@'';       // represents everything out of bound

    // breaks a string into lines of length N using regex
    static String prettify(String state) {
        String EVERY_NTH = "(?<=//G.{N})".replace("N", String.valueOf(N));
        return state.replaceAll(EVERY_NTH, "/n");
    }

    // conventional row major 2D-1D index transformation
    static int rc2i(int r, int c) {
        return r * N + c;
    }

    // checks if an entity is of a given type
    static boolean isType(char entity, String type) {
        return type.indexOf(entity) != -1;
    }

    // finds the length of a car
    static int length(char car) {
        return
            isType(car, LONGS) ? 3 :
            isType(car, SHORTS) ? 2 :
            0/0; // a nasty shortcut for throwing IllegalArgumentException
    }

    // in given state, returns the entity at a given coordinate, possibly out of bound
    static char at(String state, int r, int c) {
        return (inBound(r, M) && inBound(c, N)) ? state.charAt(rc2i(r, c)) : VOID;
    }
    static boolean inBound(int v, int max) {
        return (v >= 0) && (v < max);
    }

    // checks if a given state is a goal state
    static boolean isGoal(String state) {
        return at(state, GOAL_R, GOAL_C) == GOAL_CAR;
    }

    // in a given state, starting from given coordinate, toward the given direction,
    // counts how many empty spaces there are (origin inclusive)
    static int countSpaces(String state, int r, int c, int dr, int dc) {
        int k = 0;
        while (at(state, r + k * dr, c + k * dc) == EMPTY) {
            k++;
        }
        return k;
    }

    // the predecessor map, maps currentState => previousState
    static Map<String,String> pred = new HashMap<String,String>();
    // the breadth first search queue
    static Queue<String> queue = new LinkedList<String>();
    // the breadth first search proposal method: if we haven''t reached it yet,
    // (i.e. it has no predecessor), we map the given state and add to queue
    static void propose(String next, String prev) {
        if (!pred.containsKey(next)) {
            pred.put(next, prev);
            queue.add(next);
        }
    }

    // the predecessor tracing method, implemented using recursion for brevity;
    // guaranteed no infinite recursion, but may throw Error on
    // really long shortest-path trace (which is infeasible in standard Rush Hour)
    static int trace(String current) {
        String prev = pred.get(current);
        int step = (prev == null) ? 0 : trace(prev) + 1;
        System.out.println(step);
        System.out.println(prettify(current));
        return step;
    }

    // in a given state, from a given origin coordinate, attempts to find a car of a given type
    // at a given distance in a given direction; if found, slide it in the opposite direction
    // one spot at a time, exactly n times, proposing those states to the breadth first search
    //
    // e.g.
    //    direction = -->
    //    __n__
    //   /     /
    //   ..o....c
    //      /___/
    //      distance
    //
    static void slide(String current, int r, int c, String type, int distance, int dr, int dc, int n) {
        r += distance * dr;
        c += distance * dc;
        char car = at(current, r, c);
        if (!isType(car, type)) return;
        final int L = length(car);
        StringBuilder sb = new StringBuilder(current);
        for (int i = 0; i < n; i++) {
            r -= dr;
            c -= dc;
            sb.setCharAt(rc2i(r, c), car);
            sb.setCharAt(rc2i(r + L * dr, c + L * dc), EMPTY);
            propose(sb.toString(), current);
            current = sb.toString(); // comment to combo as one step
        }
    }

    // explores a given state; searches for next level states in the breadth first search
    //
    // Let (r,c) be the intersection point of this cross:
    //
    //     @       nU = 3     ''@'' is not a car, ''B'' and ''X'' are of the wrong type;
    //     .       nD = 1     only ''2'' can slide to the right up to 5 spaces
    //   2.....B   nL = 2
    //     X       nR = 4
    //
    // The n? counts how many spaces are there in a given direction, origin inclusive.
    // Cars matching the type will then slide on these "alleys".
    //
    static void explore(String current) {
        for (int r = 0; r < M; r++) {
            for (int c = 0; c < N; c++) {
                if (at(current, r, c) != EMPTY) continue;
                int nU = countSpaces(current, r, c, -1, 0);
                int nD = countSpaces(current, r, c, +1, 0);
                int nL = countSpaces(current, r, c, 0, -1);
                int nR = countSpaces(current, r, c, 0, +1);
                slide(current, r, c, VERTS, nU, -1, 0, nU + nD - 1);
                slide(current, r, c, VERTS, nD, +1, 0, nU + nD - 1);
                slide(current, r, c, HORZS, nL, 0, -1, nL + nR - 1);
                slide(current, r, c, HORZS, nR, 0, +1, nL + nR - 1);
            }
        }
    }
    public static void main(String[] args) {
        // typical queue-based breadth first search implementation
        propose(INITIAL, null);
        boolean solved = false;
        while (!queue.isEmpty()) {
            String current = queue.remove();
            if (isGoal(current) && !solved) {
                solved = true;
                trace(current);
                //break; // comment to continue exploring entire space
            }
            explore(current);
        }
        System.out.println(pred.size() + " explored");
    }
}

Hay dos líneas dignas de mención en el código fuente:

• El break; cuando se encuentra una solución
  • Esto ahora se comenta para que la primera búsqueda de amplitud explore todo el espacio de búsqueda, para confirmar los números que figuran en el sitio web vinculado anteriormente.
• La current = sb.toString(); en slide
  • Esencialmente esto cuenta cada movimiento de cualquier automóvil como un solo movimiento. Si un automóvil se mueve 3 espacios a la izquierda, eso significa 3 movimientos. Para combinar esto como un solo movimiento (ya que involucra el mismo automóvil moviéndose en la misma dirección), simplemente comente esta línea. El sitio web vinculado no reconoce combo, por lo que esta línea no está comentada para coincidir con el número mínimo de movimientos dados. Con el conteo combinado, el problema de 93 movimientos solo requiere 49 movimientos combinados. Es decir, si hay un asistente de estacionamiento en el estacionamiento que mueve estos autos, solo tendría que entrar y salir del automóvil 49 veces.

Descripción general del algoritmo

El algoritmo es esencialmente una búsqueda de amplitud inicial, implementada con una cola como es típico. Se mantiene un mapa predecesor para que cualquier estado pueda rastrearse hasta el estado inicial. Nunca se reasignará una clave, y como las entradas se insertan en una orden de búsqueda de primer orden, se garantiza la ruta más corta.

Un estado se representa como una String longitud NxM . Cada char representa una entidad en el tablero, almacenada en orden mayor de fila.

Los estados vecinos se encuentran escaneando las 4 direcciones desde un espacio vacío, buscando un tipo de vehículo apropiado, deslizándolo como acomoda la habitación.

Aquí hay mucho trabajo redundante (por ejemplo, los "callejones" largos se escanean varias veces), pero como se mencionó anteriormente, aunque la versión generalizada es PSPACE-completa, la clásica variante de Hora punta es muy manejable por fuerza bruta.

Referencias de Wikipedia

• Búsqueda en primer lugar
• Orden de fila mayor

Answer 7

De hecho, hay un documento de MIT que hace referencia específicamente a Rush Hour (utilicé el término de búsqueda "rompecabezas de bloques deslizantes")