Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
1998
Тип роботи:
Інші
Предмет:
Системи автоматизованого проектування ЗВТ
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
Державний університет “Львівська політехніка”
ПОТОКОВІ АЛГОРИТМИ
І Н С Т Р У К Ц І Я №1
до лабораторної роботи з курсу
“Дискретні моделі в САПР”
для базового напрямку 6.0804 “Комп’ютерні науки”
Затверджено:
на засіданні кафедри “Системи
автоматизованого провектування”
Протокол N14 від 03.04. 1997 р.
Львів - 1998
Потокові алгоритми. Інструкція до лабораторної роботи №1 з курсу “Дискретні моделі в САПР” для студентів базового напрямку 6.08.04 “Комп’ютерні науки”. /Укл. В.І.Каркульовський, С.П.Ткаченко, І.І.Чура. -Львів: ДУ ЛП, 1998р. -12с.
Укладачі: В.І.Каркульовський, канд.техн.наук, доц.,
С.П.Ткаченко, канд.техн.наук, доц.
І.І.Чура, канд.техн.наук, доц..
Відповідальний за випуск: Д.В.Федасюк, канд.техн.наук, доц.
Рецензенти: Стех Ю.В. , канд.техн.наук, доц.
Мотика І.І. , канд.техн.наук, доц.
МЕТА РОБОТИ
Метою даної лабораторної роботи є вивчення потокових алгоритмів.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
ПОНЯТТЯ ПОТОКУ
Сітка - це граф, в якому кожній дузі приписана деяка пропускна здатність. Введемо позначення: с(х,у) - пропускна здатність дуги (х,у), а(х,у) - вартість переміщення одиниці потоку по дузі (х,у), T(x,y) - час проходження потоку, k(x,y) - коефіцієнт підсилення потоку в дузі (x,y).
Припустимо, що є граф, в якому деяка кількість одиниць потоку проходить від джерела до стоку і для кожної одиниці потоку відомий маршрут руху. Назвемо кількість одиниць, що проходять по дузі (х,у), потоком в даній дузі. Будемо потік в дузі(х,у) позначати через f(х,у) вочевидь 0 f(х,у)с(х,у). Дуги графа можна віднести до трьох різних категорій:
1) дуги, в яких потік не може ні збільшуватись, ні зменшуватись (множина таких дуг позначається через - N);
2) дуги, в яких потік може збільшуватись (множина таких дуг позначається через - І);
3) дуги, в яких потік може зменшуватись (множина таких дуг позначається через - R);
Наприклад, дуги, що мають нульову пропускну здатність або значну вартість проходження потоку, повинні належати множині N. Дуги, в яких потік менше пропускної здатності, повинні належати множині I. Дуги, по яких вже проходить деякий потік, повинні належати множині R. Дуги з множини I називають збільшуючими, а дуги з множини R - зменшуючими.
Будь-яка дуга графа належить хоча б одній з трьох введених множин - I, R або N. Можливо, що якась дуга належить як множині I, так і множині R. Це має місце в тому випадку, коли по дузі вже протікає деякий потік, який можна збільшувати чи зменшувати. Відповідні дуги називаються проміжними.
Позначимо через і(х,у) максимальну величину, на яку може бути збільшений потік в дузі (х,у). Відповідно позначимо через r(х,у) максимальну величину, на яку може бути зменшений потік в дузі (х,у). Очевидно,
і(х,у) = с(х,у) - f(х,у) , а r(х,у) = f(х,у)
Припустимо, що ми хочемо переслати додаткову кількість одиниць потоку з витоку в стік. Можливі декілька способів розв’язування даної задачі (якщо вона взагалі має рішення):
Цей спосіб міг би бути реалізований, якщо б ми знайшли шлях Р з вершини “s” у вершину “t”, який би цілком складався із збільшуючих дуг (рис.1). Скільки в цьому випадку можна було б додатково переслати одиниць потоку з “s” в “t” по шляху Р? Оскільки і(х,у) являє собою максимально можливе збільшення потоку в дузі (х,у), то величина додаткового потоку з “s” в “t” по шляху Р буде складати:
min {i(х,у)}
(х,у) є Р
s a b t
i(s,a)=3 i(a,b)=2 i(b,t)=1
Рис.1. Ланцюг, що збільшує потік і включає лише прямі дуги.
Для даних прикладу ( рис.1) по шляху Р можна переслати з “s” в “t” максимум одну додаткову одиницю потоку, оскільки:
min{i(s,a), i(a,b), i(b,t)} = min{3, 2, 1}=1
2) Цей спосіб міг би бути реалізований, якщо б ми знайшли шлях Р з вершини “t” в вершину “s”, який цілком складався би із зменшуючих дуг (рис.2). При цьому можна було б зменшити потік в кожній дузі (х,у), що привело б до зменшення потоку з вершини “t” в вершину ”s”, тобто, до збільшення чистого потоку з вершини “s” в вершину “t”. На яку максимальну величину можна було б зменшити потік з витоку в стік по вказаному шляху? Оскільки в кожній дузі (х,у) шляху Р потік можна зменшити на максимальну величину r(х,у), то максимальне зменшення потоку вздовж шляху Р визначається величиною
min {r(х,у)}
(х,у) є Р
s a b t
r(a,s)=1 r(b,a)=2 r(t,b)=1
Рис.2. Ланцюг, що збільшує потік і включає лише зворотні дуги.
Для даних прикладу на рис.2 по шляху Р можна переслати назад з “t” в “s” максимум одну одиницю потоку, оскільки:
min{r(t,b), r(b,a), r(a,s)} = min{1, 2, 1}=1
3)Цей спосіб є комбінацією двох попередніх. Це означає, що необхідно знайти ланцюг, що з’єднує вершини “s” і “t”, дуги якого задовольняють наступним умовам:
- всі прямі дуги ланцюга, що мають напрям від “s” до “t”, належать множині I; - всі зворотні дуги ланцюга, що мають напрям від “t” до “s”, належать множині R.
Для прикладу розглянемо ланцюг С, що з’єднує вершини “s”,”t” і зображений на рис.3. Прямі дуги цього ланцюга (s,a), (a,b), (d,t), а зворотні -(c,b) i (d,c). Якщо кожна пряма дуга належить множині I, а кожна зворотна дуга - множині R, то вздовж розглянутого ланцюга можна переслати додатковий потік з “s” в “t”.
s a b c d
i(s,a)=4 i(a,b)=3 r(c,b)=5 r(d,c)=2 i(d,t)=3
Рис.3. Ланцюг, що збільшує потік і включає прямі і зворотні дуги.
Це здійснюється шляхом збільшення потоку в прямих дугах, що є збільшуючими, і зменшення потоку в зворотних дугах, що є зменшуючими. Максимальна величина додаткового потоку, який можна переслати вздовж відповідного ланцюга з “s” в “t”, визначається як мінімум з наступних двох величин:
min {i(x,y):(x,y) - пряма дуга}
min {r(x,y):(x,y) - зворотна дуга}
Мінімальна з двох вказаних величин називається максимальним збільшенням потоку по відповідному ланцюгу. Для прикладу на рис.3, маємо можливе збільшення потоку в прямих дугах i(s,a)=4, i(a,b)=3, i(d,t)=3. Мінімум з цих трьох величин рівний 3. Можливе зменшення потоку в зворотних дугах визначають величини r(c,d)=5, r(d,c)=2. Мінімум з цих двох величин рівний 2. Максимальне збільшення потоку по ланцюгу С дорівнює min(3,2)=2. Таким чином, в результаті збільшення на дві одиниці потоку в прямих дугах і зменшення на дві одиниці потоку в зворотних дугах по ланцюгу можна додатково переслати з “s” в “t” дві одиниці потоку.
Кожен ланцюг з “s” в “t” будь-якого з трьох розглянутих вище типів, по якому можуть бути додатково переслані одиниці потоку, називається збільшуючим ланцюгом.
ПОНЯТТЯ ПОТОКОВИХ АЛГОРИТМІВ
Поняття потокові алгоритми включає в себе ряд алгоритмів.
1) Алгоритм пошуку збільшую чого ланцюга.
Основна ідея алгоритму: побудова дерева, що росте з вершини “s” і складається з розфарбованих дуг, по яких з вершини “s” можуть пересилатись додаткові одиниці потоку.
В процесі виконання алгоритму можуть виникнути дві різні ситуації: а) стік “t” є розфарбованим???, тоді в побудованому з розфарбованих дуг дереві єдиний ланцюг з “s” в “t” є збільшуючим потік ланцюгом; б) стік “t” не вдається розфарбувати, що означає: що у вихідній сітці не існує збільшуючого ланцюга між “s” і “t” .
2) Алгоритм пошуку максимального потоку.
Основна задача алгоритму пошуку максимального потоку полягає в пошуку способів пересилання максимальної кількості одиниць потоку з витоку в стік при умові відсутності перевищення пропускних здатностей
дуг вихідного графа. В основі алгоритму пошуку максимального потоку лежить наступна ідея: вибираємо початковий потік з витоку “s” в стік “t”, потім використовуємо алгоритм пошуку збільшуючого ланцюга. Цей алгоритм дозволяє знайти єдиний збільшуючий ланцюг з “s” в “t”, якщо той існує. Послідовність, в якій повинні розфарбовуватись вершини і дуги, конкретно не визначається. Тому можливі два варіанти розфарбування вершин і дуг: 1) вибирається яка-небудь вершина, а потім проводиться розфарбування максимальної кількості вершин; 2) проводиться розфарбування, виходячи з останньої розфарбованої вершини. Який саме спосіб розфарбування буде вибраний, буде залежати від характеру більш загальної задачі, тобто від алгоритму пошуку максимального потоку, який в якості підалгоритму використовує алгоритм пошуку збільшуючого ланцюга. Якщо пошук збільшуючого ланцюга вдалий, тобто знайдено збільшуючий ланцюг з “s” в “t”, то за допомогою алгоритму пошуку максимального потоку здійснюється максимально можливе збільшення потоку вздовж знайденого ланцюга. Потім повторюється пошук нового збільшуючого ланцюга і т.д. Виконання алгоритму завершується за скінчене число кроків, коли ланцюг, що збільшує потік, знайти не вдається: це означає, що біжучий потік з “s” в “t” є максимальним.
3) Алгоритм пошуку потоку мінімальної вартості.
Дана задача полягає в організації пересилання з мінімальними витратами заданої кількості v одиниць потоку з витоку в стік в графі з заданими на дугах пропускними здатностями і вартостями проходження одної одиниці потоку.
4) Алгоритм дефекту.
Основна ідея алгоритму: рішення задачі про потік мінімальної вартості, але на відміну від попереднього алгоритму алгоритм дефекту вирішує задачу про потік мінімальної вартості у випадку, коли найменша кількість одиниць потоку, яка повинна протікати по дузі, більша або рівна 0 для всіх дуг.
5) Алгоритм пошуку динамічного потоку.
Попередні алгоритми використовували потоки, які задовольняли деяким умовам, які визначались заданими на дугах пропускними здатностями і вартостями. Даний алгоритм використовує сітки, дуги яких характеризуються ще одним показником - часом проходження потоку (кожна одиниця в цих потоках проходить з витоку в стік за час, що не перевищує заданий).
6) Потоки з підсиленням.
Попередні розгляди потоку показували, що потік не змінювався: одиниця ввійшла - одиниця вийшла. При проходженні потоку через дугу нові одиниці не створювались, але і старі не щезали. Потоки з підсиленням усувають припущення, згідно якого при проходженні по дугам потік залишається незмінним. Висувається припущення, що кількість одиниць в потоці, що проходить по дузі, може збільшуватись або зменшуватись. Точніше, вважають, що якщо в будь-яку дугу (х,у) в вершині “х” входить f(x,y) одиниць потоку, то з цієї дуги в вершині “у” вийде k(x,y)f(x,y) одиниць потоку. Можна вважають, що кожна одиниця потоку, що проходить по дузі (x,y), помножується на величину k(x,y) (яка називається підсиленням дуги (x,y).
ПРИКЛАД РОБОТИ АЛГОРИТМУ ПОШУКУ
ЗБІЛЬШУЮЧОГО ЛАНЦЮГА
Як було сказано вище, алгоритм знаходить перший збільшуючий ланцюг, якщо той існує. Процедура розфарбування буде організована таким чином, що розфарбування наступної вершини буде проводитись виходячи з останньої розфарбованої вершини.
Нехай задано граф, що має наступний вигляд(рис.4):
Рис.4.
(поряд з дугами графа вказані букви І,R,N, що визначають, до якої множини належать відповідні дуги)
Насамперед розфарбовується вершина “s” (початкова вершина). З вершини “s” може бути розфарбована вершина “а” і дуга (s,a), оскільки (s,a) (І. Розфарбовані вершини запам’ятовуються в масиві збільшуючих ланцюгів в порядку їх роçфарбування. З вершини “а” не можуть бути розфарбовані вершина “b” і дуга (a,b), оскільки (а,b) (І. Вершина “с” і дуга (а,с) можуть бути зафарбовані, оскільки (а,с)(І. Вершина “d” і дуга (d,a) можуть бути розфарбовані з вершини “а”, оскільки (d,а) ( N. Це завершує процедуру зафарбовування з вершини “а”.
Далі будемо зафарбовувати вершини і дуги з вершини “b”. Вершини “а”, “с” і “d”, які вже розфарбовані, можна вже не розглядати. З вершини “b” може бути розфарбована вершина “t” і дуга (b,t), оскільки (b,t) є І.
Отже збільшуючим ланцюгом з “s” в “t” є (s,a), (a,с), (b,c), (b,t), в якому максимальне збільшення потоку по цьому рівне min{i(s,a), i(a,c),r(b,c), t(b,t)}
На цьому процедура розфарбування завершується, оскільки виявляється розфарбованою вершина “t”. Підграф, що складається з розфарбованих вершин і дуг, має вигляд зображений на рис. 5.
Рис.5.
ПРИКЛАД РОБОТИ АЛГОРИТМУ ПОШУКУ МАКСИМАЛЬНОГО ПОТОКУ
Крок 1. Алгоритм починається з задання нульового потоку, тобто для всіх дуг (х,у) графа, що розглядається, задають f(x,y)=0.
Крок 2. Оскільки для всіх дуг f(x,y)=c(x,y), кожна дуга може бути віднесена до множини І, при цьому і(x,y)=c(x,y)-f(x,y)=c(x,y). Оскільки f(x,y)=0, тому на цьому кроці ні одну з дуг неможливо включити в множину R.
Крок 3. Використовується алгоритм пошуку збільшуючого ланцюга для визначення відповідного ланцюга з “s” в “t”.
З прикладу (рис. 6) видно, що у графі є декілька таких збільшуючих ланцюгів: sabt, sact, sbact, sbt.
Рис.6
S
a
b
c
t
S
0
0
0
0
0
a
2
0
2
0
0
b
5
3
0
0
0
c
0
4
0
0
0
t
0
0
2
1
0
Допустимо, що у використаному алгоритмі на даному кроці формується ланцюг sabt. Максимальне збільшення потоку по цьому ланцюгу
min{i(s,a), i(a,b), i(b,t)=min{2,3,2}=2.
Отже потік в цих трьох дугах збільшиться на дві одиниці. Після цього переходимо на крок 2.
Крок 2. Для нових значень потоку в дугах вхідного графа перераховуються величини і(х,у) і r(x,e); окрім цього, коректуються множини I і R:
f(s,a)=2=c(s,a) (s,a) (I (s,a)( R, r(s,a)=2,
f(a,b)=2<c(a,b) (a,b)(I, i(a,b)=1 (a,b)( R, r(a,b)=2,
f(b,t)=2=c(b,t) (b,t) (I (b,t) ( R, r(b,t)=2,
f(s,b)=0<c(s,b) (s,b)(I, i(s,b)=3 (s,b)( R,
f(a,c)=0<c(a,c) (a,c)(I, i(a,c)=4 (a,c)( R,
f(c,t)=0<c(c,t) (c,t)(I, i(c,t)=1 (c,t) ( R.
Крок 3: Знову використовується алгоритм пошуку збільшуючого ланцюга для визначення відповідного ланцюга з “s” в “t”. В даному випадку ланцюг, що збільшує потік, єдиний - це ланцюг (s,b), (b,a), (a,c), (c,t). Його і
формує алгоритм. Максимально можливе збільшення потоку вздовж знайденого ланцюга дорівнює:
min {i(s,b), r(a,b), i(a,c)} i(c,t) = min {5,2,4,1} = 1
Таким чином, з вершини “s” в вершину “t“ може бути додатково пропущена одиниця потоку. При цьому значення потоку в кожній з трьох прямих дуг (s,b), (a,c) i (c,t), що належать знайденому ланцюгу, на одиницю збільшується, а значення потоку в зворотній дузі (a,b) цього ланцюга на одиницю зменшується. Тепер потоки в дугах графа, що розглядається, будуть мати наступні значення:
f(s,a)=2, f(a,b)=2, f(b,t)}=2, f(s,b)=1, f(a,c)=1, f(c,t)=1.
Кожна з цих трьох одиниць побудованого до цього моменту потоку проходить по наступним маршрутам:
1 одиниця проходить з “s” в “t” по шляху (s,a), (a,b), (b,t);
1 одиниця проходить з “s” в “t” по шляху (s,b), (b,t);
1 одиниця проходить з “s” в “t” по шляху (s,a), (a,c), (c,t)
Далі здійснюється повернення до кроку 2.
Крок 2. Для нових значень потоку в дугах вхідного графа перераховуються величини і(х,у) і r(x,e). Крім цього, коректується множини склад множин I і R:
f(s,a)=2=c(s,a) (s,a)(I (s,a)(R, r(s,a)=2,
f(a,b)=1<c(a,b) (a,b)(I, i(a,b)=2 (a,b)(R, r(a,b)=1,
f(b,t)=2=c(b,t) (b,t)(I (b,t)(R, r(b,t)=2,
f(s,b)=1<c(s,a) (s,a)(I, i(s,b)=2 (s,a)(R, r(s,a)=1,
f(a,c)=1<c(a,c) (a,c)(I, i(a,c)=3 (a,c)(R, r(a,c)=1,
f(c,t)=1<c(c,t) i(c,t)(I (c,t)(R, r(c,t)=1.
Крок 3. Знову використовується алгоритм пошуку збільшуючого ланцюга для визначення відповідного ланцюга з “s” в “t”. При цьому виявляється, що при біжучих значеннях потоку в дугах графа в ньому не існує ні одного збільшуючого ланцюга. В процесі виконання алгоритму у вихідному графі виявляються розфарбованими вершинами “s”, “b”, “a”, “c” (причому у вказаному порядку), однак вершина “t” не розфарбовується. Оскільки ланцюг, що збільшує потік, знайти не вдається, алгоритм пошуку максимального потоку завершує свою роботу. Останній з побудованих потоків є максимальним. Тобто в розглянутому прикладі з “s” в “t” може бути додатково пропущено 3 одиниці потоку.
Відмітимо, що останнє застосування алгоритму пошуку збільшуючого ланцюга приводить до розрізу з дуг (b,t),(c,t), що мають на одній кінцевій і одній незафарбованій вершини. Пропускна здатність цього розрізу рівна с(b,c)+с(c,t)=2+1=3, що співпадає з мінімально можливим числом одиниць потоку з “s” в “t”.
3. КОНТРОЛЬНІ ЗАПИТАННЯ
Які Ви знаєте потокові алгоритми і яка схема їх вкладеності?
Які основні ідеї кожного з потокових алгоритмів?
Розкрити і зобразити блок-схему одного з потокових алгоритмів.
4. ЛАБОРАТОРНЕ ЗАВДАННЯ
Підготувати вхідне завдання на ЕОМ за зразком описаним в інструкції(додається) для роботи з учбовою програмою.
Отримати у викладача індивідуальне завдання.
Запустити на виконання програму, що вирішує задачу пошуку збільшуючого ланцюга.
Проглянути результат роботи програми. Результат роботи програми, що шукає збільшуючий ланцюг, може бути позитивний (стік є розфарбований) або негативний (стік не вдається розфарбувати).
У випадку, коли результат позитивний (або негативний) необхідно модифікувати граф (коректуючи два або три зв’язки), що дозволить знайти такий граф, на якому стік, відповідно, не вдається розфарбувати (розфарбовується).
Підготовити вхідне завдання на ЕОМ для пошуку максимального потоку за зразком, описаним в інструкції для роботи з учбовою програмою.
Запустити на виконання програму, що вирішує задачу пошуку максимального потоку.
Проглянути результат роботи програми. Вибрати маршрут, який має максимальне збільшення потоку, за зразком, описаним в інструкції для роботи з учбовою програмою.
Зафіксувати результати роботи.
Оформити і захистити звіт.
5. ЗМІСТ ЗВІТУ
Описи і блок-схеми для алгоритмів пошуку збільшуючого ланцюга і пошуку максимального потоку.
Нарисувати графи і записати вхідні дані.
Записати проміжні дані і результати розрахунків (ланцюг і потік).
Висновки.
6. ЛІТЕРАТУРА
Оре О. Теория графов. -М.: Наука. Главная редакция физико- математической литературы, 1980. -336с.
Асельдеров З.М. и др. Представление графов и операции над ними. -Киев, 1987. 18с.
Зыков А.А. Основы теории графов. -М.: Наука, 1987. -384с.
Оцуки Т. Эвристические алгоритмы для комбинаторных задач с большим обьемом вычислений. “Дэнси цусим гакайси”. 1975. 58. N4. -С.416-423.
Е. Майніка “ Алгоритмы оптимизации на сетячх и графах. “Москва, “ Мир “, 1981.
НАВЧАЛЬНЕ ВИДАННЯ
ПОТОКОВІ АЛГОРИТМИ
І Н С Т Р У К Ц І Я
до лабораторної роботи № 1
з курсу
“Дискретні моделі в САПР”
для базового напрямку 6.0804 “Комп’ютерні науки”
Укладачі: Володимир Іванович Каркульовський
Сергій Петрович Ткаченко
Ігор Іванович Чура
Редактор
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора