Пример решения задачи о дилижансе
Постановка задачі: Знайти найкоротший маршрут з кінцевого пункту в початковий, якщо відома матриця транспортних витрат (см. табл 46).
Таблиця 46. Матриця транспортних витрат
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
|
7 |
5 |
9 |
|
|
|
|
|
|
2 |
|
|
|
|
11 |
7 |
12 |
|
|
|
3 |
|
|
|
|
8 |
5 |
9 |
|
|
|
4 |
|
|
|
|
10 |
10 |
6 |
|
|
|
5 |
|
|
|
|
|
|
11 |
13 |
|
|
6 |
|
|
|
|
|
|
12 |
|
9 |
|
7 |
|
|
|
|
|
|
|
|
|
8 |
8 |
|
|
|
|
|
|
|
|
|
7 |
9 |
|
|
|
|
|
|
|
|
|
6 |
10 |
|
|
|
|
|
|
|
|
|
|
Алгоритм рішення:
fn(s) – вартість, що відповідає стратегії min витрат для шляху від пункту s, якщо до кінцевого пункту залишилося n кроків.
jn(s) - рішення, що дозволяє досягти fn(s) .
Розраховувати будемо, користуючись рекурентним співвідношенням:
fn(s) =min (csj+ fn-1(j) ) по всем s и j на сети.
Рішенне:
Шаг 1
в Из |
10 |
f |
j |
7 |
8 |
10 |
8 |
8 |
7 |
10 |
7 |
9 |
6 |
10 |
6 |
Шаг 2
в Из |
7 |
8 |
9 |
f |
j |
5 |
11+8 |
13+7 |
|
19 |
7 |
6 |
12+8 |
|
9+6 |
15 |
9 |
Шаг 3
в Из |
5 |
6 |
7 |
f |
j |
2 |
11+19 |
7+15 |
12+8 |
20 |
7 |
3 |
8+19 |
5+15 |
9+8 |
17 |
7 |
4 |
10+19 |
10+15 |
6+8 |
14 |
7 |
Шаг 4
в Из |
2 |
3 |
4 |
f |
j |
1 |
7+20 |
5+17 |
9+14 |
22 |
3 |
Рисунок 19 Транспортная сеть
Ответ: F=22, кратчайший путь 1-3-7-10.