Kajian Kes: Masalah Sembilan Ekor

Masalah sembilan ekor boleh dikurangkan kepada masalah laluan terpendek.
Masalah sembilan ekor adalah seperti berikut. Sembilan syiling diletakkan dalam matriks tiga per tiga dengan beberapa menghadap ke atas dan beberapa menghadap ke bawah. Langkah undang-undang ialah mengambil syiling yang menghadap ke atas dan membalikkannya, bersama-sama dengan syiling yang bersebelahan dengannya (ini tidak termasuk syiling yang bersebelahan menyerong). Tugas anda adalah untuk mencari bilangan minimum pergerakan yang membawa kepada semua syiling menghadap ke bawah. Sebagai contoh, mulakan dengan sembilan syiling seperti yang ditunjukkan dalam Rajah di bawah (a). Selepas anda menterbalikkan syiling kedua di baris terakhir, sembilan syiling kini seperti yang ditunjukkan dalam Rajah di bawah (b). Selepas anda membalikkan syiling kedua dalam baris pertama, sembilan syiling semuanya menghadap ke bawah, seperti yang ditunjukkan dalam Rajah di bawah (c).

Kami akan menulis atur cara yang menggesa pengguna memasukkan keadaan awal sembilan syiling dan memaparkan penyelesaiannya, seperti yang ditunjukkan dalam contoh larian berikut.

Masukkan sembilan syiling awal Hs dan Ts: HHHTTTHHH
Langkah-langkah untuk membalikkan syiling ialah
HHH
TTT
HHH
HHH
THT
TTT
TTT
TTT
TTT

Setiap keadaan sembilan syiling mewakili nod dalam graf. Sebagai contoh, tiga keadaan dalam Rajah di atas sepadan dengan tiga nod dalam graf. Untuk kemudahan, kami menggunakan matriks 3 * 3 untuk mewakili semua nod dan menggunakan 0 untuk kepala dan 1 untuk ekor. Memandangkan terdapat sembilan sel dan setiap sel sama ada 0 atau 1, terdapat sejumlah 2^9 (512) nod, berlabel 0, 1, . . . , dan 511, seperti ditunjukkan dalam Rajah di bawah.

Kami menetapkan tepi daripada nod v kepada u jika terdapat perpindahan undang-undang daripada u kepada v. Rajah di bawah menunjukkan graf separa. Perhatikan terdapat kelebihan dari 511 hingga 47, kerana anda boleh menyelak sel dalam nod 47 untuk menjadi nod 511.

Nod terakhir dalam Rajah di bawah mewakili keadaan sembilan syiling menghadap ke bawah. Untuk kemudahan, kami memanggil nod terakhir ini nod sasaran. Oleh itu, nod sasaran dilabelkan 511. Katakan keadaan awal masalah sembilan ekor sepadan dengan nod s. Masalahnya dikurangkan kepada mencari laluan terpendek dari nod s ke nod sasaran, yang bersamaan dengan mencari laluan terpendek dari nod s ke nod sasaran dalam pepohon BFS yang berakar pada nod sasaran.

Kini tugasnya ialah membina graf yang mengandungi 512 nod berlabel 0, 1, 2, . . . , 511, dan tepi antara nod. Setelah graf dibuat, dapatkan pepohon BFS yang berakar pada nod 511. Dari pokok BFS, anda boleh menemui laluan terpendek dari akar ke mana-mana puncak. Kami akan mencipta kelas bernama NineTailModel, yang mengandungi kaedah untuk mendapatkan laluan terpendek dari nod sasaran ke mana-mana nod lain. Rajah kelas UML ditunjukkan dalam Rajah di bawah.

Secara visual, nod diwakili dalam matriks 3 * 3 dengan huruf H dan T. Dalam program kami, kami menggunakan tatasusunan satu dimensi sembilan aksara untuk mewakili nod. Sebagai contoh, nod untuk bucu 1 dalam Rajah di bawah diwakili sebagai {'H', 'H', 'H' , 'H', 'H', 'H', 'H', 'H' , 'T'} dalam tatasusunan.

Kaedah getEdges() mengembalikan senarai objek Edge.

Kaedah getNode(index) mengembalikan nod untuk indeks yang ditentukan. Contohnya, getNode(0) mengembalikan nod yang mengandungi sembilan Hs. getNode(511) mengembalikan nod yang mengandungi sembilan Ts. Kaedah getIndex(nod) mengembalikan indeks nod.

Perhatikan bahawa medan data pokok ditakrifkan sebagai dilindungi supaya ia boleh diakses daripada subkelas WeightedNineTail.

Kaedah getFlippedNode(char[] nod, kedudukan int) membalikkan nod pada kedudukan yang ditentukan dan kedudukan bersebelahan dengannya. Kaedah ini mengembalikan indeks nod baharu.

Kedudukan ialah nilai daripada 0 hingga 8, yang menunjuk kepada syiling dalam nod, seperti yang ditunjukkan dalam rajah berikut.

Contohnya, untuk nod 56 dalam Rajah di bawah, flipkannya pada kedudukan 0 dan anda akan mendapat nod 51. Jika anda menyelak nod 56 pada kedudukan 1, anda akan mendapat nod 47.

Kaedah flipACell(char[] nod, baris int, lajur int) membalikkan nod pada baris dan lajur yang ditentukan. Contohnya, jika anda menyelak nod 56 pada baris 0 dan lajur 0, nod baharu ialah 408. Jika anda menyelak nod 56 pada baris 2 dan lajur 0, nod baharu ialah 30.

Kod di bawah menunjukkan kod sumber untuk 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();
    }
}

Pembina (baris 8–18) mencipta graf dengan 512 nod, dan setiap tepi sepadan dengan perpindahan dari satu nod ke nod yang lain (baris 10). Daripada graf, pokok BFS yang berakar pada nod sasaran 511 diperolehi (baris 17).

Untuk mencipta tepi, kaedah getEdges (baris 21–37) menyemak setiap nod u untuk melihat sama ada ia boleh dibalikkan ke nod lain v. Jika ya, tambahkan (v, u) pada senarai Tepi (baris 31). Kaedah getFlippedNode(nod, kedudukan) mencari nod terbalik dengan membalikkan sel H dan jirannya dalam nod (baris 43–47). Kaedah flipACell(nod, baris, lajur) sebenarnya membalikkan sel H dan jirannya dalam nod (baris 52–60).

Kaedah getIndex(nod) dilaksanakan dengan cara yang sama seperti menukar nombor perduaan kepada nombor perpuluhan (garisan 62–72). Kaedah getNode(index) mengembalikan nod yang terdiri daripada huruf H dan T (baris 74–87).

Kaedah getShortestpath(nodeIndex) menggunakan getPath(nodeIndex)
kaedah untuk mendapatkan bucu dalam laluan terpendek dari nod yang ditentukan ke nod sasaran
(baris 89–91).

Kaedah printNode(nod) memaparkan nod pada konsol (baris 93–101).

Kod di bawah memberikan program yang menggesa pengguna memasukkan nod awal dan memaparkan langkah-langkah untuk mencapai nod sasaran.

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

}

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 graf untuk mendapatkan pepohon BFS (baris 11), memperoleh laluan terpendek dari nod awal ke
nod sasaran (baris 12–13), dan memaparkan nod dalam laluan (baris 16–18).

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