Kajian Kes: Masalah Sembilan Ekor Berwajaran

Masalah sembilan ekor berwajaran boleh dikurangkan kepada masalah laluan terpendek berwajaran.
Bahagian membentangkan masalah sembilan ekor dan menyelesaikannya menggunakan algoritma BFS. Bahagian ini membentangkan variasi masalah dan menyelesaikannya menggunakan algoritma laluan terpendek.

Masalah sembilan ekor ialah mencari bilangan minimum pergerakan yang membawa kepada semua syiling menghadap ke bawah. Setiap langkah membalikkan sekeping syiling dan jirannya. Masalah sembilan ekor berwajaran menetapkan bilangan lambungan sebagai pemberat pada setiap pergerakan. Sebagai contoh, anda boleh menukar syiling dalam Rajah di bawah a kepada yang dalam Rajah di bawah b dengan membalikkan syiling pertama di baris pertama dan dua jirannya. Oleh itu, berat untuk langkah ini ialah 3. Anda boleh menukar syiling dalam Rajah di bawah c kepada Rajah di bawah d dengan menterbalikkan syiling tengah dan empat jirannya. Jadi berat untuk langkah ini ialah 5.

Masalah sembilan ekor berwajaran boleh dikurangkan kepada mencari laluan terpendek dari nod permulaan ke nod sasaran dalam graf berwajaran tepi. Graf mempunyai 512 nod. Cipta tepi daripada nod v ke u jika terdapat perpindahan dari nod u ke nod v. Tetapkan bilangan lambungan sebagai berat tepi.

Ingat bahawa dalam Bahagian kami menentukan kelas NineTailModel untuk memodelkan masalah sembilan ekor. Kami kini mentakrifkan kelas baharu bernama WeightedNineTailModel yang memanjangkan NineTailModel, seperti ditunjukkan dalam Rajah di bawah.

Kelas NineTailModel mencipta Graf dan memperoleh Pokok yang berakar pada nod sasaran 511. WeightedNineTailModel adalah sama dengan NineTailModel kecuali ia mencipta WeightedGraph dan memperoleh ShortestPathTree 11 berakar pada nod sasaran 🎜>. WeightedNineTailModel memanjangkan NineTailModel. Kaedah getEdges() mencari semua tepi dalam graf. Kaedah getNumberOfFlips(int u, int v) mengembalikan bilangan lilitan daripada nod u ke nod v. Kaedah getNumberOfFlips(int u) mengembalikan bilangan lilitan daripada nod u ke nod sasaran.

Kod di bawah melaksanakan

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 memanjangkan NineTailModel untuk membina WeightedGraph untuk memodelkan masalah sembilan ekor berwajaran (baris 10–11). Untuk setiap nod u, kaedah getEdges() mencari nod terbalik v dan menetapkan bilangan lilitan sebagai berat untuk tepi (v, u) (baris 30). Kaedah getNumberOfFlips(int u, int v) mengembalikan bilangan lilitan daripada nod u ke nod v (baris 38–47). Bilangan lilitan ialah bilangan sel yang berbeza antara dua nod (baris 44).

WeightedNineTailModel memperoleh ShortestPathTree berakar pada nod sasaran 511 (baris 14). Ambil perhatian bahawa tree ialah medan data dilindungi yang ditakrifkan dalam NineTailModel dan ShortestPathTree ialah subkelas Tree. Kaedah yang ditakrifkan dalam NineTailModel menggunakan sifat pokok.

Kaedah

getNumberOfFlips(int u) (baris 49–52) mengembalikan bilangan lilitan dari nod u ke nod sasaran, iaitu kos laluan dari nod u ke nod sasaran. Kos ini boleh diperolehi dengan menggunakan kaedah getCost(u) yang ditakrifkan dalam kelas ShortestPathTree (baris 51).

Kod di bawah memberikan atur cara yang menggesa pengguna memasukkan nod awal dan memaparkan bilangan lilitan minimum untuk mencapai nod sasaran.

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

}

Masukkan sembilan syiling awal Hs dan Ts: HHHTTTHHH

Langkah-langkah untuk membalikkan syiling ialah

HHH

TTT
HHH

HHH

THT
TTT

TTT

TTT
TTT

Bilangan lambungan ialah 8

Atur cara menggesa pengguna untuk memasukkan nod awal dengan sembilan huruf dengan gabungan Hs dan Ts sebagai rentetan dalam baris 8, memperoleh susunan aksara daripada rentetan (baris 9), mencipta model (baris 11), memperoleh laluan terpendek dari nod awal ke nod sasaran (baris 12–13), memaparkan nod dalam laluan (baris 16–17), dan memanggil getNumberOfFlips untuk mendapatkan bilangan lilitan yang diperlukan untuk mencapai nod sasaran (baris 20).

Atas ialah kandungan terperinci Kajian Kes: Masalah Sembilan Ekor Berwajaran. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!