标签: breadth-first-search

根据Norimaig在AIMA(人工智能:一种现代方法)中,深度优先算法并不完整(并不总是产生解决方案),因为有些情况下子树下降将是无限的.

另一方面,如果分支因子不是无限的,则称广度优先方法是完整的.但是,在DFS中子树无限的情况下,是不是有点像"东西"？

如果树的深度是有限的,那么DFS不能说是完整的吗？那么BFS是如何完成的而DFS不是完整的,因为BFS的完整性依赖于分支因子是有限的!

BFS,DFS和Dijkstra的实现几乎是一样的,除了BFS使用队列,DFS使用堆栈,而Dijkstra使用最小优先级队列？

更确切地说.我们是否可以对所有BFS,DFS和Dijkstra使用以下代码,Q是BFS的队列,DFS的堆栈和Dijkstra的最小优先级队列？谢谢!

Init d[]=Inf; // distance from the node s
Init c[]='w'; // color of nodes: 'w':undiscovered, 'g':discovered, 'b':fully explored
Init p[]=null; // previous node in the path
c[s]='g';
d[s]=0;
Q.push(s);
while(!Q.empty()) {
    u = Q.front();
    Q.pop();
    for v in adj[u] {
        if(c(v)=='w') {
            c[v]='g';
            if(d[u]+w(u,v)<d[v]) {
                d[v]=d[u]+w(u,v);
                p[v]=u;
            }
            Q.push(v);
        }
    }
    c[u]='b';
}

路径的"长度"是路径中的边数.

给定源和目标顶点,我想找到从源顶点到给定长度 k 的目标顶点的路径数.

• 我们可以根据需要多次访问每个顶点,因此如果路径来自a于b:a -> c -> b -> c -> b它被认为是有效的.这意味着可以有循环,我们可以不止一次通过目的地.

• 两个顶点可以通过多个边连接.因此,如果顶点a顶点b通过两条边连接,那么a -> b通过边1和a -> b边2 的路径被认为是不同的.

• 顶点数N <= 70,路径长度K <= 10 ^ 9.

• 由于答案可能非常大,因此应以模数为单位进行报告.

这是我到目前为止所想到的:

我们可以使用广度优先搜索而不将任何顶点标记为访问,在每次迭代时,我们跟踪我们对该路径所需的边数'n_e'和产品 'p'中每个边缘的重复边数路径有.

如果n_e大于k,则搜索搜索应该终止,如果我们以n_e等于k 到达目的地,我们终止搜索并添加p到路径数的计数.

我认为我们可以使用深度优先搜索而不是广度优先搜索,因为我们不需要最短路径,并且在广度优先搜索中使用的Q的大小可能是不够的.

我正在考虑的第二种算法类似于使用这种方法的Floyd Warshall的算法.只有我们不需要最短的路径,所以我不确定这是否正确.

我的第一个算法的问题是'K'可以达到1000000000,这意味着我的搜索将一直运行,直到它有10 ^ 9个边缘,n_e边缘计数将在每个级别增加1,这将非常慢,我不确定它会终止大输入.

所以我需要一种不同的方法来解决这个问题; 任何帮助将不胜感激.

我很难找到一种方法来正确地对边缘进行分类,同时在有向图上进行广度优先搜索.

在广度优先或深度优先搜索期间,您可以对满足4个类的边进行分类:

• 树
• 背部
• 交叉
• 向前

Skiena [1]给出了一个实现.如果沿着从v1到v2的边缘移动,这里有一种在Java中的DFS期间返回类的方法,以供参考.父映射返回当前搜索的父顶点,以及timeOf()方法,即发现顶点的时间.

if ( v1.equals( parents.get( v2 ) ) ) { return EdgeClass.TREE; }
    if ( discovered.contains( v2 ) && !processed.contains( v2 ) ) { return EdgeClass.BACK; }
    if ( processed.contains( v2 ) )
    {
        if ( timeOf( v1 ) < timeOf( v2 ) )
        {
            return EdgeClass.FORWARD;
        }
        else
        {
            return EdgeClass.CROSS;
        }
    }
    return EdgeClass.UNCLASSIFIED;

我的问题是我无法在有向图上进行宽度优先搜索.例如:

下图 - 这是一个循环 - 是可以的:

A -> B
A -> C
B …

我正在尝试构建一个方法,在未加权的图形中返回从一个节点到另一个节点的最短路径.我考虑过使用Dijkstra,但这似乎有点矫枉过正,因为我只需要一对.相反,我已经实现了广度优先搜索,但问题是我的返回列表包含一些我不想要的节点 - 如何修改我的代码以实现我的目标？

public List<Node> getDirections(Node start, Node finish){
    List<Node> directions = new LinkedList<Node>();
    Queue<Node> q = new LinkedList<Node>();
    Node current = start;
    q.add(current);
    while(!q.isEmpty()){
        current = q.remove();
        directions.add(current);
        if (current.equals(finish)){
            break;
        }else{
            for(Node node : current.getOutNodes()){
                if(!q.contains(node)){
                    q.add(node);
                }
            }
        }
    }
    if (!current.equals(finish)){
        System.out.println("can't reach destination");
    }
    return directions;
}

这是一个广度优先旅行的java代码:

void breadthFirstNonRecursive(){
    Queue<Node> queue = new java.util.LinkedList<Node>();
    queue.offer(root);
    while(!queue.isEmpty()){
        Node node = queue.poll();
        visit(node);
        if (node.left != null)
            queue.offer(node.left);
        if (node.right != null)
            queue.offer(node.right);
    }
}

是否可以编写递归函数来做同样的事情？

起初,我认为这很容易,所以我出来了:

void breadthFirstRecursive(){
    Queue<Node> q = new LinkedList<Node>();
    breadthFirst(root, q);
}

void breadthFirst(Node node, Queue<Node> q){
    if (node == null) return;
    q.offer(node);
    Node n = q.poll();
    visit(n);
    if (n.left != null)
        breadthFirst(n.left, q);
    if (n.right != null)
        breadthFirst(n.right, q);   
}

然后我发现它不起作用.它实际上与此相同:

void preOrder(Node node) {
    if (node == null) return;
    visit(node);
    preOrder(node.left); …

遍历图的两种最常见的方法是广度优先搜索和深度优先搜索.这两种搜索算法都遵循一个通用模板:

• 创建一个工作清单W,用起始节点s播种.
• 虽然工作清单不是空的:
  • 删除工作清单的第一个元素; 叫它v.
  • 如果没有访问v:
    • Mark v as visited.
    • 对于直接连接到v的每个节点,将u添加到W.

在广度优先搜索中,工作列表W实现为FIFO队列,而在深度优先搜索中,它是LIFO堆栈.如果W是优先级队列,则会获得统一成本搜索.

不久前,我问了一个关于从包中选择随机元素的数据结构的问题.如果您使用此随机包实现上述工作清单W,那么您将获得一个"随机优先搜索"算法,该算法从初始节点开始随机探索图中的节点.

我的问题是:有没有已知的算法使用这种类型的搜索？也就是说,是否有算法通过以这种方式生成图的随机生成树来工作？

我试图解决的问题涉及MRT系统树.

每个节点最多可以连接4个点,这简化了很多事情.这是我的想法.

struct stop {
    int path, id;
    stop* a;
    stop* b;
    stop* c;
    stop* d;
};

我可以编写代码来保存BFS搜索所有点所需的所有信息,但我主要担心的是,即使BFS找到了正确的点,我怎么知道它的路径？

BFS将搜索每个级别,当其中一个到达我的目的地时,它将跳出运行循环,然后,我将获得一个访问队列和一个未访问的队列,我该如何告诉用户他需要什么停止当访问的队列被BFS搜索到的每个节点填满时访问？

如何使用双向BFS查找最短路径？假设有一个6x6网格.起点在(0,5),终点在(4,1).使用双向bfs的最短路径是什么？没有路径成本.它是无向的.

我意识到泛型图上的BFS和DFS的运行时是O(n + m),其中n是节点数,m是边数,这是因为对于每个节点,必须考虑它的邻接列表.但是,当它在二叉树上执行时,BFS和DFS的运行时是什么？我认为它应该是O(n),因为可以离开节点的可能边数是恒定的(即2).请确认这是否正确理解.如果没有,那么请解释二叉树上BFS和DFS的正确时间复杂度是什么？