Алгоритми побудови паралельних упорядкувань, засновані на аналізі структури графів
Точний алгоритм поліноміальної складності для спеціального підкласу графів, а для другої наближений алгоритм для довільних ациклічних графів. Виділення підкласів графів, для яких існують точні алгоритми поліноміальної складності розв'язання задачі.
| Рубрика | Математика |
| Вид | статья |
| Язык | украинский |
| Дата добавления | 02.10.2024 |
| Размер файла | 1,7 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Алгоритми побудови паралельних упорядкувань, засновані на аналізі структури графів
Васильковим Поліна Олександрівна
здобувач вищої освіти факультету прикладної математики Дніпровський національний університет імені Олеся Гончара, Україна
Науковий керівник: Турчина Валентина Андріївна
канд. фіз.-мат. наук, доцент, зав.каф. обчислювальної математики та
математичної кібернетики
Дніпровський національний університет імені Олеся Гончара, Україна
Анотація
В статті запропоновано два нових алгоритми розв'язання відомих задач паралельного упорядкування вершин орграфів. Такі задачі виникають при визначенні оптимального порядку виконання скінченої множини завдань, на порядок виконання яких накладаються певні технологічні обмеження. Одна із задач полягає в мінімізації часу виконання при заданій кількості ресурсів, а друга (двоїста до неї) в мінімізації обсягу ресурсів при заданому часі, до якого виконання повинне завершитись. Для першої задачі запроповано точний алгоритм поліноміальної складності для спеціального підкласу графів, а для другої наближений алгоритм для довільних ациклічних графів.
Ключові слова: орієнтовані ациклічні графи, паралельні упорядкування, довжина, ширина упорядкування, точні та наближені алгоритми.
Задачі, що розглядаються в даній роботі, виникають в тих прикладних сферах, які пов'язані з організацією оптимального виконання частково впорядкованих завдань. Вони виникають на виробництві пов'язаному з випуском продукції на конвеєрах, при будівництві житлових об'єктів, при побудові паралельних форм алгоритмів. їх специфікою є те, що моделями, які задають частковий порядок, можуть бути орієнтовані ациклічні графи.
При розв'язанні задач в класичній постановці виходять з припущення, що будь-яке завдання може виконувати будь-який виконавець, а час виконання кожного завдання однаковий.
Задача 1 ациклічна графа задача алгоритм
По заданому графу G = {V, U} і заданій величині h розподілити елементи множини V на мінімальну кількість місць, так щоб на кожному місці стояло на більше h вершин і їх порядок в даному розподілі не прорушував технологічні обмеження.
Розподіл, який є допустимим розв'язком даної задачі називають паралельним упорядкуванням.
Задача 2
По заданому графу G = {V, U} і заданій кількості місць l розподілити елементи множини V на ці місця так, щоб максимальна кількість елементів на цих місцях була мінімальною і не порушувалися технологічні обмеження.
Це задачі комбінаторної оптимізації і вони відноситься до класу NP - повних [1]. В загальному випадку точний розв'язок цих задач можна знаходити алгоритмами, заснованими на схемах направленого перебору. Одним із них являється метод гілок та меж, який має експоненційну складність. Ще одним точним методом розв'язання задач в загальному випадку є метод, що заснований на сітковому підході. Він базується на узагальненні відомої задачі про максимальний умовний потік [2].
Для побудови упорядкування у графі типу вхідне дерево або ліс при заданому h, запропоновано наступний алгоритм:
1. Нехай задано вхідне дерево T. Помічаємо вершини дерева.
1.1. і := 1.
1.2. Шукаємо в T множину вершин, в які не входять дуги, і кожній з них приписуємо мітку і.
1.3. Якщо всі вершини дерева помічені переходимо на пункт 2.
1.4. Видаляємо помічені вершини разом з вихідними дугами із Т.
1.5. T := T, і := і+1 і переходимо до 1.2.
2. Зміна поміток дерева.
2.1. Вводимо всім вершинам графу новий атрибут changed, що буде показувати стан помітки вершини на кожній ітерації.
2.2. j := 1.
2.3. Якщо j дорівнює мітці кореневої вершини, переходимо до пункту 3.
2.4. Встановлюємо для кожної вершини значення атрибуту changed := false, що показує, що на даному етапі помітки вершин ще не змінювали.
2.5. Визначимо r - кількість вершин з міткою j. Якщо r < h, то переходимо на пункт 2.7.
2.6. Викликаємо функцію «Видалити одну вершину з M», на вхід їй передаємо мітку j та множину M, потім переходимо на пункт 2.5.
2.7. j:=j+1, переходимо до 2.3.
3. Побудова упорядкування. Ставимо вершини дерева на місця, яким відповідають їх мітки.
Функція «видалити одну вершину з M»
START
INPUT j - мітка вершин, М - множина вершин з міткою j
int max :=j
int num := номер кореневої вершини
FOR для і від 1 до кількість дуг у графі
IF (вершина, з якої виходить дуга і належить множині M AND max < мітка вершини, в яку входить дуга і) THEN
max := мітка вершини в, яку входить дуга і num := номер вершини, з якої виходить і ENDIF
ENDFOR
IF (max > j + 1) THEN
Збільшуємо помітку вершини num на 1 І відмічаємо, що помітку змінено (changed := true)
ELSE
IF (num - номер кореневої вершини) THEN Збільшуємо помітку кореневої вершини на 1 ELSE
Створюємо нову множину F FOR для і від 1 до n
IF (мітка вершини і дорівнює j + 1 AND Помітку вершини не змінювали (changed == false)) THEN
Додаємо вершину і до множини F ENDIF ENDFOR
Викликаємо функцію «Видалити одну вершину» на вхід
передаємо F та j + 1
Викликаємо функцію «Видалити одну вершину» на вхід передаємо M та j ENDIF
ENDIF
END
Приклад роботи алгоритма.
Маємо граф (рис 1.) та h = 4.
Спочатку розставляємо мітки за першим етапом алгоритму (ри c 2.).
Далі переходимо до другого етапу. Послідовно збільшуємо мітки вершин і зупиняємось, коли їх кількість для кожного номера буде не перевищувати h.
Рис. 1. Приклад вхідного дерева
Вершини, у яких мітка змінюється при j = 1, виділені червоним (рис 2.
Рис. 2. Граф з мітками
|
1 |
4 |
9 |
13 |
17 |
21 |
|
|
2 |
5 |
10 |
14 |
18 |
||
|
3 |
7 |
11 |
15 |
19 |
||
|
6 |
8 |
12 |
16 |
20 |
Отримали граф з новими мітками.
Тепер ставимо вершини на місця, що відповідають їх міткам (рис 3.):
Рис. 3. Граф з розставленими вершинами на місця
Запропонований вище алгоритм розв'язання задачі 1 відрізняється від відомого двохетапного алгоритму [3] тим, що уточнені помітки вершин фактично вказують місця, на які потрібно розмістити вершини графа. А також, ці помітки можуть бути використані при отриманні оцінок для довжини упорядкування.
Наближений алгоритм розв'язання задачі 2
Нехай Ікр - довжина критичного шляху у графі.
S та S - спеціальні упорядкування довжини Ікр, в яких визначені для k-тої вершини графу її крайнє ліве дk та крайнє праве рк допустимі місця в цих упорядкуваннях.
Розглянемо алгоритм побудови упорядкування мінімальної ширини по заданому графу G при І=Ікр.
Спочатку оцінимо знизу значення величини, що мінімізуємо, тобто ширину упорядкування. Наприклад, можна скористатися інтуїтивно зрозумілою оцінкою: (fnlh(s),h(s)).
де:
h - ширина, яку мініміуємо; n - кількість вершин графу;
І - задана довжина упорядкування; h(S) - ширина упорядкування S; h(S) - ширина упорядкування S.
1. Розстановка поміток для вершин упорядкування S .
1.1. і = 1.
1.2. У графі G визначаємо множину вершин, що не мають вхідних дуг. Присвоюємо їм помітку рк = і (де k - номер вершини) та видаляємо їх з графу разом із вихідними дугами.
1.3. Якщо у графі всі вершини помічені, переходимо до пункту 2. Інакше G=G, і=і+1 і переходмо до 1.2.
2. Розстановка поміток для вершин упорядкування S.
2.1. j = і.
2.2. У графі G визначаємо множину вершин, що не мають вихідних дуг. Присвоюємо цим вершинам помітку рк = j (де k - номер вершини) та видаляємо з їх графу разом з вхідними дугами.
2.3. Якщо всі вершини помічені, переходимо до пункту 3. Інакше G :=G, j :=j-1 і переходмо до 2.2.
3. Побудова упорядкування.
3.1. Вершини у яких помітки рк: = рк стоять на критичних шляхах, тому їх місця в упорядкуванні, що будується, визначені однозначно і заносимо їх на відповідні місця.
3.2. Оберемо те значення h, на якому (1) виконується як рівність.
3.3.
3.4. r := 1.
3.5. pr := Я - |S[r]|.
3.6. Ящко pr = 0, то переходмо на 3.7.
Інакше, шукаємо в графі G множину вершин, які не занесені в упорядкування і не мають вхідних дуг. Вершини у яких
r є [min(jufc,jufc); max(jufc,jufc)], записуємо у список P у порядку не спадання
модуля
3.7. Перші pr вершин зі списку Р ставимо на місце r та видаляємо їх з графу G разом із вихідними дугами.
3.8. Якщо r < l, то r := r + 1, G := G, очищуємо список P і переходимо на пункт 3.4.
3.9. Якщо не всі вершини поставлені на місця, Я = Я + 1, меншу помітку вершин, що не стоять на місці, змінюємо на помітку, що на 1 більше найбільшого місця вершин, з яких входять дуги в дані і які отримали місце в упорядкуванні, повертаємось до початкового графу і переходимо на крок 3.3.
Приклад роботи алгоритма.
Маємо задані величини:
N = 13, L = 5 та граф G.
Розставляємо помітки за 1 та 2 пунктами алгоритму (рис 4.).
Рис. 4. Граф з помітками
Далі виконуємо 3 етап. Визначаємо pr та заповнюємо список P.
p1 = 2 P = 6p2 = 2 P = 7p3 = 2 P = 8, 9, 10, 11, 12
p4 = 2 P = 10, 11, 12 p5 = 2 P = 13
3:4:5:
345
8 1013
9 11
Бачимо, що вершина «12» не отримала місце в упорядкуванні. Збульшуємо h.
h= h + 1 = 4 .
Знов визначаємо pr та заповнюємо список P. p1 = 2 P = 0p2 = 2 P = 0p3 = 1 P
p4 = 1 P = 0p5 = 1 P = 0
Отримали упорядкування S ширини h = 4:
1:2:3:4:
1234
67810
911
12
Подальшого дослідження потребують наступні питання: виділення підкласів графів, для яких існують точні алгоритми поліноміальної складності розв'язання задачі 2 ; оцінка похибки алгоритму, запропонованого для задачі 1, при застосуванні його для довільних графів.
Список використаних джерел:
[1] Коффман Э.Г. (ред.) (1984). Теория расписаний и вычислительные машины. Москва: Наука.
[2] Бурдюк, В. Я. & Турчина, В. А. (1985). Алгоритмы параллельного упорядочения: Учебное пособие. Днепропетровск: ДГУ.
[3] Hu, T. C. (1961). Parallel sequencing and assembly line problems. Operations research,
Размещено на Allbest.ru
...Подобные документы
Теорія графів та її використання у різних галузях. У фізиці: для побудови схем для розв’язання задач. У біології: для розв’язання задач з генетики. Спрощення розв’язання задач з електротехніки за допомогою графів. Математичні розваги і головоломки.
научная работа [2,1 M], добавлен 10.05.2009Оцінки для числа ребер з компонентами зв‘язності. Орієнтовані графи, графи з петлями, графи з паралельними дугами. Ойлерова ломиголовка "Кенігзберзьких мостів". Основні поняття та означення ойлерових графів. Сутність та поняття гамільтонових графів.
курсовая работа [2,6 M], добавлен 18.07.2010Необхідні поняття теорії графів. Задача про максимальний потік. Алгоритм Форда знаходження максимального потоку. Модифікація алгоритму Форда розв’язання задачі максимізації кількості призначень у задачах розподілу. Результати числового експерименту.
курсовая работа [499,9 K], добавлен 18.12.2013Основні положення теорії графов. Алгоритм розфарбування графу методом неявного перебору. Задання графу матрицею суміжності. Особливості програмної реалізації на мові Turbo Pascal алгоритму оптимального розфарбування вершин завантаженого з файлу графа.
курсовая работа [557,1 K], добавлен 15.06.2014Історія виникнення графів, основні поняття теорії та різновиди: повні, регулярні, платонові, двочастинні. Маршрути, ланцюги і цикли. Означення гамільтонового та напівгамільтонового графа, достатні умови. Задача побудови гамільтонових циклів у графі.
курсовая работа [327,7 K], добавлен 22.01.2013Етапи розв'язування інженерних задач на ЕОМ. Цілі, засоби й методи моделювання. Створення математичної моделі. Побудова обчислювальної моделі. Реалізація методу обчислень. Розв’язання нелінійних рівнянь методом дихотомії. Алгоритм метода дихотомії.
контрольная работа [86,1 K], добавлен 06.08.2010Історія виникнення лабіринту. Лабіринт крітського царя Міноса - одне із семи чудес світу. Перші здогади "Правило руки". Лабіринти і замкнені криві, розв'язування різних лабіринтних задач, застосування елементів теорії графів і теорії ймовірностей.
реферат [7,3 M], добавлен 29.09.2009Задачі обчислювальної математики. Алгоритми розв'язування багатьох стандартних задач обчислювальної математики. Обчислення інтерполяційного полінома Лагранжа для заданої функції. Виконання обчислення першої похідної на основі другої формули Ньютона.
контрольная работа [67,1 K], добавлен 27.03.2012Поняття та структура інтелекту людини. Процес формування інтелектуальних вмінь і навичок у молодших школярів. Особливості інтелектуального розвитку молодших школярів у процесі навчання математики. Специфіка розв'язання задач підвищеної складності.
курсовая работа [45,7 K], добавлен 20.03.2013Поняття та особливості алгоритмів обчислювальних процедур. Операторні та предикатні алгоритми, їх характеристика, порядок та принципи формування, етапи розв'язання. Алгоритмічні проблеми для L. Логіка висловлень та предикатів в представленні знань.
курс лекций [96,3 K], добавлен 25.03.2011Нове уточнення поняття алгоритму вітчизняним математиком Марковим: 7 уточнених ним параметрів. Побудова алгоритмів з алгоритмів. Універсальний набір дій по управлінню обчислювальним процесом. Нормальні алгоритми Маркова. Правило розміщення результату.
реферат [48,7 K], добавлен 30.03.2009Розв'язання графічним методом математичної моделі задачі з організації випуску продукції. Розв'язання транспортної задачі методом потенціалів. Знаходження умовних екстремумів функцій методом множників Лагранжа. Розв'язання задач симплекс-методом.
контрольная работа [48,5 K], добавлен 16.07.2010Історія виникнення відсотків, сутність цього терміна. Розв’язання задач на їх визначення за допомогою пропорцій. Добірка текстових завдань, які розв’язуються шляхом розрахунку розміру складних відсотків. Методи вирішення задач на суміші та сплави.
реферат [72,7 K], добавлен 02.12.2015Розв'язання завдання графічним способом. Зображення розв'язку системи нерівностей, визначення досягнення максимуму та мінімуму функції. Розв'язання транспортної задачі методом потенціалів та симплекс-методом, формування оціночної матриці з елементів.
задача [134,9 K], добавлен 31.05.2010Лінійні діофантові рівняння. Невизначені рівняння вищих порядків. Невизначене рівняння Ферма. Приклади розв’язання лінійних діофантових рівнянь та системи лінійних діофантових рівнянь. Алгоритми знаходження всіх цілочисельних розв’язків рівнянь.
курсовая работа [1,7 M], добавлен 29.12.2010Диференціальні рівняння другого порядку, які допускають пониження порядку. Лінійні диференціальні рівняння II порядку зі сталими коефіцієнтами. Метод варіації довільних сталих як загальний метод розв’язування та й приклад розв’язання задачі Коші.
лекция [202,1 K], добавлен 30.04.2014Розв'язання системи лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць. Будування математичної моделі задачі лінійного програмування. Умови для застосування симплекс-методу. Розв'язка спряженої задачі.
практическая работа [42,3 K], добавлен 09.11.2009Поняття та значення симплекс-методу як особливого методу розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального рішення. Розв'язання задачі з використанням програми Simplex Win.
лабораторная работа [264,1 K], добавлен 30.03.2015Послідовність графічного розв'язання задачі лінійного програмування. Сумісна система лінійних нерівностей, умови невід'ємності, визначення півплощини з граничними прямими. Графічний метод для визначення оптимального плану задачі лінійного програмування.
задача [320,6 K], добавлен 31.05.2010Прийоми розв’язання задач в першому і другому степені на Далекому Сході та Греції. Досягнення арабських математиків в області алгебраїчних рівнянь. Розв'язання похідного кубічного рівняння. Найвидатніші теореми про радикали вищих степенів, їх розв’язання.
курсовая работа [536,1 K], добавлен 23.02.2014
