Разбиение дискретного конечного множества элементов на основе кратчайшего остовного дерева
Задача дискретной математики о разбиении множества. Графовое представление связей между объектами. Анализ и тестирование алгоритма построения кратчайшего остовного дерева для ориентированного графа на основе решения задачи линейного программирования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | методичка |
| Язык | русский |
| Дата добавления | 15.01.2018 |
| Размер файла | 373,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
РАЗБИЕНИЕ ДИСКРЕТНОГО КОНЕЧНОГО МНОЖЕСТВА ЭЛЕМЕНТОВ НА ОСНОВЕ КРАТЧАЙШЕГО ОСТОВНОГО ДЕРЕВА
Составитель Кабанов Анатолий Николаевич
1. ЗАДАЧА ДИСКРЕТНОЙ МАТЕМАТИКИ О РАЗБИЕНИИ МНОЖЕСТВА
Первичные данные, сведенные в таблицу ”Объект-свойство”, часто бывают необозримыми, и непосредственно формирование отношений между объектами практически невозможно. Определение связей между объектами сильно облегчается, если исходное множество всех объектов удается описать более кратким способом, чем перечисление всех объектов со всеми их свойствами. Наиболее распространенный способ сокращения описания связан с разделением множества М объектов таблицы на небольшое число групп, связанных друг с другом каким-нибудь закономерным свойством. Обычно в качестве такого свойства используется ”похожесть” объектов одной группы. Закономерности ”групповой похожести ”позволяют намного сократить описание таблиц ”Объект-свойство” при малой потере информации. Вместо перечисления всех объектов можно дать список “типичных” или “эталонных” представителей групп, указать номера (имена) объектов, входящих в состав каждой группы. При небольшом числе групп описание данных становится обозримым и легко интерпретируемым.
В работе такая группировка делается с помощью построения кратчайшего остовного дерева. Алгоритмы разбиения отличаются друг от друга процедурой группировки и критерием качества разбиения множества. Введем некоторые обозначения. Пусть данные таблицы Т, подлежащие разбиению, содержат М объектов (а1,а2,..,аM) ,имеющих N свойств(x1,x2,…,xN), и требуется выявить К классов(S1,S2,…,SK), 1<K<N-1. Различные варианты разбиения объектов на К классов будем сравнивать по некоторому критерию качества разбиения F. Если свойства объекта представить себе в виде координат метрического пространства, то каждый объект со своими значениями свойств будет отображаться в некоторую точку этого пространства. Два объекта с почти одинаковыми значениями свойств отобразятся в две близкие точки, а объекты с сильно отличающимися свойствами будут представлены далекими друг от друга точками. Если имеются сгустки точек, отделенные промежутками от других сгустков, то их целесообразно выделить в отдельные структурные части множества - классы. В дальнейшем можно аппроксимировать сгустки каким-либо известным законом распределения. Можно также указать границы класса, описав их геометрические параметры (например, задав систему уравнений разделяющих гиперплоскостей). По этим описаниям можно узнать, какому классу принадлежит любой объект как изучаемой конечной выборки, так и любого нового объекта из генеральной совокупности.
В основу алгоритма разбиения положен метод разрезания кратчайшего остовного дерева. Если задано число классов К, то путем удаления (К-1) ребра, обеспечивающего оптимальное значение функции качества, производится разбиение на классы. В работе в качестве критерия разбиения множества элементов принято условие: суммарная дисперсия во всех классах должна быть минимальной.
дискретный математика граф линейный программирование
2. ГРАФОВОЕ ПРЕДСТАВЛЕНИЕ СВЯЗЕЙ МЕЖДУ ОБЪЕКТАМИ
Множество самых разнообразных задач естественно формулируется в терминах точек и связей между ними, т.е. в терминах графов. Поэтому эффективные алгоритмы решения задач теории графов имеют большое практическое применение.
Связи могут быть «направленными», как, например, в генеалогическом дереве или в сети дорог с односторонним движением. В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные и неориентированные.
Наиболее известный и популярный способ представления графов состоит в геометрическом изображении точек (вершин) и линий (ребер) на бумаге. При численном решении задач на вычислительных машинах граф должен быть представлен дискретным способом. Существует довольно много способов такого рода представления графов. Однако простота использования представления графа, как и эффективность алгоритма, в основе которого он лежит, в полной мере зависит от конкретного выбора этого представления. Одно из направлений теории графов связано с их матричным представлением. Существуют различные виды матриц, ассоциированные с графами. Эти алгебраические формы используются для решения многих задач теории графов.
Матрицей смежности ориентированного помеченного графа с n вершинами называется матрица A=[aij], i,j=1,2…n, в которой:
aij= m , если существует m ребер (xi, xj ),
0, если вершины xi , xj не связаны ребром (xi, xj).
Матрица смежности однозначно определяет структуру графа.
Граф называется взвешенным, если с каждым его ребром сопоставлено число. Простой взвешенный граф может быть представлен своей матрицей весов W=[wij], где wij - вес ребра, соединяющего вершины i, j =1,2..n. Веса несуществующих ребер полагают равными . Матрица весов является простым обобщением матрицы смежности.
При описании графа списком его ребер каждое ребро представляется парой его вершин. Это представление можно реализовать двумя массивами r=(r1, r2,…, rn) и t=(t1, t2,…, tn), где n - количество вершин в графе. Ребро Li,j графа выходит из вершины ri и входит в вершину tj. Здесь L - характеристика ребра, например вес ребра.
Деревом называется неориентированный граф, не имеющий циклов и изолированных вершин. Минимальным (кратчайшим) остовным деревом называется остовное дерево с минимальным общим весом его ребер.
3. ПОСТРОЕНИЕ КРАТЧАЙШЕГО ОСТОВНОГО ДЕРЕВА
3.1 Алгоритм Прима в табличной форме
По заданному графу заполняется матрица весов W(N, N). Веса несуществующих ребер предполагаются сколь угодно большими. Образуется массив P(N) меток вершин графа (столбцов матрицы весов). Алгоритм решения задачи заключается в последовательном заполнении массива меток столбцов и состоит из следующих этапов.
Предварительный этап. Обнуляется массив P(N) меток столбцов таблицы. Произвольно выбранному столбцу присваивается значение метки, равной его номеру.
Этап, повторяющийся N-1 раз (общий этап). В строках, номера которых равны номерам помеченных столбцов, находится минимальный элемент среди элементов непомеченных столбцов. Столбец, в котором находится минимальный элемент, помечается меткой, номер которой равен номеру его строки. В случае, если минимальных элементов несколько, то выбирается любой. После того, как будет помечен очередной столбец, элементу, симметричному относительно главной диагонали (для многомерного графа - с ”транспонированными индексами”) , присваивается сколь угодно большое значение.
Заключительный этап. Ребра, включенные в минимальное остовное дерево, определяются по меткам столбцов. Вес остовного дерева задается суммой весов входящих в него ребер.
Структурограмма алгоритма решения задачи о минимальном остовном дереве графа методом Прима, заданного матрицей весов W(N, N), показана на рис.1.
3.2 Алгоритм Краскала определения минимального остовного дерева
Для использования алгоритма Краскала применяется список ребер графа. Метод состоит в последовательном подключении к остовному дереву ребер с минимальным весом и заключается в следующем.
Предварительный этап. Список ребер сортируется в порядке возрастания весов. Ребро, имеющее минимальный вес (первое в упорядоченном списке), включается в искомый остов.
Этап, повторяющийся (N-1) раз (общий этап). Очередное ребро в списке включается в остов, если оно не образует цикл. Если ребро образует цикл с уже включенными в остов ребрами, то оно вычеркивается из списка и просматривается следующее по списку ребро.
Заключительный этап. Список включенных ребер составляет остов графа, а их суммарный вес определяет вес остовного дерева.
|
I=1;N |
||||||||
|
P(I)=0 |
||||||||
|
O(K)=K;Q=0 |
||||||||
|
I=1;N-1 |
||||||||
|
H= |
||||||||
|
L=1;N |
||||||||
|
P(L)0 Да |
Нет |
|||||||
|
J=1;N |
||||||||
|
P(J)=0 Да |
Нет |
|||||||
|
W(L,J) Да |
Нет |
|||||||
|
W(L, Да |
J)<H Нет |
|||||||
|
H=W(L,J) |
||||||||
|
X=L;Y=J |
||||||||
|
Q=Q+H; P(Y)=X; W(Y, X)= |
||||||||
|
I=1;N |
||||||||
|
IK Да |
Нет |
|||||||
|
Вывод: «вершина», I, «связана с вершиной», P(I) |
||||||||
|
Вывод: «вес остова=», Q |
Рис.1
3.3 Пример
Известна стоимость обеспечения связи между источником и потребителями информации (рис. 2).
Рис. 2
Нужно синтезировать топологию сети, обеспечивающей минимальную стоимость. Требуется определить методами Краскала и Прима минимальное остовное дерево графа G(5, 10), представленного на рис. 2.
Метод Прима. Матрица весов, получаемая после предварительного этапа алгоритма, представлена в табл. 1, где в качестве начальной выбрана вершина 3.
Задачей общего этапа является помечивание всех столбцов таблицы. В 3-й строке находится минимальный элемент w34=2. 4-й столбец, содержащий минимальный элемент, помечается номером строки, где этот элемент находится. Элементу w43 присваивается сколь угодно большое значение. В непомеченных столбцах 3-й и 4-й строк находится минимальный элемент w32=3. 2-й столбец, его содержащий, помечается номером 3-й строки. Элементу w23 присваивается сколь угодно большое значение. После этого шага матрица имеет вид, представленный в табл. 2.
В непомеченных столбцах 2, 3 и 4-й строк находится минимальный элемент w25 =1. 5-й столбец помечается номером 2-й строки, где находится минимальный элемент. Элементу w52 присваивается сколь угодно большое значение. На очередном шаге общего этапа в непомеченных столбцах 2, 3, 4 и 5-й строк находится минимальный элемент w21=5. 1-й столбец помечается номером 2, элементу w12 присваивается сколь угодно большое значение. Матрица после этого шага имеет вид, представленный в табл. 3.
Все столбцы таблицы помечены, общий этап закончен.
На заключительном этапе выписывается последовательность вершин, ребра между которыми включаются в минимальное остовное дерево. Это ребра, соединяющие вершины 1-2, 2-3, 3-4, 2-5.
Вес остовного дерева равен 5+3+2+1=11. Полученное остовное дерево показано на рис. 3.
Метод Краскала. По заданному графу (рис. 2) составляется список ребер (см. табл. 4), который на предварительном этапе упорядочивается в порядке возрастания весов (табл. 5). Ребро № 7, имеющее минимальный вес, включается в искомое остовное дерево (рис. 4). Выполняется общий этап. Второе по весу ребро № 6 также включается в остов. Следующее по весу ребро № 1 включается в остовное дерево, так как оно не образует цикла с ребрами № 6 и 7 (рис. 4). Ребро № 5 с минимальным весом среди оставшихся не включается в остов, так как оно образует цикл с ребрами № 1, 6 и 7. Следующее по весу ребро № 10 включается в остов. Вес остова равен 11, а его структура совпадает со структурой остова, полученного методом Прима (см. рис. 3).
Реализация алгоритма Краскала требует предварительной сортировки весов всех ребер. Алгоритм Прима не имеет этого недостатка.
3.4 Алгоритм построения кратчайшего остовного дерева для ориентированного графа на основе решения задачи линейного программирования
Пусть граф имеет следующий вид:
Веса ребер данного графа представлены в табл. 6:
Для данного графа составляется система уравнений, в которой учитывается, что все выходящие ребра берутся со знаком «+», а входящие - со знаком «-». В данном графе начальной является вершина № 1, а конечной - № 5. Число уравнений, входящих в систему, равно n, где n - число вершин графа. В данном примере n=5. Для начальной вершины сумма ребер должна равняться (n-1) (в данном примере 4), а для всех остальных вершин сумма равняется -1. Система уравнений имеет вид:
Данная система уравнений будет являться ограничением при поиске решения. При решении данной задачи необходимо найти минимум целевой функции:
х1+2*х2+0*х3+6*х4+7*х5+х6+5*х7.
Теперь рассмотрим реализацию данной задачи на Excel .
Вначале вводим значения ребер графа, т.е. значения х1 - х7 в ячейках B7:H7 (B7=x1, C7=x2, D7=x3, E7=x4, F7=x5, G7=x6, H7=x7). Они берутся произвольно и не влияют на решение. Затем вводим веса этих ребер соответственно в ячейках B9:H9 (B9=1, C9=2, D9=0, E9=6, F9=7, G9=1, H9=5). Далее в ячейках B11:B15 вводим систему уравнений:
B11=B7+C7+D7;
B12=H7-B7;
B13=F7-C7-H7-E7;
B14=E7+G7-D7;
B15=-F7-G7.
В ячейку I11 вводим целевую функцию:
B7*B9+C7*C9+D7*D9+E7*E9+F7*F9+G7*G9+H7*H9.
Теперь все условия для нахождения решения введены. Далее, выделив ячейку, содержащую целевую функцию ( I11), выбираем Сервис/Поиск решения. В открывшемся диалоговом окне указываем параметры:
- целевая ячейка: $I$11
- за счет изменения: $B$7:$H$7
- минимальное значение
- ограничения:
$B$11=4
$B$12=-1
$B$13=-1
$B$14=-1
$B$15=-1
$B$7: $H$7>=0.
Нажимаем «Выполнить». Найдено следующее решение: в ячейках, содержащих значения ребер, появляются новые значения. Ребра, не включаемые в искомый остов, принимают значение 0, а включаемые - любое другое значение. В данном примере в остов включаются ребра: х1, х2, х3, х6. Структура таблицы MS Excel с найденным решением представлена на рис. 6.
4. КОНТРОЛЬНЫЙ ТЕСТ ОБУЧАЮЩЕЙ СИСТЕМЫ ПО ИЗУЧЕНИЮ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ НАХОЖДЕНИЯ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА ГРАФА
Тест включает в себя десять вопросов. На каждый вопрос дается четыре варианта ответов. Один ответ является правильным, а остальные - нет. Информационная база вопросов реализована на MS Excel. Пользователю предлагается ответить на все десять вопросов. Отвечать на вопросы надо следующим образом. Прочитав вопрос и все четыре варианта ответа на него, пользователь должен выбрать из них тот вариант ответа, который считает правильным. Из всех вариантов ответа необходимо выбрать только один. Напротив выбранного ответа надо поставить единицу, после чего нужно переходить к следующему вопросу. После того как получены ответы на все вопросы, в поле «Результат» можно просмотреть сообщение о результатах проделанной работы. Это нужно проделать вместе с преподавателем, которому сдается данная лабораторная работа. Для просмотра результата преподаватель должен ввести в свою ячейку личный пароль. После ввода пароля необходимо вернуться в поле «Результат».
5. ВАРИАНТЫ ЗАДАНИЙ ПО ИЗУЧЕНИЮ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ НАХОЖДЕНИЯ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА ГРАФА
Вариант № 1
Вариант № 2
Вариант № 3
Вариант № 4
Вариант № 5
Вариант № 6
Вариант № 7
Вариант № 8
Вариант № 9
Вариант № 10
Вариант № 11
Вариант № 12
6. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ
1. Ознакомиться с методами решения задачи разбиения дискретного конечного множества элементов на основе кратчайшего остовного дерева.
2. С помощью обучающей программы проследить основные этапы решения задачи.
3. Ответить на тестовые вопросы и получить разрешение на выполнение работы.
4. Для заданного варианта рассчитать кратчайшее остовное дерево.
5. Для заданного варианта неориентированного дерева произвести разбиение множества. Пример расчета на MS Excel приведен на рис. 7.
6. Произвести сравнительный анализ вариантов разбиения множества.
7. Представить полученные подмножества системой линейных неравенств.
8. Представить графически полученное разбиение множества.
9. Кратко изложить возможности разбиения множества элементов в многомерном случае, когда объект характеризуется большим количеством параметров.
Рис. 7
7. СОДЕРЖАНИЕ ОТЧЕТА
1. Краткое описание задачи разбиения дискретного конечного множества
2. Результаты решения задачи по пунктам 4-9 выполнения лабораторной работы
3. Выводы
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Новиков Ф.A. Дискретная математика для программистов. СПб.: Питер, 2000. 304 c.(глава 9-Деревья).
2. Владимирский Б.М., Горстко А.Б., Ерусалимский Я.М. Математика. Общий курс. СПб.: Лань, 2002. 960 с.
Размещено на Allbest.ru
...Подобные документы
Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.
презентация [22,8 K], добавлен 16.09.2013Реализация алгоритмов Краскала и Прима для построения минимального остовного дерева взвешенного связного неориентированного графа. Анализ трудоемкости алгоритмов, их псевдокоды и тестирование. Применение алгоритма Краскала на практике в работе авиалиний.
курсовая работа [142,0 K], добавлен 25.12.2012Методы поиска подмножеств множества вершин V графа G, удовлетворяющих определенным условиям и свойствам. Понятие независимых множеств и порядок их генерации. Определение доминирующего множества. Основные этапы решения задачи о наименьшем разбиении.
контрольная работа [32,1 K], добавлен 11.03.2010Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов.
курсовая работа [195,5 K], добавлен 08.11.2009Разработка алгоритма реализации на ЭВМ процесса поиска кратчайшего пути в графе методом Дейкстры. Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа. Проверка работоспособности программы на тестовых примерах.
реферат [929,8 K], добавлен 23.09.2013Разработка программной реализации решения задачи о минимальном покрывающем дереве графа (построение минимального остова), используя алгоритмы Прима и Крускала. Подсчет времени работы алгоритмов. Их программная реализация на практике с помощью Delphi 7.
курсовая работа [538,1 K], добавлен 29.08.2010Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Разработка, макетирование и реализация экспертной системы для решения задачи о коммивояжере, используя возможности языка Prolog. Составление графа "Карта Саратовской области" и решение проблемы поиска кратчайшего пути между двумя пунктами на карте.
курсовая работа [366,4 K], добавлен 12.05.2009Постановка задачи. Математическое обоснование. Последовательность разбиений множества. Язык программирования. Реализация алгоритмов. Генерирование разбиений множества. Генерирование всех понятий.
курсовая работа [29,9 K], добавлен 20.06.2003Описание решения задачи, ее постановка, общий подход к решению. Представление исходных данных, условий задачи и целей ее решения. Составление алгоритма решения поставленной задачи. Написание программного обеспечения и тестирование конечного продукта.
курсовая работа [1,1 M], добавлен 03.07.2011Оптимизационная задача линейного программирования. Виды задач линейного программирования. Принятие решений на основе количественной информации об относительной важности критериев. Выбор средств разработки. Программный комплекс векторной оптимизации.
дипломная работа [1,3 M], добавлен 27.03.2013Математическая модель решения задачи коммивояжера. Поиск кратчайшего замкнутого пути обхода нескольких городов и возвращения в исходную точку. Описание программы и результатов ее тестирования. Основная форма программы после вывода конечных данных.
курсовая работа [603,3 K], добавлен 21.10.2012Алгоритм сортировки Шейкер: математическое описание задачи и описание алгоритма. Алгоритм покрытия: построение одного кратчайшего покрытия. Описание схемы и работы алгоритма на графах: нахождение кратчайшего пути. Контрольные примеры работы алгоритмов.
курсовая работа [43,8 K], добавлен 19.10.2010Исследование методов решения задачи о ходе коня. Описание алгоритмов для итеративной и рекурсивной программ. Генерация перестановок элементов по индексам. Построение эйлерова цикла на графе. Поиск кратчайшего пути на графе. Программная реализация задачи.
курсовая работа [411,6 K], добавлен 25.04.2013Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015История и термины теории графов. Описание алгоритма Дейкстры. Математическое решение проблемы определения кратчайшего расстояния от одной из вершин графа до всех остальных. Разработка программы на объектно-ориентированном языке программирования Delphi 7.
контрольная работа [646,9 K], добавлен 19.01.2016Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Разработка программы в среде Delphi для нахождения кратчайшего пути между стартом, лежащим в одной из вершин многоугольника, и финишем, находящимся на одной из сторон. Установка опорных точек, контроль целостности вводимых данных, методы решения задачи.
курсовая работа [778,8 K], добавлен 19.10.2010Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Теория множества, основные операции над множествами, мощность множества. Теорема о сравнении множеств. Размер множества в Turbo Pascal, предельно допустимое количество элементов и их порядок. Выполнение действий объединения, исключения и пересечения.
курсовая работа [376,6 K], добавлен 31.01.2016
