Algoritma carian luas pertama adalah salah

Algoritma carian pertama lebar strawberi editor php ialah algoritma lintasan graf yang biasa digunakan, tetapi dalam beberapa kes, ia mungkin menghasilkan hasil yang salah. Algoritma carian pertama keluasan biasanya digunakan untuk menyelesaikan masalah laluan terpendek bagi graf Idea terasnya ialah bermula dari nod permulaan dan merentasi nod dalam lapisan graf demi lapisan sehingga nod sasaran ditemui atau semua nod dilalui. Walau bagaimanapun, algoritma carian luas pertama mungkin tidak mendapat hasil yang betul apabila terdapat kitaran dalam graf atau apabila terdapat berbilang nod sasaran. Oleh itu, apabila menggunakan algoritma carian luas pertama, anda perlu memberi perhatian kepada hadnya dan memilih algoritma yang sesuai berdasarkan senario masalah tertentu.

Isi soalan

Semalam saya ada tanya soalan tentang dfs. Hari ini saya cuba melaksanakan bfs.

Kelas .java yang tidak diberikan dalam urutan ini diambil daripada soalan sebelumnya.

Saya menulis kelas ini:

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

Saya menambah yang berikut pada kelas main.java:

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

Untuk pembina breadthfirstsearch.java Saya mendapat matriks ini:

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

Tiada syarat ini benar pada mulanya, jadi kita boleh melangkaunya.

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

Saya tetapkan nod dengan position=visited jadi saya tidak perlu menyemaknya lagi.

Daripada syarat ini, hanya (1) dan (3) adalah benar, jadi kami menambah 2 int[] tatasusunan pada 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);
}

Akhir sekali, kami memadamkan nod yang dilawati:

arraydeque.remove(i);

Apa yang saya dapat dalam output ialah:

0
0
0
0
0

Jadi di manakah kodnya?

Penyelesaian

Anda tidak mengendalikan kedudukan dengan betul. Kod ini bermutasi i:

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

Nampaknya anda berfikir bahawa c ialah salinan daripada array, tetapi tidak demikian. Ia hanya merujuk tatasusunan yang dirujuk oleh c 是数组的副本，但事实并非如此。它仅引用 i 引用的数组，因此当您执行 c[0]++ 时，该单个数组现在具有该递增值。下次您应用此类代码时（在接下来的 if 块之一中），您将不会从原始位置开始，而是从已经变异的 i, jadi apabila anda melakukan c[0]++, tatasusunan single itu kini mempunyai nilai yang meningkat itu. Pada kali seterusnya anda menggunakan kod sedemikian (dalam salah satu blok if berikut), anda tidak akan bermula dari kedudukan asal, tetapi dari

yang telah bermutasi, jadi "langkah " anda akan tersasar.

Sejujurnya, saya telah menyatakan dalam jawapan saya kepada soalan anda sebelum ini

bahawa idea menggunakan kedudukan jenis tatasusunan menghasilkan kod yang kurang elegan, dan kini kita melihat betapa mudahnya memperkenalkan pepijat dengannya.

Jika anda menggunakan tatasusunan sedemikian, anda perlu membina tatasusunan baharu dan menyalin kandungan tatasusunan asal.

Berikut ialah pembetulan pada bahagian kod ini: 🎜

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

Atas ialah kandungan terperinci Algoritma carian luas pertama adalah salah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!