案例研究：九尾问题

九尾问题可以简化为最短路径问题。
九尾问题如下。九枚硬币被放置在一个三乘三的矩阵中，一些面朝上，一些面朝下。合法的举动是取出一枚正面朝上的硬币，并将其连同与其相邻的硬币一起翻转（这不包括对角相邻的硬币）。您的任务是找到导致所有硬币面朝下的最少移动次数。例如，从九个硬币开始，如下图（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中文网其他相关文章！