Алгоритм Прима нахождения оптимального каркаса

Содержание Введение

1. Постановка задачи

2. Алгоритм Прима нахождения оптимального каркаса

3. Реализация алгоритма на языке Пролог

4. Примеры работы программ Заключение Список литературы Приложение Введение Функциональные и логические языки программирования опираются на т.н. декларативную парадигму программирования. В отличии от императивной, где основное внимание уделяется разработке и реализации конкретных алгоритмов для решения определенного класса задач, в декларативной парадигме на первый план выходит формальное описание задачи, опираясь на которое вычислительная машина может сама найти путь к ее решению. Декларативный подход к разработке программ имеет перед императивным ряд преимуществ, среди которых большая выразительность и меньшая трудоемкость разработки. Меньшая трудоемкость, в частности, достигается за счет того, что программист может не заботиться о физическом представлении программы, организации памяти, взаимодействии с аппаратными средствами и т. п., и может полностью сосредоточиться на поиске решения задачи как таковой, оставляя реализацию решения компьютеру. Разумеется, у такого подхода есть и существенные недостатки, по-видимому, основным из которых является уменьшение производительности и неэффективное использование памяти. Тем не менее, этот недостаток не является критичным, поскольку в большинстве случаев к программе не предъявляются настолько жесткие требования, что использование декларативных языков становится нецелесообразным. Более того, в определенных случаях реализация на декларативных языках может оказаться даже эффективнее, чем на императивных (например, существует вариант реализации алгоритма быстрой сортировки на языке Haskell, который работает быстрее, чем реализация на языке C). Выразительность же декларативных языков является очень существенным преимуществом. Здесь можно процитировать Дональда Кнутта: «Программы пишутся прежде всего для того, чтобы их читали люди». Программы на декларативных языках гораздо легче отлаживать, поскольку ошибки заведомо заложены только в решении, в то время как по статистике более 80% всех ошибок в программах на императивных языках составляют детали реализации, например, приведение типов.

В данной работе рассматривается применения языка логического программирования Пролог и языка функционального программирования Haskell для реализации алгоритма поиска оптимального каркаса графа.

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

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

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

2. Алгоритм Прима нахождения оптимального каркаса Алгоритм Прима порождает оптимальный каркас посредством разрастания одного поддерева Ts.

Разрастание поддерева Ts происходит за счет присоединения ребер

(vi, vj)

где vi? Ts и vj ~? Ts, причем добавляемое ребро должно иметь наименьший вес cij. Процесс продолжается до тех пор, пока число ребер в Ts не станет равным n-1.

Алгоритм начинает работу с присвоения каждой вершине vj ~? Ts пометки [aj, bj], где aj на каждом шаге есть ближняя к vj вершина из поддерева Ts, а bj вес ребра (aj, bj). На каждом шаге выполнения алгоритма вершина, например v*j, с наименьшей пометкой bj присоединяется к ts посредством добавления ребра (a*j, v*j). Поскольку к Ts добавлена новая вершина v*j, то, может быть, придется изменить пометки [aj, bj] у некоторых вершин vj ~? Ts и после этого продолжить процесс.

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

1. Пусть

Ts = {vs}

где vs — произвольно выбранная вершина, и Ss = o.

2. Для каждой вершины vj ~? Ts найти вершину aj? Ts такую, что

c (aj, vj) = min[c (vi, vj)] = bj

и приписать вершине vj пометку [aj, bj]. Если такой вершины a нет, приписать вершине vj метку [0, ?].

3. Выбрать такую вершину v*j, что

b*j = min[bj]

Обновить данные: Ts = Ts E {v*j}, Ss = Ss E {(a*j, v*j)}. Если |T| = n, то стоп. Ребра в Ss образуют оптимальный каркас. Если |Ts| < n, то перейти к п. 4.

4. Для всех vj ~? Ts таких, что vj? Гv*j, обновить метки следующим образом:

• Если bj > c (v*j, vj), то положить bj = c (v*j, vj), aj = v*j

• Если bj <= c (v*j, vj), то не изменять метку перейти к шагу 3

3. Реализация алгоритма на языке Пролог Из описаного алгоритма можно выделить следующие функции:

1. Первичное размечивание графа, т. е. Сопоставление каждой вершине метки [aj, bj].

2. Поиск вершины vj с минимальным значением bj в метке.

3. Переразмечивание вершин, смежных с vj

Все эти функции являются частью итеративного процесса поиска, т. е. могут быть скомпонованы в рекурсивную функцию поиска. В Пролог-программе в роли такой функции выступает предикат primeSearch/5, который связывает граф, множество T, множество S, список меток вершин и оптимальный каркас. Базовый случай этого предиката (условие остановки поиска) — высказывание, принимающее значение Истина, когда размер множества T совпадает с размером множества вершин графа, т. е. каркас охватывает все вершины графа. Определение данного предиката выглядит следующим образом:

primeSearch (graph (V, E), T, S, _, S) : — length (V, L1), length (T, L2), L1 is L2.

primeSearch (graph (V, E), T, S, MN, Res) :-primeMinimum (MN, par (X, Y)), remark (MN, E, X, D), primeSearch (graph (V, E), [X|T], [edge (X, Y)|S], D, Res).

Как можно видеть, граф представлен в виде функтора, связывающего множество вершин и множество ребер графа. Ребро, в свою очередь, представлено функтором edge/2, связывающего концевые вершины. Предикат реализует п. 3 и п. 4 алгоритма Для выполнения п. 1 и п. 2 определен предикат primeInit, определяющий начальное содержание множеств T и S, и осуществляющий первичную разметку вершин графа, вызывая предикат markerVx/4.

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

markerVx ([], _, _, []).

markerVx ([H|T], S, E, [X|XS]) : — elem (edge (H, S, W), E), X = mark (H, S, W), markerVx (T, S, E, XS).

markerVx ([H|T], S, E, [mark (H, S, 99 999)|XS]) : — not (elem (edge (H, S, W), E)), markerVx (T, S, E, XS).

Поиск добавляемого ребра осуществляет предикат primeMin. Этот предикат определяет пару вершин, первая из которых является не пренадлежащей Ts вершиной с минимальным значением метки b, а вторая — определенная меткой вершина, принадлежащая каркасу. Определение предиката:

primeMin ([], M, par (X, Y)) : — M = mark (X, Y, _).

primeMin ([H|T], mark (X, Y, M), XS) : — H = mark (X1, Y1, Z1), Z1 < M, !, primeMin (T, H, XS).

primeMin ([H|T], X, XS) : — primeMin (T, X, XS).

Задачу перемаркировки выполняет предикат remark.

В данном предикате происходит сравнение меток вершин, инцидентных добавленной вершине, с весом ребра, идущего к добавленной вершине.

Если вес ребра меньше значения метки, метка меняется в соответствии с п. 4 алгоритма. Предикат определен следующим образом:

remark ([], _, _, []).

remark ([H|HS], E, X, TH) : — H = mark (X, _, _), remark (HS, E, X, TH).

remark ([H|T], E, X, [NH|TH]) : — H = mark (X1, X2, W), elem (edge (X1, X, W1), E), W1 < W, NH = mark (X1, X, W1), remark (T, E, X, TH).

remark ([H|T], E, X, [H|TH]) : — remark (T, E, X, TH).

Код программы на языке Пролог представлен в Приложении Б.

4. Примеры работы программ Рассмотрим работу алгоритма на примере графа, представленного на рисунке 1. Слева на рисунке представлен граф, справа — оптимальный каркас этого графа.

Рисунок 1 — Тестовый граф (слева) и соответствующий ему оптимальный каркас (справа) каркас граф алгоритм прима В языке Пролог данный граф кодируется следующим образом:

g2(X) : — X = graph

([1,2,3,4,5,6,7],[edge (1,6,23), edge (1,7,1), edge (1,2,20), edge (2,1,20), edge (2,7,4), edge (2,3,15), edge (3,2,15), edge (3,7,9), edge (3,4,3), edge (4,3,3), edge (4,7,16), edge (4,5,17), edge (5,4,17), edge (5,7,25), edge (5,6,28), edge (6,5,28), edge (6,7,36), edge (6,1,23), edge (7,1,1), edge (7,2,4), edge (7,3,9), edge (7,4,16), edge (7,5,25), edge (7,6,36)]).

Целевая функция для этого графа

main : — g2(X), primeInit (X, T, S, M), primeSearch (X, T, S, M, R), write ('Graph optimal carcas: '), writeln®.

Результат

Graph optimal carcas: [edge (6, 1), edge (5, 4), edge (4, 3), edge (3, 7), edge (2, 7), edge (7, 1)]

Результат соответствует действительному.

Для программы на языке Haskell определим главную функцию main:

main = do

let

gs = [

(Nothing, 1, [(2,20), (6,23), (7,1)]),

(Nothing, 2, [(1,20), (3,15), (7,4)]),

(Nothing, 3, [(2,15), (7,9), (4,3)]),

(Nothing, 4, [(3,4), (7,16), (5,17)]),

(Nothing, 5, [(4,17), (7,25), (6,28)]),

(Nothing, 6, [(5,28), (7,36), (1,23)]),

(Nothing, 7, [(1,1), (6,36), (5,25), (4,16), (3,9), (2,4)])

]

(graph, vf, kf, wf) = graphFromWEdges gs

ts = primeOptimalCarcas graph wf

print ts

Результат:

[(0,6),(6,1),(6,2),(2,3),(3,4),(0,5)]

Результат соответствует действительному.

Заключение

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

1 Душкин Р. В. Функциональное программирование на языке Haskell. М.: ДМК Пресс, 2007. — 608 с., ил.

2 Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог: Пер. с англ.-М.: Мир, 1990. -235 с., ил.

3 Абельсон Х., Сассман Дж. Структура и интерпретация компьютерных программ — М.: Добросвет, КДУ, 2006. — 608 с.: ил.

4 Иван Братко. Алгоритмы искусственного интеллекта на языке PROLOG, 3-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2004. — 640 с.: ил. Парал. тит. Англ.

5 Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. — Спб.: БХВ-Петербург, 2003. — 1104 с.: ил.

6 Кристофидес Н. Теория графов. Алгоритмический подход. М. ДМК Пресс, 2003. — 356 с., ил.

Приложение

elem (X, [X|_]).

elem (X, [_|HS]) : — elem (X, HS).

primeInit (graph ([V|VS], E), [V], [], XS) : — markerVx (VS, V, E, XS).

markerVx ([], _, _, []).

markerVx ([H|T], S, E, [X|XS]) : — elem (edge (H, S, W), E), X = mark (H, S, W), markerVx (T, S, E, XS).

markerVx ([H|T], S, E, [mark (H, S, 99 999)|XS]) : — not (elem (edge (H, S, W), E)), markerVx (T, S, E, XS).

primeMin ([], M, par (X, Y)) : — M = mark (X, Y, _).

primeMin ([H|T], mark (X, Y, M), XS) : — H = mark (X1, Y1, Z1), Z1 < M, !, primeMin (T, H, XS).

primeMin ([H|T], X, XS) : — primeMin (T, X, XS).

primeMinimum (X, Res) : — primeMin (X, mark (0, 0, 99 999), Res).

primeSearch (graph (V, E), T, S, _, S) : — length (V, L1), length (T, L2), L1 is L2.

primeSearch (graph (V, E), T, S, MN, Res) :-primeMinimum (MN, par (X, Y)), remark (MN, E, X, D), primeSearch (graph (V, E), [X|T], [edge (X, Y)|S], D, Res).

remark ([], _, _, []).

remark ([H|HS], E, X, TH) : — H = mark (X, _, _), remark (HS, E, X, TH).

remark ([H|T], E, X, [NH|TH]) : — H = mark (X1, X2, W), elem (edge (X1, X, W1), E), W1 < W, NH = mark (X1, X, W1), remark (T, E, X, TH).

remark ([H|T], E, X, [H|TH]) : — remark (T, E, X, TH).

g (X) : — X = graph (

[0,1,2],

[

edge (0,1,1),

edge (0,2,2),

edge (1,0,1),

edge (1,2,3),

edge (2,0,2),

edge (2,1,3)

]).

g2(X) : — X =

graph (

[1,2,3,4,5,6,7],

[

edge (1,6,23),

edge (1,7,1),

edge (1,2,20),

edge (2,1,20),

edge (2,7,4),

edge (2,3,15),

edge (3,2,15),

edge (3,7,9),

edge (3,4,3),

edge (4,3,3),

edge (4,7,16),

edge (4,5,17),

edge (5,4,17),

edge (5,7,25),

edge (5,6,28),

edge (6,5,28),

edge (6,7,36),

edge (6,1,23),

edge (7,1,1),

edge (7,2,4),

edge (7,3,9),

edge (7,4,16),

edge (7,5,25),

edge (7,6,36)

]).

main : — g2(X), primeInit (X, T, S, M), primeSearch (X, T, S, M, R), write ('Graph optimal carcas: '), writeln®.