hex*_*nal 4 algorithm search graph-theory breadth-first-search graph-algorithm
我之前参加了考试,有一个问题困扰着我和我交谈的其他人.它问了以下问题:
给出一个未加权的图G和两个顶点s和f的例子,这样s和f之间有一条最短路径,即广度优先搜索(从s开始)将永远不会找到,无论它访问邻近的顶点的顺序如何特别的优势.
对我们来说,这似乎不可能.我的第一个想法是,如果最短路径包含一个顶点作为其第n个步骤,可以从s以m步长到达,其中m < n,那么BFS将永远不会找到该路径,因为顶点已经被标记为参观.但如果是这种情况,所述路径根本不是最短路径,因为通过以m步进入顶点然后继续正常而获得的路径更短.
我们的教授提出了一个不可能的问题(可能是一个错字),还是我错过了什么？
编辑:为了消除任何可能的歧义,问题并没有要求举例说明BFS无法找到从s到f的最短路径.相反,它要求给出一个例子,其中存在从S到f的一些最短路径,BFS将永远找不到.因此,BFS完整且最优的事实并不排除这种可能性,除非我误解了这些术语的含义.
编辑2:也可以假设我们正在使用的BFS算法不会两次处理同一节点.例如,请参阅BFS Wiki上的算法大纲.
让我们G = (V,E)用图
V = ? ? {-1, 0}和E = { {-1,t}, {t,0} | t ? ? }
让s = -1与f = 0.存在着从长度为2的路径无限多s来f,但因为s有邻居无限多的,BFS不会来f.
不存在有限图,因此BFS没有找到从中s到达的最短路径f.让我们说G是一个有限图,是从最短的路径到.然后存在BFS的执行顺序,如下所示:s = a? ? a? ? ... ? an ? an+1 = fsf
对于所有人来说
i,0首先n访问,然后是所有其他直接邻居.ai+1ai
由于G是有限图,每个节点也只存在有限的许多直接邻居.因此它将完成列表并进入路径上的下一个节点.由于路径是最短的一个,它是被发现连接的第一个和.因此,有可能不存在一个有限的图形,使得BFS没有找到最短路径来.aisfsf
还可以存在没有例如用从路径s至f短于2
一个能想到的是长度为1,如果该最短路径s和f被认为不是相同的节点.但这意味着它f是一个直接的邻居,s所以存在一个f首先访问的BFS,然后继续与无数个其他邻居.