круги друзей

[Sky_Flex]

круги друзей

подскажите как организовывать круги друзей?!
т.е. у каждого пользователя есть определенные друзья на сайте (храняться в БД), у тех еще, а у тех в свою очередь еще и т.д....
как программно определить как связанны два различных человека, через какую цепочку "друзей" ?!?!
хотя все равно придеться перебирать наверно все возможные варианты, т.е. по каждому "другу" пока не наткнемся до искомого человека... но это наверно зверски рессурсоемко и долго....

а вот вариант например:
есть человек "А" и "Б", надо определить через кого знакомы.
сначала смотрим 1-й круг друзей "А", потом 1-й круг друзей "Б", ищем совпадения (т.е. может какой то друг одинаковый)... нет? тогда смотрим 2-й круг всех друзей "А", т.е. всех друзей друзей найденный в первом круге, так же смотрим 2-й круг друзей "Б", ищем совпадения... нет? тогда смотрим 3-й круг друзей у "А", 3-1 у "Б"...

Короче тоже ресурсоемко идолго - но лучше чемтупой перебор только со стороны "А" пока не найдем "Б"... хотя....

У КОГО КАКИЕ МЫСЛИ!?! делитесь!

 

[neko]

надо почитать про алгоритмы поиска кратчайшего пути в графе.
например алгоритм дейкстры или A*
ну и там другие еще есть.

 

[Sky_Flex]

ща погуглю....
а есть ссыли по теме?

 

[neko]

этим решениям уже по 50 лет примерно
ссылки какие-то специальные не требуются в данном случае.

 

[Sky_Flex]

может знаеш примеры на php?
нашел про этот алгоритм, идаже про некоторые другие по теме. Беллмана-Форда, Флойда-Уоршолла, Йена.
но скрипт на php - для лучшего понимания был бы супер!

 

[neko]

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

 

[Sky_Flex]

нашел очень подробное описание работы алгоритма...
http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
но... для работы алгоритма кроме "цены" каждого ребра графа (это можно еще селать, если связи разные: друг, знакомый, родственник... дать им разную цену, либо всем дать одинаковую цену и считать.)... короче жесть... ищем все кратчайшие пути во все вершины, причем в итоге находим не путь из "А" в "Б", а кратчайший пусть из "А" в "Б" = 22... и че?!
блин - короче я мало понял как это использовать...
может есть идеи? или покажите где глуплю...

 

[neko]

что именно непонятно?

 

[Sky_Flex]

непонятно что мне дает число это?
когда мне нужна цепочка через которую связь минимальна...

и... эфективен ли этот алгоритм... ?!
вот отрывок из найденого:


"Автор: SunComp
на С# и PHP
обе реализации показали не
очень хорошый результат по скорости
тестировал на базе с более 5000
клиентов и более 13000 связей между ними
в результате получил (на
P4(Prescott) 2.8Hz 512 RAM) время первого поиска (нахождения всех путей от
выбранной вершины к остальным) около 30 секунд"

может все таки есть еще варианты?

 

[neko]

непонятно что мне дает число это?
когда мне нужна цепочка через которую связь минимальна...

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

найди нормальное описание.
книгу возьми в библиотеке чтоли.

и... эфективен ли этот алгоритм... ?!

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

может все таки есть еще варианты?

да, навалом, ты сам несколько перечислил только что.

 

[Fally]

Если кратчайший путь тебе найти надо, то это "Алгоритм поиска в ширину" (или глубину)... Далее алгоритм дейкстры самый оптимальный, наряду с алгоритмом Форда-Беллмана.... (насколько я помню)

 

[neko]

да ладно "самый оптимальный"
этож насущная проблема, постоянно что-то пишут по этому поводу.

ну и еще раз -- от конфигурации графа очень многое зависит
тот же алгоритм дейкстры можно по разному реализовать.

 

[Sky_Flex]

Автор оригинала: neko
да ладно "самый оптимальный"
этож насущная проблема, постоянно что-то пишут по этому поводу.

ну и еще раз -- от конфигурации графа очень многое зависит
тот же алгоритм дейкстры можно по разному реализовать.

так если знаеш, подскажи как сконфигурировать оптимальнее и как оптимальнее реализовать его...

 

[neko]

предлагаю разобрать самостоятельно с любой реализацией
тем более что материала достаточно.

 

[Sky_Flex]

neko, отписал в личку.

 

[Wicked]

а почему бы для начала не сделать просто последовательность выборок:
select from friends as f1
select from friends as f1 inner join friends as f2
select from friends as f1 inner join friends as f2 inner join friends as f3
и т.д., до некоторого лимита, или до тех пор, пока не будет найден тот самый юзер?

 

[AmdY]

только where добавь

 

[Румата]

algolist.manual.ru - там посмотри. Кормена почитай еще.

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

При задании графа списком смежных вершин сложность алгоритма Дейкстры - О(n^2).

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

Sky_Flex
а можно нескоромный вопрос - а в институте такого не рассказывали?

 

[Sky_Flex]

а все таки, как на php осуществимть алгоритм Дейкстры

Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив S содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие рас- стояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний A[i,k] задает длины дуге A[i,k]; если такой дуги нет, то A[i,k] присваивается большое число Б, равное "машинной бесконечности".

1 (инициализация). В цикле от 1 до N заполнить нулями массив
S; заполнить числом i массив C; перенести i-ю строку матрицы
A в массив B,
   S[i]:=1; C[i]:=0 (i - номер стартовой вершины)
2 (общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для
которых S[k]=0); пусть минимум достигается на индексе j, т. е. B[j]<=B[k]
Затем выполняются следующие операции:
 S[j]:=1;
 если B[k] > B[j]+A[j,k], то (B[k]:=B[j]+A[j,k]; C[k]:=j)
(Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk).
(Если все S[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь
надо) перечислить вершины, входящие в кратчайший путь).
3 (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке
следующей процедурой)
3.1.  z:=C[k];
3.2.  Выдать z;
3.3.  z:=C[z]. Если z = О, то конец,
      иначе перейти к 3.2.

Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность: O(n2).

можно примеры массивов исходных?
не совсем потнимаю что это за массивы... S, B, C и что за матрица A.

 

[bkonst]

Если чтение из базы выполняется значительно чаще, чем изменение, желательно использовать транзитивное замыкание графа - не придется каждый раз при запросе запускать алгоритм поиска пути.