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[] 数组:
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);
我在输出中得到的是:
0 0 0 0 0
那么代码在哪里呢?
您没有正确处理职位。此代码变异 i
:
int[] c = i; c[0]++;
您似乎认为 c
是数组的副本,但事实并非如此。它仅引用 c
是数组的副本,但事实并非如此。它仅引用 i
引用的数组,因此当您执行 c[0]++
时,该单个数组现在具有该递增值。下次您应用此类代码时(在接下来的 if
块之一中),您将不会从原始位置开始,而是从已经变异的 i
引用的数组,因此当您执行 c[0]++
时,该单个数组现在具有该递增值。下次您应用此类代码时(在接下来的 if
块之一中),您将不会从原始位置开始,而是从已经变异的
老实说,我已经在我对你上一个问题的回答
中指出,使用数组类型位置的想法导致代码不太优雅,现在我们看到用它引入错误是多么容易。如果您使用此类数组,则必须真正构造新数组并复制原始数组的内容。
以下是对这部分代码的更正:🎜
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中文网其他相关文章!