Comment implémenter l'algorithme Java BFS, DFS, la programmation dynamique et l'algorithme glouton

Recherche en largeur d'abord

L'algorithme de recherche en largeur d'abord est un algorithme qui traverse ou recherche un arbre ou un graphique. Il recherche à partir du nœud racine et s'étend vers le bas couche par couche jusqu'à ce que l'état cible soit trouvé ou que tous les nœuds soient traversés. BFS est généralement implémenté à l'aide d'une file d'attente, qui place le nœud suivant dans la file d'attente à chaque fois jusqu'à ce que tous les nœuds aient été visités.

Voici une implémentation 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);
            }
        }
    }
}

Recherche en profondeur d'abord

L'algorithme de recherche en profondeur est un algorithme qui parcourt ou recherche un arbre ou un graphique en parcourant récursivement tous les sous-arbres à partir du nœud racine jusqu'à l'état cible ou tous les nœuds. sont parcourus. DFS est généralement implémenté à l'aide d'une pile, qui pousse le nœud suivant sur la pile à chaque fois jusqu'à ce que tous les nœuds aient été visités.

Ce qui suit est une implémentation 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);
        }
    }
}

Programmation dynamique

L'algorithme de programmation dynamique (DP) est une méthode de résolution de problèmes utilisée pour résoudre des sous-problèmes qui se chevauchent et des problèmes de sous-structure optimale. DP est généralement utilisé pour résoudre des problèmes d'optimisation, tels que le problème du chemin le plus court, le problème du sac à dos, etc.

Ce qui suit est une implémentation 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

L'algorithme glouton est une méthode de résolution de problèmes d'optimisation qui choisit toujours la solution optimale actuelle. Contrairement à la programmation dynamique, l’algorithme glouton ne considère pas tous les sous-problèmes, mais examine uniquement la solution optimale actuelle.

Voici une implémentation 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;
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!