标签: breadth-first-search

在Prolog中使用广度优先于默认深度优先搜索方案的一般思路是什么？

没有采取无限的分支？

在Prolog中有没有使用广度优先的一般方法？我一直在谷歌搜索,我没有找到太多有用的新手信息.

假设我找到符合我标准的节点,我需要停止搜索.

假设我有以下Haskell树类型,其中"State"是一个简单的包装器:

data Tree a = Branch (State a) [Tree a]
            | Leaf   (State a)
            deriving (Eq, Show)

我还有一个函数"expand :: Tree a - > Tree a",它接受一个叶子节点,并将它扩展为一个分支,或者取一个分支并不加改变地返回它.此树类型表示N元搜索树.

搜索深度优先是一种浪费,因为搜索空间显然是无限的,因为我可以通过在所有树的叶节点上使用扩展来轻松地继续扩展搜索空间,以及意外错过目标状态的机会是巨大的...因此唯一的解决方案是广度优先搜索,在这里实施相当不错,如果它在那里将找到解决方案.

我怎么想生成的,虽然是经过的树高达寻找解决方案.这是一个问题,因为我只知道如何执行深度优先,这可以通过在第一个子节点上一次又一次地简单地调用"expand"函数来完成......直到找到目标状态.(这真的不会产生任何其他的东西,然后是一个非常不舒服的列表.)

任何人都可以给我任何关于如何做到这一点(或整个算法)的暗示,或判断它是否可能具有相当复杂性？(或者是这方面的任何消息来源,因为我发现相当少.)

我已多次阅读有关DFS和BFS的内容,但我对此长期以来一直怀疑.在很多文章中提到DFS可能陷入无限循环.

据我所知,通过跟踪访问的节点可以很容易地消除这种限制.事实上,在我读过的所有书中,这个小支票都是DFS的一部分.

那么为什么"无限循环"被提到是DFS的缺点呢？是不是因为原始DFS算法没有对访问过的节点进行此检查？请解释.

我已经了解了这些算法的工作原理,但它们用于什么？

我们用它们来:

• 在图表中找到某个节点或
• 找到最短的路径或
• 在图表中查找循环

？

他们两个只是访问所有节点并标记他们访问过,我没有看到这样做的意义.

我在这里迷失了什么.

您将获得一个包含N个顶点的完整无向图.除了K边之外的所有边都有A的成本.那些K边的成本为B,你知道它们(作为对的列表).从节点0到节点N-1的最低成本是多少.

2 <= N <= 500k
0 <= K <= 500k
1 <= A, B <= 500k 

显然,问题是当那些K边缘比其他边缘花费更多并且节点0和节点N-1通过K边缘连接时.

Dijkstra不起作用.我甚至尝试过与BFS非常相似的东西.

Step1: Let G(0) be the set of "good" adjacent nodes with node 0.
Step2: For each node in G(0):
              compute G(node)
              if G(node) contains N - 1
                  return step

              else
                  add node to some queue
       repeat step2 and increment step

问题是由于每个节点都需要从0到N-1进行循环以便找到"好"的相邻节点,因此占用了大量时间.

有没有人有更好的想法？谢谢.

编辑:以下是ACM比赛的链接:http://acm.ro/prob/probleme/B.pdf

我一直在寻找一种计算JavaScript中最短路径的方法.我在https://github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter09上一直在玩Groner的数据结构和算法(适当命名) .

我一直在寻找的麻烦是代码是如此定制的,几乎不可能重写以产生所需的结果.我希望能够获得从任何给定顶点到任何其他顶点的最短路径,而不是像Groner编码那样,只是来自A的所有内容的列表.我希望能够获得,例如,从F到B,或从C到A.

完整的代码在这里:http://jsfiddle.net/8cn7e2x8/

有人可以帮忙吗？

var graph = new Graph();
var myVertices = ['A','B','C','D','E','F'];
for (var i=0; i<myVertices.length; i++) {
    graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('B', 'E');
graph.addEdge('C', 'D');
graph.addEdge('C', 'E');
graph.addEdge('C', 'G');
graph.addEdge('D', 'E');
graph.addEdge('E', 'F');

graph.dfs();

console.log('********* sortest path - BFS ***********');
var shortestPathA = graph.BFS(myVertices[0]);

//from A to all other vertices
var fromVertex = myVertices[0];

for (i = 1; i < myVertices.length; i++) {
    var toVertex = myVertices[i],
    path …

void traverse(Node* root)
{
    queue<Node*> q;

    Node* temp_node= root;

    while(temp_node)
    {
        cout<<temp_node->value<<endl;

        if(temp_node->left)
            q.push(temp_node->left);

        if(temp_node->right)
            q.push(temp_node->right);

        if(!q.empty())
        {
            temp_node = q.front();
            q.pop();
        }
        else
            temp_node = NULL;
   }
 }

上面发布的代码是我的级别订单遍历代码.这段代码对我来说很好,但我不喜欢的一件事是我明确初始化temp_node = NULL或者使用break.但它对我来说似乎不是一个好的代码.

是否有比这更好的实现或如何使这个代码更好？

最近,我已经从Stackoverflow中的Graph中提出了构建DFS树的问题,并且已经了解到可以使用State Monad简单地实现它.

在haskell的DFS

虽然DFS要求仅跟踪被访问节点,因此我们可以使用"Set"或"List"或某种线性数据结构来跟踪被访问节点,BFS需要完成"被访问节点"和"队列"数据结构.

我的BFS伪代码是

Q = empty queue
T = empty Tree
mark all nodes except u as unvisited
while Q is nonempty do
u = deq(Q)
    for each vertex v ? Adj(u)
        if v is not visited 
        then add edge (u,v) to T
             Mark v as visited and enq(v)

从伪代码可以推断,我们每次迭代只需要做3个进程.

1. 从队列中出列点
2. 将点的所有未访问的邻居添加到当前树的子节点,队列和"已访问"列表
3. 在队列中重复此操作

由于我们没有使用递归遍历进行BFS搜索,我们需要一些其他的遍历方法,例如while循环.我在hackage中查找了loop-while包,但似乎有点弃用了.

我假设我需要这样的代码:

{-...-}
... =   evalState (bfs) ((Set.singleton start),[start])
where 
    neighbors x = Map.findWithDefault [] x adj 
    bfs =do (vis,x:queue)<-get
             map (\neighbor ->
                  if (Set.member …

题:

给定两个单词(beginWord和endWord)和一个字典的单词列表,找到从beginWord到endWord的所有最短变换序列,这样:

一次只能更改一个字母.每个转换后的单词必须存在于单词列表中.请注意,beginWord不是转换后的单词.

例1:

输入:beginWord ="hit",endWord ="cog",wordList = ["hot","dot","dog","lot","log","cog"]

输出:[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

我的解决方案基于这个想法,但我如何分析此解决方案的时间和空间复杂性？

1)通过将每个字母转换为26个字母中的一个来执行从beginWord开始的BFS,并查看转换后的单词是否在wordList中,如果是,则放入队列.

2)在BFS期间,为所有有效的下一个单词维护{word:nextWord}的图形

3)当nextWord到达endWord时,在图形上进行回溯DFS(预先遍序遍历)以获得所有路径.

class Solution:
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        wordListSet = set(wordList+[beginWord])
        graph = collections.defaultdict(list)
        q = set([beginWord])    
        count = 0
        result = []
        while q:
            count +=1
            newQ = set()
            for word in q:
                wordListSet.remove(word)
            for word in q:
                if word == endWord:                                        
                    self.getAllPaths(graph, beginWord, endWord, result, [])
                    return result
                for i in range(len(word)): …