Debuggen der Implementierung der Breitensuche (BFS).

php-Editor Youzi führt Sie in die Implementierung des Debuggens von Breadth First Search (BFS) ein. Die Breitensuche ist ein Durchlaufalgorithmus für Diagramme und Bäume, der von einem Startknoten ausgeht und benachbarte Knoten Schicht für Schicht aufsucht, bis der Zielknoten gefunden wird. Bei der Implementierung des BFS-Algorithmus ist das Debuggen ein sehr wichtiger Link. Es kann uns helfen, Fehler und logische Probleme im Code zu finden und die Effizienz und Genauigkeit des Programms zu verbessern. Dieser Artikel stellt Ihnen ausführlich vor, wie Sie den BFS-Algorithmus debuggen, und hofft, Ihnen beim Lernen und Üben behilflich zu sein.

Frageninhalt

Hintergrund

Ich habe 3D-Voxel im 3D-Raum. Die Anzahl der Komponenten, aus denen sie bestehen x, y, z 索引。它们被标记为 full 或 empty。我尝试有效地计算由邻居 full Voxel.

bfs-Details

Ich habe den folgenden Code zum Implementieren des BFS-Algorithmus (Breadth First Search). Jedes Voxel wird durch [3]int{x, y, z} dargestellt.

// 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
}

Frage

Die obige Implementierung funktioniert nicht richtig. Denn sollte nur 8 组件的简单模型，它返回组件计数为 1224 enthalten:

Frage

Ich habe den Code mit dem vs-Code-Debugger durchgegangen. Aber ich kann diesen Fehler nicht herausfinden. Erkennt irgendjemand etwas Verdächtiges im Code? Irgendwelche Tipps, die mich in die richtige Richtung weisen?

Lösung

Das Problem ist, dass Sie immer noch empty 体素上调用 bfs sind.

Ein countcomponents 中，已验证 bfs Wird nur bei Voxeln aufgerufen, die noch nicht besucht sind (gut):

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

...aber es fehlt der Test, ob das Voxel full （不好），并且 bfs 会很乐意将其添加到队列中，期望它是 full。因此，每个 empty Das Voxel wird auch als (1 Voxelgröße) Komponente gezählt.

Das obige ist der detaillierte Inhalt vonDebuggen der Implementierung der Breitensuche (BFS).. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!