Математична модель задачі

Вступ

З метою закріплення знань і навичок по вирішенню задач оптимізаційного характеру в рамках даної курсової роботи мені була поставлена наступна задача:

Знайти найкоротшу відстань і маршрут від заводу збірного залізобетону, що знаходяться в пункті 0 до будівельних майданчиків 1-8 при заданій схемі автомобільних шляхів(рис 1.) Знайти також найкоротший шлях холостого пробігу машини за умови, що частина доріг має односторонній напрямок руху (вказано стрілками на схемі)

Рис. 1 задана схема автомобільних шляхів

Числа приписані дугам, дорівнюють відстаням між відповідними пунктами.

Для вирішення задачі будемо використовувати алгоритм Флойда, який дозволяє знайти найкоротший шлях між кожною парою вузлів. На вхід алгоритму потрібна початкова матриця відстаней, яка представлена а табл. 1.

			∞	∞	∞	∞	∞	∞	∞	∞
							∞	∞	∞	∞	∞
	∞			∞	∞	∞	∞	∞	∞
	∞		∞					∞	∞	∞	∞
	∞		∞					∞	∞	∞	∞
	∞		∞				∞	∞	∞	∞	∞
	∞	∞	∞			∞		∞		∞	∞
	∞	∞	∞	∞	∞		∞				∞
	∞	∞	∞	∞		∞					∞
	∞	∞		∞	∞	∞	∞
		∞		∞	∞	∞	∞	∞	∞

Табл.1. Початкова матриця відстаней

0- це будівельні майданчики

1-8 позначається маршрут від заводу збірного залізобетону

3. Обґрунтування вибору методу та алгоритму розв’язання

Існує компактний за записом алгоритм Флойда-Уоршелла. В зв’язку із цим ми і обрали цей метод для вирішення завдання курсової роботи.

Запишемо сам алгоритм:

1. Визначити вершину графа k = 1, через яку буде здійснюватися перерахунок відстані між вершинами і та j.

2.Визначити вершину і = 1.
3. Визначити вершину j = 1,

4. Якщо величина d_{j, k} + d_k,j менша за значення d_i,j,то замінити значення d_i,j на d_{i, k} + d_k,і. В іншому разі залишити зна­чення d_i,j без змін.

5. Якщо j < = п, то перейти до наступної вершини j+ 1 і повер­нутися до п. 4.

6. Якщо i<= п, то перейти до наступної вершини і + 1 і повернутися до п. 3.

7. Якщо k<=n, топерейти до наступної вершини k + 1 і повер­нутися до п. 2,

8. Завершити алгоритм.

У результаті виконання алгоритму елементи d_i,j будуть міс­тити найкоротшу відстань між відповідними вершинами графа і та j.

Можна вирішити цю задачу, послідовно застосовуючи алгоритм Дейкстри для кожної вершини. Але існує прямий спосіб рішення даної задачі, що використовує алгоритм Флойда. Для визначеності припустимо, що вершини графа послідовно пронумеровані від 0 до n. Алгоритм Флойда використовує матрицю А розміру n х n, у якій обчислюються довжини найкоротших шляхів. Спочатку для всіх . Якщо дуга відсутня, то . Кожен діагональний елемент матриці А дорівнює 0.

Над матрицею А виконується n ітерацій. Після k-ї ітерації містить значення найменшої довжини шляхів з вершини i вершину j, що не проходять через вершини з номером, великим k. Іншими словами, між кінцевими вершинами шляху I та j можуть знаходитися тільки вершини, номера яких менші чи рівні k.

На k-й ітерації для обчислення матриці А застосовується наступна формула:

Нижній індекс k позначає значення матриці А після k-ї ітерації, але це не означає, що існує n різних матриць, цей індекс використовується для скорочення запису. Графічна інтерпретація цієї формули показана на рис. 1

Рис 1.

Три вкладені цикли містять операцію, яка виконується сталий час. тобто алгоритм має кубічну складність, при цьому простим розширенням можна отримати також інформацію про найкоротші шляхи — крім відстані між двома вузлами записувати в матрицю ідентифікатор першого вузла в дорозі.

Алгоритм Флойда-Уоршелла може бути використаний для знаходження замикання відносини по транзитивності. Для цього в якості W[0] використовується бінарна матриця суміжності графа, ; оператор min замінюється диз'юнкцією, додавання замінюється кон'юнкцією:

for k = 1 to n for i = 1 to n for j = 1 to n W[i][j] = W[i][j] or (W[i][k] and W[k][j])

Після виконання алгоритму матриця W є матрицею досяжності.

Дата добавления: 2015-08-31