Étude de cas : le problème des neuf queues

Le problème à neuf queues peut être réduit au problème du chemin le plus court.
Le problème à neuf queues est le suivant. Neuf pièces sont placées dans une matrice de trois par trois, certaines face visible et d'autres face cachée. Un mouvement légal consiste à prendre une pièce face visible et à la renverser, ainsi que les pièces adjacentes (cela n'inclut pas les pièces diagonalement adjacentes). Votre tâche est de trouver le nombre minimum de mouvements qui conduisent à ce que toutes les pièces soient face cachée. Par exemple, commencez par les neuf pièces comme indiqué dans la figure ci-dessous (a). Après avoir lancé la deuxième pièce de la dernière rangée, les neuf pièces sont maintenant telles qu'indiquées dans la figure ci-dessous (b). Après avoir lancé la deuxième pièce de la première rangée, les neuf pièces sont toutes face cachée, comme le montre la figure ci-dessous (c).

Nous allons écrire un programme qui invite l'utilisateur à entrer un état initial des neuf pièces et affiche la solution, comme le montre l'exemple d'exécution suivant.

Entrez les neuf pièces initiales Hs et Ts : HHHTTTHHH
Les étapes pour lancer les pièces sont
HHH
TTT
HHH
HHH
THT
TTT
TTT
TTT
TTT

Chaque état des neuf pièces représente un nœud dans le graphique. Par exemple, les trois états de la figure ci-dessus correspondent à trois nœuds du graphique. Pour plus de commodité, nous utilisons une matrice 3 * 3 pour représenter tous les nœuds et utilisons 0 pour les têtes et 1 pour les queues. Puisqu'il y a neuf cellules et que chaque cellule est soit 0 ou 1, il y a un total de 2^9 (512) nœuds, étiquetés 0, 1, . . . , et 511, comme le montre la figure ci-dessous.

Nous attribuons une arête du nœud v à u s'il y a un mouvement légal de u à v. La figure ci-dessous montre un graphique partiel. Notez qu'il y a un bord de 511 à 47, puisque vous pouvez retourner une cellule dans le nœud 47 pour devenir le nœud 511.

Le dernier nœud de la figure ci-dessous représente l'état de neuf pièces face cachée. Pour plus de commodité, nous appelons ce dernier nœud le nœud cible. Ainsi, le nœud cible est étiqueté 511. Supposons que l'état initial du problème à neuf queues corresponde au nœud s. Le problème se réduit à trouver le chemin le plus court du nœud s au nœud cible, ce qui équivaut à trouver le chemin le plus court du nœud s au nœud cible dans un arbre BFS enraciné à le nœud cible.

Maintenant, la tâche consiste à créer un graphe composé de 512 nœuds étiquetés 0, 1, 2, . . . , 511, et les arêtes parmi les nœuds. Une fois le graphique créé, obtenez un arbre BFS enraciné au nœud 511. À partir de l’arborescence BFS, vous pouvez trouver le chemin le plus court depuis la racine jusqu’à n’importe quel sommet. Nous allons créer une classe nommée NineTailModel, qui contient la méthode permettant d'obtenir le chemin le plus court du nœud cible à n'importe quel autre nœud. Le diagramme de classe UML est présenté dans la figure ci-dessous.

Visuellement, un nœud est représenté dans une matrice 3*3 avec les lettres H et T. Dans notre programme, nous utilisons un tableau unidimensionnel de neuf caractères pour représenter un nœud. Par exemple, le nœud du sommet 1 dans la figure ci-dessous est représenté par {'H', 'H', 'H' , 'H', 'H', 'H', 'H', 'H' , 'T'} dans le tableau.

La méthode getEdges() renvoie une liste d'objets Edge.

La méthode getNode(index) renvoie le nœud pour l'index spécifié. Par exemple, getNode(0) renvoie le nœud qui contient neuf H. getNode(511) renvoie le nœud qui contient neuf T. La méthode getIndex(node) renvoie l'index du nœud.

Notez que le champ de données tree est défini comme protégé afin qu'il soit accessible depuis la sous-classe WeightedNineTail.

La méthode getFlippedNode(char[] node, int position) retourne le nœud à la position spécifiée et ses positions adjacentes. Cette méthode renvoie l'index du nouveau nœud.

La position est une valeur comprise entre 0 et 8, qui pointe vers une pièce de monnaie dans le nœud, comme le montre la figure suivante.

Par exemple, pour le nœud 56 dans la figure ci-dessous, retournez-le à la position 0, et vous obtiendrez le nœud 51. Si vous retournez le nœud 56 à la position 1, vous obtiendrez le nœud 47.

La méthode flipACell(char[] node, int row, int column) retourne un nœud au niveau de la ligne et de la colonne spécifiées. Par exemple, si vous inversez le nœud 56 à la ligne 0 et à la colonne 0, le nouveau nœud est 408. Si vous retournez le nœud 56 à la ligne 2 et à la colonne 0, le nouveau nœud est 30.

Le code ci-dessous montre le code source de NineTailModel.java.

import java.util.*;

public class NineTailModel {
    public final static int NUMBER_OF_NODES = 512;
    protected AbstractGraph<Integer>.Tree tree; // Define a tree

    /** Construct a model */
    public NineTailModel() {
        // Create edges
        List<AbstractGraph.Edge> edges = getEdges();

        // Create a graph
        UnweightedGraph<Integer> graph = new UnweightedGraph<>(edges, NUMBER_OF_NODES);

        // Obtain a BSF tree rooted at the target node
        tree = graph.bfs(511);
    }

    /** Create all edges for the graph */
    private List<AbstractGraph.Edge> getEdges() {
        List<AbstractGraph.Edge> edges = new ArrayList<>(); // Store edges

        for (int u = 0; u < NUMBER_OF_NODES; u++) {
            for (int k = 0; k < 9; k++) {
                char[] node = getNode(u); // Get the node for vertex u
                if (node[k] == 'H') {
                    int v = getFlippedNode(node, k);
                    // Add edge (v, u) for a legal move from node u to node v
                    edges.add(new AbstractGraph.Edge(v, u));
                }
            }
        }

        return edges;
    }

    public static int getFlippedNode(char[] node, int position) {
        int row = position / 3;
        int column = position % 3;

        flipACell(node, row, column);
        flipACell(node, row - 1, column);
        flipACell(node, row + 1, column);
        flipACell(node, row, column - 1);
        flipACell(node, row, column + 1);

        return getIndex(node);
    }

    public static void flipACell(char[] node, int row, int column) {
        if (row >= 0 && row <= 2 && column >= 0 && column <= 2) {
            // Within the boundary
            if (node[row * 3 + column] == 'H')
                node[row * 3 + column] = 'T'; // Flip from H to T
            else
                node[row * 3 + column] = 'H'; // Flip from T to H
            }
    }

    public static int getIndex(char[] node) {
        int result = 0;

        for (int i = 0; i < 9; i++)
            if (node[i] == 'T')
                result = result * 2 + 1;
            else
                result = result * 2 + 0;

        return result;
    }

    public static char[] getNode(int index) {
        char[] result = new char[9];

        for (int i = 0; i < 9; i++) {
            int digit = index % 2;
            if (digit == 0)
                result[8 - i] = 'H';
            else
                result[8 - i] = 'T';
            index = index / 2;
        }

        return result;
    }

    public List<Integer> getShortestPath(int nodeIndex) {
        return tree.getPath(nodeIndex);
    }

    public static void printNode(char[] node) {
        for (int i = 0; i < 9; i++)
            if (i % 3 != 2)
                System.out.print(node[i]);
            else
                System.out.println(node[i]);

        System.out.println();
    }
}

Le constructeur (lignes 8 à 18) crée un graphe avec 512 nœuds, et chaque arête correspond au passage d'un nœud à l'autre (ligne 10). À partir du graphique, un arbre BFS enraciné au nœud cible 511 est obtenu (ligne 17).

Pour créer des arêtes, la méthode getEdges (lignes 21 à 37) vérifie chaque nœud u pour voir s'il peut être basculé vers un autre nœud v. Si tel est le cas, ajoutez (v, u) à la liste Edge (ligne 31). La méthode getFlippedNode(node, position) trouve un nœud inversé en retournant une cellule H et ses voisines dans un nœud (lignes 43 à 47). La méthode flipACell(node, row, column) retourne en fait une cellule H et ses voisines dans un nœud (lignes 52 à 60).

La méthode getIndex(node) est implémentée de la même manière que la conversion d'un nombre binaire en nombre décimal (lignes 62 à 72). La méthode getNode(index) renvoie un nœud composé des lettres H et T (lignes 74 à 87).

La méthode getShortestpath(nodeIndex) appelle la getPath(nodeIndex)
méthode pour obtenir un sommet sur le chemin le plus court du nœud spécifié au nœud cible
(lignes 89 à 91).

La méthode printNode(node) affiche un nœud sur la console (lignes 93 à 101).

Le code ci-dessous donne un programme qui invite l'utilisateur à saisir un nœud initial et affiche les étapes pour atteindre le nœud cible.

import java.util.Scanner;

public class NineTail {

    public static void main(String[] args) {
        // Prompt the user to enter nine coins' Hs and Ts
        System.out.print("Enter the initial nine coins Hs and Ts: ");
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        char[] initialNode = s.toCharArray();

        NineTailModel model = new NineTailModel();
        java.util.List<Integer> path = model.getShortestPath(NineTailModel.getIndex(initialNode));

        System.out.println("The steps to flip the coins are ");
        for (int i = 0; i < path.size(); i++)
            NineTailModel.printNode(NineTailModel.getNode(path.get(i).intValue()));
    }

}

Le programme invite l'utilisateur à saisir un nœud initial avec neuf lettres avec une combinaison de Hs et Ts sous forme de chaîne à la ligne 8, obtient un tableau de caractères de la chaîne (ligne 9), crée un modèle de graphique pour obtenir un arbre BFS (ligne 11), obtient le chemin le plus court du nœud initial au
nœud cible (lignes 12 à 13) et affiche les nœuds du chemin (lignes 16 à 18).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!