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 verwenden0für Köpfe und1für Schwänze. Da es neun Zellen gibt und jede Zelle entweder0oder1ist, gibt es insgesamt 2^9 (512) Knoten mit der Bezeichnung0,1, . . . und511, wie in der Abbildung unten gezeigt.

Wir weisen eine Kante vom Knotenvzuuzu, wenn es eine legale Bewegung vonunachvgibt. Die folgende Abbildung zeigt eine Teilgrafik. Beachten Sie, dass es eine Kante von511bis47gibt, da Sie eine Zelle im Knoten47umdrehen können, um zum Knoten511zu 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 denZielknoten. Daher erhält der Zielknoten die Bezeichnung511. Angenommen, der Anfangszustand des Neun-Schwanz-Problems entspricht dem Knotens. Das Problem reduziert sich darauf, einen kürzesten Pfad vom Knotenszum Zielknoten zu finden, was dem Finden eines kürzesten Pfads vom Knotenszum 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 Bezeichnungen0,1,2, ... besteht. . . ,511und Kanten zwischen den Knoten. Sobald das Diagramm erstellt ist, erhalten Sie einen BFS-Baum mit der Wurzel am Knoten511. Im BFS-Baum können Sie den kürzesten Weg von der Wurzel zu jedem Scheitelpunkt finden. Wir erstellen eine Klasse mit dem NamenNineTailModel, 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 BuchstabenHundTdargestellt. In unserem Programm verwenden wir ein eindimensionales Array aus neun Zeichen, um einen Knoten darzustellen. Beispielsweise wird der Knoten für Scheitelpunkt1in der Abbildung unten als {'H','H','H'dargestellt ,'H','H','H','H','H','T'} im Array.

Die MethodegetEdges()gibt eine Liste vonEdge-Objekten zurück.

Die MethodegetNode(index)gibt den Knoten für den angegebenen Index zurück. Beispielsweise gibtgetNode(0)den Knoten zurück, der neunHs enthält.getNode(511)gibt den Knoten zurück, der neunTs enthält. Die MethodegetIndex(node)gibt den Index des Knotens zurück.

Beachten Sie, dass das DatenfeldBaumals geschützt definiert ist, sodass über die UnterklasseWeightedNineTaildarauf zugegriffen werden kann.

Die MethodegetFlippedNode(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 von0bis8, der auf eine Münze im Knoten zeigt, wie in der folgenden Abbildung dargestellt.

Zum Beispiel drehen Sie den Knoten56in der Abbildung unten an der Position0um, und Sie erhalten den Knoten51. Wenn Sie Knoten56an Position1umdrehen, erhalten Sie Knoten47.

Die MethodeflipACell(char[] node, int row, int columns)dreht einen Knoten in der angegebenen Zeile und Spalte um. Wenn Sie beispielsweise den Knoten56in Zeile0und Spalte0umdrehen, ist der neue Knoten408. Wenn Sie den Knoten56in Zeile2und Spalte0umdrehen, ist der neue Knoten30.

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.Tree tree; // Define a tree /** Construct a model */ public NineTailModel() { // Create edges List edges = getEdges(); // Create a graph UnweightedGraph 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 getEdges() { List 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 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 Zielknoten511verwurzelt ist (Zeile 17).

Um Kanten zu erstellen, prüft die MethodegetEdges(Zeilen 21–37) jeden Knotenu, um zu sehen, ob er auf einen anderen Knotenvumgedreht werden kann. Wenn ja, fügen Sie (v,u) zur ListeEdgehinzu (Zeile 31). Die MethodegetFlippedNode(node, position)findet einen umgedrehten Knoten, indem sie eineH-Zelle und ihre Nachbarn in einem Knoten umdreht (Zeilen 43–47). Die MethodeflipACell(node, row, Column)dreht tatsächlich eineH-Zelle und ihre Nachbarn in einem Knoten um (Zeilen 52–60).

Die MethodegetIndex(node)wird auf die gleiche Weise implementiert wie die Konvertierung einer Binärzahl in eine Dezimalzahl (Zeilen 62–72). Die MethodegetNode(index)gibt einen Knoten zurück, der aus den BuchstabenHundTbesteht (Zeilen 74–87).

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

Die MethodeprintNode(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 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 ausHs undTs 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!