L'algorithme de recherche en largeur d'abord est erroné

L'algorithme de recherche en largeur de fraise d'abord de l'éditeur

php est un algorithme de traversée de graphiques couramment utilisé, mais dans certains cas, il peut produire des résultats erronés. L'algorithme de recherche en largeur est généralement utilisé pour résoudre le problème du chemin le plus court des graphiques. Son idée principale est de partir du nœud de départ et de parcourir les nœuds du graphique couche par couche jusqu'à ce que le nœud cible soit trouvé ou que tous les nœuds soient traversés. Cependant, l'algorithme de recherche en largeur peut ne pas obtenir de résultats corrects lorsqu'il y a des cycles dans le graphique ou lorsqu'il y a plusieurs nœuds cibles. Par conséquent, lorsque vous utilisez l'algorithme de recherche en largeur, vous devez faire attention à ses limites et sélectionner un algorithme approprié en fonction de scénarios de problèmes spécifiques.

Contenu de la question

Hier, j'ai posé une question sur dfs. Aujourd'hui, j'essaie d'implémenter bfs.

La classe .java non donnée dans ce fil est tirée de la question précédente.

J'ai écrit ce cours :

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);
                }
            }
        }
    }
}

J'ai ajouté ce qui suit à la classe main.java :

breadthfirstsearch bfs = new breadthfirstsearch(9);
bfs.print();
bfs.calc(pos);

Pour le constructeur de breadthfirstsearch.java j'obtiens cette matrice :

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);
        }

Aucune de ces conditions n'est vraie au départ, nous pouvons donc les ignorer.

else
{
    grid[i[0]][i[1]].setisvisited(true);

J'ai défini le nœud avec position=visited donc je n'ai pas besoin de le vérifier à nouveau.

Parmi ces conditions, seuls (1) et (3) sont vrais, nous ajoutons donc 2 tableaux int[] au deque :

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);
}

Enfin, nous supprimons les nœuds visités :

arraydeque.remove(i);

Ce que j'obtiens en sortie est :

0
0
0
0
0

Alors, où est le code ?

Solution

Vous ne gérez pas le poste correctement. Ce code mute i :

int[] c = i;
    c[0]++;

Vous semblez penser que c est une copie d'un tableau, mais ce n'est pas le cas. Il fait uniquement référence au tableau référencé par c 是数组的副本，但事实并非如此。它仅引用 i 引用的数组，因此当您执行 c[0]++ 时，该单个数组现在具有该递增值。下次您应用此类代码时（在接下来的 if 块之一中），您将不会从原始位置开始，而是从已经变异的 i, donc lorsque vous faites c[0]++, ce tableau unique a désormais cette valeur incrémentée. La prochaine fois que vous appliquerez un tel code (dans l'un des blocs if suivants), vous ne partirez pas de la position d'origine, mais du

déjà muté, donc votre "étape" s'égarera.

Honnêtement, j'ai déjà souligné dans ma réponse à votre question précédente

que l'idée d'utiliser des positions de type tableau aboutissait à un code moins élégant, et nous voyons maintenant à quel point il est facile d'introduire des bugs avec celui-ci.

Si vous utilisez un tel tableau, vous devez réellement construire le nouveau tableau et copier le contenu du tableau d'origine.

Ce qui suit est la correction de cette partie du code : 🎜

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});
        }

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!