Алгоритм Прима нахождения оптимального каркаса
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
p>
Если bj <= c(v*j, vj), то не изменять метку перейти к шагу 3
. Реализация алгоритма на языке Пролог
Из описаного алгоритма можно выделить следующие функции:
1.Первичное размечивание графа, т.е. Сопоставление каждой вершине метки [aj, bj].
2.Поиск вершины vj с минимальным значением bj в метке.
.Переразмечивание вершин, смежных с 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([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, 99999)|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).([H|T], X, XS) :- primeMin(T, X, XS).
Задачу перемаркировки выполняет предикат remark.
В данном предикате происходит сравнение меток вершин, инцидентных добавленной вершине, с весом ребра, идущего к добавленной вершине.
Если вес ребра меньше значения метки, метка меняется в соответствии с п.4 алгоритма. Предикат определен следующим образом:
([], _, _, []).
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).([H|T], E, X, [H|TH]) :- remark(T, E, X, TH).
Код программы на языке Пролог представлен в Приложении Б.
. Примеры работы программ
Рассмотрим работу алгоритма на примере графа, представленного на рисунке 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(R).
Результат
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=[
(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= primeOptimalCarcas graph wfts
Результат:
[(0,6),(6,1),(6,2),(2,3),(3,4),(0,5)]
Результат соответствует действительному.
Заключение
Теория графов применяется во многих областях человеческой деятельности для формализации информации и выявления скрытых закономерностей. На примере задачи об отыскании оптимального каркаса можно видеть, что теоретико-графовые алгоритмы легко и в виде, удобном для восприятия, переводятся на декларативные языки, при этом эффективность реализации лишь в некоторых случаях уступает реализациям на императивных языках программирования. Также можно отметить, что все инструкции программы направлены исключительно на решение задачи, отсутствуют операции приведения типов, присваивания и т.п., что значительно сокращает количество возможных ошибок. Т.о., декларативные языки программирования являются мощным и удобным инструментом решения задач.
Список литературы
1 Душкин Р.В. Функциональное программирование на языке Haskell. М.: ДМК Пресс, 2007. - 608 с., ил.
Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог: Пер. с англ.-М.: Мир, 1990. -235 с., ил.
Абельсон Х., Сассман Дж. Структура и интерпретация компьютерных программ - М.: Добросвет, КДУ, 2006. - 608 с.: ил.
Иван Братко. Алгоритмы искусственного интеллекта на языке PROLOG, 3-е издание. : Пер. с англ. - М.: Издательский дом Вильямс, 2004. - 640 с.: ил. Парал. тит. Англ.
Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. - Спб.: БХВ-Петер?/p>