Предыдущая страница реферата | 5  6  7  8  9  10  11  12  13  14  15 | Следующая страница реферата

push(x, stack2)

End

End;

PrintList(stack2)

End.

Задача Прима–Краскала.

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

Или в терминах теории графов:

Дан граф с n вершинами; длины ребер заданы матрицей. Найти остовное дерево минимальной длины.

Представим себе, что зимовщику оставлен некоторый запас продуктов, и его задачей является составление вкусного меню на всю зиму. Если зимовщик начнет с того, что сперва будет есть самую вкусную еду (например, шоколад), потом – вторую по вкусности (например, мясо), то он рискует оставить на последний месяц только соль и маргарин. Подобным образом, если оптимальный (для определенности, минимальный) объект строится как-то по шагам, то нельзя на первом шаге выбирать что-нибудь самое малое, на втором шаге – оставшееся самое малое и т.д. За такую политику обычно приходится расплачиваться на последних шагах. Такой алгоритм называется жадным.

Удивительно, но в задаче Прима–Краскала, которая не кажется особенно простой, жадный алгоритм дает точное оптимальное решение.

Как известно (это легко доказать по индукции), дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро нужно выбирать жадно (лишь бы не возникали циклы). То есть n-1 раз выбирать самое короткое ребро из еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными.

А как следить, чтобы новое ребро не образовывало цикла со старыми? Сделать это просто. До построения дерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра, например (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т.е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет.

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

Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро.

Действительно, пусть добавлено ребро (u, v) – “добавлено” означает, что ребро – новое, что раньше его в дереве не было. Поскольку дерево является связанным графом, то существует цепь C(u, …, v) из нескольких ребер, соединяющая вершины u и v. Добавление ребра (u, v) замыкает цепь, превращая ее в цикл.

Теорема. Алгоритм Прима–Краскала получает минимальное остовное дерево.

Доказательство. Результатом работы алгоритма является набор из n-1 ребер. Они не образуют цикла, ибо на каждом из n-1 шагов соединялись вершины разного цвета, т.е. ранее не связанные. Этот граф связный, потому что после проведения 1-го ребра осталось n-1 разных цветов, …, после проведения (n-1)-го ребра остался один цвет, т.е. одна компонента связности. Итак, полученный набор ребер образует связный граф без циклов, содержащий n-1 ребер и n вершин. Следовательно, граф есть остовное дерево.

Для реализации алгоритма понадобятся:

Matrix – матрица расстояний, значение пересечении i-ой строки и j-го столбца равно расстоянию между i-ой и j-ой вершинами. Если такого ребра нет то значение равно Infinity – просто большому числу (машинная бесконечность);

Color – массив цветов вершин;

Ribs – в этом массиве запоминаются найденные ребра;

a, b – вершины, соединяемые очередным минимальным ребром

len – длина дерева.

Матрицу расстояний будем хранить в текстовом файле INPUT.MTR, где число на первой строке – количество вершин n, а остальные n строк по n чисел в каждой – матрица расстояний. Если расстояние равно 1000 (Infinity), то такого ребра нет.

Program Algorithm_PrimaKrascala;

Рекомендуем скачать другие рефераты по теме: экологические рефераты, конспект 2 класс.





Предыдущая страница реферата | 5  6  7  8  9  10  11  12  13  14  15 | Следующая страница реферата