Редактирование: Алгоритм отмены цикла минимального среднего веса

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 21: Строка 21:
  
 
===Псевдокод===
 
===Псевдокод===
  '''Edge[]''' findMin('''Graph''' G)
+
    '''Edge[]''' findMin ('''Graph''' G)
 
       '''while''' f
 
       '''while''' f
          <font color="green">// найдём M(C) {{---}} вес минимального цикла</font>
+
      <font color="green">// найдём M(C) {{---}} вес минимального цикла</font>
          C = c : M(c) = <tex>\min\limits_c</tex> M(c)   
+
      C = c : M(c) = <tex>\min\limits_c</tex> M(c)   
          '''if''' M(C) <tex>\geqslant</tex> 0
+
      '''if''' M(C) <tex>\geqslant</tex> 0
              <font color="green">// Если величина M(C) положительна, то мы нашли f {{---}} поток минимальной стоимости, на этом алгоритм завершается</font>
+
        <font color="green">// Если величина M(C) положительна, то мы нашли f {{---}} поток минимальной стоимости, на этом алгоритм завершается</font>
              '''return''' f                             
+
        '''return''' f                             
          '''else'''
+
      '''else'''
              <font color="green">// в противном случае отменяем цикл</font>
+
        <font color="green">// в противном случае отменяем цикл</font>
              f += c_f * f(C)
+
        f += c_f * f(C)
  
 
===Корректность===
 
===Корректность===
Строка 135: Строка 135:
 
====Псевдокод====
 
====Псевдокод====
  
  '''func''' findMinCycleBinarySearch('''int''' l, '''int''' r)
+
    '''func''' findMinCycleBinarySearch ('''int''' l, '''int''' r)
      <font color="green">// находим среднюю величину <tex>m</tex></font>
 
 
       m = (l + r) / 2
 
       m = (l + r) / 2
      <font color="green">// вычитаем её из веса каждого ребра в сети</font>
 
 
       '''for''' e '''in''' edges
 
       '''for''' e '''in''' edges
          e.weight -= m
+
        e.weight -= m
 
       '''while''' l > r - 1
 
       '''while''' l > r - 1
      <!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
+
        '''if''' <tex>\exists</tex>C : M(C) < 0 <!--- cho-t xz za4em C: mb exists? eee ugadala)0))--->
          '''if''' <tex>\exists</tex>C : M(C) < 0 <!--- cho-t xz za4em C: mb exists? eee ugadala)0))--->
+
          findMinCycleBinarySearch (l, m)
              <font color="green">// если есть отрицательный цикл, то веса циклов находятся в диапазоне <tex>[l;m]</tex>
+
        '''else'''
              // рассмотрим этот промежуток</font>
+
          findMinCycleBinarySearch (m, r)
              findMinCycleBinarySearch (l, m)
 
          '''else'''
 
              <font color="green">// иначе запускаем двоичный поиск на отрезке <tex>[m;r]</tex></font>
 
              findMinCycleBinarySearch (m, r)
 
  
 
===Продвинутый алгоритм===
 
===Продвинутый алгоритм===
Добавим к нашему графу вершину <tex>s</tex> и рёбра из неё во все остальные вершины.
+
Добавим к нашему графу вершину <tex>s</tex> и ребра из нее во все остальные вершины.
 
Запустим [[алгоритм Форда-Беллмана]] и попросим его построить нам квадратную матрицу со следующим условием: <tex>d[i][u]</tex> {{---}} длина минимального пути от <tex>s</tex> до <tex>u</tex> ровно из <tex>i</tex> ребер.
 
Запустим [[алгоритм Форда-Беллмана]] и попросим его построить нам квадратную матрицу со следующим условием: <tex>d[i][u]</tex> {{---}} длина минимального пути от <tex>s</tex> до <tex>u</tex> ровно из <tex>i</tex> ребер.
 
Тогда длина оптимального цикла <tex>\mu^{*}</tex> минимального среднего веса вычисляется как <tex>\min\limits_{u} {\max\limits_{k} {\dfrac{d[n][u]-d[k][u]}{n-k}}}</tex>.
 
Тогда длина оптимального цикла <tex>\mu^{*}</tex> минимального среднего веса вычисляется как <tex>\min\limits_{u} {\max\limits_{k} {\dfrac{d[n][u]-d[k][u]}{n-k}}}</tex>.
Строка 163: Строка 157:
  
 
====Псевдокод====
 
====Псевдокод====
  '''func''' findMinCycle('''Graph''' G)
+
    '''func''' findMinCycle('''Graph''' G)
      <font color="green">// вводим мнимую вершину <tex>s</tex>, от которой проведём рёбра нулевого веса в каждую вершину графа</font>
 
 
       '''Node''' s
 
       '''Node''' s
 
       '''Edge[]''' e
 
       '''Edge[]''' e
 +
      <font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>
 
       insert(s)   
 
       insert(s)   
 
       i = 0                                       
 
       i = 0                                       
 
       '''for''' u '''in''' G
 
       '''for''' u '''in''' G
          e[i].begin = s
+
        e[i].begin = s
          e[i].end = u
+
        e[i].end = u
          e[i].weight = 0
+
        e[i].weight = 0
          i++
+
        i++
      <font color="green">// строим матрицу кратчайших расстояний, запустив алгоритм Форда-Беллмана из вершины <tex>s</tex></font>
 
 
       fordBellman(s)
 
       fordBellman(s)
      <font color="green">// <tex>m</tex> {{---}} длина оптимального цикла</font>
 
 
       m = <tex>\min\limits_{u} {\max\limits_{k} }</tex>((d[n][u] - d[k][u]) / (n - k))
 
       m = <tex>\min\limits_{u} {\max\limits_{k} }</tex>((d[n][u] - d[k][u]) / (n - k))
      <!-----<font color="green">// запомнив значения <tex>u</tex> и <tex>k</tex>, дающих оптимальный результат, найдём цикл</font>--------->
+
<!----чуть не забыла про отступы, дура тупая----->
      <!----чуть не забыла про отступы, дура тупая----->
 
  
 
==См. также==
 
==См. также==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)