廣度優先搜尋演算法是錯誤的

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中文網其他相關文章！