案例研究：九尾问题

九尾问题可以简化为最短路径问题。
九尾问题如下。九枚硬币被放置在一个三乘三的矩阵中，一些面朝上，一些面朝下。合法的举动是取出一枚正面朝上的硬币，并将其连同与其相邻的硬币一起翻转（这不包括对角相邻的硬币）。您的任务是找到导致所有硬币面朝下的最少移动次数。例如，从九个硬币开始，如下图（a）所示。当你翻转最后一排的第二枚硬币后，九枚硬币现在如下图（b）所示。翻转第一排第二枚硬币后，九枚硬币全部面朝下，如下图(c)所示。

我们将编写一个程序，提示用户输入九个硬币的初始状态并显示解决方案，如下面的示例运行所示。

输入前九个硬币hs和ts：hhhttthhh
抛硬币的步骤是
哈哈哈
tt
哈哈哈
哈哈哈
tht
tt
tt
tt
tt

九个硬币的每个状态代表图中的一个节点。例如，上图中的三个状态对应图中的三个节点。为了方便起见，我们使用 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图如下图所示。

酷表ChatExcel

北大团队开发的通过聊天来操作Excel表格的AI工具

下载

在视觉上，节点以字母 h 和 t 的 3 * 3 矩阵表示。在我们的程序中，我们使用九个字符的一维数组来表示一个节点。例如，下图中顶点 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, intposition)方法翻转指定位置及其相邻位置的节点。该方法返回新节点的索引。

0到8之间的值，指向节点中的一枚币，如下图

56，在0位置翻转，就会得到节点51。如果你在位置1翻转节点56，你将得到节点47.

方法翻转指定行和列处的节点。例如，如果翻转第 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.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();
    }
}

为根的bfs树（第17行）。 为了创建边，

方法（第21-37行）检查每个节点u以查看它是否可以翻转到另一个节点v。如果是这样，请将 (v, u) 添加到 edge 列表（第 31 行）。 getflippednode(node,position) 方法通过翻转节点中的 h 单元及其邻居来查找翻转节点（第 43-47 行）。 flipacell(node, row, column) 方法实际上翻转节点中的 h 单元格及其邻居（第 52-60 行）。 getindex(node)

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

}

h
s 和

s 的组合作为字符串，从字符串中获取字符数组（第 9 行），创建一个图形模型获取bfs树（第11行），获取从初始节点到的最短路径 目标节点（第 12-13 行），并显示路径中的节点（第 16-18 行）。