Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Потокові алгоритми
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКНІ
Факультет:
Комп’ютерні науки
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2015
Тип роботи:
Лабораторна робота
Предмет:
Дискретні моделі в САПР
Частина тексту файла (без зображень, графіків і формул):
НУЛП, ІКНІ, САПР
Тема
оцінка
підпис
Потокові алгоритми
№ залікової:
Дискретні моделі в САПР
Викладач:
Мета роботи : метою даної лабораторної роботи є вивчення потокових алгоритмів.
Короткі теоретичні відомості :
Останнім часом значно зросла зацікавленість учених та практиків потоковими моделями. Це пов’язано із впровадженням та активним розвитком різноманітних територіально розподілених систем: трубопровідних, транспортних, телекомунікаційних та ін. Основою таких систем є певна мережа (мережа трубопроводів, доріг, каналів зв’язку тощо), в якій циркулюють певні потоки (потоки речовин, транспорту, даних тощо), тому задачі, які доводиться розв’язувати при проектуванні та експлуатації систем з мережною структурою, часто зводяться до розробки математичних моделей розподілу потоків та постановки і розв’язання відповідних оптимізаційних задач. Відомі моделі розподілу потоків у мережах базуються на поняттях теорії графів. Це пов’язано з тим, що граф дає можливість наочно відобразити структуру мережі, а параметри його вузлів і дуг – представити основними числовими характеристиками її елементів. Набір характеристик залежить від природи модельованої системи, а також характеру розв’язуваних задач, однак у потокових моделях їх, як правило, представляють такими параметрами, як зовнішній потік у вузлі, потік по дузі, пропускна здатність дуги, вартість передавання одиниці потоку по дузі тощо. Потокові задачі, як правило, зводяться до пошуку такого розподілу потоків у мережі, при якому б забезпечувався екстремум деякого критерію. При цьому мають враховуватися обмеження, що накладаються умовами збереження потоків у вузлах і неперевищення потоками пропускної здатності дуг. Типовими потоковими задачами є задача про потік мінімальної вартості, про максимальний потік, транспортна задача, задача про призначення та інші. Для їх розв’язання
розроблено чимало ефективних алгоритмів, сформувався навіть відповідний напрям обчислювальних методів під назвою потокового програмування. Потік-визначає спосіб пересилання деяких об’єктів з одного пункту в інший. Розв’язання задачі потоку зводиться до таких основних підзадач:
максимізація сумарного обсягу перевезень;
мінімізація вартості пересилань предметів з одного пункту в інший;
мінімізація часу перевезень в заданій системі. Реалізація алгоритму (Java) :
int maxFlow = 0;//Початковий максимальний потік int pathFlow;//Тимчасовий потік int[][] residualGraph = new int[numberOfVertices + 1][numberOfVertices + 1];//Залишкова матриця ваг графу /* Копіювання матриці ваг в залишуову матрицю */ for (int sourceVertex = 1; sourceVertex <= numberOfVertices; sourceVertex++) { for (int destinationVertex = 1; destinationVertex <= numberOfVertices; destinationVertex++) { residualGraph[sourceVertex][destinationVertex] = graph[sourceVertex][destinationVertex]; } } /* Доки шлях існує знаходимо найкращий потік */ while (bfs(source ,destination, residualGraph)) { pathFlow = Integer.MAX_VALUE; for (v = destination; v != source; v = parent[v]) { u = parent[v]; pathFlow = Math.min(pathFlow, residualGraph[u][v]); } for (v = destination; v != source; v = parent[v]) { u = parent[v]; residualGraph[u][v] -= pathFlow; residualGraph[v][u] += pathFlow; System.out.println(v + " до " + u); } System.out.println(pathFlow); maxFlow += pathFlow; } return maxFlow; }
Інструкція по експлуатації:
Для роботи програми необхідно запустити файл Lab_3_DM.java . Спочатку необхідно ввести кількість вершин графа, далі матрицю ваг, початкову та кінцеву точки потоку. Далі програма знаходить максимальний потік та виводить його значення.
Граф:
Результат виконання:
***HELP***
0. Програма знаходить максимальний потік в графі!
Для коректної роботи програми необхідно:
1. Ввести кількість вершин графу.
2. Ввести матрицю ваг(цілі числа).
3. Ввести початкову та кінцеву точку потоку.
4. Нумерація вершин графа починається з 1 з інкрементом в 1 (1,2,3...) !
Введіть кількість вершин:4
Введіть матрицю ваг:
0 5 2 0
0 0 3 4
0 0 0 1
0 0 0 0
Введіть стартову вершину:1
Введіть кінцеву вершину:4
4 до 2
2 до 1
4
4 до 3
3 до 1
1
Максимальний потік становить:5
Висновок : в результаті виконання лабораторної роботи я вивчив алгоритм Форда-Фалкерсона для знаходження максимального потоку та реалізував йог на мові Java .
13.05.2016 23:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора