調試廣度優先搜尋 (BFS) 的實現

php小編柚子為您介紹除錯廣度優先搜尋（BFS）的實作。廣度優先搜尋是一種用於圖和樹的遍歷演算法，它從起始節點開始，逐層地存取相鄰節點，直到找到目標節點。在實作BFS演算法時，調試是非常重要的環節，它可以幫助我們發現程式碼中的錯誤和邏輯問題，提高程式的效率和準確性。本文將為您詳細介紹如何調試BFS演算法，希望能對您的學習和實踐有所幫助。

問題內容

背景

我在 3d 空間中有 3d 體素。它們由 x, y, z 索引。它們被標記為 full 或 empty。我嘗試有效地計算由鄰居 full 體素組成的組件數量。

bfs 詳細資訊

我有以下程式碼來實現廣度優先搜尋（bfs）演算法。每個體素以 [3]int{x, y, z} 表示。

// Count separate components consisting of disconnected finite elements.
func (vg *VoxelGrid) CountComponents() int {
    // Map key is (x, y, z) index of voxel.
    visited := make(map[[3]int]bool)
    count := 0
    for z := 0; z < vg.Len.Z; z++ {
        for y := 0; y < vg.Len.Y; y++ {
            for x := 0; x < vg.Len.X; x++ {
                if !visited[[3]int{x, y, z}] {
                    count++
                    vg.bfs(visited, [3]int{x, y, z})
                }
            }
        }
    }
    return count
}

// Algorithm: breadth-first search (BFS).
// This is much faster than depth first search (DFS) algorithm.
func (vg *VoxelGrid) bfs(visited map[[3]int]bool, start [3]int) {
    queue := [][3]int{start}
    visited[start] = true

    for len(queue) > 0 {
        v := queue[0]
        queue = queue[1:]

        neighbors := vg.getNeighbors(v)

        for _, n := range neighbors {
            if !visited[n] {
                visited[n] = true
                queue = append(queue, n)
            }
        }
    }
}

// It returns a list of neighbor voxels that are full, i.e. not empty.
func (vg *VoxelGrid) getNeighbors(v [3]int) [][3]int {
    var neighbors [][3]int
    for i := -1; i <= 1; i++ {
        for j := -1; j <= 1; j++ {
            for k := -1; k <= 1; k++ {
                if i == 0 && j == 0 && k == 0 {
                    continue
                }

                x := v[0] + i
                y := v[1] + j
                z := v[2] + k

                if x >= 0 && x < vg.Len.X &&
                    y >= 0 && y < vg.Len.Y &&
                    z >= 0 && z < vg.Len.Z {
                    // Index is valid.
                } else {
                    continue
                }

                // Is neighbor voxel empty or not?
                if vg.IsNotEmpty(x, y, z) {
                    neighbors = append(neighbors, [3]int{x, y, z})
                }
            }
        }
    }
    return neighbors
}

問題

上面的實作無法正常工作。對於僅應包含 8 元件的簡單模型，它會傳回元件計數為 1224：

問題

我透過 vs code 偵錯器單步調試了代碼。但我無法找出這個錯誤。有人在程式碼中看到任何可疑的東西嗎？有什麼提示可以指引我正確的方向嗎？

解決方法

問題是您還在 empty 體素上呼叫 bfs。

在 countcomponents 中，已驗證 bfs 僅在尚未訪問的體素上調用（良好）：

if !visited[[3]int{x, y, z}] {

...但它缺少測試該體素是否為full （不好），並且bfs 會很樂意將其添加到隊列中，期望它是full。因此，每個 empty 體素也被計為一個（1 體素大小）組件。

以上是調試廣度優先搜尋 (BFS) 的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！