個案研究：九尾問題

九尾問題可以簡化為最短路徑問題。
九尾問題如下。九枚硬幣被放置在一個三乘三的矩陣中，有些面朝上，有些面朝下。合法的舉動是取出一枚正面朝上的硬幣，並將其連同與其相鄰的硬幣一起翻轉（這不包括對角相鄰的硬幣）。您的任務是找出導致所有硬幣面朝下的最少移動次數。例如，從九個硬幣開始，如下圖（a）所示。翻轉最後一行的第二枚硬幣後，九枚硬幣現在如下圖（b）所示。翻轉第一排第二枚硬幣後，九枚硬幣全部面朝下，如下圖(c)所示。

我們將編寫一個程序，提示使用者輸入九個硬幣的初始狀態並顯示解決方案，如以下範例運行所示。

輸入前九個硬幣H和T：HHHTTTHHH
拋硬幣的步驟是
呵呵
TTT
呵呵
呵呵
THT
TTT
TTT
TTT
TTT

九個硬幣的每個狀態代表圖中的一個節點。例如，上圖中的三個狀態對應圖中的三個節點。為了方便起見，我們使用 3 * 3 矩陣來表示所有節點，並使用 0 表示頭節點，使用 1 表示尾節點。由於有9 個單元，每個單元要不是0 要嘛是1，所以總共有2^9 (512) 個節點，標記為0、 1, . 。 。 、511，如下圖

如果存在從 u 到 v 的合法移動，我們將從節點 v 到 u 分配一條邊。下圖顯示了部分圖表。請注意，從 511 到 47 有一條邊，因為您可以翻轉節點 47 中的單元格以成為節點 511。

下圖中的最後一個節點代表九個面朝下的硬幣的狀態。為了方便起見，我們將最後一個節點稱為目標節點。因此，目標節點被標記為511。假設九尾問題的初始狀態對應於節點s。問題簡化為尋找從節點 s 到目標節點的最短路徑，相當於在以 為根的 BFS 樹中尋找從節點 s 到目標節點的最短路徑目標節點。

現在的任務是建構一個由 512 個節點組成的圖，標記為 0、1、2、。 。 。 ，511，以及節點之間的邊。建立圖表後，取得以節點 511 為根的 BFS 樹。從BFS樹中，你可以找到從根到任頂點的最短路徑。我們將建立一個名為 NineTailModel 的類，其中包含獲取從目標節點到任何其他節點的最短路徑的方法。類別UML圖如下圖所示。

在視覺上，節點以字母 H 和 T 的 3 * 3 矩陣表示。在我們的程式中，我們使用九個字元的一維數組來表示一個節點。例如，下圖頂點1 的節點表示為{'H', 'H', 'H' , 'H', 'H', 'H', 'H', 'H' , 'T'} 在陣列中。

getEdges() 方法傳回 Edge 物件的清單。

getNode(index) 方法傳回指定索引的節點。例如，getNode(0) 傳回包含九個 H 的節點。 getNode(511) 傳回包含九個 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 個節點的圖，每條邊對應於從一個節點到另一個節點的移動（第 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) 方法的實作方式與將二進位數轉換為十進位數相同（第 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 行提示使用者輸入一個由9 個字母組成的初始節點，其中由H 和T 組合作為字串，從字串（第9行），建立圖模型以取得BFS樹（第11行），取得從初始節點到
的最短路徑 目標節點（第 12-13 行），並顯示路徑中的節點（第 16-18 行）。

以上是個案研究：九尾問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！