我一直在玩弄一些东西并想到了试图弄清楚的想法凯文·培根数字。我有一个网站的数据，为此我们可以考虑将其视为社交网络。让我们假设它是 Facebook（为了简化讨论）。我有一些人，我有他们的朋友名单，所以我有他们之间的联系。我如何计算一个人到另一个人的距离（基本上是凯文·培根数）？
我最好的想法是双向搜索，有深度限制（以限制计算复杂性并避免人们在图中根本无法连接的问题），但我意识到这是相当暴力的。
制作一些小子图（相当于 Facebook 上的群组），计算它们之间的最短距离（也许提前），然后尝试使用这些子图来查找链接是否会更好？虽然这需要预先计算，但它可以搜索更少的节点（节点可以是组而不是个体，从而使图小得多）。但这仍然是双向搜索。
我还可以预先计算一个人连接到的人数，首先在节点中搜索“受欢迎”的人，因为他们最有机会连接到给定的目的地个人。我意识到这将是速度与可能的最短路径的权衡。我想我还想使用深度优先搜索，而不是我计划在其他情况下使用的广度优先搜索。
有人能想出一种更简单/更快的方法吗？我希望能够找到两个人之间的最短长度，因此这并不像总是具有相同的终点那么容易（例如在凯文·培根问题中）。
我意识到存在诸如我可以获得 200 人的连锁之类的问题，但这可以解决我愿意搜索的深度的限制。
这是一个标准最短路径问题。有很多解决方案，包括迪杰斯特拉算法 and 贝尔曼-福特。您可能特别有兴趣查看A*算法并看看它如何使用相对于任何特定节点度数的倒数的成本函数来执行。这个想法是首先访问更受欢迎的节点（具有更高程度的节点）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
