Bagaimana untuk melaksanakan algoritma Java BFS, DFS, pengaturcaraan dinamik dan algoritma tamak

Carian keluasan didahulukan

Algoritma carian didahulukan keluasan ialah algoritma yang merentasi atau mencari pokok atau graf Ia mencari dari nod akar dan mengembang ke bawah lapisan demi lapisan sehingga keadaan sasaran ditemui atau semua nod adalah Traverse. BFS biasanya dilaksanakan menggunakan baris gilir, yang meletakkan nod seterusnya ke dalam baris gilir setiap kali sehingga semua nod telah dilawati.

Berikut ialah pelaksanaan 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);
            }
        }
    }
}

Carian mendalam-dahulu

Algoritma carian mendalam-dahulu ialah algoritma yang merentasi atau mencari pokok atau graf bermula dari nod akar Mula melintasi semua subpokok secara rekursif sehingga keadaan sasaran ditemui atau semua nod dilalui. DFS biasanya dilaksanakan menggunakan tindanan, yang menolak nod seterusnya ke tindanan setiap kali sehingga semua nod telah dilawati.

Berikut ialah pelaksanaan 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);
        }
    }
}

Pengaturcaraan Dinamik

Algoritma pengaturcaraan dinamik (DP) ialah kaedah penyelesaian masalah yang digunakan untuk menyelesaikan sub- masalah dan masalah substruktur yang optimum. DP biasanya digunakan untuk menyelesaikan masalah pengoptimuman, seperti masalah laluan terpendek, masalah knapsack, dll.

Berikut ialah pelaksanaan 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];
}

Rakus

Algoritma tamak ialah kaedah menyelesaikan masalah pengoptimuman yang sentiasa memilih penyelesaian optimum semasa. Tidak seperti pengaturcaraan dinamik, algoritma tamak tidak mempertimbangkan semua sub-masalah, tetapi hanya melihat pada penyelesaian optimum semasa.

Berikut ialah pelaksanaan 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;
    }
}

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma Java BFS, DFS, pengaturcaraan dinamik dan algoritma tamak. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!