php小編草莓廣度優先搜尋演算法是一種常用的圖遍歷演算法，但在某些情況下，它可能會出現錯誤的結果。廣度優先搜尋演算法通常用於解決圖的最短路徑問題，其核心思想是從起始節點開始，逐層遍歷圖中的節點，直到找到目標節點或遍歷完所有節點。然而，當圖中存在環路或存在多個目標節點時，廣度優先搜尋演算法可能無法得到正確的結果。因此，在使用廣度優先搜尋演算法時，需要注意其局限性，並結合特定問題場景選擇合適的演算法。
昨天我問了一個關於dfs的問題。今天我正在嘗試實作 bfs。
本線程中未給出的 .java 類別取自上一個問題。
我寫了這個類別：
breadthfirstsearch.java
import java.util.arraydeque;
import java.lang.system;
public class breadthfirstsearch extends searchalgorithm{
public breadthfirstsearch(int gridsize)
{
super(gridsize);
}
public void calc(int[]pos)
{
arraydeque<int[]>arraydeque = new arraydeque<>();
arraydeque.add(pos);
while(!arraydeque.isempty())
{
for(int[]i:arraydeque) {
system.out.println(grid[i[0]][i[1]].getposition());
if (grid[i[0]][i[1]].getisexit()) {
system.out.println("path been found!");
arraydeque.remove(i);
} else if (grid[i[0]][i[1]].gettype() == 1) {
system.out.println("path been blocked!");
arraydeque.remove(i);
} else if (grid[i[0]][i[1]].getisvisited()) {
arraydeque.remove(i);
}
else
{
grid[i[0]][i[1]].setisvisited(true);
if (i[0] < gridlength - 1) {
int[] c = i;
c[0]++;
arraydeque.add(c);
}
if (i[0] > 0) {
int[] d = i;
d[0]--;
arraydeque.add(d);
}
if (i[1] < gridlength - 1) {
int[] e = i;
e[1]++;
arraydeque.add(e);
}
if (i[1] > 0) {
int[] f = i;
f[1]--;
arraydeque.add(f);
}
arraydeque.remove(i);
}
}
}
}
}我在 main.java 類別中加入了以下內容：
breadthfirstsearch bfs = new breadthfirstsearch(9); bfs.print(); bfs.calc(pos);
對於 breadthfirstsearch.java 的建構函數，我得到這個矩陣：
position:0 type:0 position:1 type:0 position:2 type:1 position:3 type:0 position:4 type:1 position:5 type:1 position:6 type:1 position:7 type:0 position:8 type:0
while(!arraydeque.isempty())
{
for(int[]i:arraydeque) {
system.out.println(grid[i[0]][i[1]].getposition());
if (grid[i[0]][i[1]].getisexit()) {
system.out.println("path been found!");
arraydeque.remove(i);
} else if (grid[i[0]][i[1]].gettype() == 1) {
system.out.println("path been blocked!");
arraydeque.remove(i);
} else if (grid[i[0]][i[1]].getisvisited()) {
arraydeque.remove(i);
}這些條件一開始都不成立，因此我們可以跳過它們。
else
{
grid[i[0]][i[1]].setisvisited(true);我用position=visited設定了節點，所以我不需要再檢查它。
在這些條件中，只有 (1) 和 (3) 為真，因此我們為雙端佇列新增 2 個 int[] 陣列：
if (i[0] < gridlength - 1) {
int[] c = i;
c[0]++;
arraydeque.add(c);
}
if (i[0] > 0) {
int[] d = i;
d[0]--;
arraydeque.add(d);
}
if (i[1] < gridlength - 1) {
int[] e = i;
e[1]++;
arraydeque.add(e);
}
if (i[1] > 0) {
int[] f = i;
f[1]--;
arraydeque.add(f);
}最後，我們刪除造訪過的節點：
arraydeque.remove(i);
我在輸出中得到的是：
0 0 0 0 0
那麼程式碼在哪裡呢？
您沒有正確處理職位。此程式碼變異 i：
int[] c = i;
c[0]++;您似乎認為 c 是陣列的副本，但事實並非如此。它僅引用 i 引用的數組，因此當您執行 c[0] 時，該單一數組現在具有該遞增值。下次您應用此類程式碼時（在接下來的if 區塊之一中），您將不會從原始位置開始，而是從已經變異的i 開始，因此您的「步驟」會誤入歧途。
老實說，我已經在我對你上一個問題的回答中指出，使用數組類型位置的想法導致程式碼不太優雅，現在我們看到用它引入錯誤是多麼容易。
如果您使用此類數組，則必須真正建構新數組並複製原始數組的內容。
以下是對這部分程式碼的更正：
if (i[0] < gridLength - 1) {
arrayDeque.add(new int[] {i[0]+1, i[1]});
}
if (i[0] > 0) {
arrayDeque.add(new int[] {i[0]-1, i[1]});
}
if (i[1] < gridLength - 1) {
arrayDeque.add(new int[] {i[0], i[1]+1});
}
if (i[1] > 0) {
arrayDeque.add(new int[] {i[0], i[1]-1});
}以上是廣度優先搜尋演算法是錯誤的的詳細內容。更多資訊請關注PHP中文網其他相關文章！
