Fallstudie: Das Weighted Nine Tails Problem

Das gewichtete Neun-Schwänze-Problem kann auf das gewichtete Problem des kürzesten Weges reduziert werden.
Abschnitt stellte das Neun-Schwänze-Problem vor und löste es mithilfe des BFS-Algorithmus. In diesem Abschnitt wird eine Variante des Problems vorgestellt und mithilfe des Kürzeste-Wege-Algorithmus gelöst.

Das Neun-Schwänze-Problem besteht darin, die Mindestanzahl der Züge zu finden, die dazu führen, dass alle Münzen nach unten zeigen. Bei jedem Zug werden eine Kopfmünze und ihre Nachbarn geworfen. Das gewichtete Problem mit neun Schwänzen weist jedem Zug die Anzahl der Würfe als Gewicht zu. Sie können beispielsweise die Münzen in Abbildung unten a in die in Abbildung unten b ändern, indem Sie die erste Münze in der ersten Reihe und ihre beiden Nachbarn umdrehen. Somit beträgt das Gewicht für diesen Zug 3. Sie können die Münzen in Abbildung unten c in Abbildung unten d ändern, indem Sie die mittlere Münze und ihre vier Nachbarn umdrehen. Das Gewicht für diesen Zug beträgt also 5.

Das gewichtete Neun-Schwänze-Problem kann auf die Suche nach einem kürzesten Weg von einem Startknoten zum Zielknoten in einem kantengewichteten Diagramm reduziert werden. Der Graph hat 512 Knoten. Erstellen Sie eine Kante vom Knoten v nach u, wenn eine Verschiebung vom Knoten u zum Knoten v erfolgt. Weisen Sie die Anzahl der Drehungen als Gewicht der Kante zu.

Erinnern Sie sich daran, dass wir im Abschnitt eine Klasse NineTailModel zur Modellierung des Neun-Schwänze-Problems definiert haben. Wir definieren jetzt eine neue Klasse mit dem Namen WeightedNineTailModel, die NineTailModel erweitert, wie in der Abbildung unten gezeigt.

Die Klasse NineTailModel erstellt einen Graph und erhält einen Baum, der am Zielknoten 511 verwurzelt ist. WeightedNineTailModel ist dasselbe wie NineTailModel, außer dass es einen WeightedGraph erstellt und einen ShortestPathTree erhält, der am Zielknoten 511. WeightedNineTailModel erweitert NineTailModel. Die Methode getEdges() findet alle Kanten im Diagramm. Die Methode getNumberOfFlips(int u, int v) gibt die Anzahl der Flips vom Knoten u zum Knoten v zurück. Die Methode getNumberOfFlips(int u) gibt die Anzahl der Flips vom Knoten u zum Zielknoten zurück.

Der folgende Code implementiert

WeightedNineTailModel.

package demo;
import java.util.*;

public class WeightedNineTailModel extends NineTailModel {
    /** Construct a model */
    public WeightedNineTailModel() {
        // Create edges
        List<WeightedEdge> edges = getEdges();

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

        // Obtain a shortest path tree rooted at the target node
        tree = graph.getShortestPath(511);
    }

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

        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);
                    int numberOfFlips = getNumberOfFlips(u, v);

                    // Add edge (v, u) for a legal move from node u to node v
                    edges.add(new WeightedEdge(v, u, numberOfFlips));
                }
            }
        }

        return edges;
    }

    private static int getNumberOfFlips(int u, int v) {
        char[] node1 = getNode(u);
        char[] node2 = getNode(v);

        int count = 0; // Count the number of different cells
        for(int i = 0; i < node1.length; i++)
            if(node1[i] != node2[i]) count++;

        return count;
    }

    public int getNumberOfFlips(int u) {
        return (int)((WeightedGraph<Integer>.ShortestPathTree)tree).getCost(u);
    }
}

WeightedNineTailModel erweitert NineTailModel, um einen WeightedGraph zu erstellen, um das gewichtete Neun-Schwanz-Problem zu modellieren (Zeilen 10–11). Für jeden Knoten u findet die Methode getEdges() einen umgedrehten Knoten v und weist die Anzahl der Umdrehungen als Gewicht für die Kante zu (v, u) (Zeile 30). Die Methode getNumberOfFlips(int u, int v) gibt die Anzahl der Flips vom Knoten u zum Knoten v zurück (Zeilen 38–47). Die Anzahl der Flips ist die Anzahl der verschiedenen Zellen zwischen den zwei Knoten (Zeile 44).

Das

WeightedNineTailModel erhält einen ShortestPathTree, der am Zielknoten 511 verwurzelt ist (Zeile 14). Beachten Sie, dass tree ein geschütztes Datenfeld ist, das in NineTailModel definiert ist, und ShortestPathTree eine Unterklasse von Tree ist. Die in NineTailModel definierten Methoden verwenden die Eigenschaft tree.

Die Methode

getNumberOfFlips(int u) (Zeilen 49–52) gibt die Anzahl der Flips vom Knoten u zum Zielknoten zurück, was den Kosten des Pfads vom Knoten entspricht u zum Zielknoten. Diese Kosten können durch Aufrufen der Methode getCost(u) ermittelt werden, die in der Klasse ShortestPathTree (Zeile 51) definiert ist.

Der folgende Code stellt ein Programm dar, das den Benutzer auffordert, einen Anfangsknoten einzugeben, und die Mindestanzahl von Flips anzeigt, um den Zielknoten zu erreichen.

package demo;

import java.util.Scanner;

public class WeightedNineTail {

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

        WeightedNineTailModel model = new WeightedNineTailModel();
        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()));

        System.out.println("The number of flips is " +  model.getNumberOfFlips(NineTailModel.getIndex(initialNode)));
    }

}

Geben Sie zunächst 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

Die Anzahl der Würfe beträgt 8

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 Modell (Zeile 11), ermittelt den kürzesten Pfad vom Anfangsknoten zum Zielknoten (Zeilen 12–13), zeigt die Knoten im Pfad an (Zeilen 16–17) und ruft getNumberOfFlips um die Anzahl der Flips zu erhalten, die zum Erreichen des Zielknotens erforderlich sind (Zeile 20).

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