3. Примеры постановок задач, сводимых к задаче о кратчайшей цепи
ПРИМЕР 1. Задача о покупке автомобиля
|
Таблица 2. Результаты вычислений
узел Шаг |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
0 |
[0] |
|
|
|
|
|
|
|
|
1 |
[0] |
1450 |
2750 |
3850 |
4750 |
|
|
|
|
2 |
[0] |
[1450] |
2750 |
3850 |
4750 |
|
|
|
|
3 |
[0] |
[1450] |
2750 |
3850 |
4750 |
6900 |
|
|
|
4 |
[0] |
[1450] |
[2750] |
3850 |
4750 |
6900 |
|
|
|
5 |
[0] |
[1450] |
[2750] |
3850 |
4750 |
6900 |
8550 |
|
|
6 |
[0] |
[1450] |
[2750] |
[3850] |
4750 |
6900 |
8550 |
|
|
7 |
[0] |
[1450] |
[2750] |
[3850] |
4750 |
6900 |
8550 |
10000 |
|
8 |
[0] |
[1450] |
[2750] |
[3850] |
[4750] |
6900 |
8550 |
10000 |
|
9 |
[0] |
[1450] |
[2750] |
[3850] |
[4750] |
6825 |
8550 |
10000 |
11250 |
10 |
[0] |
[1450] |
[2750] |
[3850] |
[4750] |
[6825] |
8550 |
10000 |
11250 |
11 |
[0] |
[1450] |
[2750] |
[3850] |
[4750] |
[6825] |
[8550] |
10000 |
11250 |
12 |
[0] |
[1450] |
[2750] |
[3850] |
[4750] |
[6825] |
[8550] |
10000 |
11250 |
13 |
[0] |
[1450] |
[2750] |
[3850] |
[4750] |
[6825] |
[8550] |
[10000] |
11250 |
14 |
[0] |
[1450] |
[2750] |
[3850] |
[4750] |
[6825] |
[8550] |
[10000] |
11250 |
15 |
[0] |
[1450] |
[2750] |
[3850] |
[4750] |
[6825] |
[8550] |
[10000] |
[11250] |
ПРИМЕР 2. Задача о транспортировке нефти
нефтехранилище пункты потребления
Рис. 4. Распределительная сеть |
А
В
C
D
E
F
G |
