Maison > développement back-end > Golang > Débogage de l'implémentation de la recherche en largeur d'abord (BFS)

Débogage de l'implémentation de la recherche en largeur d'abord (BFS)

王林
Libérer: 2024-02-10 15:18:19
avant
882 Les gens l'ont consulté

调试广度优先搜索 (BFS) 的实现

l'éditeur php Yuzi vous présente l'implémentation du débogage Breadth First Search (BFS). La recherche en largeur d'abord est un algorithme de parcours pour les graphiques et les arbres qui part d'un nœud de départ et visite les nœuds adjacents couche par couche jusqu'à ce que le nœud cible soit trouvé. Lors de la mise en œuvre de l'algorithme BFS, le débogage est un maillon très important. Il peut nous aider à trouver des erreurs et des problèmes logiques dans le code et à améliorer l'efficacité et la précision du programme. Cet article vous présentera en détail comment déboguer l'algorithme BFS, dans l'espoir d'être utile à votre apprentissage et à votre pratique.

Contenu des questions

Contexte

J'ai des voxels 3D dans l'espace 3D. Le nombre de composants qui les composent x, y, z 索引。它们被标记为 fullempty。我尝试有效地计算由邻居 full voxels.

détails bfs

J'ai le code suivant pour implémenter l'algorithme de recherche en largeur (bfs). Chaque voxel est représenté par [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
}

Copier après la connexion

Question

L'implémentation ci-dessus ne fonctionne pas correctement. Car ne doit contenir que 8 组件的简单模型,它返回组件计数为 1224 : 

Question

J'ai parcouru le code via le débogueur vs code. Mais je n'arrive pas à comprendre cette erreur. Est-ce que quelqu'un voit quelque chose de suspect dans le code ? Des conseils pour m'orienter dans la bonne direction ?

Solution

Le problème c'est que tu es toujours empty 体素上调用 bfs.

On countcomponents 中,已验证 bfs Appelé uniquement sur les voxels qui n'ont pas encore visité (bon) :

if !visited[[3]int{x, y, z}] {
Copier après la connexion

... mais il manque le test de savoir si le voxel est full (不好),并且 bfs 会很乐意将其添加到队列中,期望它是 full。因此,每个 empty Le voxel est également compté comme un composant (taille de 1 voxel).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

source:stackoverflow.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal