廣度優先搜尋演算法是一種遍歷或搜尋樹或圖的演算法,它從根節點開始搜尋並逐層向下擴展,直到找到目標狀態或所有節點都被遍歷。 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]; }
貪心演算法是一種解決最佳化問題的方法,它總是選擇目前最優解。與動態規劃不同,貪心演算法並沒有考慮所有的子問題,而是只看當前的最優解。
下面是一個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中文網其他相關文章!