So implementieren Sie die Java-Algorithmen BFS, DFS, dynamische Programmierung und Greedy-Algorithmus

Breitensuche

Der Breitensuchalgorithmus ist ein Algorithmus, der einen Baum oder ein Diagramm durchläuft oder durchsucht. Er sucht vom Wurzelknoten aus und erweitert ihn Schicht für Schicht nach unten, bis der Zielzustand gefunden wird oder alle Knoten durchlaufen werden. BFS wird normalerweise mithilfe einer Warteschlange implementiert, die jedes Mal den nächsten Knoten in die Warteschlange stellt, bis alle Knoten besucht wurden.

Hier ist eine Java-Implementierung:

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

Tiefensuche

Der Tiefensuchalgorithmus ist ein Algorithmus, der einen Baum oder ein Diagramm durchläuft oder durchsucht, indem er alle Unterbäume vom Wurzelknoten bis zum Zielzustand oder alle Knoten rekursiv durchläuft werden durchquert. DFS wird normalerweise mithilfe eines Stapels implementiert, der jedes Mal den nächsten Knoten auf den Stapel schiebt, bis alle Knoten besucht wurden.

Das Folgende ist eine Java-Implementierung:

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

Dynamische Programmierung

Der dynamische Programmieralgorithmus (DP) ist eine Problemlösungsmethode, die zur Lösung überlappender Teilprobleme und optimaler Unterstrukturprobleme verwendet wird. DP wird normalerweise zur Lösung von Optimierungsproblemen verwendet, z. B. dem Problem des kürzesten Wegs, dem Rucksackproblem usw.

Das Folgende ist eine Java-Implementierung:

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

Der Greedy-Algorithmus ist eine Methode zur Lösung von Optimierungsproblemen, die immer die aktuell optimale Lösung wählt. Im Gegensatz zur dynamischen Programmierung berücksichtigt der Greedy-Algorithmus nicht alle Teilprobleme, sondern betrachtet nur die aktuell optimale Lösung.

Hier ist eine Java-Implementierung:

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

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Java-Algorithmen BFS, DFS, dynamische Programmierung und Greedy-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!