Fallstudie: Das Nine-Tails-Problem

Das Neun-Schwänze-Problem kann auf das Problem des kürzesten Weges reduziert werden.
Das Neun-Schwänze-Problem ist wie folgt. Neun Münzen werden in einer Drei-mal-Drei-Matrix platziert, einige mit der Vorderseite nach oben und andere mit der Vorderseite nach unten. Ein legaler Zug besteht darin, eine aufgedeckte Münze zu nehmen und sie zusammen mit den angrenzenden Münzen umzudrehen (davon ausgenommen sind diagonal angrenzende Münzen). Ihre Aufgabe besteht darin, die Mindestanzahl an Zügen zu finden, die dazu führt, dass alle Münzen verdeckt liegen. Beginnen Sie beispielsweise mit den neun Münzen, wie in Abbildung unten (a) gezeigt. Nachdem Sie die zweite Münze in der letzten Reihe geworfen haben, sehen die neun Münzen nun wie in Abbildung unten (b) dargestellt aus. Nachdem Sie die zweite Münze in der ersten Reihe geworfen haben, sind alle neun Münzen verdeckt, wie in Abbildung unten (c) gezeigt.

Wir werden ein Programm schreiben, das den Benutzer auffordert, einen Anfangszustand der neun Münzen einzugeben, und die Lösung anzeigt, wie im folgenden Beispiellauf gezeigt.

Geben Sie die ersten neun Münzen Hs und Ts ein: HHHTTTHHH
Die Schritte zum Werfen der Münzen sind
HHH
TTT
HHH
HHH
THT
TTT
TTT
TTT
TTT

Jeder Zustand der neun Münzen stellt einen Knoten im Diagramm dar. Beispielsweise entsprechen die drei Zustände in der Abbildung oben drei Knoten im Diagramm. Der Einfachheit halber verwenden wir eine 3 * 3-Matrix zur Darstellung aller Knoten und verwenden 0 für Köpfe und 1 für Schwänze. Da es neun Zellen gibt und jede Zelle entweder 0 oder 1 ist, gibt es insgesamt 2^9 (512) Knoten mit der Bezeichnung 0, 1, . . . und 511, wie in der Abbildung unten gezeigt.

Wir weisen eine Kante vom Knoten v zu u zu, wenn es eine legale Bewegung von u nach v gibt. Die folgende Abbildung zeigt eine Teilgrafik. Beachten Sie, dass es eine Kante von 511 bis 47 gibt, da Sie eine Zelle im Knoten 47 umdrehen können, um zum Knoten 511 zu werden.

Der letzte Knoten in der Abbildung unten stellt den Zustand von neun verdeckten Münzen dar. Der Einfachheit halber nennen wir diesen letzten Knoten den Zielknoten. Daher erhält der Zielknoten die Bezeichnung 511. Angenommen, der Anfangszustand des Neun-Schwanz-Problems entspricht dem Knoten s. Das Problem reduziert sich darauf, einen kürzesten Pfad vom Knoten s zum Zielknoten zu finden, was dem Finden eines kürzesten Pfads vom Knoten s zum Zielknoten in einem BFS-Baum mit der Wurzel entspricht der Zielknoten.

Die Aufgabe besteht nun darin, einen Graphen zu erstellen, der aus 512 Knoten mit den Bezeichnungen 0, 1, 2, ... besteht. . . , 511 und Kanten zwischen den Knoten. Sobald das Diagramm erstellt ist, erhalten Sie einen BFS-Baum mit der Wurzel am Knoten 511. Im BFS-Baum können Sie den kürzesten Weg von der Wurzel zu jedem Scheitelpunkt finden. Wir erstellen eine Klasse mit dem Namen NineTailModel, die die Methode enthält, um einen kürzesten Pfad vom Zielknoten zu jedem anderen Knoten zu erhalten. Das Klassen-UML-Diagramm ist in der Abbildung unten dargestellt.

Optisch wird ein Knoten in einer 3 * 3-Matrix mit den Buchstaben H und T dargestellt. In unserem Programm verwenden wir ein eindimensionales Array aus neun Zeichen, um einen Knoten darzustellen. Beispielsweise wird der Knoten für Scheitelpunkt 1 in der Abbildung unten als {'H', 'H', 'H' dargestellt , 'H', 'H', 'H', 'H', 'H' , 'T'} im Array.

Die Methode getEdges() gibt eine Liste von Edge-Objekten zurück.

Die Methode getNode(index) gibt den Knoten für den angegebenen Index zurück. Beispielsweise gibt getNode(0) den Knoten zurück, der neun Hs enthält. getNode(511) gibt den Knoten zurück, der neun Ts enthält. Die Methode getIndex(node) gibt den Index des Knotens zurück.

Beachten Sie, dass das Datenfeld Baum als geschützt definiert ist, sodass über die Unterklasse WeightedNineTail darauf zugegriffen werden kann.

Die Methode getFlippedNode(char[] node, int position) dreht den Knoten an der angegebenen Position und seinen angrenzenden Positionen um. Diese Methode gibt den Index des neuen Knotens zurück.

Die Position ist ein Wert von 0 bis 8, der auf eine Münze im Knoten zeigt, wie in der folgenden Abbildung dargestellt.

Zum Beispiel drehen Sie den Knoten 56 in der Abbildung unten an der Position 0 um, und Sie erhalten den Knoten 51. Wenn Sie Knoten 56 an Position 1 umdrehen, erhalten Sie Knoten 47.

Die Methode flipACell(char[] node, int row, int columns) dreht einen Knoten in der angegebenen Zeile und Spalte um. Wenn Sie beispielsweise den Knoten 56 in Zeile 0 und Spalte 0 umdrehen, ist der neue Knoten 408. Wenn Sie den Knoten 56 in Zeile 2 und Spalte 0 umdrehen, ist der neue Knoten 30.

Der folgende Code zeigt den Quellcode für 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();
    }
}

Der Konstruktor (Zeilen 8–18) erstellt einen Graphen mit 512 Knoten, und jede Kante entspricht der Bewegung von einem Knoten zum anderen (Zeile 10). Aus dem Diagramm wird ein BFS-Baum erhalten, der am Zielknoten 511 verwurzelt ist (Zeile 17).

Um Kanten zu erstellen, prüft die Methode getEdges (Zeilen 21–37) jeden Knoten u, um zu sehen, ob er auf einen anderen Knoten v umgedreht werden kann. Wenn ja, fügen Sie (v, u) zur Liste Edge hinzu (Zeile 31). Die Methode getFlippedNode(node, position) findet einen umgedrehten Knoten, indem sie eine H-Zelle und ihre Nachbarn in einem Knoten umdreht (Zeilen 43–47). Die Methode flipACell(node, row, Column) dreht tatsächlich eine H-Zelle und ihre Nachbarn in einem Knoten um (Zeilen 52–60).

Die Methode getIndex(node) wird auf die gleiche Weise implementiert wie die Konvertierung einer Binärzahl in eine Dezimalzahl (Zeilen 62–72). Die Methode getNode(index) gibt einen Knoten zurück, der aus den Buchstaben H und T besteht (Zeilen 74–87).

Die Methode getShortestpath(nodeIndex) ruft die Methode getPath(nodeIndex)
auf Methode zum Abrufen eines Scheitelpunkts auf dem kürzesten Weg vom angegebenen Knoten zum Zielknoten
(Zeilen 89–91).

Die Methode printNode(node) zeigt einen Knoten auf der Konsole an (Zeilen 93–101).

Der folgende Code stellt ein Programm dar, das den Benutzer auffordert, einen Anfangsknoten einzugeben, und die Schritte zum Erreichen des Zielknotens anzeigt.

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

}

Das Programm fordert den Benutzer auf, einen Anfangsknoten mit neun Buchstaben mit einer Kombination aus Hs und Ts als Zeichenfolge in Zeile 8 einzugeben, um daraus ein Array von Zeichen zu erhalten Die Zeichenfolge (Zeile 9) erstellt ein Diagrammmodell, um einen BFS-Baum zu erhalten (Zeile 11), und erhält einen kürzesten Pfad vom Anfangsknoten zum
Zielknoten (Zeilen 12–13) und zeigt die Knoten im Pfad an (Zeilen 16–18).

Das obige ist der detaillierte Inhalt vonFallstudie: Das Nine-Tails-Problem. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!