Задача, как реализовать алгоритм для шести степеней разделения?
UserA-UserB-UserC-UserD-UserF
Пользователи, связанные знаком "-", знают друг друга.
И мне нужен алгоритм для этих 2 задач:
- Рассчитать путь от UserX до UserY
- Для UserX рассчитайте всех пользователей, которые находятся на расстоянии не более 3 шагов.
Есть ли эффективное решение?
РЕДАКТИРОВАТЬ
Моя цель не в том, чтобы доказать, что это правильно или неправильно, а в том, чтобы вычислять результат в реальном времени, когда это необходимо.
Кроме того, я думаю, что самый выразительный способ - это код, даже псевдо.
ИЗМЕНИТЬ СНОВА
Я решил, что такая работа должна выполняться внутри базы данных, поэтому это должно быть решение SQL!
12 ответов
Представьте этот список пользователей графиком
- Каждый пользователь является узлом
- Между любыми двумя пользователями, которые знают друг друга, есть грань
- Рассчитать путь от UserX до UserY
- Для UserX рассчитайте всех пользователей, которые находятся на расстоянии не более 3 шагов.
Эти вопросы настолько тесно связаны, что один и тот же алгоритм фактически решает оба из них. Вы можете назвать это "алгоритмом Дейкстры со всеми ребрами, имеющими вес 1", или "поиск в ширину".
По сути, начиная с первого узла, посетите всех его родственников; затем отметьте их как посещенные, запишите кратчайший путь к каждому (кратчайший путь к ним + край, который вы только что прошли), и повторите для каждого из них. Остановитесь после того, как вы достигли пункта назначения для Задачи № 1, остановитесь после того, как кратчайший путь> 3 для Проблемы № 2.
Это будет выполнено за O(n) раз. Нет, более быстрого пути нет.
Самый быстрый алгоритм O(n) для шести степеней разделения, вероятно, будет находить наборы всех пользователей на расстоянии одного шага от UserX и UserY и находить пересечение этих двух наборов. Если нет, то добавьте пользователей в 2 шагах от UserX и пересекайте; затем добавьте пользователей в 2 шагах от UserY и пересекайте; и т. д. до 3.
Если у каждого человека есть в среднем 100 друзей, для этого может потребоваться около 2020,2 тыс. Пользователей, в отличие от 1,010 млрд. Для алгоритма Дейкстры. На практике эти цифры будут намного меньше, так как часто два ваших друга также дружат друг с другом.
Это единственный метод решения шести ступеней разделения (из упомянутых выше), который будет работать на практике.
График алгоритмы могут помочь вам здесь. Узнать о них тоже весело!
- График подключения для подключения.
- Дейкстра (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] );
Предполагая, что исходные данные находятся в таблице: Соединения: (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
У меня есть предложение, которое сильно отличается от тех, которые у вас уже есть. Если вам нужно придерживаться базы данных SQL, и вы не знаете Java, это предложение не будет иметь большого смысла.
Ваша проблема - это, в частности, проблема с графиком, поэтому я хотел бы предположить, что, хотя база данных SQL для хранения графика будет работать, другой подход будет заключаться в использовании решения, предназначенного специально для задач с графами.
Проект Neo4j предоставляет базу данных графов на основе диска, вместе с ней будет работать множество графовых алгоритмов. Цитата:
Neo4j - это графическая база данных. Это встроенный дисковый полностью транзакционный движок Java, который хранит данные, структурированные в виде графиков, а не таблиц. График (математический жаргон для сети) - это гибкая структура данных, которая обеспечивает более гибкий и быстрый стиль разработки.
Соответствующий пример использования Neo4j в их вики демонстрирует веб-приложение со степенью разделения, использующее данные IMDB. Пример иллюстрирует вычисления кратчайшего пути между любым актером и Кевином Бэконом.
Мне нравится этот пример, так как он много говорит о моделировании области, которую будет представлять ваш график. Моделирование вашего домена гарантирует, что вы подумали о таких вещах, как:
- Направленный против Ненаправленный
- Типы кромок / отношения
- Атрибуты, такие как веса ребер
Как уже упоминалось в других статьях, существует ряд алгоритмов для вычисления кратчайших путей, таких как Dijkstra, Floyd Warshall или BFS. Все это было реализовано в Neo4j, и некоторые примеры приведены здесь.
Следующие скрипты написаны на 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
(Этот ответ эквивалентен ответу Джикстры. Это в основном детали реализации.)
Чтобы ответить на вопрос № 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 для добавления:
Вы можете оптимизировать это много, делая умножение только для записей, которые ранее были ложными, а также понимая, что матрица симметрична. Это оставлено в качестве упражнения для читателя.
Для задачи 2 вы не добьетесь большего успеха, чем поиск в ширину, за исключением, может быть, кэширования.
Для задачи 1 примените свое решение для задачи 2. Найдите всех пользователей на расстоянии не более 3 прыжков от пользователя X. Конечно, если пользователь Y находится в этом наборе, все готово. Если нет, выполните поиск в ширину, начиная с пользователя Y, и остановитесь, как только вы достигнете любого пользователя, о котором вы уже знаете, что он доступен из X.
(Если вы кешируете небольшую информацию о том, как вы достигли каждого пользователя во время задачи 2, вам будет легко восстановить точный путь, когда вы найдете ссылку в задаче 1.)
На самом деле есть достаточно эффективный способ сделать это с 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
Я взглянул на это некоторое время назад и не смог найти эффективного решения для веб-приложения.
Я получил 5 уровней, а не шесть
Смотрите здесь для моего сообщения группы Google есть решение SQL и C#.
Обратите внимание: вам следует поискать "алгоритм Дейкстры", так как он известен как хороший алгоритм для поиска кратчайшего пути.
Изменить: Попробуйте эту ссылку
Кстати, метод CLR выполняется быстрее всего.
Первый вопрос можно решить с помощью алгоритма Дейкстры. Второй по использованию алгоритма DFS. Об этом уже говорили другие ребята, просто хотели отметить, что наиболее эффективное решение для обеих проблем не доступно в одном алгоритме.
псевдокод можно найти по адресу:
[Википедия][1]
для дейкстра и один в питоне для DFS по адресу:
Я отвечаю только на решение SQL. Это дает всем путям 3 шага, хотя это не может быть "эффективным" для больших наборов данных. Таблицы "ЗНАТЬ", "ЗНАТЬ_1" и т. Д. Все идентичны и имеют два поля P1 и P2. Он имеет запись, только если 1) P1 знает P2 или 2) P2 знает P1. Данные в P1 и P2 могут быть произвольными строками, соответствующими каждому человеку.
Этот SQL-запрос Acccess должен дать все пути, где a знает, что b знает, что знает, d знает без циклов (например, a знает, что b знает, что знает, знает a). Вам все еще нужно удалить дубликаты (abcd = dcba), но вы сможете легко это сделать на втором этапе. Циклы устраняются путем предотвращения повторений предыдущих людей в выражениях Where.
ВЫБЕРИТЕ Know.P1, Know.P2, Know_1.P2, Know_2.P2
ИЗ (ЗНАЙТЕ ВНУТРЕННЕЕ СОЕДИНЕНИЕ ЗНАЙТЕ КАК ЗНАЕТЕ_1 ПО ЗНАЮ
ВНУТРЕННЕЕ СОЕДИНЕНИЕ ЗНАЙТЕ КАК ЗНАЕТЕ_2 ВКЛ
ГДЕ (((Know_1.P2)<>[Know].[P1]) И ((Know_2.P2)<>[Know].[P1] И (Know_2.P2)<>[Know].[P2]))
ЗАКАЗАТЬ ПО ЗНАЮ.P1, Знать.P2, Знать_1.P2, Знать_2.P2;
Не так элегантно, как предыдущие решения, но, похоже, работает нормально. У нас был некоторый опыт выполнения аналогичной работы с программированием ограничений и мы обнаружили, что процесс SQL быстрее для определенных проблем.
Google это, и вы найдете много.
Я сомневаюсь, что вы можете найти псевдокод (по крайней мере, я пока не нашел). Вот некоторые из интересных чтений:
"Шесть степеней разделения" объяснены в новом компьютерном алгоритме
CU ученый помогает объяснить, как работает "шесть степеней разделения"
ТАК - Как я могу доказать концепцию "шести степеней разделения" программно?