Java アルゴリズム BFS、DFS、動的プログラミング、貪欲アルゴリズムの実装方法

幅優先検索

幅優先検索アルゴリズムは、ツリーまたはグラフを横断または検索するアルゴリズムです。ルート ノードから検索し、目的の状態が見つかるまで階層ごとに下方向に拡張します。すべてのノードがトラバースされます。 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) は、重複する部分問題と問題を解決するために使用される問題解決手法です。最も重要なEU部分構造問題。 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 中国語 Web サイトの他の関連記事を参照してください。