Java 알고리즘 BFS, DFS, 동적 프로그래밍 및 탐욕 알고리즘 구현 방법-java지도 시간-php.cn

Java 알고리즘 BFS, DFS, 동적 프로그래밍 및 탐욕 알고리즘 구현 방법

WBOY

풀어 주다： 2023-04-18 20:13:01

앞으로

999명이 탐색했습니다.

폭우선탐색

폭우선탐색 알고리즘은 트리나 그래프를 순회하거나 검색하는 알고리즘으로, 루트 노드부터 검색하여 대상 상태를 찾거나 모든 노드를 순회할 때까지 계층별로 하향 확장합니다. BFS는 일반적으로 모든 노드를 방문할 때까지 매번 다음 노드를 대기열에 넣는 대기열을 사용하여 구현됩니다.

다음은 Java 구현입니다.

public void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();

    queue.offer(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.print(node.val + " ");

        for (Node neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

로그인 후 복사

깊이 우선 검색

깊이 우선 검색 알고리즘은 루트 노드부터 시작하여 대상 상태 또는 모든 노드까지 모든 하위 트리를 재귀적으로 순회하여 트리 또는 그래프를 순회하거나 검색하는 알고리즘입니다. 통과됩니다. DFS는 일반적으로 모든 노드를 방문할 때까지 매번 다음 노드를 스택에 푸시하는 스택을 사용하여 구현됩니다.

다음은 Java 구현입니다.

public void dfs(Node node, Set<Node> visited) {
    System.out.print(node.val + " ");
    visited.add(node);

    for (Node neighbor : node.neighbors) {
        if (!visited.contains(neighbor)) {
            dfs(neighbor, visited);
        }
    }
}

로그인 후 복사

동적 프로그래밍

동적 프로그래밍 알고리즘(DP)은 중첩되는 하위 문제와 최적의 하위 구조 문제를 해결하는 데 사용되는 문제 해결 방법입니다. DP는 일반적으로 최단 경로 문제, 배낭 문제 등과 같은 최적화 문제를 해결하는 데 사용됩니다.

다음은 Java 구현입니다.

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (weights[i - 1] <= j) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][capacity];
}

로그인 후 복사

Greedy

그리디 알고리즘은 항상 현재의 최적 솔루션을 선택하는 최적화 문제를 해결하는 방법입니다. 동적 프로그래밍과 달리 그리디 알고리즘은 모든 하위 문제를 고려하지 않고 현재 최적의 솔루션만 살펴봅니다.

다음은 Java 구현입니다.

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    Item[] items = new Item[n];

    for (int i = 0; i < n; i++) {
        items[i] = new Item(weights[i], values[i]);
    }

    Arrays.sort(items, (a, b) -> b.valuePerWeight - a.valuePerWeight);

    int totalValue = 0;
    int remainingCapacity = capacity;

    for (Item item : items) {
        if (remainingCapacity >= item.weight) {
            totalValue += item.value;
            remainingCapacity -= item.weight;
        } else {
            totalValue += item.valuePerWeight * remainingCapacity;
            break;
        }
    }

    return totalValue;
}

class Item {
    int weight;
    int value;
    int valuePerWeight;

    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
        this.valuePerWeight = value / weight;
    }
}

로그인 후 복사

위 내용은 Java 알고리즘 BFS, DFS, 동적 프로그래밍 및 탐욕 알고리즘 구현 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!