Ім'я файлу: уаепувапвапвапвапа.docx
Розширення: docx
Розмір: 83кб.
Дата: 22.09.2020
скачати

ываап

Практична робота № 2

з дослідження операцій в транспортних системах студентки групи МП 2-2 Маркиної Ельзи

Номер у журналі академічної групи - 9

Номер залікової книжки – 49092

Розглянемо задачу пошуку найкоротшого маршруту (шляху) на графі (у сенсі найкоротшої відстані). Задано граф G, у якому кожному ребру приписана позитивна вага.

Граф – математична структура, яка складається з вершин графу і ребер (дуг), які об’єднують цей граф у єдине ціле.

Довжина шляху в такій постановці дорівнює сумі довжин ребер, що складають цей шлях. Задача зводиться до пошуку найкоротшого шляху між двома заданими вершинами графа G. Нехай є орієнтований граф G: G = (V; Е), у якого всі дуги мають позитивні вартості, а одна вершина визначена як джерело.

Завдання полягає у пошуку вартості найкоротших шляхів від джерела до усіх інших вершин графа G.

Представимо граф G у вигляді карти рейсових маршрутів з одного міста у інший, де кожна вершина відповідає місту, а друга V → W – рейсовому маршруту з міста V до міста W. Таким чином мітка дуги V → W – це час переїзду з міста V у місто W. При цьому може виникнути припущення, що в даному випадку у якості моделі більше підходить неорієнтований граф, оскільки мітки дуг V → W і W → V можуть збігатися, але допущення про збіг цих міток принципово не впливає на рішення поставленої задачі. Таким чином, для рішення поставленої задачі будемо використовувати алгоритм Деікстри. Накреслимо наш неорієнтований граф:



Цей алгоритм будує множину вершин S для яких найкоротші шляхи від джерела (вершина А 1 (1)) уже відомі. На кожному кроці до множини S додається та з вершин, яка залишилась, відстань до якої від джерела менша , ніж від інших вершин, що залишились.

Якщо вартості всіх дуг – позитивні, то можна бути упевненим, що найкоротший шлях (маршрут) від джерела до вершини проходить тільки через вершини множини S. Назвемо такий шлях особливим.

На кожному кроці алгоритму (методу) використовується масив D, у який записуються довжини найкоротших особливих шляхів до кожної вершини. Коли множина S буде містити усі вершини графа G, тобто для усіх вершин будуть знайдені особливі шляхи, тоді масив D буде містити довжини найкоротших шляхів від джерела до кожної вершини.

С – двовимірний масив, який містить вартості перевезення одиниці вантажу між усіма транспортними вузлами ДТМ.

1 2 3 4 5 6 7



1

5

4

6





1



4





2

2

5

4



3





2

4



3



5



3

6





5



6





2





6



2



2

2

3



2



1

2

3

С= 4


5

6

7

Для опрацювання блок-схеми алгоритму побудуємо наступну таблицю:



Крок

S

W







D/P







2

3

4

5

6

7

Початок

1

-

1/1

5/1

4/1

6/1





1

1,2

2

-

5/1

4/1

6/1

3/2

3/2

2

1,2,6

6

-

5/1

4/1

6/1

-



3

1,2,4,6

4

-

5/1

-

6/1

-

7/4

4

1,2,4,5,6

5

-

5/1

-

-

-



5

1,2,3,4,5,6

3

-

-

-

-

-

7/3

6

1,2,3,4,5,6,7

7

-

-

-

-

-

-



𝐃[𝐕] = 𝐦𝐢𝐧(𝐃[𝐕],𝐃[𝐖]+ 𝐂[𝐖,𝐕])

(𝐃[𝐖]+ 𝐂[𝐖,𝐕]) < 𝐃[𝐕]

Крок 1:

V=3: D [3] = min (D [3], D [2]+C [2,3]) = min(5,1+4) = 5

(D[2] + C[2,3]) < D[3]

1 + 4 < 5 - умова не виконується

V=4: D [4] = min (D [4], D[2]+C[2,4]) = min(4,1+∞) = 4

(D[2] + C[2,4]) < D[4]

1 + ∞ < 4 - умова не виконується

V=5: D[5] = min(D[5],D[2]+C[2,5]) = min(6,1+∞) = 6

(D[2] + C[2,5]) < D[5]

1 + ∞ < 6 – умова не виконується

V=6: D[6] = min(D[6],D[2]+C[2,6]) = min(∞,1+2) = 3

(D[2] + C[2,6]) < D[6]

1 + 2 < ∞ - умова виконується

P[V] = W P[6] = 2

V=7: D[7] = min(D[7],D[2]+C[2,7]) = min(∞,1+2) = 3

(D[2] + C[2,7]) < D[7]

1 + 2 < ∞ - умова виконується

P[V] = W P[7] = 2

Крок 2

V=3: D[3] = min(D[3],D[6]+C[6,3]) = min(5, ∞+∞) = 5

(D[6] + C[6,3]) < D[3]

∞ + ∞ < 5 - умова не виконується

V=4: D[4] = min(D[4],D[6]+C[6,4]) = min(4, ∞+∞) = 4

(D[6] + C[6,4]) < D[4]

∞ + ∞ < 4 - умова не виконується

V=5: D[5] = min(D[5],D[6]+C[6,5]) = min(6, ∞+6) = 6

(D[6] + C[6,5]) < D[5]

∞ + 6 < 6 - умова не виконується

V=7: D[7] = min(D[7],D[6]+C[6,7]) = min(∞,∞+2) =∞

(D[6] + C[6,7]) < D[7]

∞ + 2 < ∞ - умова не виконується

Крок 3

V=3: D[3] = min(D[3],D[4]+C[4,3]) = min(5,4+3) = 5

(D[4] + C[4,3]) < D[3]

4 + 3 < 5 - умова не виконується

V=5: D[5] = min(D[5],D[4]+C[4,5]) = min(6,4+5) = 6

(D[4] + C[4,5]) < D[5]

4 + 5 < 6 - умова не виконується

V=7: D[7] = min(D[7],D[4]+C[4,7]) = min(∞,4+3) = 7

(D[4] + C[4,7]) < D[7]

4 + 3 < ∞ - умова виконується

P[V] = W P[7] = 4

Крок 4

V=3: D[3] = min(D[3],D[5]+C[5,3]) = min(5,6+∞) = 5 (D[5] + C[5,3]) < D[3]

6 + ∞ < 5 - умова не виконується

V=7: D[7] = min(D[7],D[5]+C[5,7]) = min(∞,6+∞) = ∞

(D[5] + C[5,7]) < D[7]

6 + ∞ < ∞ - умова не виконується

Крок 5

V=7: D[7] = min(D[7],D[3]+C[3,7]) = min(∞,5+2) = 7

(D[3] + C[4,7]) < D[7]

5 + 2 < ∞ - умова виконується

P[V] = W P[7] = 3

Побудуємо найкоротші маршрути від третьої вершини (джерела), до вершин, які залишились (1, 2, 4, 5, 6, 7):

1 → 2 = 1

1 → 3 = 5

1 → 4 = 4

1 → 5 = 6

1 → 2 → 6 = 3

1 → 2 → 7 = 3



Крок

S

W







D/P







1

3

4

5

6

7

Початок

2

-

1/1

4/1





2/1

2/2

1

2,1

1

-

4/1

5/1

7/1

2/1

2/1

2

1,2,6

6

-

4/1



8/6

-

2/1

3

1,2,6,7

7

-

4/1

5/7



-

-

4

1,2,3,6,7

3

-

-

7/3



-

-

5

1,2,3,4,6,7

4

-

-

-



-

-

6

1,2,3,4,5,6,7

5

-

-

-

-

-

-



Крок 1:

V=3: D[3] = min(D[3],D[1]+C[1,3]) = min(4,1+5) = 4

(D[1] + C[1,3]) < D[3]

1 + 5 < 4 – умова не виконується

V=4: D[4] = min(D[4],D[1]+C[1,4]) = min(∞,1+4) = 5

(D[1] + C[1,4]) < D[4]

1 + 4 < ∞ – умова виконується

P[V] = W P[4] = 1

V=5: D[5] = min(D[5],D[1]+C[1,5]) = min(∞,1+6) = 7

(D[1] + C[1,5]) < D[5]

1 + 6 < ∞ – умова виконується

P[V] = W P[5] = 1

V=6: D[6] = min(D[6],D[1]+C[1,6]) = min(2,1+∞) = 2

(D[1] + C[1,6]) < D[6]

1 + ∞ < 2 – умова не виконується

V=7: D[7] = min(D[7],D[1]+C[1,7]) = min(2,1+∞) = 2

(D[1] + C[1,7]) < D[7]

  1. + ∞ < 2 – умова не виконується



Крок 2:

V=3: D[3] = min(D[3],D[6]+C[6,3]) = min(4,2+∞) = 4

(D[6] + C[6,3]) < D[3]

  1. + ∞ < 4 – умова не виконується



V=4: D[4] = min(D[4],D[6]+C[6,4]) = min(∞,2+∞) = ∞

(D[6] + C[6,4]) < D[4]

2 + ∞ < ∞ – умова не виконується

V=5: D[5] = min(D[5],D[6]+C[6,5]) = min(∞,2+6) = 8

(D[6] + C[6,5]) < D[5]

2 + 6 < ∞ – умова виконується

P[V] = W P[5] = 6

V=7: D[7] = min(D[7],D[6]+C[6,7]) = min(2,2+2) = 2

(D[6] + C[6,7]) < D[7]

2 + 2 < 2 – умова не виконується

Крок 3:

V=3: D[3] = min(D[3],D[7]+C[7,3]) = min(4,2+2) = 4 (D[7] + C[7,3]) < D[3]

2 + 2 < 4 – умова не виконується

V=4: D[4] = min(D[4],D[7]+C[7,4]) = min(∞,2+3) = 5

(D[7] + C[7,4]) < D[4]

2 + 3 < ∞ – умова виконується

P[V] = W P[4] = 7

V=5: D[5] = min(D[5],D[7]+C[7,5]) = min(∞,2+∞) = ∞

(D[7] + C[7,5]) < D[5]

2 + ∞ < ∞ – умова не виконується

Крок 4:

V=4: D[4] = min(D[4],D[3]+C[3,4]) = min(∞,4+3) = 7

(D[3] + C[3,4]) < D[4]

4 + 3 < ∞ – умова виконується

P[V] = W P[4] = 3

V=5: D[5] = min(D[5],D[3]+C[3,5]) = min(∞,4+∞) = ∞

(D[3] + C[3,5]) < D[5]

4 + ∞ < ∞ – умова не виконується

Крок 5:

V=5: D[5] = min(D[5],D[4]+C[4,5]) = min(∞,∞+5) = ∞

(D[4] + C[4,5]) < D[5]

∞ + 5 < ∞ – умова не виконується

Побудуємо найкоротші маршрути від другої вершини (джерела), до вершин, які залишились (1, 3, 4, 5, 6, 7):

2 → 1 = 1

2 → 3 = 4

2 → 1 → 4 = 5

2 → 1 → 5 = 7

2 → 6 = 2

2 → 7 = 2



Крок

S

W







D/P







1

2

4

5

6

7

Початок

3

-

5/1

4/1

3/1





2/1

1

3,7

7

5/1

4/1

3/1



4/7

-

2

3,4,7

4

5/1

4/1

-

8/4



-

3

2,3,4,7

2

5/1

-

-



6/2

-

4

1,2,3,4,7

1

-

-

-

11/1



-

5

1,2,3,4,5,7

5

-

-

-

-



-

6

1,2,3,4,5,6,7

6

-

-

-

-

-

-

Крок 1:

V=1: D[1] = min(D[1],D[7]+C[7,1]) = min(5,2+∞) = 5

(D[7] + C[7,1]) < D[1]

2 + ∞ < 5 – умова не виконується

V=2: D[2] = min(D[2],D[7]+C[7,2]) = min(4,2+2) = 4

(D[7] + C[7,2]) < D[2]

2 + 2 < 4 – умова не виконується

V=4: D[4] = min(D[4],D[7]+C[7,4]) = min(3,2+3) = 3

(D[7] + C[7,4]) < D[4]

2 + 3 < 3 – умова не виконується

V=5: D[5] = min(D[5],D[7]+C[7,5]) = min(∞,2+∞) = ∞

(D[7] + C[7,5]) < D[5]

2 + ∞ < ∞ – умова не виконується

V=6: D[6] = min(D[6],D[7]+C[7,6]) = min(∞,2+2) = 4

(D[7] + C[7,6]) < D[6]

  1. + 2 < ∞ – умова виконується

P[V] = W P[6] = 7

Крок 2:

V=1: D[1] = min(D[1],D[4]+C[4,1]) = min(5,3+4) = 5

(D[4] + C[4,1]) < D[1]

  1. + 4 < 5 – умова не виконується



V=2: D[2] = min(D[2],D[4]+C[4,2]) = min(4,3+∞) = 4

(D[4] + C[4,2]) < D[2]

3 + ∞ < 4 – умова не виконується

V=5: D[5] = min(D[5],D[4]+C[4,5]) = min(∞,3+5) = 8

(D[4] + C[4,5]) < D[5]

3 + 5 < ∞ – умова виконується

P[V] = W P[5] = 4

V=6: D[6] = min(D[6],D[4]+C[4,6]) = min(∞,3+∞) = ∞

(D[4] + C[4,6]) < D[6]

  1. + ∞ < ∞ – умова не виконується



Крок 3:

V=1: D[1] = min(D[1],D[2]+C[2,1]) = min(5,4+1) = 5

(D[2] + C[2,1]) < D[1]

  1. + 1 < 5 – умова не виконується



V=5: D[5] = min(D[5],D[2]+C[2,5]) = min(∞,4+∞) = ∞

(D[2] + C[2,5]) < D[5]

4 + ∞ < ∞ – умова не виконується

V=6: D[6] = min(D[6],D[2]+C[2,6]) = min(∞,4+2) = 6

(D[2] + C[2,6]) < D[6]

  1. + 2 < ∞ – умова виконується

P[V] = W P[6] = 2

Крок 4:

V=5: D[5] = min(D[5],D[1]+C[1,5]) = min(∞,5+6) = 11

(D[1] + C[1,5]) < D[5]

  1. + 6 < ∞ – умова виконується

P[V] = W P[5] = 1

V=6: D[6] = min(D[6],D[1]+C[1,6]) = min(∞,5+∞) = ∞

(D[1] + C[1,6]) < D[6]

5 + ∞ < ∞ – умова не виконується

Крок 5:

V=6: D[6] = min(D[6],D[5]+C[5,6]) = min(∞,∞+6) = ∞

(D[5] + C[5,6]) < D[6]

∞ + 6 < ∞ – умова не виконується

Побудуємо найкоротші маршрути від третьої вершини (джерела), до вершин, які залишились (1, 2, 4, 5, 6, 7):

3 → 1 = 5

3 → 2 = 4

3 → 4 = 3

3 → 1→ 5 = 11

3 → 7 → 6 = 4

3 → 7 = 2
скачати

© Усі права захищені
написати до нас