挑战,如何实现六度分离算法？

Question

用户A,用户B,用户C-UserD-UserF

通过' - '连接的用户互相认识.

我需要一个算法来完成这两项任务:

1. 计算从UserX到UserY的路径
2. 对于UserX,计算距离不超过3步的所有用户.

有效的解决方案吗？

编辑

我的目的不是证明它是对还是错,而是在必要时实时计算结果.

另外,我认为最具表现力的方式是代码,甚至是伪代码.

再次编辑

我已经决定这种工作必须在数据库内完成,所以它必须是一个sql解决方案!

Answer 1

通过图表表示此用户列表

• 每个用户都是一个节点
• 任何两个相互了解的用户之间都存在优势

1. 计算从UserX到UserY的路径
2. 对于UserX,计算距离不超过3步的所有用户.

这些问题密切相关,相同的算法实际上解决了这两个问题.您可以将其称为"Dijkstra算法,所有边缘都具有权重1"或"广度优先搜索".

基本上,从第一个节点开始,访问其所有亲属; 然后将它们全部标记为已访问,记录每个最短路径(到达它们的最短路径+刚刚遍历的边缘),并为每个路径重复.在问题#1到达目的地后停止,在问题#2的最短路径> 3后停止.

这将在O(n)时间内运行.不,没有更快的方法.

用于六度分离的最快O(n)算法可能是找到距离UserX和UserY一步的所有用户的集合,并找到这两个集合的交集.如果没有,则从UserX添加用户2步并交叉; 然后从UserY添加用户2步并交叉; 最多3个.

如果每个人平均有100个朋友,这可能需要查看最多约2,020,200个用户,而不是Dijkstra算法的1,010亿.在实践中,这些数字会小得多,因为你的两个朋友通常也是彼此的朋友.

这是解决六度分离的唯一方法 (目前提到的那些) 将在实践中起作用.

Answer 2

图算法可以在这里帮助您.了解它们也很有趣!

• 连接的图形连接.
• Dijkstra(A*)用于用户之间的路径
• 简单的DFS,用于查找远离用户的所有用户N个节点

如果要在两个用户之间找到最短路径,则应使用Dijkstra或类似方法.它们之间可能有几条路径,Dijkstra注意到它找到了一条短路径而不是之前发现的路径.

要找到所有用户之间的最短路径,您必须使用像Floyd-Warshall这样的东西.这是动态编程的一个很好的例子,实现起来非常简单.维基百科的伪代码是:

 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
 2    (infinity if there is none).
 3    Also assume that n is the number of vertices and edgeCost(i,i) = 0
 4 */
 5
 6 int path[][];
 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
 8    from i to j using intermediate vertices (1..k?1).  Each path[i][j] is initialized to
 9    edgeCost(i,j) or infinity if there is no edge between i and j.
10 */
11
12 procedure FloydWarshall ()
13    for k := 1 to n
14       for i := 1 to n
15          for j := 1 to n
16             path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

Answer 3

我有一个与你已有的建议完全不同的建议.如果你必须坚持使用SQL数据库并且你不知道任何java,那么这个建议将没有多大用处.

你的问题特别是一个图形问题,所以我建议虽然使用SQL数据库来存储图形是可行的,但另一种方法是使用专门用于图形问题的解决方案.

该Neo4j的项目提供了一个基于磁盘的图形数据库,一起将大量的图形算法来使用它.引用:

Neo4j是一个图形数据库.它是一个嵌入式,基于磁盘的完全事务性Java持久性引擎,它存储以图形而不是表格形式构建的数据.图形(网络的数学术语)是一种灵活的数据结构,允许更灵活,更快速的开发方式.

在他们的wiki上使用Neo4j的适当示例演示了使用IMDB数据的分离度Web应用程序.该示例说明了任何演员和Kevin Bacon之间的最短路径计算.

我喜欢这个例子,因为它谈论了很多关于图形所代表的域的建模.对域进行建模可确保您考虑以下事项:

1. 定向与未定向
2. 边缘类型/关系
3. 边缘权重等属性

正如其他帖子中提到的,有许多用于计算最短路径的算法,例如Dijkstra,Floyd Warshall或BFS.所有这些都在Neo4j中实现,这里提供了一些示例.

Answer 4

假设源数据在表中:Connections:(PersonID,KnowsPersonID)

1)这将必须采用广度优先的方法.由于问题的指数性,你的良好表现潜力是有限的(虽然这种指数性质是理论上你只需要6度的原因:D).确保限制搜索深度.无论您选择哪种SQL,您最好使用其迭代扩展而不是基于纯集的解决方案.

以下是使用Microsoft的T-SQL的基本方法:

CREATE PROCEDURE FindPath (@UserX int, @UserY int)

CREATE TABLE #SixDegrees(
  ConnectedUser int,
  Depth int,
  Path varchar(100),
  CONSTRAINT PK_SixDegrees PRIMARY KEY CLUSTERED (
    ConnectedUser
  )
)

DECLARE @Depth int,
        @PathFound varchar(100)
SET @Depth = 0

INSERT INTO #SixDegrees (@UserX, 0, CAST(@UserX as varchar))
/*Next line just in case X & Y are the same*/
SET @PathFound = (SELECT Path 
                  FROM #SixDegrees 
                  WHERE ConnectedUser = @UserY)

WHILE @Depth < 6 AND @PathFound IS NULL
BEGIN
  SET @Depth = @Depth + 1
  INSERT INTO #SixDegrees
  SELECT  k.KnowsPersonID, @Depth, (SELECT Path 
                                    FROM #SixDegrees 
                                    WHERE ConnectedUser = k.Link) + ',' + CAST(k.KnowsPersonID AS varchar)
  FROM (
      SELECT  MIN(ConnectedUser) Link, KnowsPersonID
      FROM    #SixDegrees
              JOIN Connections ON
                PersonID = ConnectedUser
      WHERE   Depth = @Depth
              /*EDIT: Added the following*/
              AND KnowsPersonID NOT IN (
                  SELECT  ConnectedUser
                  FROM    #SixDegrees
                  )
      GROUP BY KnowsPersonID
      ) k

  SET @PathFound = (SELECT Path 
                    FROM #SixDegrees 
                    WHERE ConnectedUser = @UserY)
END

IF @Path IS NULL
  PRINT 'No path found'
ELSE
  PRINT @Path
GO

编辑:在上面的解决方案中,我最初忘记排除已经在#SixDegrees临时表中的用户.

2)对上面的一点调整总是循环到3的深度会让你的#SixDegrees包含你感兴趣的所有用户.

但是,以下基于纯集的解决方案应该更有效:

SELECT  DISTINCT KnowsPersonID
FROM    Connections
WHERE   PersonID IN (
    SELECT  DISTINCT KnowsPersonID
    FROM    Connections
    WHERE   PersonID IN (
        SELECT  KnowsPersonID
        FROM    Connections
        WHERE   PersonID = @UserX
        ) l1
    ) l2

Answer 5

以下脚本是用sybase sql编写的.您可能必须根据您的数据库服务器进行微小的修改.

问题1.

create table #connections (
    my_user  varchar(10)  not null  ,
    knows varchar(10)  not null  ,
        CONSTRAINT connection_pk PRIMARY KEY CLUSTERED ( my_user, knows)   
) 

create table #traversed (id varchar(10) primary key)

insert into #connections VALUES ('UserA','UserB')
insert into #connections VALUES ('UserB','UserA')
insert into #connections VALUES ('UserB','UserC')
insert into #connections VALUES ('UserC','UserB')
insert into #connections VALUES ('UserC','UserD')
insert into #connections VALUES ('UserD','UserC')
insert into #connections VALUES ('UserD','UserF')
insert into #connections VALUES ('UserF','UserD')

DECLARE @str_sql   varchar(200)               
DECLARE @str_order varchar(60)

declare @start varchar(10)
set @start = ('UserD')
declare @end varchar(10)
set @end = ('UserA')

if (@start >= @end)
    set @str_order = " order by id desc"
else
    set @str_order = " order by id asc"


INSERT INTO #traversed VALUES (@start)

WHILE (select count(*) from #traversed where id = @end) = 0    
BEGIN     
  INSERT INTO #traversed (id)    
  SELECT DISTINCT knows  
  FROM #connections e JOIN #traversed p ON p.id = e.my_user  
  WHERE e.knows NOT IN (SELECT id FROM #traversed)     
  AND e.knows between (select case when @start < @end then @start else @end end)  
      and (select case when @start < @end then @end  else @start end) 
END

set @str_sql = "SELECT #traversed.id FROM #traversed" + @str_order 
exec (@str_sql)

问题2.

create table #connections (
    my_user  varchar(10)  not null  ,
    knows varchar(10)  not null  ,
        CONSTRAINT connection_pk PRIMARY KEY CLUSTERED ( my_user, knows)   
) 

create table #traversed (id varchar(10) primary key)

insert into #connections VALUES ('UserA','UserB')
insert into #connections VALUES ('UserB','UserA')
insert into #connections VALUES ('UserB','UserC')
insert into #connections VALUES ('UserC','UserB')
insert into #connections VALUES ('UserC','UserD')
insert into #connections VALUES ('UserD','UserC')
insert into #connections VALUES ('UserD','UserF')
insert into #connections VALUES ('UserF','UserD')

declare @start varchar(10)
set @start = ('UserB')

declare @higher_counter int
declare @lower_counter int

set @higher_counter = 0
set @lower_counter = 0

INSERT INTO #traversed VALUES (@start)

WHILE (@higher_counter < 3)
BEGIN     
  INSERT INTO #traversed (id)    
  SELECT DISTINCT knows  
  FROM #connections e JOIN #traversed p ON p.id = e.my_user  
  WHERE e.knows NOT IN (SELECT id FROM #traversed)     
  AND e.knows > @start 

  set @higher_counter = @higher_counter +1
END  

WHILE (@lower_counter < 3)
BEGIN     
  INSERT INTO #traversed (id)    
  SELECT DISTINCT knows  
  FROM #connections e JOIN #traversed p ON p.id = e.my_user  
  WHERE e.knows NOT IN (SELECT id FROM #traversed)     
  AND e.knows < @start 

  set @lower_counter = @lower_counter +1
END   

SELECT #traversed.id FROM #traversed