4430
правок
Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока: различия между версиями
Перейти к навигации
Перейти к поиску
м
Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока (посмотреть исходный код)
Версия от 23:04, 17 апреля 2017
, 17 апреля 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 308: | Строка 308: | ||
Следствие 2. Минимальный сетевой разрез в схеме N = (V, E) | Следствие 2. Минимальный сетевой разрез в схеме N = (V, E) можно найти за время O(|V| |E|). | ||
Эвристика для сбалансированного биразбиения с минимальным разрезом | |||
'''Эвристика для сбалансированного биразбиения с минимальным разрезом''' | |||
Вначале неоднократно применяется эвристический алгоритм вычисления максимального потока и минимального разреза, затем выполняется сбалансированное биразбиение потока (FBB) для нахождения r-сбалансированного биразбиения, минимизирующего количество пересекаемых сеток. Затем разрабатывается эффективная реализация FBB, имеющая ту же асимптотическую сложность, что и однократное вычисление минимального потока. Ради упрощения представления алгоритм FBB излагается здесь в формулировке для исходной схемы, а не для транспортной сети, построенной из этой схемы. Эвристический алгоритм представлен на рис. 1, на рис. 6 приведен пример использования. | Вначале неоднократно применяется эвристический алгоритм вычисления максимального потока и минимального разреза, затем выполняется сбалансированное биразбиение потока (FBB) для нахождения r-сбалансированного биразбиения, минимизирующего количество пересекаемых сеток. Затем разрабатывается эффективная реализация FBB, имеющая ту же асимптотическую сложность, что и однократное вычисление минимального потока. Ради упрощения представления алгоритм FBB излагается здесь в формулировке для исходной схемы, а не для транспортной сети, построенной из этой схемы. Эвристический алгоритм представлен на рис. 1, на рис. 6 приведен пример использования. | ||
В таблице 2 сравниваются лучшие варианты реализации FBB с точки зрения размеров сетевых разрезов с лучшими вариантами алгоритмов разбиения на базе аналитических методов – EIG1 (Хаген и Канг, [7]) и PARABOLI (PB) (Рисс и др. [ ]). Результаты алгоритма PARABOLI ранее были наилучшими известными результатами для эталонных схем. Результаты алгоритма FBB оказались лучшими из десяти прогонов. В среднем FBB превзошел EIG1 и PARABOLI на 58,1% and 11,3%, соответственно. Для схемы S38417 субоптимальный результат FBB может быть улучшен за счет (1) увеличения количества прогонов и (2) применения техник кластеризации к схеме на базе знания имеющихся соединений (до выполнения разбиения). | В таблице 2 сравниваются лучшие варианты реализации FBB с точки зрения размеров сетевых разрезов с лучшими вариантами алгоритмов разбиения на базе аналитических методов – EIG1 (Хаген и Канг, [7]) и PARABOLI (PB) (Рисс и др. [13]). Результаты алгоритма PARABOLI ранее были наилучшими известными результатами для эталонных схем. Результаты алгоритма FBB оказались лучшими из десяти прогонов. В среднем FBB превзошел EIG1 и PARABOLI на 58,1% and 11,3%, соответственно. Для схемы S38417 субоптимальный результат FBB может быть улучшен за счет (1) увеличения количества прогонов и (2) применения техник кластеризации к схеме на базе знания имеющихся соединений (до выполнения разбиения). | ||
| Строка 322: | Строка 322: | ||
Теорема 2. Алгоритм FBB имеет временную сложность O( | '''Теорема 2. Алгоритм FBB имеет временную сложность O(|V| |E|) для связной схемы N = (V, E).''' | ||
Теорема 3. Количество итераций и финальный размер сетевого разреза представляют собой невозрастающие функции от | '''Теорема 3. Количество итераций и финальный размер сетевого разреза представляют собой невозрастающие функции от <math>\epsilon</math>.''' | ||
На практике алгоритм FBB завершается намного быстрее, чем указывает временная сложность для наихудшего случая, как показано в разделе «Экспериментальные результаты». Теорема 3 позволяет повысить эффективность FBB и качество разбиения для больших значений | На практике алгоритм FBB завершается намного быстрее, чем указывает временная сложность для наихудшего случая, как показано в разделе «Экспериментальные результаты». Теорема 3 позволяет повысить эффективность FBB и качество разбиения для больших значений <math>\epsilon</math>. Это неверно для других подходов к разбиению – таких как эвристика K&L. | ||
== Применение == | == Применение == | ||