круги друзей

Sky_Flex · 17 Июн 2007

так. вот сделал Дейкстру, вроде...
т.е. находит вроде коэффициенты минимальных путей к вершине.
а как сами пути вытащить миимальные?

PHP:

	# ВЕРШИНЫ
	$M = array(1,1,1,1,1);
	# МАССИВ РАСМАТРИВАЕМЫХ СЕЙЧАС ВЕРШИН
	#$M1 = array();
	# МАССИВ ПРОЙДЕННЫЙ ВЕРШИН
	$M2 = array(0,0,0,0,0);
	# МАССИВ РАСТОЯНИЙ, ВНАЧАЛЕ ВСЕ БЕСКОНЕЧНОСТИ,КРОМЕ ПЕРВОГО
	$A = array(0,1000,1000,1000,1000);
	# МАТРИЦА СМЕЖНОСТИ
	$C =  array(
		# 			 -1-2-3-4-5-
				array(0,2,0,5,0), #-1-
				array(2,0,3,2,4), #-2-
				array(0,3,0,6,2), #-3-
				array(5,2,6,0,0), #-4-
				array(0,4,2,0,0));#-5-

	# количесвто вершин
	$n = sizeof($M);
	
	
	
while (array_key_exists(0, array_flip($M2))) {

	$min = $n - 1;
	
	# найдем минимальное растоянии
	for ($i=0; $i<$n; $i++)
		if (!$M2[$i] && $A[$i] <= $A[$min])
			$min = $i;
	$M2[$min] = 1;
	
	for ($i=0; $i<$n; $i++)
		if (!$M2[$i] && $C[$min][$i] && ($A[$i] > $A[$min] + $C[$min][$i]))
			$A[$i] = $A[$min] + $C[$min][$i];
}
			
	echo '<pre>';
		print_r ($A);
	echo '</pre>';

-~{}~ 17.06.07 17:20:

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

PHP:

	# ВЕРШИНЫ
	$M = array(1,2,3,4,5,6,7,8);
	# МАССИВ ПРОЙДЕННЫЙ ВЕРШИН
	$M2 = array(0,0,0,0,0,0,0,0);
	# МАССИВ РАСТОЯНИЙ, ВНАЧАЛЕ ВСЕ БЕСКОНЕЧНОСТИ,КРОМЕ ПЕРВОГО
	$A = array(0,1000,1000,1000,1000,1000,1000,1000);
	# МАТРИЦА СМЕЖНОСТИ
	$C =  array(
		# 			 -1-2-3-4-5-6-7-8
				array(0,2,0,5,0,0,0,0), #-1-
				array(2,0,3,2,4,7,0,0), #-2-
				array(0,3,0,6,2,3,0,0), #-3-
				array(5,2,6,0,0,0,1,0), #-4-
				array(0,4,2,0,0,0,0,9), #-5
				array(0,7,3,0,0,0,0,0), #-6-
				array(0,0,0,1,0,0,0,2), #-7-
				array(0,0,0,0,9,0,2,0));#-8

Румата · 17 Июн 2007

А теперь вопрос такой:почему ты решил для данной задачи применить именно Дейкстру? У тебя ведь между друзьями связи с точки зрения веса одинаковы. У тебя в начале будет матрица, в которой будут единички.

Sky_Flex · 17 Июн 2007

короче у меня матрица смежности построенна ошибочно ))

PHP:

 $C =  array( 
        #              -1-2-3-4-5-6-7-8 
                array(0,2,0,5,0,0,0,0), #-1- 
                array(2,0,3,0,4,7,0,0), #-2- 
                array(0,3,0,6,2,3,0,0), #-3- 
                array(5,0,6,0,0,0,1,0), #-4- 
                array(0,4,2,0,0,0,0,9), #-5 
                array(0,7,3,0,0,0,0,0), #-6- 
                array(0,0,0,1,0,0,0,2), #-7- 
                array(0,0,0,0,9,0,2,0));#-8

так что алгоритм работает.
насчет того что вес равен 1-чке это да... но пока делал уже подумал что можно внедрить веса (знакомый,друг,родственник и т.д.) и уже ранжировать по этим весам "эффективно"

но вот как выводить минимальный путь - чето не пойму...

Crazy · 17 Июн 2007

Sky_Flex, внедрять веса "знакомый", "родственник" и т.п. -- нельзя. Теперь в вузах теорию измерений вообще не читают?

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

Вот навскидку класс, вычисляющий 1-3 круги. Пользоваться им не нужно (почему не нужно -- это первый вопрос, на который тебе следует ответить). Показываю исключительно для понимания принципа:

Код:

class Linker {
             
  var $m_ids;
  var $m_linkedByIds;
  var $m_links1;
  var $m_links2;
  var $m_links3;

  function Linker() {
    $this->m_linkedByIds = array();
    $this->m_ids = array();
  }

  function links_for($id) {

    $this->m_links1 = array();
    $this->m_links2 = array();
    $this->m_links3 = array();

    $this->scan_ids($id, $this->m_links1);
    $this->scan_ids_array($this->m_links1, $this->m_links2);
    $this->scan_ids_array($this->m_links2, $this->m_links3);

    $this->m_links3 = array_diff_assoc($this->m_links3, $this->m_links2);
    $this->m_links3 = array_diff_assoc($this->m_links3, $this->m_links1);
    $this->m_links2 = array_diff_assoc($this->m_links2, $this->m_links1);
    unset($this->m_links2[$id]);
    unset($this->m_links3[$id]);

  }

  function scan_ids($targetId, &$found) {
    foreach(array_keys($this->m_ids) as $otherId) {
      if ($this->is_linked($targetId, $otherId)) {
        $found[$otherId] = true;
      }
    }
  }

  function scan_ids_array(&$targetIds, &$found) {
    foreach(array_keys($targetIds) as $targetId) {
      $this->scan_ids($targetId, $found);
    }
  }

  function & get1() {
    return $this->m_links1;
  }

  function & get2() {
    return $this->m_links2;
  }

  function & get3() {
    return $this->m_links3;
  }

  function _KEY($id1, $id2) {
    return "$id1:$id2";
  }

  function add_link($id1, $id2) {
    $this->m_ids[$id1] = true;
    $this->m_ids[$id2] = true;
    $this->m_linkedByIds[Linker::_KEY($id1, $id2)] = true;
    $this->m_linkedByIds[Linker::_KEY($id2, $id1)] = true;
  }

  function is_linked($id1, $id2) {
    return isset($this->m_linkedByIds[Linker::_KEY($id1, $id2)]);
  }

}

1. Регистрируешь связи.
2. Вызывавешь links_for($ТвойID);
3. Вызщываешь get1..get3.

Итак, вопрос: почему этим классом не следует пользоваться?

Sky_Flex · 17 Июн 2007

Итак, вопрос: почему этим классом не следует пользоваться?

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

Crazy · 17 Июн 2007

вообще говоря, класс написан из соображений максимальной понятности, а не максимальной скорости...

Sky_Flex · 17 Июн 2007

кстати, не втему, но:

PHP:

$this->m_links3 = array_diff_assoc($this->m_links3, $this->m_links2);
    $this->m_links3 = array_diff_assoc($this->m_links3, $this->m_links1);

можно было написать:

PHP:

$this->m_links3 = array_diff_assoc($this->m_links3, $this->m_links2, $this->m_links1);

смотрю дальше...

-~{}~ 17.06.07 18:36:

Sky_Flex, внедрять веса "знакомый", "родственник" и т.п. -- нельзя. Теперь в вузах теорию измерений вообще не читают?

а почему если не секрет?

Crazy · 17 Июн 2007

а почему если не секрет?

Простой вопрос: что больше: 7 друзей или 3 родственника? И почему.

Sky_Flex · 17 Июн 2007

ну да. сразу не пришло в голову.
а твой класс ищет по какому алгоритму 3 круга?

Crazy · 17 Июн 2007

Что значит "по какому алгоритму"? Исходник же перед тобой. Вроде как несложно посмотреть, где упоминается $this->m_links3.

Sky_Flex · 17 Июн 2007

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

Crazy · 17 Июн 2007

Начиная с какого места ты его не понимаешь?

Sky_Flex · 17 Июн 2007

я классы не понимаю, начну с этого.

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

Crazy · 17 Июн 2007

Дийкстру я обсуждать не буду, поскольку он тебе не нужен.

Пойдем по коду. Понятно, что делает эта функция?

Код:

function scan_ids($targetId, &$found) {
  foreach(array_keys($this->m_ids) as $otherId) {
    if ($this->is_linked($targetId, $otherId)) {
      $found[$otherId] = true;
    }
  }
}

Известно, что в $this->m_ids у нас ключами стоят все существующие ID. Функция is_linked возвращает true, если между парой указанных id есть непосредственная связь.

-~{}~ 17.06.07 20:41:

Автор оригинала: Sky_Flex
прошу помощи теперь только в алгоритме, программно реализую сам.

Легко.

Для каждого ID пользователя X:

1. Составить список1, включающий ID всех пользователей, связанных с X.
2. Составить список2, включющий ID всех пользователей, непосредственно связанных с пользователями из список1.
3. Составить список3, включющий ID всех пользователей, непосредственно связанных с пользователями из список2.
4. Вычесть список2 и список1 из список3.
5. Вычесть список1 из список2.
6. Вычасть X из всех трех списков.

Тривиально.

Реализовывать ТОЛЬКО на SQL. Не на PHP. Причина понятна?

Sky_Flex · 17 Июн 2007

Ну да - это мы получаем кто в каком круге путем вычитания списков, ок.

как вывести минимальный путь? от начального до конечного?

algo · 17 Июн 2007

На большом графе алгоритм Дейкстры в чистом виде - безумие, т.к он квадратичный.

Имхо, вариант через замыкание, и его вариации - правильнее всего.

Crazy · 17 Июн 2007

Автор оригинала: Sky_Flex
как вывести минимальный путь? от начального до конечного?

Путь куда? От начального ЧЕГО до конечного ЧЕГО?

-~{}~ 17.06.07 22:38:

Автор оригинала: algo
На большом графе алгоритм Дейкстры в чистом виде - безумие, т.к он квадратичный.

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

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

Sky_Flex · 17 Июн 2007

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

пытаюсь списки сейчас в sql-е вычитать... примерный путь решения подскажи.

Crazy · 17 Июн 2007

Еще раз. Медленно. Ты хотел алгоритм, формирующий списки друзей для 1-3 кругов. Я его тебе дал.

Откуда ты в нем взял какие-то пути?

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

Sky_Flex · 17 Июн 2007

с sql-разбираюсь, а насчет кругов, и то и то надо было...
вот цитата первого поста:

есть человек "А" и "Б", надо определить через кого знакомы.

круги друзей

Новичок

Новичок

Новичок

Developer

Новичок

Developer

Новичок

Developer

Новичок

Developer

Новичок

Developer

Новичок

Developer

Новичок

To the stars!

Developer

Новичок

Developer

Новичок