사례 연구: 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.Tree tree; // Define a tree /** Construct a model */ public NineTailModel() { // Create edges List edges = getEdges(); // Create a graph UnweightedGraph 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 getEdges() { List 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 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 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!