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

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

шим, чем у ребра е, то тогда остовным деревом для G было бы Т-\-е-f с весом, меньшим, чем у Т. Последнее противоречило бы предположению о том, что Т является остовным деревом минимального веса для G.

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

Правильность алгоритма

Алгоритм PRIM является еще одним примером того, что называется «грубым» алгоритмом (см. разд. 3.2). Нужно принимать последовательность решений (в данном случае выбор ребер). Каждый раз, когда мы принимаем одно из этих решений, мы просматриваем всю текущую информацию и делаем по возможности наименее дорогой выбор. Этот выбор производится без учета воздействия, которое он может оказать на последующие выборы.

Правильность алгоритма PRIM основана на различных фундаментальных результатах, касающихся деревьев, в частности на теореме 2.2.4. Прежде чем обсуждать правильность, имеет смысл остановиться на одном общем факте, относящемся к разработке алгоритмов.

Вообще говоря, нетрудно разработать какой-то алгоритм для решения некоторой проблемы. Трудно разработать эффективный алгоритм, и очень трудно разработать наилучший возможный алгоритм (см. разд. 1.3).

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

Наше доказательство правильности алгоритма PRIM состоит из приведенной ниже последовательности теорем.

Теорема 4.1.1. При каждом завершении шага 2 алгоритма PRIM ребра, принадлежащие в данный момент Т, образуют дерево на множестве вершин, выбранных к данному моменту.

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

Теперь предположим, что-после К выполнений шага 2 ребра, в данный момент входящие в Т, образуют дерево (назовем его TJ на множестве выбранных к данному моменту вершин. Рассмотрим (/С+1)-е выполнение шага 2.

Оно обязательно включает добавление одной новой вершины и одного нового ребра к Т. Так как это новое ребро является единствен-



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

Теорема 4.1.2. При завери/ении работы алгоритма PRIM Т является остовным деревом для G.

Доказателы:тво. Это непосредственно следует из теоремы 4.1.1, которая гарантирует нам, что Т - дерево, и из того, что Т содержит все вершины G, т. е. алгоритм прекращает работу только тогда, когда все вершины выбраны.

Теорема 4.1.3. Пусть Т - поддерево сети О, а е - ребро с наименьшим весом, соединяющее вершину, принадлежащую Т, и вершину, не принадлежащую Т. Тогда в G существует остовное дерево Т, содержащее Т ие, такое, что если Т" - любое остовное дерево в G, содержащее Т, то W{T)W{T").

Доказательство. Пусть Т" - остовное дерево для G, содержащее Т и обладающее минимальным весом среди всех остовных деревьев, содержащих Т. Предположим далее, что Т" не содержит е. Рассмотрим сеть Т" и [е) и единственный цикл С в ней, содержащий е. Теперь цикл С должен содержать ребро 1фе, соединяющее вершину, принадлежащую Т, с вершиной, не принадлежащей Т. Почему? Согласно нашим предположениям, однако, мы знаем, что w{e)w(f). Следовательно, дерево, полученное из Т" удалением / и добавлением е:

Т"-{!) и {е}Т,

является остовным деревом G, содержащим Т и е, и удовлетворяет условию Wir)W{T").

Теорема 4.1.3 дает достаточное обоснование шага 2 алгоритма PRIM; она утверждает, что оснований для выбора нового ребра на шаге 2 достаточно, чтобы гарантировать существование остовного дерева минимального веса, содержащего выбранное ребро. Далее мы Пул ем использовать обозначение ОДМВ для остовного дерева миним,-;.чьн)го веса.

TeopcAia 4.1.4. Пусть G(V, Е) - связная взвешенная сеть, и nycnvt e={v, w) ~ ребро с наименьшим весом, инцидентное вершине v. Тогда существует ОДМВ Т, содержащее е.

Доказательство. Пусть Т - ОДМВ G, не содержащее е. Рассмотрим сеть Т и {е}. Согласно теореме 2.2.4(e), Т (J {е} содержит в точности один цикл. Этот цикл содержит два ребра, инцидентных вершине v, включая е=(о, w) и другое ребро, скажем /=(ы, v). Согласно гипотезе, w{e)-w{f), и поэтому T-{f}\j{e} является ОДМВ для G, содержащим е.

Теорема 4.1.5. Алгорипил PRIM находит ОДМВ Т во взвешенной связной сети G с М вершинами.



Доказательство. Согласно теореме 4.1.2, алгоритм PRIM находит остовное дерево.

Согласно теореме 4.1.4 существует ОДМВ Ti, содержащее первое ребро - назовем его Ci - выбранное алгоритмом PRIM.

Согласно теореме 4.1.3, существует остовное дерево Т, содержащее первое ребро Ci и второе ребро е, выбранное алгоритмом PRIM. также обладает минимальным весом среди всех остовных деревьев, содержащих ег, т. е. W{T2) = W{Ti), так как Ti - наше ОДМВ.

Повторяя этот процесс, по теореме 4.1.3, мы убеждаемся в существовании ОДМВ, содержащего первые k ребер, выбранных алгоритмом PRIM, для всех fe=l, 2, . . . , M-l.

Наконец, так как выбранные М-I ребер сами образуют остовное дерево, из этого следует, что Т есть остовное дерево минимального веса для G.

Реализация алгоритма

Теперь настало время описать програмгду для машины, отыскивающую ОДМВ, с использованием алгоритма PRIM. Алгоритм будет реализован в виде подпрограммы. Это соглашение вводится для того, чтобы избежать определенных вопросов ввода и вывода, зависящих от местных требований к организации вычислений и вопросов стиля. Используя данное соглашение, мы не подразумеваем этим, что вопросы ввода и вывода тривиальны. Например время ввода/вывода может оказаться существенно больше временя вычислений при отыскании ОДМВ для очень больших сетей.

Первое, что можно было бы спросить: каковы должны быть входные и выходные параметры этой подпрограммы? Начальное предложение алгоритма PRIM частично отвечает на этот вопрос: на входе должна быть взвешенная связная сеть G с М вершинами и ребрами, а на выходе нужно получить для О остовное дерево Т минимального веса.

Следовательно, мы должны решить, как хранить сеть в памяти. В разд. 2.2 и 2.3 обсуждались некоторые способы представления сети в машине. Пока мы произвольно решим организовать массив размера МхМ (т. е. матрицу стоимостей), где с равно весу ребра G между vt и Vj. Если же между Vt и Vj нет ребра, то используем Cj,=l ООО ООО, т. е. некоторое значение, большее веса любого ребра в G. Мы также будем предполагать для удобства, что все веса - положительные целые.

Выходная информация будет состоять из последовательности М-1 упорядоченных троек, элементы которых расположены в трех массивах FROM(/), ТО(/), COST(/). Пара FROM(/), ТО{/) представляет /-е ребро ОДМВ Т, вес которого равен COST(/).

Решив, как представить входную и выходную информацию для подпрограммы, мы приступаем к реализации каждого шага алгоритма PRIM. Шаги О и I предполагают наличие массива CHOSEN, в котором CHOSEN (/)=1, если вершина / «выбрана», и CHOSEN (/)=0, если вершина / пока еще «не выбрана».



[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.001