广度优先搜索算法是错误的-Java-PHP中文网

广度优先搜索算法是错误的

王林

发布： 2024-02-11 09:33:08

转载

1292人浏览过

php小编草莓广度优先搜索算法是一种常用的图遍历算法，但在某些情况下，它可能会出现错误的结果。广度优先搜索算法通常用于解决图的最短路径问题，其核心思想是从起始节点开始，逐层遍历图中的节点，直到找到目标节点或遍历完所有节点。然而，当图中存在环路或存在多个目标节点时，广度优先搜索算法可能无法得到正确的结果。因此，在使用广度优先搜索算法时，需要注意其局限性，并结合具体问题场景选择合适的算法。

问题内容

昨天我问了一个关于dfs的问题。今天我正在尝试实现 bfs。

本线程中未给出的 .java 类取自上一个问题。

我写了这个类：

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

登录后复制

我在 main.java 类中添加了以下内容：

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

登录后复制

对于 breadthfirstsearch.java 的构造函数，我得到这个矩阵：

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

登录后复制

这些条件一开始都不成立，因此我们可以跳过它们。

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

登录后复制

我用position=visited设置了节点，所以我不需要再次检查它。

在这些条件中，只有 (1) 和 (3) 为真，因此我们向双端队列添加 2 个 int[] 数组：

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

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

登录后复制

我在输出中得到的是：

登录后复制

那么代码在哪里呢？

解决方法

您没有正确处理职位。此代码变异 i：

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

登录后复制

您似乎认为 c 是数组的副本，但事实并非如此。它仅引用 i 引用的数组，因此当您执行 c[0]++ 时，该单个数组现在具有该递增值。下次您应用此类代码时（在接下来的 if 块之一中），您将不会从原始位置开始，而是从已经变异的 i 开始，因此您的“步骤”会误入歧途。

老实说，我已经在我对你上一个问题的回答中指出，使用数组类型位置的想法导致代码不太优雅，现在我们看到用它引入错误是多么容易。

如果您使用此类数组，则必须真正构造新数组并复制原始数组的内容。

以下是对这部分代码的更正：

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

登录后复制

以上就是广度优先搜索算法是错误的的详细内容，更多请关注php中文网其它相关文章！