21 votos

Desafío,cómo implementar un algoritmo para los seis grados de separación?

UserA-Usuario B-UserC-UserD-UserF

Los usuarios conectados por '-' saber el uno del otro.

Y necesito un algoritmo para estas 2 tareas:

  1. Calcular la ruta desde Usuariox a UserY
  2. Para Usuariox,calcular todos los usuarios que hay más de 3 pasos de distancia.

Hay una solución eficiente?

EDITAR

Mi objetivo no es demostrar lo bien o mal,pero para calcular el resultado en tiempo real cuando sea necesario.

Además,creo que la mayoría de la forma expresiva es el código,hasta el pseudo.

EDITAR DE NUEVO

He decidido que este tipo de trabajo debe ser hecho dentro de la base de datos,por lo que debe ser un sql solución!

16voto

Representar a esta lista de usuarios por medio de un gráfico

  • Cada usuario es un nodo
  • Hay una arista entre dos usuarios que se conocen
  1. Calcular la ruta desde Usuariox a UserY
  2. Para Usuariox,calcular todos los usuarios que hay más de 3 pasos de distancia.

Estas preguntas están tan íntimamente relacionados que el mismo algoritmo que en realidad soluciona ambos de ellos. Se le puede llamar "el de Dijkstra el algoritmo con todos los bordes de tener peso 1," o "búsqueda en anchura."

Esencialmente, comenzando en el primer nodo, visita a todos sus parientes; marcarlos todos como la visita, registro de la ruta más corta a cada uno (el camino más corto para ellos + el borde que acaba de recorrido), y repita el proceso para cada uno de ellos. Parar después de que usted haya llegado a su destino para el Problema #1, parada después de la ruta más corta es > 3 para el Problema de la #2.

Este se ejecutará en O(n) tiempo. No, No hay manera más rápida.

La forma más rápida de O(n) para el algoritmo de seis grados de separación sería probablemente la de la búsqueda de los conjuntos de todos los usuarios 1-paso de Usuariox y UserY, y la búsqueda de la intersección de los dos conjuntos. Si ninguno, a continuación, agregue los usuarios 2-pasos de Usuariox y se cruzan; a continuación, agregue los usuarios de 2-pasos de UserY y se cruzan; etc. hasta 3.

Si cada persona tiene un promedio de 100 amigos, esto podría requerir mirando hasta alrededor de 2,020,200 los usuarios, como contraposición a la de 1.010 millones de dólares para el de Dijkstra el algoritmo. En la práctica, estas cifras podrían ser mucho menor, ya que a menudo dos de sus amigos también son amigos unos con otros.

Este es el único método de resolución de seis grados de separación (de los mencionados hasta el momento) que funcionará en la práctica.

8voto

Eli Bendersky Puntos 82298

Algoritmos de gráfico puede ayudar a usted aquí. Aprender acerca de ellos también es divertido!

  • Gráfico de la conectividad para la conectividad.
  • Dijkstra (*) para las rutas entre los usuarios
  • Simple DFS para la búsqueda de todos los usuarios de N nodos lejos de su usuario

Dijkstra o similares debe ser utilizado si usted quiere encontrar el camino más corto entre dos usuarios. Puede haber varios caminos, entre ellos, y de Dijkstra se ocupa de señalar, cuando encontró un cortocircuito en el camino de otro que se ha encontrado antes de.

Para encontrar los caminos más cortos entre todos los usuarios que usted tendrá que usar algo como Floyd-Warshall. Es un buen ejemplo de programación dinámica y es bastante simple de implementar. El pseudocódigo de la Wikipedia es:

 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] );

6voto

Binary Nerd Puntos 6497

Tengo una sugerencia que es muy diferente de los que ya tiene. Si usted tiene que pegarse con una base de datos SQL y no sabes nada de java esta sugerencia no servirá de mucho uso.

Que problema es específicamente un gráfico problema, así que me gustaría sugerir que, si bien el uso de una base de datos SQL para almacenar el gráfico de trabajo, un enfoque diferente sería el uso de una solución que está diseñado específicamente para los problemas de gráfico.

El Neo4j proyecto proporciona un disco basado en la base de datos en grafo, juntos en un montón de algoritmos de gráfico para trabajar con él. Cita:

Neo4j es un gráfico de la base de datos. Es un integrado, basado en disco, totalmente transaccional de persistencia Java motor que almacena los datos estructurados en los gráficos en lugar de en las mesas. Un gráfico (matemática lingo para una red) es una flexible estructura de datos que permite una gestión más ágil y rápido de estilo de desarrollo.

Un ejemplo apropiado de uso de Neo4j en su wiki muestra un grados de separación aplicación web utilizando datos de IMDB. El ejemplo ilustra la ruta más corta cálculos entre cualquier actor y Kevin Bacon.

Me gusta este ejemplo, puesto que se habla mucho sobre el modelado del dominio de su gráfico se representan. El modelado de su dominio se asegura de que usted ha pensado acerca de cosas como:

  1. Dirigido vs Grafo
  2. Tipos de arista/relaciones
  3. Atributos tales como el borde de pesos

Como se ha mencionado en otros posts, hay una serie de algoritmos para el cálculo de corta-rutas de acceso, tales como Dijkstra, Floyd y Warshall o BFS. Todos estos han sido implementados en Neo4j y se dan algunos ejemplos aquí.

6voto

Craig Young Puntos 5570

Suponiendo que la fuente de datos en una tabla: Conexiones:(PersonID, KnowsPersonID)

1) se tiene que utilizar una amplitud primera aproximación. Su potencial para el buen desempeño es limitado debido a la exponencial de la naturaleza del problema (aunque este exponencial de la naturaleza es por eso que, teóricamente, usted sólo necesita 6 grados :D). Asegúrese de limitar la profundidad de la búsqueda. Cualquiera que sea el sabor de SQL que usted elija usted probablemente va a ser mejor con su iterativo extensiones frente a un puro conjunto a partir de la solución.

El siguiente sería el enfoque básico de Microsoft de 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

EDIT: En la solución anterior, originalmente me olvidé de excluir a los usuarios que ya están en el #SixDegrees de la tabla temporal.

2) Un pequeño arreglo en la de arriba para siempre bucle a una profundidad de 3 que le dejaría con #SixDegrees que contiene todos los Usuarios que están interesados en.

Sin embargo, los siguientes puro establece en función de la solución debe ser más eficiente:

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

5voto

George Dontas Puntos 12116

Las siguientes secuencias de comandos se escriben en sybase sql. Usted podría tener que ir a través de pequeñas modificaciones de acuerdo a su servidor de db.

Problema 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)

Problema 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

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X