Heure de pointe - Résoudre le problème

Question

L'Heure De Pointe
si vous n'êtes pas familier avec elle, le jeu se compose d'une collection de voitures de différentes tailles, soit horizontalement ou verticalement, sur un NxM grille qui a une seule sortie.
Chaque voiture peut se déplacer vers l'avant/vers l'arrière dans les directions de l'ensemble, aussi longtemps que l'autre voiture n'est pas bloquant. Vous pouvez ne jamais changer la direction d'une voiture.
Il y en a un spécial voiture, habituellement, c'est le rouge. C'est dans la même ligne que la sortie est dans, et l'objectif du jeu est de trouver une série de mouvements (un mouvement de déplacement de la voiture N pas en arrière ou en avant) qui permettra à la voiture rouge pour sortir du labyrinthe.

J'ai essayé de réfléchir à la façon de résoudre ce problème par le calcul, et je peux vraiment pas penser à une bonne solution.
Je suis venu avec quelques-uns:

1. Les retours en arrière. C'est assez simple, Récursivité et un peu plus de la récursivité jusqu'à ce que vous trouver la réponse. Cependant, chaque voiture peut être déplacé un peu de façons différentes, et dans chaque état de jeu un peu de voitures peuvent être déplacés, et l'arborescence du jeu va être ÉNORME.
2. Une sorte de contrainte algorithme qui permettra de prendre en compte ce qui doit être déplacé, et de travailler de manière récursive en quelque sorte. C'est une idée très approximative, mais c'est une idée.
3. Les graphiques? Le modèle du jeu des états sous forme de graphique et d'appliquer une sorte de variation sur un algorithme de coloration, à résoudre des dépendances? Encore une fois, c'est une idée très approximative.
4. Un ami a suggéré d'algorithmes génétiques. C'est possible, mais pas facilement. Je ne peux pas penser à une bonne façon de faire une fonction d'évaluation, et sans que nous l'ayons rien.

Donc la question est - Comment créer un programme qui prend une grille et le véhicule de la disposition, et les sorties d'une série d'étapes nécessaires pour obtenir le rouge voiture?

Sous-questions:

1. Trouver quelque solution.
2. Trouver une optimale de la solution minimale (nombre de coups)
3. L'évaluation de la qualité d'un état actuel est

Exemple: Comment pouvez-vous déplacer les voitures dans ce cadre, de sorte que la voiture rouge peut "sortir" le labyrinthe jusqu'à la sortie sur la droite?

Answer 1

Pour classique de l'Heure de pointe, ce problème est très souple avec un simple largeur de recherche. Le prétendu plus dur connu configuration initiale nécessite 93 se déplace à résoudre, avec un total de seulement 24132 accessible configurations. Même un naïvement mis en œuvre en largeur d'abord l'algorithme de recherche peut étudier l'ensemble de l'espace de recherche en moins de 1 seconde sur la même modeste de la machine.

Références

• Wikipedia/Heure de pointe (jeu de plateau)
• L'Heure de pointe Configurations Initiales -- ce sont des prétendait être le "noyau dur" des problèmes
• Le solveur de la source à l'ideone.com - avec sortie pour le "noyau dur" d'entrée

---

La Java solveur

Voici le code source complet de la largeur de la première recherche exhaustive solveur, écrit en C-style.

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 StackOverflowError 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");
    }
}

Il y a deux note digne de lignes dans le code source:

• L' break; lorsqu'une solution est trouvée
  • C'est maintenant, a commenté à ce que la largeur de recherche explore l' ensemble de l' espace de recherche, afin de confirmer les chiffres donnés dans le site lié ci-dessus
• L' current = sb.toString(); en slide
  • Essentiellement, cela compte chaque mouvement de la voiture comme un seul mouvement. Si une voiture est déplacé 3 cases vers la gauche, c'est 3 coups. Au combo ce que l'un déménagement (puisqu'il s'agit de la même voiture se déplaçant dans la même direction), il suffit de commenter cette ligne. Les sites liés ne reconnaît pas le combo, cette ligne est maintenant retirée pour correspondre le nombre minimum de coups donnés. Avec combo de comptage, le 93 se déplace problème ne nécessite 49 combinaisons de mouvements. C'est, si il y a un gardien de parking dans le lot qui se déplace de ces voitures, il ne lui avait suffit d'aller dans et hors d'une voiture 49 fois.

---

Vue d'ensemble de l'algorithme

L'algorithme est essentiellement une largeur de recherche, mis en œuvre avec une file d'attente comme il est typique. Un prédécesseur de la carte est maintenue afin que tout état peut être retracée à l'état initial. Une clé ne sera jamais reconfiguré, et que les inscriptions sont insérés dans la largeur-premier ordre de recherche de plus court chemin d'accès est garanti.

Un état est représenté comme un NxM-longueur String. Chaque char représente une entité sur la carte, stockées en ligne ordre majeur.

Les états voisins sont trouvés par le contrôle tous les 4 directions à partir d'un espace vide, à la recherche d'une voiture de type, glissant comme type de chambre peut accueillir.

Il y a beaucoup de travail inutile (par exemple le long de la "ruelles" sont analysés à plusieurs reprises), mais comme mentionné précédemment, bien que la version généralisée est PSPACE-complet, le classique de l'Heure de pointe variante est très traitable par la force brute.

Référence sur wikipédia

• En largeur d'abord de recherche
• Ligne ordre majeur

Answer 2

Voici ma réponse. Son résout le puzzle du grand maître en un peu moins de 6 secondes.

Il utilise une première recherche étendue (BFS). L'astuce consiste à rechercher une disposition de tableau que vous avez déjà vue dans les recherches précédentes et à annuler cette séquence. En raison du BFS, si vous avez déjà vu cette mise en page avant d'y arriver de manière plus courte, laissez donc cette séquence continuer à essayer de la résoudre plutôt que celle-ci plus longue.

 #!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

Il y a en fait un article du MIT qui fait spécifiquement référence à Rush Hour (j'ai utilisé le terme de recherche "puzzles à blocs coulissants")

Answer 4

Vous devriez recurse (votre "retour en arrière" de la solution). C'est probablement la seule façon de résoudre les énigmes de ce genre; la question est de savoir comment le faire vite.

Comme vous l'avez remarqué, l'espace de recherche sera grande, mais pas trop grand, si vous avez une taille raisonnable conseil d'administration. Par exemple, vous avez établi une grille de 6x6 avec 12 voitures sur elle. En supposant que chacun est un montant de 2 voiture, ce qui donne 5 places/p, donc au plus 5^12 = 244,140,625 postes potentiels. Cette place même dans un entier de 32 bits. Donc, une possibilité consiste à allouer un tableau énorme, un emplacement par le potentiel de position, et l'utilisation memoization pour vous assurer de ne pas répéter une position.

La prochaine chose à noter est que la plupart de ces "potentiel" les positions ne sont pas, en fait, possible (ils avaient impliquer les voitures qui se chevauchent). Donc, au lieu de cela, utiliser une table de hachage pour garder une trace de chaque position que vous avez visités. Cela aura une petite surcharge de la mémoire par l'entrée, mais il sera probablement plus efficace que la "panoplie" de la solution. Il sera, cependant, prendre un peu plus de temps pour chaque point d'accès.

Comme le MIT le papier dans @Daniel en réponse dit, le problème est PSPACE-complet, ce qui signifie beaucoup d'astuces utilisées pour réduire la complexité des problèmes NP probablement ne peut pas être utilisé.

Cela dit, l'une des deux solutions ci-dessus à la répétition de position est un problème qui doit travailler pour de petits réseaux. Tout sera déterminé par la taille de la problème est, et la quantité de mémoire de votre ordinateur; mais l'exemple que vous avez affichée doit être pas mal du tout, même pour un pc ordinaire.

Answer 5

Juste de finir d'écrire mon de la mise en œuvre et expérimenter avec elle. Je suis d'accord avec polygenelubricants que l'espace d'état est vraiment petit pour le jeu classique (6x6 conseil d'administration). Cependant, j'ai essayé un savant de recherche, de mise en œuvre (A* recherche). J'ai été curieux au sujet de la réduction de la exploré espace d'état par rapport à un simple BFS.

Algorithme A* peut être considérée comme une généralisation de la SECTION de recherche. La décision de chemin à explorer suivante est déterminée par un score qui combine à la fois la longueur du chemin (c'est à dire le nombre de coups) et une borne inférieure sur les mouvements restants comptent. La façon dont j'ai choisi de calculer cette dernière, est d'obtenir la distance de la voiture rouge de la sortie, puis ajouter 1 pour chaque véhicule dans le chemin, il doit être déplacé au moins une fois afin de dégager la voie. Lorsque je remplace la limite inférieure de calcul avec une constante 0, je reçois régulièrement des BFS comportement.

Après l'inspection de quatre puzzles à partir de cette liste, j'ai trouvé que* recherche explore en moyenne 16% de moins d'états que régulièrement BFS.