назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [ 70 ] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


70

Введем два определения.

Определение 1. Последовательность дуг сети, в которой каждая дуга имеет с предыдущей ровно одну общую вершину, назовем цепью.

Определение 2. Последовательность дуг сети, в которой конечная вершина каждой дуги является начальной вершиной следующей, назовем путем.

Например, на рис. 8.1 последовательность дуг (1,2)-(2,3)-(4,3)- является цепью, но не является путем, в то время как последовательность (1,2)-(2,3)-(3,4) есть путь.

8.2. Задача о кратчайшем пути

Задача нахождения путей минимальной длины из данной вершину во все остальные называется задачей о кратчайшем пути.

Предположим, что каждая дуга имеет длину. Предположим также, что мы вьщеляем некоторую верпшну, например, вершину 1. Задача нахождения путей минимальной длины из данной вершины во все остальные называется задачей о кратчайшем пути.

Пример. Предположим, что в вершине 1 находится электростанция, вырабатывающая электроэнергию. Необходимо передать выработанную электроэнергию в город, который находится в вершине 6. Передача производится по линиям электропередач, соединяющим промежуточные подстанции - вершины 2, 3, 4, 5. Расстояния между всеми пунктами показаны на рис. 8.2. Предполагая, что стоимость передачи электроэнергии прямо пропорциональна длине передающих линий, необходимо найти оптимальный (с минимальной стоимостью) маршрут передачи электроэнергии.

Рис, 8.2



Сетевое представление допускают и многие задачи, не связанные непосредственно с какими-либо перевозками или территориальными перемещениями. Рассмотрим следующий пример.

Пример. В 0-й момент времени приобретается новая машина по цене 12 ООО. Годовые расходы на эксплуатацию зависят от возраста автомобиля и приведены в табл. 8.1.

Таблица 8.1

Возраст автомобиля

Ежегодные расходы

на эксплуатацию

2 000

4 000

5 000

9 000

12 000

Для того чтобы избежать высоких расходов на эксплуатацию, имеет смысл в какой-то момент продать автомобиль и приобрести новый. Продажная стоимость автомобиля в зависимости от возраста приведена в табл. 8.2.

Таблица 8.2

Возраст

Продажная

автомобиля

стоимость

7 000

6 000

2 000

1000

Предполагаем, что стоимость покупки нового автомобиля всегда составляет 12 000. Требуется минимизировать затраты на автомобиль в ближайшие пять лет. Под затратами понимается - «стоимость покупки нового автомобиля» + «стоимость эксплуатационных расходов» -«стоимость продажи подержанного автомобиля».

Решение.

Сформулируем данную задачу как задачу о кратчайшем пути. Сеть будет содержать 6 вершин. Вершина с номером / соответствует началу /-го года. Для / < j дуга (Uj) соответствует ситуации покупки нового автомобиля в начале года и содержание его до начало года. Длина дуги (/,7), обозначаемая как с у., вычисляется следующим образом:



cj - «стоимость эксплуатации в течение года» + «стоимость покупки

автомобиля в начале года» - «стоимость продажи подержанного автомобиля в начале года». Используя данные задачи, можем вычислить:

ci2=2+ 12-7 = 7 Ci3 = 2 + 4+12-6=12 с,4 = 2 + 4 + 5+12-2 = 21 Ci5=2 + 4 + 5+9+12-l=31 ci6 = 2 + 4 + 5 + 9+12+12-0 = 44 С2з = 2+12-7 = 7 С24 = 2 + 4+12-6=12 С25 = 2 + 4 + 5 + 12-2 = 21

С2б = 2 + 4 + 5 + 9+ 12-1=31 сз4 = 2+ 12-7 = 7 сз5 = 2 + 4+ 12-6= 12 сзб = 2 + 4 + 5+12-2 = 21 С45 = 2+12-7 = 7 С4б = 2 + 4+12-6=12 С5б = 2+12-7 = 7.

Теперь легко заметить, что длина любого пути из вершины 1 в вершину 6 соответствует 5-летним затратам на автомобиль при выборе соответствующей стратегии продажи и покупки. Соответствующая сеть для данной задачи изображена на рис. 8.3.

Рис, 83

Например, предположим, что машина продается в начале 3-го года, а далее в конце года 5 (начало года 6). Эта стратегия соответствует пути 1-3-6. Длина данного пути составляет с =33 и соответствует затратам на автомобиль за рассматриваемый период.

8.2.1. Алгоритм Дейкстры. Предположим, что длины всех ребер - неотрицательные числа, тогда для нахождения кратчайших путей из не-

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [ 70 ] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]