Глава 4. Полный пример

в гл. 1 обсуждались несколько основных этапов, входящих в полное построение алгоритма. Гл. 2 и 3 продемонстрировали некоторые основные средства проектирования и методы, которые можно использовать при построении алгоритма. В этой главе многие из этих идей проиллюстрированы на конкретном примере •- полностью построенном алгоритме отыскания остовного дерева минимального веса в некоторой сети. Этот пример также иллюстрирует многие приемы проверки программ и составления документации.

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

4.1. Построение алгоритма для отыскания остовного дерева ллини.У1ального веса

Ад1Министратор вычислительного центра сталкивается с необходимостью принять решение, надо или нет организовать сеть малых вычислительных машин в N различных территориальных пунктах. Это решение является довольно сложным и зависит от большого количества факторов. Эти факторы включают вычислительные ресурсы, доступные в каждом пункте, соответствующие уровни потребностей, пиковые нагрузки на систему, возможное неэффективное использование основного ресурса в системе и, кроме того, стоимость предлагаемой сети. В эту стоимость входят приобретение оборудования, прокладка линий связи, обслуживание системы и стоимости прогона задания данного, типа в данном пункте. Администратор просит нас определить стоимость такой сети.

Поразмыслив, глы решаем, что нужна сеть минимальной стоимости, в которой каждый пункт может связаться с любым другим. Позвонив представителю телефонной компании, мы можем выяснить, какова стоимость dj прокладки прямой линии связи (некоммутируемой линии) между двумя пунктами t и / в предполагаемой сети. Представитель телефонной компании информирует нас, что стоимость некоммутируемой линии является функцией географического расстояния между пунктами, необходимой скорости передачи и желаемой информационной емкости линии.

После дальнейшего обсуждения этого вопроса вместе с администратором и представителем телефонной компании нам удается определить

подходящие цены Cjj>0, т. е. мы получаем симметричную матрицу стоимостей, подобную использованной в задаче о коммивояжере в разд. 1.3.

Построение модели

Что представляет собой решение задачи? Мы должны решить, какие именно соединения следует установить, а какие не следует, т. е. ДЛЯ каждой пары i и / следует решить, устанавливать или нет соединение стоимостью Сц.

Следовательно, решение должно представлять собой модифицированную матрицу С, полученную из первоначальной матрицы цен, в которой элементы (i, /) и (/, i) равны оо, если мы не устанавливаем соединения, и Cij, если устанавливаем. Кроме того, поскольку предполагается, что каждый пункт может устанавливать связь в сети с любым другим, то в каждой строке (и в каждом столбце) матрицы С должен содержаться по крайней мере один конечный элемент. Но любая ли модифицированная матрица, удовлетворяющая этому условию на строки и столбцы, является решением? Оставив пока этот вопрос открытым, давайте рассмотрим вторую модель для этой же задачи. Рис. 4.1.1 показывает, как можно представить любую симметричную матрицу стоимостей полной сетью с весами. Рис. 4.1.1, а представляет гипотетическую матрицу С для сети связи, состоящей из пяти пунктов, помеченных цифрами 1, 2, 3, 4 и 5. Для удобства стоимости с для i¥=j предполагаются положительньши целыми числами. Заметим, что Сц=Сл, т. е. С - симметричная матрица. Все элементы на главной диагонали сделаны бесконечньши, чтобы избежать установления связи некоторого пункта с самим собой. Пять вершин полной сети с весами на рис. 4.1.1, б, помеченные цифрами 1, 2, 3, 4 и 5, соответствуют пяти

1 2 3

~ 11 9 7 8

11 ~ 15 14 13

9 15 ~

7 14 12

8 13 14

12 14

оо 6

Рис. 4.1.1. (а) матрица стоимостей С; (б) соответствующая взвешенная полная сеть G.

пунктам сети связи. Для любой пары различных вершин Vi и Vj ребро, соединяющее их, помечено стоимостью сц.

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

7 2 3 4 5

- 11 - -

11 - - - -

- - - 12 14

- - 12 - 6

- - 14 6 -

Рис. 4.1.2. (а) С; (б) G.

бы ЭТО быть решением? Визуальное рассмотрение соответствующей подсети G и G показывает, что это не может быть решением, так как в G не существует пути, соединяющего пункты 3, 4 или 5 с пунктами 1 или 2.

На рис. 4.1.2 мы обнаружили, что подсеть G не является связной. Поэтому образуем связную сеть добавлением (самой дешевой) линии связи между пунктами 1 или 2 и пунктами 3, 4 или 5, т. е. соединяем пункты 1 и 4, стоимость Ci4=7 (см. сеть G" на рис. 4.1.3, а). Могла бы

Рис. 4.1.3. (а) G"; (б) С".

сеть G" быть решением? Стоимость этой сети является суммой стоимостей всех линий связи, которые она содержит. Посмотрим, что произошло бы, если бы мы удалили соединение между пунктами 3 и 5