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

Ответ 1

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

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

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

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

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

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

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

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

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

Ответ 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] );

Ответ 3

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

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

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

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

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

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

• Directed vs Undirected
• Типы/отношения края
• Атрибуты, такие как вес ребер

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

Ответ 4

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

EDIT. В приведенном выше решении я изначально забыл исключить пользователей уже в таблице temp #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

Ответ 5

Следующие сценарии написаны в sybase sql. Возможно, вам придется пройти незначительные изменения в соответствии с вашим сервером db.

Задача 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

Ответ 6

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

Я закончил с 5 уровнями, а не с шестью

См. здесь сообщение google group, есть SQL и С# решение.

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

Изменить: Попробуйте ссылка

BTW Самый быстрый метод CLR.

Ответ 7

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

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

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

для dijkstra и один в python для DFS:

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

Ответ 8

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

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

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

Ответ 9

(Этот ответ эквивалентен Djikstra's. Это в основном деталь реализации.)

Чтобы ответить на # 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 для добавления:

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

Ответ 10

Google, и вы найдете много.

Я сомневаюсь, что вы можете найти псевдокод (по крайней мере, мне еще нужно). Вот некоторые из интересных замечаний:

"Шесть степеней разделения" , объясненных в новом алгоритме компьютера
Ученый-компьютер CU помогает объяснить, как работает "шесть степеней разделения" SO - Как я могу доказать концепцию "Six Degrees of Separation" программно?

Ответ 11

Я отвечаю только на SQL-решение. Это дает все пути в 3 шага, хотя это может быть не "эффективно" для больших наборов данных. Таблицы "KNOW", "KNOW_1" и т.д. Идентичны и имеют два поля P1 и P2. Он имеет запись только в том случае, если 1) P1 знает P2 или 2) P2 знает P1. Данные в P1 и P2 могут быть произвольными строками, соответствующими каждому человеку.

В этом SQL-запросе Acccess должны быть указаны все пути, в которых известно, что b знает c знает d без циклов (например, знает, знает ли b знает c знает a). Вам по-прежнему необходимо устранить дубликаты (abcd = dcba), но они должны быть в состоянии сделать это легко на втором шаге. Циклы устраняются путем предотвращения повторений предыдущих людей в инструкциях Where.

SELECT Know.P1, Know.P2, Know_1.P2, Know_2.P2

FROM (Знать ВНУТРЕННЕЙ ВЕЩЬ Знать AS Know_1 ON Know.P2 = Know_1.P1)

INNER JOIN Знать AS Know_2 ON Know_1.P2 = Know_2.P1

WHERE (((Know_1.P2) < > [Знать]. [P1]) AND ((Know_2.P2) < > [Знать]. [P1] И (Know_2.P2) < > [Знать ]. [P2]))

ЗАКАЗ BY Know.P1, Know.P2, Know_1.P2, Know_2.P2;

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