Главная  Полное построение алгоритма 

[0] [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]

(см. сеть С" на рис. 4.1.3, б). Полученная сеть оказывается более дешевой, но все еще связной, т. е. любой пункт может связаться с любым другим пунктом.

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

Наша первоначальная задача теперь может быть сформулирована математически следующим образом: Дана связная полная сеть G с весами, найти остовное дерево минимальной стоимости (или веса).

Разработка алгоритма

Теперь, когда мы поставили нашу задачу математически, мы должны найти решение. Возможно, естественнее всего было бы испытать грубый алгоритм, т. е. выбрать сперва самое дешевое ребро, затем следующее самое дешевое из оставшихся и т. д. Но, выбирая ребра, мы должны помнить о трех требованиях: (1) окончательная подсеть должна содержать все вершины и должна быть связной; (2) окончательная сеть не должна содержать циклов; (3) окончательная сеть должна обладать минимальным возможным весом. Заглядывая несколько вперед, мы должны также приготовиться доказать, что наша окончательная сеть действительно обладает минимальным весом.

Попытаемся сфоэмулировать эту процедуру в виде алгоритма.

Algorithm А. Отыскание остовного дерева Т минимального веса во взвешенной, связной и полной сети G с М вершинами и N ребрами. Шаг 0. [Инициализация] Set Т сеть, состоящая из М вершин, но

без ребер; set Н G. Шаг 1. [Цикл] While Т не является связной сетью do through шаг 3 od; and STOP.

Шаг 2. [Отыскание ребра с минимальным весом] Пусть {U, V) - ребро с наименьшим весом в Я; if Т-\-{11, V) не имеет циклов then [добавить ([/, V) к Т\ set Т <-T+(U, V) fi.

Шаг 3, [Удаление {U, Щ из Я] Set Я H-~{U, V).

Возникает несколько вопросов относительно этого алгоритма:

1. Всегда ли он выходит на STOP?

2. Когда он выходит на STOP, всегда ли Т оказывается остовным деревом для G?

3. Гарантировано ли, что Т - остовное дерево минимального веса?

4. Является ли алгоритм замкнутым (или содержит скрытые или неявные подалгоритмы)?

5. Эффективен ли алгоритм?



Сейчас БЫ уже могли бы подумать над вопросами 1, 2 и 3; ответ на все три будет «да». Сосредоточимся на вопросах 4 и 5.

На вопрос 4 ответ будет «нет», а на вопрос 5 - «может быть». Шаг 1 требует подалгоритма определения связности сети, а шаг 2 требует подалгоритма для решения вопроса о наличии циклов в сети. Эти два шага могут сделать алгоритм неэффективным, потому что подалгоритмы могли бы потребовать много времени.

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

Следующий алгоритм, принадлежащий Приму, делает как раз то, что мы хотим. Он настолько прост, что трудно поверить в то, что он всегда работает. Его правильность будет доказана в следующем разделе.

Algorithm PRIM. Найти остовное дерево Т минимального веса во взвешенной связной сети G с М вершинами и ребрами. Шаг 0. [Инициализация] Помечаем все вершины «невыбранными»;

set Т сеть с М вершинами и без ребер; выбираем произвольную вершину и помечаем ее «выбранной». Шаг 1. [Цикл] While существует невыбранная вершина do шаг 2 od; and STOP.

Шаг 2. [Отыскание ребра с минимальным весом] Пусть {U, V) - ребро с наименьшим весом между произвольной выбранной вершиной U и произвольной невыбранной вершиной V; помечаем V как «выбранную»; and set TT{U, V).

Блок-схема алгоритма PRIM приведена на рис. 4.1.4. На рис. 4.1.5, а показана сеть с рис. 4.1.1,6; рис. 4.1.5,6-

иллюстрируют рост остовного дерева Т минимального веса по мере работы алгоритма PRIM; выбранные вершины указываются черными квадратами, а невыбранные - окружностями. Начальной вершиной на рис. 4.1.5, б является вершина 5.

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

Отрабатывание назад часто используется для пЬнимания разработки алгоритма. Ключевую идею разработки алгоритма PRIM можно было бы найти отрабатыванием назад. Предположим, что мы нашли каким-либо методом остовное дерево Т минтального веса для сети G. Ребра G, не входящие в Т, должны быть как-то устранены из рассмотрения. Введем одно из них обратно в Т, например ребро е. По теореме 2.2.4 (е) Т-\-е имеет в точности один цикл, который мы назовем С. Вес ребра е должен быть не меньше веса каждого из остальных ребер из С. Это следует из того, что если ребро / из С обладает весом, боль-




(отнчшш)

Помвчаем, вершину V нак выбранную

Присоедшяем ребро е к Т

Рис. 4.1.4. Блок-схема алгоритма PRIM.


о2 S


о2 S


Рис. 4.1.5.



[0] [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]

0.0015