VPF::находнение всех путей в графе - Форум программистов

xber9

Дата 31.10.2012, 13:44 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

народ привет
не знаю насколько вопрос подходит теме (если что перенесет)
и так есть граф описывающий метрополитен Москвы
и функция которая ищет минимальный путь от а до б

Код


    <?php 
    // определяем граф
    $graph = array(
    //зеленая ветка
    //рречной  - водный стадион 
      55  => array(60),
    //  водныфй -(речной, войковская) 
      60  => array(55,74),
    //войковская =(водныйб сокол)
      74  => array(60,75),
    //сокол-( войковский аэропорт)
      75  => array(74,76),
      //  аэропоорт -(сокол динамо)
      76  => array(75,62),
// динамо - (аэропорт , белорусская)
      62  => array(76,63),
      //БЕЛОРУССКАЯ зеленая-( БЕЛОРУССКАЯ кольц, ДИНАМО, маяковская)
     63  => array(153,62,47),
//маяковского -(белоруская зеленая,  тверская)
    47  => array(63,48),
    // тверская-( маяковского, пушкинская, чеховская, театральная)
     48  => array(47,52,53, 152),
    // театральная-(тверская, охотный,пл революции,новокузнецувя )
     152  => array(48,44,24,34),
         //новокущнецкая-(театравльныя,  третьявка желтая и отрна, повелецкая зеленая,) 
          34  => array(152,33,164, 31),
      //повелецкая зеленая-(новокущнецкая, повелекая кольцвая, автозаводская)
          31  => array(34,32,18),
          //автозаводская-( повелецкая зеленая, коломеннская)
          18  => array(31,113),
          //коломеннская-(автозаводская, каширская зененая)
          113 => array(18,114),
//каширская зененая -(коломеннская, кашрская голубая, кантимировкская) 
          114 => array(113,154, 147),
          //кантимировкская-(каширская зененая, царицкно)
          147 => array(114,150),
          //ЦРИЦКНО -(кантимировкска,  орехово)
          150 => array(147,148),
          //орехово-( царицено домодедовская)
          148 => array(150,151),
          //домодедовская-*(орехово, красногвыардейская)
          151 => array(148,149),
          //красногвыардейская-домодедовская
          149 => array(151),
          
    //серая ветка      
    //алтуфьево -( биберево)
          59 => array(58),
          //биберево -(алтуфьево, отрадное)
          58 => array(59,57),
    //отрадное -(биберево, владыкино)
              57 => array(58,73),
              //владыкино-(отрадное, петровско-разумовское) 
              73 => array(57,69),
              //петровско-разумовское-( владыкино, темарязевскач)
              69 => array(73,71),
              //темерязв -(петровско-разумовское, дмировская)
              71 => array(69,70),
//дмтровская -(темерзычув, савеловская
    70 => array(71,72),
    //савеловская-(дмитровка, менделева)
    72 => array(70,10),
 // менделевская-(савеловская,новослободская, цветной бульвар)
    10 => array(72,7,54),
    ///цветной бульвар -( меднелевскаЯ, чеховсекая)
    54 => array(10,53),
    //чеховская -(цветной, тверская,пушкниская, борровитсякая)  
    53 => array(54,48,52, 42),
    
     
     //кольцквая
      //БЕЛОРУССКАЯ кольц-(БЕЛОРУССКАЯ зеленая  новослободская, краснопреснч)
     153  => array(63,7, 61),
     //новослоболская -( мендеевская, БЕЛОРУССКАЯ кольц, проспект мира кольц )
     7  => array(10,153, 6),
     
     //повелекая кольцвая-(повелекая зеленая, таганка кольцевая, добрыненская
     32=>array(31,30, 17),


     // глубая ветка
//кашрская голубая-(кашрская зеленая, варшавская(
    154=>array(114,92)
      // ................................................
    );

   
   
    function find_path($graph, $start, $end, $path)
    {
      $path[] = $start;
      
      if ($start == $end)
         return $path;
      
      if (!isset($graph[$start]))
         return false;
      
      $shortest = array();

      foreach($graph[$start] as $node) {
   if (!in_array($node, $path)) {
     $newpath = find_path($graph, $node, $end, $path);
     if ($newpath) {
       if (!$shortest || (count($newpath) < count($shortest)))
         $shortest = $newpath;
     }   
   }
      }
      return $shortest;
    }
    if (isset($_GET['from']) && isset($_GET['to'])) 
    {
      if (in_array($_GET['from'], array_keys($graph)) &&  in_array($_GET['to'], array_keys($graph))) 
      {
    
     $shortestPath = find_path($graph, $_GET['from'], $_GET['to'],null);

$out='{"routes":{"from":"'.$_GET['from'].'","to":"'.$_GET['to'].'","time":16,"transfers":1,"waypoints":[';

//     echo($out);
     foreach($shortestPath as $station) {

$out.='"'.$station.'",';
     }
$out=substr($out, 0, strlen($out)-1);     
     $out.=']}}';
     echo($out);
      } else { 
   echo(' 400');
       }
      } ?>

я понимаю что эта функция  ищет  минимальное расстояние в зависимости от количества пройденных точек
но мне нужно  чтобы она искала  ни минимальный путь,  а  путь с минимумом  пересадок с ветки на ветку
я вижу это так, что сначала мне надо  получить все возможные пути из А в Б  а потом их проверять на наличие пересадок

как проверять я себе тоже представляю (сделать массив с пересадками и проверять соответствия )
но как заставить мою функцию вернуть все  возможные пути я не знаю

помогите изменить функцию чтобы она возвращала все возможные пути от А  в Б
заранее спасибо smile

skyboy

Дата 31.10.2012, 18:15 (ссылка)

(нет голосов)

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 1
Всего: 260

если опишешь, как в настоящий момент находишь минимальный путь(название алгоритма, или словесное описание), перенесу в раздел "Алгоритмы"

xber9

Дата 1.11.2012, 12:53 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Алгоритмы можно вкратце описать так: для вершины, которую мы еще не посетили, нужно отыскать все еще не посещенные смежные вершины и повторить поиск для них
то есть поиск в глубину

skyboy

Дата 1.11.2012, 15:49 (ссылка)

(нет голосов)

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 1
Всего: 260

тебе надо кастомизировать алгоритм добавлением весов.
то есть, вместо

Цитата

count($newpath) < count($shortest)

использовать

Код


path_length($newpath) < path_length($shortest)

а path_length для станции на той же ветке добавляет +1, а для станции другой ветки(пересадка) — скажем, +3.

xber9

Дата 1.11.2012, 17:51 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(skyboy @ 1.11.2012, 15:49

)

а path_length для станции на той же ветке добавляет +1, а для станции другой ветки(пересадка) — скажем, +3.

бррр что то не соображу как будет path_length выглядить и как записывать данные о весе
для меня это все в новинку так что сори что сразу не впиливаю)

baldina

Дата 1.11.2012, 18:06 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

Цитата(xber9 @ 1.11.2012, 12:53

)

то есть поиск в глубину

поищи в ширину. погляди алгоритм Дейкстры

xber9

Дата 1.11.2012, 19:08 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(baldina @ 1.11.2012, 18:06

)

поищи в ширину. погляди алгоритм Дейкстры

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

а как все это интерпритировать в матрицу смежности не знаю

skyboy

Дата 1.11.2012, 20:58 (ссылка)

(нет голосов)

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 1
Всего: 260

Цитата(xber9 @ 1.11.2012, 16:51

)

бррр что то не соображу как будет path_length выглядить и как записывать данные о весе

во-первых, тебе нужно решить, какой вес будет у пересадки. то есть, начиная с какого количества "проехать лишние N станция без пересадок" предпочтительнее, чем совершить одну пересадку и не ехать эти самые N станций.
во-вторых, count($newpath) — это простейший алгоритм рассчета "длины пути" — каждая станция считается за единицу. чем больше станций — тем больше сумма — тем больше длина. я ж предлагаю вместо count использовать самописную функцию, которая для заданного списка станций будет увеличивать значение длины пути на 1 для каждой станции, кроме пересадочных. А для станций пересадки — увеличивать сразу на N.

xber9

Дата 1.11.2012, 21:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(skyboy @ 1.11.2012, 20:58

)

во-вторых, count($newpath) — это простейший алгоритм рассчета "длины пути" — каждая станция считается за единицу. чем больше станций — тем больше сумма — тем больше длина. я ж предлагаю вместо count использовать самописную функцию, которая для заданного списка станций будет увеличивать значение длины пути на 1 для каждой станции, кроме пересадочных. А для станций пересадки — увеличивать сразу на N.

то есть мне надо сделать массив в котором будут все id станций с которых можно сделать пересадку
"самописная" функция принимает в себя массив точек и для каждой из них проверяет принадлежит ли она массиву пересадок
если принадлежит то возвращаемое значение увеличивается на какое то большое число
если нет то увеличивается на 1

я правельно понимаю или что то не так

baldina

Дата 1.11.2012, 22:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

Цитата(xber9 @ 1.11.2012, 19:08

)

но е понял как можно реализовать чтобы использовать такую запись данных как уменя

у тебя списки смежности. все реализуемо.

Добавлено через 1 минуту и 18 секунд

Цитата(xber9 @ 1.11.2012, 19:08

)

ибо данные уже готовы

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

Добавлено через 5 минут и 23 секунды

Цитата(baldina @ 1.11.2012, 22:52

)

у тебя списки смежности

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

xber9

Дата 1.11.2012, 23:33 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(baldina @ 1.11.2012, 22:52

)

поглядел, вижу что не прав. но все равно реализуемо.

переделывать в матрицу не времени так что придктся юзать глубину

baldina

Дата 2.11.2012, 08:59 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

Цитата(xber9 @ 1.11.2012, 23:33

)

переделывать в матрицу не времени так что придктся юзать глубину

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

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

xber9

Дата 2.11.2012, 13:04 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(baldina @ 2.11.2012, 08:59

)

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

смотрел вчера на вики реализацию на псевдокоде
но моих мозгов не хватает чтобы понять как это померкнуть на php и использовать свои списки (нашел 1 реализацию на javasctript которую можно на php перекинуть но там матрица
так что я в тупике
увы

Это сообщение отредактировал(а) xber9 - 2.11.2012, 14:35

xber9

Дата 2.11.2012, 15:44 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

вот та самая функция переведенная на пхп
а как ее для моих данных адаптировать?

Код


    

//---------------------------------------------------------------------------
//Алгоритм Дейкстры.поиска кратчайшего пути
function fin($s, $g){
$v;

  $VERTEXES =6;

   $infinity=1000;                     // Бесконечность

   $p= $VERTEXES;             // Количество вершин в графе
   $a=array(                   array(0,1,0,0,1,3),  
                               array(1,0,5,0,0,1),
                               array(0,5,0,5,20,1),
                               array(0,0,5,0,3,2),
                               array(1,0,20,3,0,10),
                               array(3,1,1,2,10,0)
                                );
 
   // Будем искать путь из вершины s в вершину g
   // s;                   // Номер исходной вершины
   // g;                   // Номер конечной вершины
   $x=array(); //Массив, содержащий единицы и нули для каждой вершины,
                  // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                  // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   $t= array();  //t[i] - длина кратчайшего пути от вершины s в i
   $h=array();  //h[i] - вершина, предшествующая i-й вершине
                 // на кратчайшем пути
 
   // Инициализируем начальные значения массивов
   $u;        // Счетчик вершин
   for ($u=0; $u < $p; $u++)
   {
      $t[$u]=$infinity; //Сначала все кратчайшие пути из s в i 
    //равны бесконечности
      $x[$u]=0;        // и нет кратчайшего пути ни для одной вершины
   }
   $h[$s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
   $t[$s]=0; // Кратчайший путь из s в s равен 0
   $x[$s]=1; // Для вершины s найден кратчайший путь
   $v=$s;    // Делаем s текущей вершиной
   
   while(1)
   {
      // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
      for($u=0;$u < $p;$u++)
      {
         if($a[$v][$u]==0)continue; // Вершины u и v несмежные
         if($x[$u]==0 && $t[$u]>$t[$v]+$a[$v][$u]) //Если для вершины u еще не 
    //найден кратчайший путь
                // и новый путь в u короче чем 
    //старый, то
         {
            $t[$u]=$t[$v]+$a[$v][$u];  //запоминаем более короткую длину пути в
    //массив t и
            $h[$u]=$v; //запоминаем, что v->u часть кратчайшего 
    //пути из s->u
         }
      }
 
      // Ищем из всех длин некратчайших путей самый короткий
      $w=$infinity;  // Для поиска самого короткого пути
      $v=-1;            // В конце поиска v - вершина, в которую будет 
                       // найден новый кратчайший путь. Она станет 
                       // текущей вершиной
      for($u=0;$u < $p; $u++) // Перебираем все вершины.
      {
         if($x[$u]==0 && $t[$u]< $w) // Если для вершины не найден кратчайший 
                               // путь и если длина пути в вершину u меньше
                               // уже найденной, то
         {
            $v=$u; // текущей вершиной становится u-я вершина
            $w=$t[$u];
         }
      }
      if($v==-1)
      {
        echo( "Нет пути из вершины ".$s." в вершину ".$g.".");
         break;
      }
      if($v==$g) // Найден кратчайший путь,
      {        // выводим его
         echo("Кратчайший путь из вершины ".$s." в вершину ".$g.":");
       $u=$g;
       while($u!=$s)
         {
            echo(" ".$u);
            $u=$h[$u];
         }
         echo(" ".$s.". Длина пути - ".$t[$g]);
       break;
      }
      $x[$v]=1;
   }
}
/*Программа запрашивает вершины s и q и выводит кратчайший путь. Например, после ввода s = 3, q = 6, программа выводит 
 
Нет пути из вершины 3 в вершину 6. 
 
После ввода s = 0, q = 2 программа выводит 
 
Кратчайший путь из вершины 0 в вершину 2: 2 5 1 0. Длина пути = 3.*/
 
//---------------------------------------------------------------------------

Это сообщение отредактировал(а) xber9 - 2.11.2012, 15:47

Aliance

Дата 2.11.2012, 18:04 (ссылка)

(нет голосов)

Загрузка ...

I ♥ <script>

Профиль
Группа: Модератор
Сообщений: 6418
Регистрация: 2.8.2004
Где: spb

Репутация: нет
Всего: 137

называть переменные $v, $w, $u и т.п. - мощно.

--------------------

• Все о событиях
• Объекты и массивы
• ОКНА И ФРЕЙМЫ

JAVA ≠ JavaScript

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| PHP: Для профи \| Следующая тема »

Внимание: данный раздел предназначен для решения сложных, нестандартных задач.