4430
правок
Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока: различия между версиями
Материал из WEGA
Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока (посмотреть исходный код)
Версия от 12:17, 17 апреля 2017
, 17 апреля 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 75: | Строка 75: | ||
4. Положить s источником N', а t – стоком N'. | 4. Положить s источником N', а t – стоком N'. | ||
5. Присвоить единичную [[пропускная способность|пропускную способность]] всем мостовым ребрам и бесконечную пропускную способность – всем остальным ребрам в E'. | 5. Присвоить единичную [[пропускная способность дуги|пропускную способность]] всем мостовым ребрам и бесконечную пропускную способность – всем остальным ребрам в E'. | ||
6. Для вершины <math>v \in V\ \;</math>, соответствующей вершине в V, w(v) обозначает вес v в N. Для вершины <math>u \in V' \;</math>, отщепленной от сетки, w(u) = 0. | 6. Для вершины <math>v \in V\ \;</math>, соответствующей вершине в V, w(v) обозначает вес v в N. Для вершины <math>u \in V' \;</math>, отщепленной от сетки, w(u) = 0. | ||
| Строка 92: | Строка 92: | ||
[[Файл:CP_6.png]] | [[Файл:CP_6.png]] | ||
Рисунок 6. Алгоритм FBB для примера на рис. 5 для значений r= 1/2, | Рисунок 6. Алгоритм FBB для примера на рис. 5 для значений r = 1/2, <math>\epsilon</math> = 0,15 и единичного веса каждой вершины. Алгоритм завершает работу после нахождения разреза <math>(X_2, \bar{X_2}) \;</math>. | ||
Маленькая черная вершина обозначает, что мостовое ребро, соответствующее сетке, насыщено потоком | Маленькая черная вершина обозначает, что мостовое ребро, соответствующее сетке, насыщено потоком | ||
Таблица 1. Сравнение алгоритмов SN, PFM3 и FBB (r = 1/2, | Таблица 1. Сравнение алгоритмов SN, PFM3 и FBB (r = 1/2, <math>\epsilon</math> = 0,1) | ||
Схема Средний размер сетевого разреза Биразбиение FBB Улучшение % | Схема Средний размер сетевого разреза Биразбиение FBB Улучшение % | ||
| Строка 108: | Строка 108: | ||
Ave 1:1,10 24,5 19,0 | Ave 1:1,10 24,5 19,0 | ||
Таблица 2. Сравнение алгоритмов EIG1, PB и FBB (r = 1/2, | Таблица 2. Сравнение алгоритмов EIG1, PB и FBB (r = 1/2, <math>\epsilon</math> = 0,1) Все допускают отклонение <math>\le 10%</math> | ||
Размер t-сетевого разреза Улучшение % к FBB продолж. | Размер t-сетевого разреза Улучшение % к FBB продолж. | ||
