Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі
Розглядається комбiнаторна задача знаходження максимального потоку в мережi, яка
 зводиться до евклiдової комбiнаторної задачi на розмiщеннях. Запропоновано наближений алгоритм для її розв’язання, визначено полiномiальну оцiнку його складностi. Рассматривается комбинаторная задача нахождения...
Saved in:
| Published in: | Доповіді НАН України |
|---|---|
| Date: | 2013 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/85634 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі / О.О. Ємець, Є.М. Ємець, Ю.Ф. Олексійчук // Доповiдi Нацiональної академiї наук України. — 2013. — № 4. — С. 33–37. — Бібліогр.: 12 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860049459676708864 |
|---|---|
| author | Ємець, О.О. Ємець, Є.М. Олексійчук, Ю.Ф. |
| author_facet | Ємець, О.О. Ємець, Є.М. Олексійчук, Ю.Ф. |
| citation_txt | Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі / О.О. Ємець, Є.М. Ємець, Ю.Ф. Олексійчук // Доповiдi Нацiональної академiї наук України. — 2013. — № 4. — С. 33–37. — Бібліогр.: 12 назв. — укр. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Розглядається комбiнаторна задача знаходження максимального потоку в мережi, яка
зводиться до евклiдової комбiнаторної задачi на розмiщеннях. Запропоновано наближений алгоритм для її розв’язання, визначено полiномiальну оцiнку його складностi.
Рассматривается комбинаторная задача нахождения максимального потока в сети, которая сводится к эвклидовой комбинаторной задаче на размещениях. Предложен приближенный алгоритм для ее решения, определена полиномиальная оценка его сложности.
The combinatorial problem finding of the maximal flow in a network is considered. This problem
is a Euclidean combinatorial one on arrangements. An approximate algorithm for the solution of
this problem is proposed. The polynomial estimation of the complexity of this algorithm is found.
|
| first_indexed | 2025-12-07T16:59:04Z |
| format | Article |
| fulltext |
УДК 519.85
О.О. Ємець, Є.М. Ємець, Ю.Ф. Олексiйчук
Полiномiальний метод наближеного розв’язання
комбiнаторної задачi знаходження максимального
потоку в мережi
(Представлено академiком НАН України I. В. Сергiєнком)
Розглядається комбiнаторна задача знаходження максимального потоку в мережi, яка
зводиться до евклiдової комбiнаторної задачi на розмiщеннях. Запропоновано наближе-
ний алгоритм для її розв’язання, визначено полiномiальну оцiнку його складностi.
Задача знаходження максимального потоку широко дослiджена [1–7] та вiдомi полiномiаль-
нi методи для її розв’язання, зокрема, методи Форда i Фалкерсона [1], Едмондса i Карпа [4],
Дiнiца [5], Карзанова [6] та iн. Задача, що розглядається, є узагальненням задачi знаходжен-
ня максимального потоку. Комбiнаторну задачу знаходження максимального потоку можна
звести [8] до евклiдової комбiнаторної задачi оптимiзацiї на розмiщеннях [9–11], для розв’я-
зання якої вiдомi неполiномiальнi алгоритми. Тому побудова наближених полiномiальних
методiв є актуальною.
У роботi розглядається жадiбний метод розв’язання комбiнаторної задачi знаходження
максимального потоку в мережi i аналiзується його складнiсть.
Постановка задачi. Нехай дано зв’язний орiєнтований граф Γ = (V,U), де V — множи-
на вершин; U — множина дуг. Дугу, що сполучає вершини vi i vj, позначимо uij ; vi, vj ∈ V .
Означення 1. Транспортною мережею називають орiєнтований граф Γ = (V,U ), в яко-
му кожнiй iз дуг uij привласнене невiд’ємне число bij > 0, яке називають пропускною
спроможнiстю дуги. Хоча б одна iз вершин має лише вихiднi дуги. Таку вершину нази-
вають джерелом и позначають vs. Також є принаймнi одна вершина, що має лише вхiднi
дуги. Її називають стоком i позначають vt.
Далi будемо розглядати транспортнi мережi з одним джерелом i одним стоком. Вважа-
тимемо, що кожна дуга uij в протилежному напрямку має пропускну спроможнiсть bji = 0.
Означення 2 [7]. Потоком називають функцiю w : U → R з такими властивостями для
будь-якої дуги uij :
1) значення функцiї w на дузi uij не може перевищувати пропускну здатнiсть дуги,
тобто w(uij) 6 bij ;
2) збереження балансу у всiх вершинах, крiм стоку и джерела, тобто
∑
uiz∈U
w(uiz) =
=
∑
uzj∈U
w(uzj) ∀ vz, vi, vj ∈ V , vz 6= vs, vz 6= vt.
Означення 3. Величиною потоку |w| будемо називати суму значень функцiї w по дугах,
що виходять iз джерела: |w| =
∑
usi∈U
w(usi), де vi ∈ V .
Величина потоку |w| також дорiвнює сумi значень функцiї w по дугах, що входять в стiк.
Задача знаходження максимального потоку формулюється так: знайти потiк w, для
якого величина потоку |w| є максимальною.
© О.О. Ємець, Є. М. Ємець, Ю.Ф. Олексiйчук, 2013
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №4 33
Означення 4. Залишковою пропускною спроможнiстю ребра uij називають величину
hij = bij − w(uij).
Якщо в транспортнiй мережi замiнити пропускнi спроможностi на залишковi пропускнi
спроможностi, отримаємо мережу, яку назвемо залишковою.
Потоком на дузi uij будемо називати величину w(uij).
Введемо додатковi обмеження на потiк. Нехай потiк по дугах uij ∈ Uc ⊆ U може набува-
ти значень, якi не перевищують число xij = gl ∈ G, тобто w(uij) 6 xij , де мультимножина
G = {g1, g2, . . . , gη}; причому вектор iз чисел xij є розмiщенням елементiв iз G [9–11], тоб-
то x = (xi1j1 , xi2j2 , . . . , xikjk) ∈ Ek
ηn(G), де Ek
ηn(G) — множина розмiщень, k = |Uc|; n —
кiлькiсть рiзних в G елементiв.
Назвемо задачу знаходження максимального потоку з додатковими комбiнаторними
обмеженнями комбiнаторною задачею знаходження максимального потоку.
Математична модель. Розглянемо математичну модель задачi. Нехай потiк по дузi uij
дорiвнює yij, тобто yij = w(uij).
Задача полягає у знаходженнi максимального значення функцiї f i вiдповiдних зна-
чень xij , yij
f =
∑
ujt∈U
yjt → max (1)
при виконаннi таких умов:
збереження балансу у вершинах
∑
uiz∈U
yiz =
∑
uzj∈U
yzj, ∀ z, z 6= t, z 6= s, (2)
обмеження на пропускну здатнiсть дуг
0 6 yij 6 bij ∀ i ∀ j, uij ∈ U, (3)
додатковi комбiнаторнi обмеження
yij 6 xij ∀ i ∀ j, uij ∈ Uc, (4)
x = (xi1j1 , xi2j2 , . . . , xikjk) ∈ Ek
ηn(G). (5)
Задача (1)–(5) є частковим випадком задачi евклiдової комбiнаторної оптимiзацiї на
розмiщеннях.
Розробцi методiв розв’язання задач комбiнаторної оптимiзацiї, дослiдженню властивос-
тей опуклих оболонок комбiнаторних множин присвячено багато робiт (див., зокрема, [9–
12]). Методи розв’язання комбiнаторних задач на розмiщеннях з додатковими обмеженнями
запропонованi, наприклад, в [11] i [12]; всi вони є неполiномiальними.
Зазначимо, що комбiнаторну задачу знаходження максимального потоку в мережi мож-
на звести до задачi евклiдової комбiнаторної оптимiзацiї на переставленнях. Для цього до-
статньо побудувати нову мультимножину, взявши k найбiльших елементiв мультимножи-
ни G, де k — кiлькiсть дуг, на якi накладенi комбiнаторнi обмеження.
У [8] розглядається метод розв’язання задачi (1)–(5). Але з урахуванням неполiномiаль-
ностi методу актуальною є розробка наближених методiв розв’язання задачi.
34 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №4
Жадiбний метод. Розглянемо метод, який дозволяє знайти наближений розв’язок по-
ставленої задачi. В методi використовуються iдеї Едмондса i Карпа [4] для знаходження
максимального потоку. На кожному етапi максимально насичується найкоротший шлях,
тому метод названий жадiбним.
К р о к 0. Покладаємо потiк рiвним нулю. Розширимо мультимножину G, додавши k
нулiв, де k — кiлькiсть дуг, на якi накладено додатковi комбiнаторнi обмеження. Для всiх
дуг покладаємо xij = 0 i будемо вважати всi ненульовi елементи мультимножини G неви-
користаними. Залишкова мережа на початковому етапi збiгається з початковою.
К р о к 1. Знаходимо в залишковiй мережi, не враховуючи додаткових комбiнаторних
обмежень, найкоротший шлях iз джерела в стiк з максимальною пропускною здатнiстю,
використовуючи модифiкований пошук у ширину. Нехай шлях складається iз p дуг i має
пропускну здатнiсть, що дорiвнює b. (Пiд пропускною здатнiстю шляху розумiємо мiнi-
мальну пропускну здатнiсть серед дуг цього шляху.) Якщо такого шляху немає — зупинка
алгоритму.
К р о к 2. Переберемо всi дуги знайденого шляху у порядку спадання пропускних спро-
можностей bij. Привласнимо всiм xij, для яких xij < b + yij, мiнiмальнi значення iз
мультимножини G, якi незайнятi i перевищують b + yij, де yij — поточне значення по-
току по дузi uij . Якщо такого елемента немає, беремо найбiльший елемент iз G. Вва-
жатимемо цi елементи мультимножини зайнятими, а попереднi значення xij — незайня-
тими.
К р о к 3. Пускаємо через знайдений шлях максимально можливий потiк (враховуючи
комбiнаторнi обмеження).
К р о к 4. Модифiкуємо залишкову мережу. Змiнюємо пропускнi здатностi i видаляємо
дуги, для яких виконується хоча б одна умова:
а) yij = bij ;
б) yij = xij i в G немає вiльних елементiв, що перевищують xij.
При цьому, якщо умови а i б бiльше не виконуються для деякої ранiше видаленої дуги,
повертаємо її в залишкову мережу.
Переходимо на крок 1.
Модифiкований пошук в ширину дозволяє знайти найкоротший шлях з джерела до
стоку. Якщо таких шляхiв кiлька, метод дозволяє знайти серед них шлях з найбiльшою
пропускною здатнiстю.
Для кожної вершини vi потрiбно задати такi поля:
1) стан вершини, можливi значення: не помiчена, помiчена, переглянута;
2) предок — iнша вершина графу;
3) вiдстань вiд джерела di;
4) потенцiйний потiк pi.
Модифiкований пошук в ширину.
К ро к 0. Джерело вважаємо помiченим, ps = ∞, ds = 0. Всi iншi вершини — не помiче-
ними, pi = 0, ∀ i, i 6= s. Створюємо чергу iз помiчених вершин.
К р о к 1. Якщо черга порожня — шляху не iснує, зупинка алгоритму, iнакше — вважаємо
першу вершину черги vc переглянутою i видаляємо її iз черги.
К р о к 2. Розглядаємо всi дуги uci, що виходять з вершини vc, i перебираємо вершини vi,
якi або мiстяться в черзi i di > dc, або є непомiченими. Якщо pi < min(pc, bci), то pi =
= min(pc, bci), предком вершини vi стає вершина vc, di = dc+1 та, якщо вершина непомiчена,
помiчаємо її та додаємо в кiнець черги.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №4 35
К ро к 3. Якщо vt мiститься в черзi i dt = dz, де vz — перша в черзi вершина, то зупинка
алгоритму. (Зворотний до шуканого шлях можна отримати, почавши зi стоку i переходячи
вiд вершини до її предка, доки не досягнемо джерела.) Iнакше — перехiд до кроку 1.
Оцiнка складностi жадiбного методу. Нехай |V | — кiлькiсть вершин графу, |U | —
кiлькiсть дуг.
Теорема 1. Час роботи модифiкованого алгоритму пошуку в ширину T (n) = O(|U | +
+ |V |).
Зауваження. Оскiльки в роботi розглядаються зв’язнi графи, то час роботи модифi-
кованого алгоритму пошуку в ширину дорiвнює T (n) = O(|U |).
Теорема 2. Час роботи жадiбного алгоритму розв’язання комбiнаторної задачi зна-
ходження максимального потоку T (n = O(|U | ·n · |w∗|), де |w∗| — шукана величина макси-
мального потоку; n — кiлькiсть рiзних елементiв у мультимножинi G.
Таким чином, в роботi розглянута комбiнаторна задача знаходження максимального
потоку, запропонований наближений метод її розв’язання та зроблена оцiнка часу роботи
цього методу. Метод може застосовуватися для знаходження початкового розв’язку в то-
чних методах. В подальшому доцiльно оцiнити точнiсть роботи алгоритму та провести об-
числювальнi експерименти.
1. Форд Л., Фалкерсон Д. Потоки в сетях. – Москва: Мир, 1966. – 277 с.
2. Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы. – Нижний Новгород: Изд-во Нижегород. гос. ун-та
им. Н.И. Лобачевского, 2004. – 330 с.
3. Ху Т. Целочисленное программирование и потоки в сетях – Москва: Мир, 1974. – 519 с.
4. Edmonds J., Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems //
J. ACM. – 1972. – 19, No 2. – P. 248–264.
5. Диниц Е.А. Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой // Докл.
АН СССР. – 1970. – 194, № 4. – С. 754–757.
6. Карзанов А.А. Нахождение максимального потока в сети методом предпотоков // Там же. – 1974. –
215, № 1. – С. 49–53.
7. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-е изд. – Москва:
ИД “Вильямс”, 2005. – 1296 с.
8. Ємець О.О., Ємець Є.М., Олексiйчук Ю.Ф. Знаходження максимального потоку в мережi з дода-
тковими комбiнаторними обмеженнями // Таврич. вестник информатики и математики. – 2011. –
№ 1. – С. 43–50.
9. Стоян Ю.Г., Ємець О.О. Теорiя i методи евклiдової комбiнаторної оптимiзацiї – Київ: IСДО, 1993. –
188 с. (див. також http://informatics.org.ua/uploads/books/stoyan_emets_eko.pdf).
10. Стоян Ю.Г., Ємець О.О., Ємець Є.М. Оптимiзацiя на полiрозмiщеннях: теорiя та методи. – Полта-
ва: РВЦ ПУСКУ, 2005. – 103 с. (http://informatics.org.ua/uploads/books/st_em_em_monography.pdf).
11. Емец О.А., Барболина Т.Н. Комбинаторная оптимизация на размещениях: Монография. – Киев:
Наук. думка, 2008. – 159 с. (http://informatics.org.ua/uploads/books/em_bar_monography.pdf).
12. Ємець О.О., Ємець Є.М., Олексiйчук Ю.Ф. Прямий метод вiдсiкання для задач комбiнаторної опти-
мiзацiї на розмiщеннях // Вiсн. Запорiзьк. нац. ун-ту: Зб. наук. статей. Фiз.-мат. науки. – 2011. – № 1. –
С. 36–43.
Надiйшло до редакцiї 08.06.2012Полтавський унiверситет економiки i торгiвлi
36 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №4
О.А. Емец, Е.М. Емец, Ю.Ф. Олексийчук
Полиномиальный метод приближенного решения комбинаторной
задачи нахождения максимального потока в сети
Рассматривается комбинаторная задача нахождения максимального потока в сети, кото-
рая сводится к эвклидовой комбинаторной задаче на размещениях. Предложен приближен-
ный алгоритм для ее решения, определена полиномиальная оценка его сложности.
O.O. Iemets, Ye. M. Yemets, Yu. F. Oleksiichuk
An approximate polynomial method for solving a combinatorial
problem of finding the maximum flow in a network
The combinatorial problem finding of the maximal flow in a network is considered. This problem
is a Euclidean combinatorial one on arrangements. An approximate algorithm for the solution of
this problem is proposed. The polynomial estimation of the complexity of this algorithm is found.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №4 37
|
| id | nasplib_isofts_kiev_ua-123456789-85634 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:59:04Z |
| publishDate | 2013 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Ємець, О.О. Ємець, Є.М. Олексійчук, Ю.Ф. 2015-08-11T13:10:37Z 2015-08-11T13:10:37Z 2013 Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі / О.О. Ємець, Є.М. Ємець, Ю.Ф. Олексійчук // Доповiдi Нацiональної академiї наук України. — 2013. — № 4. — С. 33–37. — Бібліогр.: 12 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/85634 519.85 Розглядається комбiнаторна задача знаходження максимального потоку в мережi, яка
 зводиться до евклiдової комбiнаторної задачi на розмiщеннях. Запропоновано наближений алгоритм для її розв’язання, визначено полiномiальну оцiнку його складностi. Рассматривается комбинаторная задача нахождения максимального потока в сети, которая сводится к эвклидовой комбинаторной задаче на размещениях. Предложен приближенный алгоритм для ее решения, определена полиномиальная оценка его сложности. The combinatorial problem finding of the maximal flow in a network is considered. This problem
 is a Euclidean combinatorial one on arrangements. An approximate algorithm for the solution of
 this problem is proposed. The polynomial estimation of the complexity of this algorithm is found. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі Полиномиальный метод приближенного решения комбинаторной задачи нахождения максимального потока в сети An approximate polynomial method for solving a combinatorial problem of finding the maximum flow in a network Article published earlier |
| spellingShingle | Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі Ємець, О.О. Ємець, Є.М. Олексійчук, Ю.Ф. Інформатика та кібернетика |
| title | Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі |
| title_alt | Полиномиальный метод приближенного решения комбинаторной задачи нахождения максимального потока в сети An approximate polynomial method for solving a combinatorial problem of finding the maximum flow in a network |
| title_full | Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі |
| title_fullStr | Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі |
| title_full_unstemmed | Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі |
| title_short | Поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі |
| title_sort | поліноміальний метод наближеного розв'язання комбінаторної задачі знаходження максимального потоку в мережі |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85634 |
| work_keys_str_mv | AT êmecʹoo polínomíalʹniimetodnabliženogorozvâzannâkombínatornoízadačíznahodžennâmaksimalʹnogopotokuvmereží AT êmecʹêm polínomíalʹniimetodnabliženogorozvâzannâkombínatornoízadačíznahodžennâmaksimalʹnogopotokuvmereží AT oleksíičukûf polínomíalʹniimetodnabliženogorozvâzannâkombínatornoízadačíznahodžennâmaksimalʹnogopotokuvmereží AT êmecʹoo polinomialʹnyimetodpribližennogorešeniâkombinatornoizadačinahoždeniâmaksimalʹnogopotokavseti AT êmecʹêm polinomialʹnyimetodpribližennogorešeniâkombinatornoizadačinahoždeniâmaksimalʹnogopotokavseti AT oleksíičukûf polinomialʹnyimetodpribližennogorešeniâkombinatornoizadačinahoždeniâmaksimalʹnogopotokavseti AT êmecʹoo anapproximatepolynomialmethodforsolvingacombinatorialproblemoffindingthemaximumflowinanetwork AT êmecʹêm anapproximatepolynomialmethodforsolvingacombinatorialproblemoffindingthemaximumflowinanetwork AT oleksíičukûf anapproximatepolynomialmethodforsolvingacombinatorialproblemoffindingthemaximumflowinanetwork |