ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitry Volkov                        2:5015/185.5   12 Jun 2002  10:41:45
 To : All
 Subject : FAQ "Алгоритмы на графах" [3/4]
 -------------------------------------------------------------------------------- 
 

   * 8.1. Постановка задачи. * 
 
     Дан взвешенный орграф G=(V, E), веса дуг записаны в матрице смежности A 
  (причем, если i и j не связаны дугой, то A[i, j] = +oo ).
     Даны две вершины - s и t. Путь между s и t оценивается суммой весов дуг.
     Hайти путь с минимальной оценкой ( _кратчайший путь_ ).
 
   * Решение *
 
     Разобьем  задачу  на две  подзадачи: поиск  самого пути  и  поиск веса 
  кратчайшего пути. Обозначим последний как D[s, t].
     Определим D как *array[1..n] of Integer*, где D[i]-оценка пути от вершины 
  s до вершины i графа.
     Предположим, что мы нашли D, т.е. решили 2-ую подзадачу.
 
   * 8.2. Построение самого пути *
 
     Тогда найти сам путь просто: 
 
     _Реализация:_
      Function Way (s, t : integer) : integer;
      Var v, u, l : integer;
      Begin
        Path[1] := t;   v := t;    l := 1;
        While v <> s do begin
          u := < номер вершины, для которой d[v] = d[u] + a[u,v] >
          inc(l);   Path[l] := v;   v := u;
        End;       
        Way := l;
      End;
 
     Теперь в массиве Path - перевернутый путь длины L.
     Как решить 2-ую подзадачу? Воспользуемся след. алгоритмом:
 
 [...]
 // Алгоритм Форда-Беллмана - планируется  в будующей версии //
 [...]
 
   * 8.3. Алгоритм Дейкстры (Дийкстры) *
 
     _Сложность :_ O( n^2 ).
     _Область применения:_ ориентированный граф без дуг с отрицательным весом.
     _Идея      :_ Hа каждом шаге пытаемся уменьшить кратчайшее расстояние до 
  непросмотренных вершин, используя очередную вершину, длину пути к которой
  уменьшить уже нельзя.
 
     _Реализация:_
         Procedure Deykstra( s : integer );
         Var v, u : integer; 
             t : set of 1..N;
         Begin
           For v :=1 To N Do D[v] := A[s, v];
           d[s] := o; t:= [1..N]-[s];
           While T<>[] Do Begin
             u := <принадлежащая T вершина, у которой минимальное D[u]>;
             T := T - [u];
             For v := 1 to n do
               If v in T Then            { min(a,b) - ваша функция }
                 d[v] := min (d[v], d[u] + a[u,v] ); 
           End;
         End;
 
   * 8.3.1.  _Доказательство верности алгоритма:_*
 
     Hа  каждом шаге мы выбераем  еще  непомеченную  вершину L,  у  которой 
  наименьшая из непомеченных длина пути и  пытаемся из нее с помощью ее дуг 
  уменьшить длину пути до оставшихся вершин.
     Очевидно, длину пути до тех пунктов, которые уже просмотрены, уменьшить
  нельзя  (действительно, для всех i (где i - пункт, который уже промотрен)
  _D[i] < D[L] + NewPath[i, L]_, т.к. _D[i] < D[L]_ - по алгоритму, а все дуги 
  имеют неотрицательный вес ).
     Далее,  предположим  для выбранной вершины  длина  пути  не минимальна. 
  Тогда  существует путь с  суммарным весом меньше, чем D[I]. Обозначим за 
  J - предпоследний пункт в этом пути. Получили, что:
     _D[I] > D[J] + A[I, J]_ - противоречие из-за неправильного предположения.
 
   * 8.4. Пути в бесконтурном графе *
 
     Дан орграф без циклов(контуров), веса произвольны.
     _Утверждение_. В произвольном  бесконтурном   графе   вершины    можно 
  перенумеровать так, что для каждой дуги (i, j) номер вершины i < номера j.
     _Алгоритм._ Для каждой вершины подсчитываем - сколько у нее входящих дуг.
  Hа  каждом шаге выбераем  вершину с нулевым  количеством  "входящих"  дуг, 
  присваиваем  ей  очередной номер и "удаляем" дуги,  выходящие  из  нее - в
  данном случае, уменьшаем кол-во "входящих" дуг у соответствующих вершин.
     _Сложность  :_ O( n^2 ).
 
     Теперь можем вычислить за O(n^2)кратчайшие расстояния от первой вершины: 
     _Реализация :_
 
          Procedure NoSidebar;
          Var i, j : integer;
          Begin 
            d[1] := 0;
            For i := 2 To n Do d[i] := MaxNumber;
            For i := 2 To n Do 
              For j:=1 To i-1 Do 
                If A[j, i] <> MaxNumber Then
                  D[j] := min( d[i], d[j] + a[j,i] );       
          End;
 
   * 8.5. Кратчайшие пути между всеми парами вершин *
 
     * Алгоритм Флойда *
     _Сложность:_ O( n^3 ).
     _Область применения:_ ориентированный граф без дуг с отрицательным весом.
     _Идея     :_ Пусть  D[k, i, j] - длина кратчайшего пути  из  i  в  j  с 
  промежуточными вершинами из множества [1..k].
                  M[i, j] - предпоследняя вершина кратчайшего пути из i в j.
     Предположим, что D[0] = A ( т.е. D[0, i, j] = a[i, j] для всех i, j )
     Cправедлива формула:
         _D[k+1, i, j] = min (D[k, i, j], D[k, i, k+1] + D[k, k+1, j] )_
         (нужно не забывать менять M[i, j] !)
     Тогда нам нужно найти D[n].     
     _Реализация :_
          Procedure Floyd;
          Var m, i, j : integer;
          Begin 
            For i := 1 To n Do 
              For j := 1 To n Do  Begin
                D[i, j] := A[, j];  M[i,j] := i;
              End;       
            For i := 1 To n Do d[i, i] := 0;
            For m := 1 To n Do
              For i := 1 To n Do 
                For j := 1 To n Do 
                  If D[i, j] > D[i, m] + D[m, j] Then Begin
                    M[i, j] := M[m, j];
                    D[i, j] := D[i, m] + D[m, j];                  
                  End;
          End;
 
 [...]
 // Hезависимые, доминирующие множества, раскраски                //
 //              - планируется в будующей версии                  //
 [...] 
 
 * 9. Потоки в сетях. *
 
 Q:> * 9.1. Задача. * 
 
     Определить максимальный поток, протекающего  от  вершины-источника  s 
  орграфа к вершине-стоку t. При этом каждой дуге *(i, j)* орграфа приписана 
  _пропускная способность_ *c[i, j]* определяющая максимальное значение  потока,
  протекающего по этой дуге.
 
 A:> (по *[1]* )
 
    * 9.2. Теорема Форда-Фалкерсона*
 
     _Разрез_ - множество дуг,удаление которых приводит к разрыву всех путей из
  s в t.
     _Пропускная способность разреза_ - суммарная пропускная способность дуг его
  составляющих.
     Справедлива следующая
     *Теорема  Форда-Фалкерсона*. Величина каждого потока  из  s  в  t   не 
  превосходит пропускной способности минимального разреза,разделяющего s и t,
  причем существует поток, достигающий этого значения.
     Т.о. задачи нахождения макс. потока и мин. разреза эквивалентны.
 
    * 9.3. Решение. *
 
     *"Техника меток" Форда и Фалкерсона*   заключается  в  последовательном
  (итерационном)  построении макс. потока путем  поиска  на   каждом  шаге 
  увеличивающейся цепи,т.е. пути, поток по которому можно увеличить. Ее суть:
     - на каждой итерации вершины могут находиться в одном из трех состояний:
          * вершине присвоена метка и она просмотрена; 
          * присвоена метка, но не промотрена;
          * вершина не имеет метки
     - на каждой итерации мы выбираем помеченную,но не просмотренную вершину
  v и пытаемся найти непомеченную вершину u, причем (u, v) принадлежит E.
     - помеченные вершины образуют множество вершин G,достижимых из источника.
  Если среди них есть сток, то мы нашли цепочку,  увеличивающую  поток,  при 
  неизменности потока - конец работы.
     Подробнее о потоках см. *[4]* .
 
     _Реализация :_ ( не лучший вариант! )
 
  Var c    ,      { пропускная способность }
      f           { поток }
           : array [1..n, 1..n] of integer; 
      p    : array [1..n, 1..2] of integer; { для хранения меток }
  { p[i, 1] - номер вершины, из которой можно поток p[i,2] переместить в i }
      Lg   : boolean; { нашли цепоцку? }
      s, t : integer; { источник и сток  }
  { основная программа }
  Begin 
    < Ввод данных >
    Lg := True;
    While Lg Do Begin
      FillChar(P, SizeOf(P), 0);
      Mark;
      If Lg Then Stream;
    End; 
  End.
 
 { _процедура расстановки меток_
   если вершину t не смогли пометить, то Lg := false; Результат работы - P }
  Procedure Mark;
  Var M    : set of 1..MaxN;
      i, l : integer;
  Begin
    M := [1..N]; {непросмотренные вершины} 
    P[s, 1] := s; P[s, 2] := MaxInt; { присвоим метку вершине-источнику }
    l := s;
    While (P[t, 1] = 0){до стока не дошли} And Lg{цепочки есть} Do Begin
      For i := 1 to N Do  { поиск непомеченной вершины }
        If (P[i, 1] = 0) And ( (C[l, i]<>0) or (C[i,l]<>0) )  Then
          If F[l, i] < C[l, i] Then Begin { дуга прямая }
            P[i, 1] :=  l;
            If P[l, 2] < C[l, i] - F[l, i] Then P[i, 2] := P[l,2]
                                           Else P[i, 2] := C[l, i]-F[l, i];
          End Else If F[i, 1] > 0 Then Begin { дуга обратная }
            P[i, 1] := -l;
            If P[l, 2]< F[i, 1] Then P[i, 2] := P[l, 2]
                                Else P[i, 2] := F[i, l];  
          End;
      M := M - [l];   { вершина l просмотрена } 
      l:=1; { находим помеченную и непросмотренную вершину }
      Repeat 
        Inc(l);
      Until (l>n)  Or ((P[l, 1]<>0) And (l In M));
      If l>n then Lg := False; { не нашли }
    End;
  End;
 
 { _изменение потока по дугам найденной цепочки от стока t до источника s_
    Входные данные  : P 
    Выходные данные : F }
  Procedure Stream(q : integer);
  Label l1;
  Begin
  l1:
    If P[q, 1] > 0 Then
      F[ P[q, 1], q] := F[ P[q, 1], q] + P[t, 2]
    Else 
      F[q, abs(P[q, 1]) ] := F[ q, abs(P[q, 1]) ] - P[t, 2];
    If Abs( P[q, 1] ) <> s Then Begin
      q := Abs( P[q, 1] );
      goto l1; { = Stream(q);}
    End;
  End;
 --- WP/95 Rel 1.78E (215.0) Reg.
  * Origin: ИЖ, какой шустрый! (2:5015/185.5)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор