案例研究：九尾问题

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

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

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

九枚硬币的每个状态代表图中的一个节点。例如，上图中的三个状态对应图中的三个节点。为了方便起见，我们使用它 3 * 3 表示所有节点并使用矩阵 0 表示头部，1 表示尾部。由于有 9 每个单元要么是每个单元？ 0 要么是 所以一共有 2^9 (512) 一个节点，标记为 0、1、 。 。 。 、511，如下图

如果有从U到V的合法移动，我们将从节点V分配一个侧到U。下图显示了一些图表。请注意，从511到47有一个边缘，因为您可以将节点47中的单元格翻转成节点511。

下图中的最后一个节点代表了九枚面朝下的硬币的状态。为了方便起见，我们称最后一个节点为目标节点。因此，目标节点被标记为511。假设九尾问题的初始状态对应于节点s。问题简化为从节点s到目标节点的最短路径，相当于从节点s到目标节点的最短路径。

目前的任务是构建一个原因 512 由节点组成的图纸标记为0、1、2、。 。 。 ，以及节点之间的边缘。创建地图后，获得以节点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) 返回包含 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<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 = 0 &amp;&amp; row = 0 &amp;&amp; column  getshortestpath(int nodeindex) {
        return tree.getpath(nodeindex);
    }

    public static void printnode(char[] node) {
        for (int i = 0; i 



<br>构造函数(第 8-18 行)创建一个包含 512 节点图，从一个节点到另一个节点，每个侧对应于移动(第) 10 行）。从图中获得目标节点511<p>bfs树(第17行)为根。<strong>

</strong>为创建边缘，</p>getedges<p>检查每个节点(第21-37行)<strong>u</strong>检查它是否可以转向另一个节点<strong>v</strong>。如果是这样，请将就 (<strong>v</strong>, <strong>u</strong>) 添加到 <strong>edge</strong> 列表（第 31 行）。 <strong>getflippednode(node,position)</strong> 通过翻转节点的方法 <strong>h</strong> 单位及其邻居来找翻转节点(第一) 43-47 行）。 <strong>flipacell(node, row, column)</strong> 实际上，该方法翻转了节点中的节点 <strong>h</strong> 单位格及其邻居(第 52-60 行）。<strong>

</strong>getindex(node)</p>该方法的实现方法与将二进制数转换为十进制数(第62-72行)相同。 <p>getnode(index)<strong> 通过字母返回一个方法 </strong>h<strong> 和 </strong>t<strong> 组成节点(第) 74-87 行）。</strong>

<strong></strong>getshortestpath(nodeindex)</p> 方法调用 <p>getpath(nodeindex)<strong></strong>
从指定节点到目标节点的最短路径获取顶点的方法<strong>
（第 89-91 行）.</strong>

<br>printnode(node)<br> 该方法在控制台上显示节点(第一) 93-101 行）。</p>

<p>该程序提示用户输入初始节点并显示到达目标节点的步骤。<strong>
</strong>

</p>
<pre class="brush:php;toolbar:false">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 



程序在第 8 线路提示用户输入由 9 由字母组成的初始节点，并以 <p>h<br>s 和 </p>t<p>s 作为字符串的组合，从字符串中获得字符数组(第 9 行)，创建图形模型获取bfs树(第11行)，获取从初始节点到<strong>的最短路径
目标节点(第 12-13 行），并显示路径中的节点(第) 16-18 行）。</strong>


          <strong>

            
        </strong></p></integer>

以上是案例研究：九尾问题的详细内容，请关注图灵教育的其他相关文章！