사례 연구: 9개의 꼬리 문제

9개의 꼬리 문제는 최단 경로 문제로 축소될 수 있습니다.
9개의 꼬리 문제는 다음과 같습니다. 9개의 동전은 일부는 위로 향하고 일부는 아래로 향하도록 3x3 매트릭스에 배치됩니다. 합법적인 이동은 앞면이 위로 향한 동전을 가져와서 인접한 동전과 함께 뒤집는 것입니다(대각선으로 인접한 동전은 포함되지 않음). 당신의 임무는 모든 동전이 뒤집어지게 만드는 최소 이동 횟수를 찾는 것입니다. 예를 들어 아래 그림(a)에 표시된 대로 9개의 동전으로 시작합니다. 마지막 행의 두 번째 동전을 뒤집으면 이제 아래 그림(b)와 같이 9개의 동전이 표시됩니다. 첫 번째 줄의 두 번째 동전을 뒤집으면 아래 그림(c)와 같이 9개의 동전이 모두 뒤집어져 있습니다.

다음 샘플 실행과 같이 사용자에게 9개의 동전의 초기 상태를 입력하라는 메시지를 표시하고 답을 표시하는 프로그램을 작성하겠습니다.

초기 9개의 코인 H와 T를 입력하세요: HHHTTTHHH
동전 뒤집기 단계는
ㅋㅋㅋ
ㅜㅜ
ㅋㅋㅋ
ㅋㅋㅋ
그렇군요
ㅜㅜ
ㅜㅜ
ㅜㅜ
ㅜㅜ

9개 코인의 각 상태는 그래프의 노드를 나타냅니다. 예를 들어 위 그림의 세 가지 상태는 그래프의 세 노드에 해당합니다. 편의상 3 * 3 행렬을 사용하여 모든 노드를 나타내고 머리에는 0, 꼬리에는 1을 사용합니다. 9개의 셀이 있고 각 셀이 0 또는 1이므로 0으로 표시된 총 2^9(512)개의 노드가 있습니다. 1, . . . , 511은 아래 그림과 같습니다.

u에서 v로 합법적인 이동이 있는 경우 노드 v에서 u로 에지를 할당합니다. 아래 그림은 부분 그래프를 보여줍니다. 노드 47의 셀을 뒤집어 노드 511이 될 수 있으므로 511에서 47까지 가장자리가 있습니다.

아래 그림의 마지막 노드는 뒷면이 뒤집힌 동전 9개의 상태를 나타냅니다. 편의상 이 마지막 노드를 대상 노드라고 부릅니다. 따라서 대상 노드에는 511이라는 라벨이 지정됩니다. 9개 꼬리 문제의 초기 상태가 s 노드에 해당한다고 가정합니다. 문제는 노드 s에서 대상 노드까지의 최단 경로를 찾는 것으로 줄어듭니다. 이는 노드 s에서 루트에 있는 BFS 트리의 대상 노드까지의 최단 경로를 찾는 것과 동일합니다. 대상 노드입니다.

이제 작업은 0, 1, 2, . . . , 511 및 노드 사이의 가장자리입니다. 그래프가 생성되면 노드 511에 루트가 있는 BFS 트리를 얻습니다. BFS 트리에서는 루트에서 모든 정점까지의 최단 경로를 찾을 수 있습니다. 대상 노드에서 다른 노드까지의 최단 경로를 가져오는 메서드가 포함된 NineTailModel이라는 클래스를 만듭니다. 클래스 UML 다이어그램은 아래 그림과 같습니다.

시각적으로 노드는 H 및 T 문자를 사용하여 3 * 3 행렬로 표시됩니다. 우리 프로그램에서는 노드를 표현하기 위해 9개의 문자로 구성된 1차원 배열을 사용합니다. 예를 들어 아래 그림에서 정점 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, int position) 메소드는 지정된 위치와 인접 위치의 노드를 뒤집습니다. 이 메소드는 새 노드의 인덱스를 반환합니다.

위치는 0부터 8까지의 값으로, 다음 그림과 같이 노드에 있는 코인을 가리킵니다.

예를 들어 아래 그림의 56 노드를 0 위치에서 뒤집으면 51 노드를 얻게 됩니다. 1 위치에서 56 노드를 뒤집으면 47 노드를 얻게 됩니다.

flipACell(char[] node, int row, int column) 메서드는 지정된 행과 열에서 노드를 뒤집습니다. 예를 들어 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 < 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();
    }
}

생성자(8~18행)는 512개의 노드가 있는 그래프를 생성하며 각 모서리는 한 노드에서 다른 노드로의 이동에 해당합니다(10행). 그래프에서 대상 노드 511을 루트로 하는 BFS 트리를 얻습니다(17행).

가장자리를 생성하기 위해 getEdges 메소드(21~37행)는 각 노드 u를 검사하여 다른 노드 v로 전환할 수 있는지 확인합니다. 그렇다면 Edge 목록(31행)에 (v, u)를 추가하세요. getFlippedNode(node, position) 메서드는 H 셀과 노드의 이웃 셀을 뒤집어서 뒤집힌 노드를 찾습니다(43~47행). flipACell(node, row, columns) 메서드는 실제로 H 셀과 노드의 이웃 셀을 뒤집습니다(52~60행).

getIndex(node) 메소드는 이진수를 십진수로 변환하는 것과 동일한 방식으로 구현됩니다(62~72행). 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<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()));
    }

}

프로그램은 사용자에게 8행의 문자열로 Hs와 Ts의 조합을 사용하여 9개의 문자로 구성된 초기 노드를 입력하라는 메시지를 표시하고, 다음에서 문자 배열을 얻습니다. 문자열(9행), BFS 트리를 얻기 위한 그래프 모델 생성(11행), 초기 노드에서
까지의 최단 경로를 얻습니다. 대상 노드(12~13행), 경로에 노드를 표시합니다(16~18행).

위 내용은 사례 연구: 9개의 꼬리 문제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!