2

我一直在阅读很多关于如何使用广度优先搜索、dfs、A* 等的 stackoverflow 问题,问题是最佳用法是什么以及如何在现实中实现它与模拟图。例如

假设您有 Twitter/Facebook/某个社交网站的社交图,对我来说,搜索算法的工作原理如下:

如果用户 A 有 10 个朋友,那么其中一个有 2 个朋友,另一个有 3 个朋友。搜索首先会找出用户 A 的朋友是谁,然后必须向十个用户中的每一个查找谁的朋友在哪里。对我来说,这似乎是 bfs?

但是,我不确定这是否是实现算法的方法。

谢谢,

4

2 回答 2

0

对于我的两分钱,如果你只是想遍历整个图,那么你使用什么算法并不重要,只要它只命中每个节点一次。当您注意到时,这似乎是您所说的:

我只是想遍历整个图表

这意味着您的术语在技术上存在缺陷-您是在谈论遍历图表,而不是搜索图表。除非您实际上是在尝试搜索特定的东西,否则您似乎根本没有在问题中提及。

话虽如此,Facebook 和 Twitter 是非常不同的图结构,它们确实会影响你如何走它们:

  1. Facebook 本质上是一个无向图。如果 X 是 Y 的朋友,则 Y 必须是 X 的朋友。(或与 X 有关系,或相关等)。

  2. Twitter 本质上是一个有向图。如果 X 跟随 Y,则 Y 不必跟随 X。

这些问题将显着影响图行走算法。老实说,如果你只想访问所有节点,你还需要一个图吗?为什么不遍历所有这些?如果您在某些可迭代的数据结构 MY_DATA 中拥有所有节点,则可以使用如下生成器表达式:

def nodeGenerator(MY_DATA)
    for node in MY_DATA:
        yield node

显然,您需要调整 nodeGenerator 内部以处理您实际访问节点的方式。话虽如此,大多数图结构都实现了节点迭代器。然后,您可以随时通过以下方式创建迭代器:

 for node in nodeGenerator(MY_DATA):
     (Do something here)

也许我只是在这里遗漏了问题的重点,但目前您已经提出了一个关于没有搜索问题的搜索算法的问题。由于优化和搜索的无免费午餐性质,任何搜索算法的价值将完全取决于您尝试检查的搜索问题。

即使在相同的数据集中也是如此。毕竟,如果您要搜索名字以字母 D 开头的每个人,一个很好的方法是按字母顺序对每个人进行排序并进行二进制搜索。相反,如果您试图找到每个人与 Kevin Bacon 的分离程度,您将需要从 Bacon 先生开始并递归迭代每个认识他的人和他们认识的每个人的算法。这些都是你可以在 Facebook 或 Twitter 上做的事情,但没有任何细节,真的没有办法推荐算法。因此,如果您一无所知,只需将每个人都作为列表进行迭代。它和其他任何东西一样好。如果你想优化,缓存任何计算。

于 2011-06-06T00:15:02.947 回答
0

我在 facebook 上有大约 300 个朋友,我的一些朋友平均也有 300 个朋友。如果你要用它建立一个图表,它会是巨大的。纠正我,如果我错了?. 在这种情况下,BFS 会要求很高吗?

谢谢J

于 2011-06-13T19:09:32.560 回答