Der Breitensuchalgorithmus ist falsch

Der Erdbeer-Breitensuchalgorithmus des

php-Editors ist ein häufig verwendeter Graph-Traversal-Algorithmus, der jedoch in einigen Fällen zu falschen Ergebnissen führen kann. Der Breitensuchalgorithmus wird normalerweise verwendet, um das Problem des kürzesten Pfads von Diagrammen zu lösen. Seine Kernidee besteht darin, vom Startknoten aus zu beginnen und die Knoten im Diagramm Schicht für Schicht zu durchlaufen, bis der Zielknoten gefunden wird oder alle Knoten durchlaufen werden. Der Breitensuchalgorithmus liefert jedoch möglicherweise keine korrekten Ergebnisse, wenn das Diagramm Zyklen enthält oder wenn mehrere Zielknoten vorhanden sind. Daher müssen Sie bei der Verwendung des Breitensuchalgorithmus auf dessen Einschränkungen achten und einen geeigneten Algorithmus basierend auf bestimmten Problemszenarien auswählen.

Frageninhalt

Gestern habe ich eine Frage zu dfs gestellt. Heute versuche ich, bfs zu implementieren.

Die in diesem Thread nicht angegebene .java-Klasse stammt aus der vorherigen Frage.

Ich habe diesen Kurs geschrieben:

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

Ich habe der main.java-Klasse Folgendes hinzugefügt:

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

Für den Konstruktor von breadthfirstsearch.java erhalte ich diese Matrix:

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

Keine dieser Bedingungen trifft zunächst zu, daher können wir sie überspringen.

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

Ich habe den Knoten mit position=visited festgelegt, damit ich ihn nicht noch einmal überprüfen muss.

Von diesen Bedingungen sind nur (1) und (3) wahr, daher fügen wir der Deque zwei int[]-Arrays hinzu:

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

Abschließend löschen wir die besuchten Knoten:

arraydeque.remove(i);

Was ich in der Ausgabe erhalte, ist:

0
0
0
0
0

Wo ist der Code?

Lösung

Sie handhaben die Position nicht richtig. Dieser Code mutiert i:

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

Sie scheinen zu denken, dass c eine Kopie eines Arrays ist, aber das ist nicht der Fall. Es verweist nur auf das Array, auf das durch c 是数组的副本，但事实并非如此。它仅引用 i 引用的数组，因此当您执行 c[0]++ 时，该单个数组现在具有该递增值。下次您应用此类代码时（在接下来的 if 块之一中），您将不会从原始位置开始，而是从已经变异的 i verwiesen wird. Wenn Sie also c[0]++ ausführen, hat dieses einzelne Array jetzt diesen inkrementierten Wert. Wenn Sie das nächste Mal einen solchen Code anwenden (in einem der folgenden if-Blöcke), beginnen Sie nicht an der ursprünglichen Position, sondern an der bereits mutierten

, sodass Ihr „Schritt“ in die Irre geht.

Ehrlich gesagt habe ich bereits in meiner Antwort auf Ihre vorherige Frage

darauf hingewiesen, dass die Idee, Array-Typ-Positionen zu verwenden, zu weniger elegantem Code geführt hat, und jetzt sehen wir, wie einfach es ist, damit Fehler einzuführen.

Wenn Sie ein solches Array verwenden, müssen Sie das neue Array tatsächlich erstellen und den Inhalt des ursprünglichen Arrays kopieren.

Das Folgende ist die Korrektur dieses Teils des Codes: 🎜

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

Das obige ist der detaillierte Inhalt vonDer Breitensuchalgorithmus ist falsch. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!