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

重み付き九尾問題は、重み付き最短経路問題に還元できます。
セクションでは、九尾問題を提示し、BFS アルゴリズムを使用してそれを解決しました。このセクションでは、問題のバリエーションを示し、最短パス アルゴリズムを使用して解決します。

九尾問題は、すべてのコインが下を向く最小の手数を見つけることです。各手は表のコインとその隣のコインを投げます。重み付き 9 尾問題では、フリップの回数が各動きの重みとして割り当てられます。たとえば、最初の行とその隣の 2 つのコインを裏返すことで、下の図 a のコインを下の図 b のコインに変更できます。したがって、この動きの重みは 3 です。中央のコインとその隣の4枚のコインを裏返すと、下図cのコインを下図dに変えることができます。したがって、この動きの重みは 5 です。

加重九尾問題は、エッジ加重グラフで開始ノードからターゲット ノードまでの最短経路を見つけることに還元できます。グラフには 512 個のノードがあります。ノード u からノード v への移動がある場合、ノード v から u へのエッジを作成します。フリップの数をエッジの重みとして割り当てます。

セクションで、九尾問題をモデル化するクラス NineTailModel を定義したことを思い出してください。以下の図に示すように、NineTailModel を拡張する WeightedNineTailModel という名前の新しいクラスを定義します。

NineTailModel クラスは Graph を作成し、ターゲット ノード 511 をルートとする Tree を取得します。 WeightedNineTailModel は NineTailModel と同じですが、WeightedGraph を作成し、ターゲット ノード 511ShortestPathTree を取得する点が異なります。 🎜>。 WeightedNineTailModel は NineTailModel を拡張します。メソッド getEdges() は、グラフ内のすべてのエッジを検索します。 getNumberOfFlips(int u, int v) メソッドは、ノード u からノード v へのフリップの数を返します。 getNumberOfFlips(int u) メソッドは、ノード u からターゲット ノードまでのフリップ数を返します。

以下のコードは

WeightedNineTailModel を実装します。

package demo;
import java.util.*;

public class WeightedNineTailModel extends NineTailModel {
    /** Construct a model */
    public WeightedNineTailModel() {
        // Create edges
        List<WeightedEdge> edges = getEdges();

        // Create a graph
        WeightedGraph<Integer> graph = new WeightedGraph<>(edges, NUMBER_OF_NODES);

        // Obtain a shortest path tree rooted at the target node
        tree = graph.getShortestPath(511);
    }

    /** Create all edges for the graph */
    private List<WeightedEdge> getEdges() {
        // Store edges
        List<WeightedEdge> edges = new ArrayList<>();

        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);
                    int numberOfFlips = getNumberOfFlips(u, v);

                    // Add edge (v, u) for a legal move from node u to node v
                    edges.add(new WeightedEdge(v, u, numberOfFlips));
                }
            }
        }

        return edges;
    }

    private static int getNumberOfFlips(int u, int v) {
        char[] node1 = getNode(u);
        char[] node2 = getNode(v);

        int count = 0; // Count the number of different cells
        for(int i = 0; i < node1.length; i++)
            if(node1[i] != node2[i]) count++;

        return count;
    }

    public int getNumberOfFlips(int u) {
        return (int)((WeightedGraph<Integer>.ShortestPathTree)tree).getCost(u);
    }
}

WeightedNineTailModel は NineTailModel を拡張して、加重九尾問題をモデル化するための WeightedGraph を構築します (行 10 ～ 11)。各ノード u について、getEdges() メソッドは反転したノード v を見つけ、反転の数をエッジの重みとして割り当てます (v、u) (30 行目)。 getNumberOfFlips(int u, int v) メソッドは、ノード u からノード v へのフリップの数を返します (行 38 ～ 47)。フリップの数は、 間の異なるセルの数です。 2 つのノード (44 行目)。

WeightedNineTailModelは、ターゲット ノード 511 をルートとする ShortestPathTree を取得します (行 14)。 tree は NineTailModel で定義された保護されたデータ フィールドであり、ShortestPathTree は Tree のサブクラスであることに注意してください。 NineTailModel で定義されたメソッドは、tree プロパティを使用します。

getNumberOfFlips(int u) メソッド (行 49 ～ 52) は、ノード u からターゲット ノードまでのフリップ数を返します。これは、ノードからのパスのコストです。 u をターゲット ノードに送信します。このコストは、ShortestPathTree クラス (51 行目) で定義されている getCost(u) メソッドを呼び出すことで取得できます。

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

package demo;

import java.util.Scanner;

public class WeightedNineTail {

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

        WeightedNineTailModel model = new WeightedNineTailModel();
        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()));

        System.out.println("The number of flips is " +  model.getNumberOfFlips(NineTailModel.getIndex(initialNode)));
    }

}

最初の 9 つのコイン H と T を入力します: HHHTTTHHH

コインを投げる手順は次のとおりです

うーん

TT
はぁ

うーん

THT
TT

TT

TT
TT

フリップ回数は8回です

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

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