Задача, как реализовать алгоритм для шести степеней разделения?

Question

UserA-UserB-UserC-UserD-UserF

Пользователи, подключенные через '-', знают друг друга.

И мне нужен алгоритм для этих 2 задач:

1. Рассчитать путь от UserX до UserY
2. Для UserX рассчитать всех пользователей, которые находятся на расстоянии не более 3 шагов.

Есть ли эффективное решение?

EDIT

Моя цель не в том, чтобы доказать, правильно это или нет, а в случае необходимости вычислить результат в реальном времени.

Плюс, я думаю, что самый выразительный способ - это код, даже псевдо-.

ИЗМЕНИТЬ СНОВА

Я решил, что такая работа должна выполняться внутри базы данных, поэтому это должно быть решение sql!

Answer 1

Представьте этот список пользователей графиком

• Каждый пользователь является узлом
• Между любыми двумя пользователями, которые знают друг друга, есть грань

1. Рассчитать путь от UserX до UserY
2. Для UserX рассчитать всех пользователей, которые находятся на расстоянии не более 3 шагов.

Эти вопросы настолько тесно связаны, что один и тот же алгоритм фактически решает оба из них. Вы можете назвать это "Алгоритм Дейкстры со всеми ребрами, имеющими вес 1," или "поиск в ширину".

По сути, начиная с первого узла, посещайте всех его родственников; затем пометьте их всех как посещенных, запишите кратчайший путь к каждому (кратчайший путь к ним + край, который вы только что прошли), и повторите для каждого из них. Остановитесь после того, как вы достигли пункта назначения для Задачи № 1, остановитесь после того, как кратчайший путь> 3 для Задачи № 2.

Это будет выполнено за O (n) время. Нет, более быстрого пути нет.

Самый быстрый алгоритм O (n) для разделения на шесть градусов , вероятно, будет находить наборы всех пользователей на расстоянии одного шага от UserX и UserY и найти пересечение этих двух множеств. Если нет, то добавьте пользователей в 2 шагах от UserX и пересекайте; затем добавьте пользователей в 2 шагах от UserY и пересекайте; и т. д. до 3.

Если у каждого человека в среднем 100 друзей, для этого может потребоваться поискать около 2 020 200 пользователей , в отличие от 1 010 млрд. для алгоритма Дейкстры. На практике эти цифры были бы намного меньше, поскольку часто двое ваших друзей также дружат друг с другом.

Это единственный метод решения шести ступеней разделения (из упомянутых выше) , который будет работать на практике.

Answer 2

График алгоритмы могут помочь вам здесь. Узнать о них тоже весело!

• График подключения для подключения.
• Dijkstra (A *) для путей между пользователями
• Простая DFS для поиска всех пользователей на расстоянии N узлов от вашего пользователя

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

Предполагается, что исходные данные находятся в таблице: Соединения: (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 4

У меня есть предложение, которое сильно отличается от тех, которые у вас уже есть. Если вам нужно придерживаться базы данных SQL, и вы не знаете Java, это предложение не будет иметь большого значения.

Ваша проблема - это, в частности, проблема с графиком, поэтому я хотел бы предположить, что, хотя база данных SQL для хранения графика будет работать, другой подход будет заключаться в использовании решения, предназначенного специально для задач с графами.

Проект Neo4j предоставляет базу данных графов на основе диска, а также множество графических алгоритмов для работы с ней. Цитата:

Neo4j - это графическая база данных. Это встроенный, на основе диска, полностью транзакционный движок Java который хранит данные, структурированные в виде графиков а не в таблицах. График (математический жаргон для сети) гибкая структура данных, которая позволяет более проворный и быстрый стиль развитие.

Подходящий пример использования Neo4j в их вики демонстрирует веб-приложение со степенью разделения , использующее данные IMDB. Пример иллюстрирует вычисления кратчайшего пути между любым актером и Кевином Бэконом.

Мне нравится этот пример, так как он много говорит о моделировании области, которую будет представлять ваш график. Моделирование вашего домена гарантирует, что вы подумали о таких вещах, как:

1. Направлено против Ненаправленного
2. Типы ребер / отношения
3. Атрибуты, такие как веса ребер

Как уже упоминалось в других статьях, существует ряд алгоритмов для вычисления кратчайших путей, таких как Dijkstra, Floyd Warshall или BFS. Все это было реализовано в Neo4j, и некоторые примеры приведены здесь .

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

Answer 6

На самом деле есть достаточно эффективный способ сделать это с MariaDB, используя OQGraph.

Предполагая, что данные содержатся в двух таблицах:

CREATE TABLE `entity` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `type` enum('ACTOR','MOVIE','TV MOVIE','TV MINI','TV SERIES','VIDEO MOVIE','VIDEO GAME','VOICE','ARCHIVE') NOT NULL,
  `name` varchar(128) COLLATE utf8_unicode_ci NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `type` (`type`,`name`) USING BTREE
) ENGINE=InnoDB;

CREATE TABLE `link` (
  `rel_id` int(11) NOT NULL AUTO_INCREMENT,
  `link_from` int(11) NOT NULL,
  `link_to` int(11) NOT NULL,
  PRIMARY KEY (`rel_id`),
  KEY `link_from` (`link_from`,`link_to`),
  KEY `link_to` (`link_to`)
) ENGINE=InnoDB;

Виртуальная таблица OQGraph может быть объявлена ​​как:

CREATE TABLE movie_graph (
  latch SMALLINT UNSIGNED NULL,
  origid BIGINT UNSIGNED NULL,
  destid BIGINT UNSIGNED NULL,
  weight DOUBLE NULL,
  seq BIGINT UNSIGNED NULL,
  linkid BIGINT UNSIGNED NULL,
  KEY (latch, origid, destid) USING HASH,
  KEY (latch, destid, origid) USING HASH
) ENGINE=OQGRAPH 
  data_table='link' origid='link_from' destid='link_to';

Затем данные могут быть запрошены:

MariaDB [imdb]> SELECT
             -> GROUP_CONCAT(name ORDER BY seq SEPARATOR ' -> ') AS path
             -> FROM imdb_graph JOIN entity ON (id=linkid)
             -> WHERE latch=1
             -> AND origid=(SELECT a.id FROM entity a
             ->             WHERE name='Kevin Bacon')
             -> AND destid=(SELECT b.id FROM entity b
                            WHERE name='N!xau')\G
*************************** 1. row ***************************
path: Kevin Bacon -> The 45th Annual Golden Globe Awards (1988) -> Richard Attenborough -> In Darkest Hollywood: Cinema and Apartheid (1993) -> N!xau
1 row in set (10 min 6.55 sec)

График приблизительно 3,7 миллиона узлов с 30 миллионами ребер. Размер таблиц составляет около 3,5 ГБ, а InnoDB настроен для пула буферов 512 МБ на жестком диске ноутбука. Примерно 16 миллионов считываний вторичного ключа. Холодный, данные не загружаются в буферный пул. MacBook Pro 2010 года.

Конечно, намного быстрее, если таблица может храниться в пуле буферов.

Этот пример взят из: https://www.slideshare.net/AntonyTCurtis/oqgraph-scale2013-17332168/21

Answer 7

(Этот ответ эквивалентен ответу Джикстры. В основном это детали реализации.)

Чтобы ответить # 2, вы можете использовать умножение логической матрицы для определения связности вплоть до степени P.

Предполагается, что у вас логическая матрица M, где:

M(A, B)= A is directly connected to B

Тогда

(M(A, B))^P= A is connected to B within P links.

Для умножения матрицы следует использовать AND для умножения и OR для сложения:

Вы можете оптимизировать это много, делая умножение только для записей, которые ранее были ложными, а также понимая, что матрица симметрична. Это оставлено читателю в качестве упражнения.

Answer 8

Для задачи 2 вы не добьетесь большего успеха, чем поиск в ширину, за исключением, может быть, кэширования.

Для задачи 1 примените свое решение для задачи 2. Найдите всех пользователей на расстоянии не более 3 прыжков от пользователя X. Конечно, если пользователь Y находится в этом наборе, все готово. Если нет, выполните поиск в ширину, начиная с пользователя Y, и остановитесь, как только вы достигнете любого пользователя, о котором вы уже знаете, что он доступен из X.

(Если вы кешируете небольшую информацию о том, как вы достигли каждого пользователя во время задачи 2, вам будет легко восстановить точный путь, когда вы найдете ссылку в задаче 1.)

Answer 9

Первый вопрос можно решить с помощью алгоритма Дейкстры.Второй по использованию алгоритма DFS.Об этом уже говорили другие парни, просто хотели отметить, что наиболее эффективное решение для обеих проблем не доступно в одном алгоритме.

псевдокод можно найти по адресу:

[Википедия] [1]

для дижкстра и один в python для DFS по адресу:

http://en.wikipedia.org/wiki/Depth-first_search

Answer 10

Я смотрел на это некоторое время назад и не смог найти эффективное решение для веб-приложения.

Я получил 5 уровней, а не шесть

См. Здесь для моего сообщения группы Google есть решение для SQL и C #.

Примечание: , что вам следует поискать «алгоритм Дейкстры», поскольку это хороший алгоритм для поиска кратчайшего пути.

Редактировать: Попробуйте ссылку

КСТАТИ Метод CLR выполняется быстрее всего.