ケーススタディ: 九尾問題

九尾問題は最短経路問題に還元できます。
九尾問題は次のとおりです。 9 枚のコインが 3 行 3 列のマトリックスに配置され、一部は表向き、一部は裏向きになります。合法な手は、表向きのコインを取り、それに隣接するコインと一緒に反転させることです (これには斜めに隣接するコインは含まれません)。あなたの仕事は、すべてのコインが裏向きになる最小の手数を見つけることです。たとえば、次の図 (a) に示すように、9 枚のコインから始めます。最後の列の 2 番目のコインを投げると、9 枚のコインは次の図 (b) のようになります。最初の列の 2 番目のコインを投げると、下の図 (c) に示すように、9 枚のコインがすべて裏向きになります。

次のサンプル実行に示すように、ユーザーに 9 枚のコインの初期状態の入力を求め、解決策を表示するプログラムを作成します。

最初の 9 つのコインの H と T を入力します: HHHTTTHHH
コインを投げる手順は
はぁ
TT
はぁ
はぁ
THT
TT
TT
TT
TT

9 枚のコインの各状態は、グラフ内のノードを表します。たとえば、上の図の 3 つの状態は、グラフ内の 3 つのノードに対応します。便宜上、すべてのノードを表すために 3 * 3 の行列を使用し、表には 0、裏には 1 を使用します。 9 つのセルがあり、各セルは 0 または 1 であるため、合計 2^9 (512) 個のノードがあり、0、1、 。 。 。以下の図に示すように、511。

u から v への正当な移動がある場合、ノード v から u へのエッジを割り当てます。以下の図はグラフの一部を示しています。ノード 47 のセルを反転してノード 511 になることができるため、511 から 47 までのエッジがあることに注意してください。 >

下の図の最後のノードは、9 枚の裏向きのコインの状態を表します。便宜上、この最後のノードを

ターゲット ノード

と呼びます。したがって、ターゲット ノードには 511 というラベルが付けられます。九尾問題の初期状態がノード s に対応すると仮定します。問題は、ノード s からターゲット ノードへの最短パスを見つけることに帰着します。これは、ノード s からルートとなる BFS ツリー内のターゲット ノードへの最短パスを見つけることと同じです。ターゲットノード。

ここでのタスクは、

0

、1、2、...というラベルが付いた 512 個のノードで構成されるグラフを構築することです。 。 。 、511、およびノー​​ド間のエッジ。グラフが作成されたら、ノード 511 をルートとする BFS ツリーを取得します。 BFS ツリーから、ルートから任意の頂点までの最短パスを見つけることができます。 NineTailModel という名前のクラスを作成します。このクラスには、ターゲット ノードから他のノードへの最短パスを取得するメソッドが含まれています。クラス UML 図を下の図に示します。

視覚的には、ノードは文字

H

および T を含む 3 * 3 行列で表されます。私たちのプログラムでは、9 文字の 1 次元配列を使用してノードを表します。たとえば、下図の頂点 1 のノードは、{'H'、'H'、'H' として表されます。 、'H'、'H'、'H'、'H'、'H' 、'T'} 配列内。

getEdges()

メソッドは、Edge オブジェクトのリストを返します。

getNode(index)

メソッドは、指定されたインデックスのノードを返します。たとえば、getNode(0) は、9 つ​​の H を含むノードを返します。 getNode(511) は、9 つ​​の T を含むノードを返します。 getIndex(node) メソッドは、ノードのインデックスを返します。 データ フィールド

tree

は、WeightedNineTail サブクラスからアクセスできるように保護されているものとして定義されていることに注意してください。

getFlippedNode(char[] node, int Position) メソッドは、指定された位置とその隣接する位置でノードを反転します。このメソッドは、新しいノードのインデックスを返します。

次の図に示すように、位置は 0 から 8 までの値であり、ノード内のコインを指します。

たとえば、下図のノード 56 の場合、位置 0 で反転すると、ノード 51 が得られます。位置 1 でノード 56 を反転すると、ノード 47 が得られます。

flipACell(char[] node, int row, int column) メソッドは、指定された行と列でノードを反転します。たとえば、行 0、列 0 のノード 56 を反転すると、新しいノードは 408 になります。行 2 と列 0 でノード 56 を反転すると、新しいノードは 30 になります。

以下のコードは、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();
    }
}

コンストラクター (8 ～ 18 行目) は 512 個のノードを持つグラフを作成し、各エッジは 1 つのノードから別のノードへの移動に対応します (10 行目)。グラフから、ターゲット ノード 511 をルートとする BFS ツリーが取得されます (17 行目)。

エッジを作成するために、getEdges メソッド (行 21 ～ 37) は各ノード u をチェックして、別のノード v に反転できるかどうかを確認します。その場合は、(v, u) を Edge リスト (31 行目) に追加します。 getFlippedNode(node,position) メソッドは、ノード内の H セルとその隣接セルを反転することにより、反転されたノードを見つけます (行 43 ～ 47)。 flipACell(node, row, column) メソッドは実際に、ノード内の H セルとその隣接セルを反転します (行 52 ～ 60)。

getIndex(node) メソッドは、2 進数を 10 進数に変換するのと同じ方法で実装されます (行 62 ～ 72)。 getNode(index) メソッドは、文字 H と T で構成されるノードを返します (行 74 ～ 87)。

getShortestpath(nodeIndex) メソッドは、getPath(nodeIndex)
を呼び出します。 指定したノードからターゲットノードまでの最短パス上の頂点を取得するメソッド
(89 ～ 91 行目).

printNode(node) メソッドは、コンソールにノードを表示します (行 93 ～ 101)。

以下のコードは、ユーザーに初期ノードの入力を促し、ターゲット ノードに到達する手順を表示するプログラムを提供します。

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

}

プログラムは、8 行目に H と T を組み合わせた 9 文字の初期ノードを文字列として入力するようユーザーに要求し、次から文字の配列を取得します。文字列 (9 行目)、グラフ モデルを作成して BFS ツリーを取得します (11 行目)、最初のノードから
への最短パスを取得します。 ターゲット ノード (12 ～ 13 行目)、パス内のノードを表示します (16 ～ 18 行目)。

以上がケーススタディ: 九尾問題の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。