사례 연구: 가중 9개 꼬리 문제

가중 9개 꼬리 문제는 가중 최단 경로 문제로 축소될 수 있습니다.
섹션에서는 9개의 꼬리 문제를 제시하고 이를 BFS 알고리즘을 사용하여 해결했습니다. 이 섹션에서는 문제의 변형을 제시하고 최단 경로 알고리즘을 사용하여 문제를 해결합니다.

9개의 꼬리 문제는 모든 동전이 아래로 향하도록 하는 최소 이동 횟수를 찾는 것입니다. 각 움직임은 선두 동전과 그 이웃 동전을 뒤집습니다. 가중 9개 꼬리 문제는 뒤집기 횟수를 각 동작의 가중치로 지정합니다. 예를 들어, 첫 번째 행의 첫 번째 동전과 두 이웃 동전을 뒤집어 아래 그림 a의 동전을 아래 그림 b의 동전으로 변경할 수 있습니다. 따라서 이번 이동의 가중치는 3입니다. 중앙 동전과 네 개의 이웃 동전을 뒤집어 아래 그림 c의 동전을 아래 그림 d로 변경할 수 있습니다. 따라서 이번 이동의 가중치는 5입니다.

가중 9개의 꼬리 문제는 간선 가중치 그래프에서 시작 노드에서 대상 노드까지의 최단 경로를 찾는 것으로 축소될 수 있습니다. 그래프에는 512개의 노드가 있습니다. 노드 u에서 노드 v로 이동하는 경우 노드 v에서 u로 에지를 생성합니다. 뒤집기 횟수를 가장자리의 무게로 지정하세요.

섹션에서 9개의 꼬리 문제를 모델링하기 위해 NineTailModel 클래스를 정의했음을 기억하세요. 이제 아래 그림과 같이 NineTailModel을 확장하는 WeightedNineTailModel이라는 새 클래스를 정의합니다.

NineTailModel 클래스는 Graph를 생성하고 대상 노드 511에 루트가 있는 Tree를 얻습니다. WeightedNineTailModel은 WeightedGraph를 생성하고 대상 노드 511ShortestPathTree를 얻는다는 점을 제외하면 NineTailModel과 동일합니다. 🎜>. 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를 구축하여 가중 9개 꼬리 문제(10~11행)를 모델링합니다. 각 노드 u에 대해 getEdges() 메서드는 뒤집힌 노드 v를 찾고 뒤집힌 횟수를 가장자리의 가중치(v, u)(30행). getNumberOfFlips(int u, int v) 메서드는 노드 u에서 노드 v까지 뒤집힌 횟수를 반환합니다(38~47행). 뒤집기 횟수는 사이에 있는 서로 다른 셀의 수입니다. 두 개의 노드(라인 44).

WeightedNineTailModel

은 대상 노드 511에 루트가 있는 ShortestPathTree를 얻습니다(라인 14). tree는 NineTailModel에 정의된 보호된 데이터 필드이고 ShortestPathTree는 Tree의 하위 클래스입니다. NineTailModel에 정의된 메소드는 tree 속성을 사용합니다.

getNumberOfFlips(int u)

메서드(49~52행)는 u 노드에서 대상 노드까지의 뒤집기 횟수를 반환합니다. 이는 노드에서 경로 비용입니다. u 대상 노드로 이동합니다. 이 비용은 ShortestPathTree 클래스(51행)에 정의된 getCost(u) 메소드를 호출하여 얻을 수 있습니다. 아래 코드는 사용자에게 초기 노드를 입력하라는 메시지를 표시하고 대상 노드에 도달하기 위한 최소 뒤집기 횟수를 표시하는 프로그램을 제공합니다.

초기 9개의 코인 H와 T를 입력하세요: HHHTTTHHH

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

}

동전 뒤집기 단계는

ㅋㅋㅋ

ㅜㅜ

ㅋㅋㅋ

ㅋㅋㅋ

그렇군요

ㅜㅜ

TT

ㅜㅜ

ㅜㅜ

뒤집는 횟수는 8번입니다

프로그램은 사용자에게 8행의 문자열로 Hs와 Ts의 조합을 사용하여 9개의 문자로 구성된 초기 노드를 입력하라는 메시지를 표시하고, 다음에서 문자 배열을 얻습니다. 문자열(9행), 모델 생성(11행), 초기 노드에서 대상 노드까지의 최단 경로 획득(12~13행), 경로에 노드를 표시(16~17행)하고 getNumberOfFlips는 대상 노드(라인 20)에 도달하는 데 필요한 뒤집기 횟수를 가져옵니다.

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