Алгоритм Прима нахождения оптимального каркаса
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Содержание
Введение
. Постановка задачи
. Алгоритм Прима нахождения оптимального каркаса
. Реализация алгоритма на языке Пролог
. Примеры работы программ
Заключение
Список литературы
Приложение
Введение
Функциональные и логические языки программирования опираются на т.н. декларативную парадигму программирования. В отличии от императивной, где основное внимание уделяется разработке и реализации конкретных алгоритмов для решения определенного класса задач, в декларативной парадигме на первый план выходит формальное описание задачи, опираясь на которое вычислительная машина может сама найти путь к ее решению. Декларативный подход к разработке программ имеет перед императивным ряд преимуществ, среди которых большая выразительность и меньшая трудоемкость разработки. Меньшая трудоемкость, в частности, достигается за счет того, что программист может не заботиться о физическом представлении программы, организации памяти, взаимодействии с аппаратными средствами и т.п., и может полностью сосредоточиться на поиске решения задачи как таковой, оставляя реализацию решения компьютеру. Разумеется, у такого подхода есть и существенные недостатки, по-видимому, основным из которых является уменьшение производительности и неэффективное использование памяти. Тем не менее, этот недостаток не является критичным, поскольку в большинстве случаев к программе не предъявляются настолько жесткие требования, что использование декларативных языков становится нецелесообразным. Более того, в определенных случаях реализация на декларативных языках может оказаться даже эффективнее, чем на императивных (например, существует вариант реализации алгоритма быстрой сортировки на языке Haskell, который работает быстрее, чем реализация на языке C). Выразительность же декларативных языков является очень существенным преимуществом. Здесь можно процитировать Дональда Кнутта: Программы пишутся прежде всего для того, чтобы их читали люди. Программы на декларативных языках гораздо легче отлаживать, поскольку ошибки заведомо заложены только в решении, в то время как по статистике более 80% всех ошибок в программах на императивных языках составляют детали реализации, например, приведение типов.
В данной работе рассматривается применения языка логического программирования Пролог и языка функционального программирования Haskell для реализации алгоритма поиска оптимального каркаса графа.
1. Постановка задачи
Каркасом графа называют подграф без циклов, содержащий все вершины исходного графа и множество ребер которого является подмножеством ребер исходного графа. Оптимальным каркасом взвешенного графа называют G называют каркас, минимизирующий некоторую функцию от весов входящих в него ребер. Чаще всего в качестве такой функции выступает сумма весов ребер, реже - произведение, еще реже - произвольная сепарабельная функция. Отпимальный каркас еще называют кратчайшей связывающей сетью. Задача об отыскании оптимального каркаса является одной из наиболее часто возникающих задач в теории графов.
Существует большое количество алгоритмов поиска оптимального каркаса, показывающего различные результаты для различных типов графов. Очевидным является метод нахождения всех каркасов и выделение из них каркаса с минимальной функцией стоимости. Однако такой подход требует значительных вычислительных ресурсов для больших графов. К наиболее употребимым алгоритмам поиска оптимального каркаса относятся алгоритм Краскала, алгоритм Прима, алгоритм Соллина, алгоритм Тарьяна-Черитона. Эти алгоритмы гарантированно находят оптимальный каркас, при этом их эффективность различна для разных типов графов.
В данной курсовой работе рассматривается реализация алгоритма Прима поиска оптимального каркаса. Алгоритм Прима имеет преимущество перед другими алгоритмами нахождения оптимального каркаса в графах, близких к полным.
. Алгоритм Прима нахождения оптимального каркаса
Алгоритм Прима порождает оптимальный каркас посредством разрастания одного поддерева 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 = .
2.Для каждой вершины vj ~? Ts найти вершину aj ? Ts такую, что
c(aj, vj) = min[c(vi, vj)] = bj
и приписать вершине vj пометку [aj, bj]. Если такой вершины a нет, приписать вершине vj метку [0, ?].
.Выбрать такую вершину v*j, что
b*j = min[bj]
Обновить данные: Ts = Ts {v*j}, Ss = Ss {(a*j, v*j)}. Если |T| = n, то стоп. Ребра в Ss образуют оптимальный каркас. Если |Ts| < n, то перейти к п.4.
.Для всех vj ~? Ts таких, что vj ? Гv*j, обновить метки следующим образом:
Если bj > c(v*j, vj), то положить bj = c(v*j, vj), aj = v*j