Вход

оптимизационные задачи на графах

Рекомендуемая категория для самостоятельной подготовки:
Курсовая работа*
Код 66309
Дата создания 2014
Страниц 17
Источников 4
Мы сможем обработать ваш заказ 26 сентября в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
1 810руб.
КУПИТЬ

Содержание

Содержание ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. Основные определения и понятия теории графов . . . . . . . 2 2. Оптимизационные задачи на графах . . . . . . . . . . . . . . 4 3. Алгоритм построения минимального остова . . . . . . . . . . 7 4. Реализация жадного алгоритма поиска минимального остовного дерева на MatLab . . . . . . . . . . . . . . . . . . . 8 5. Тестирование работы программы поиска минимального остовного дерева . . . . . . . . . . . . . . . . . . . . . . . . 12 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Список использованной литературы . . . . . . . . . . . . . 18 Содержание

Фрагмент работы для ознакомления

Ввод исходных данных: матрица с координатами вершин и матрица с ребрами и их весами: clear all disp('Решение задачи о минимальном покрытии') V=[0 4;1 4;2 4;3 4;4 4;0 3;1 3;2 3;3 3;4 3;... 0 2;1 2;2 2;3 2;4 2;0 1;1 1;2 1;3 1;4 1;... 0 0;1 0;2 0;3 0;4 0]; E=[1 2 1;3 2 2;4 3 3;5 4 4;6 1 5;2 7 6;8 2 7;3 8 8;... 9 4 9;9 5 8;10 5 7;7 6 6;8 7 5;8 9 4;10 9 3;11 6 2;... 7 12 1;13 8 2;14 9 3;15 10 4;12 11 5;13 12 6;13 14 7;... 14 13 8;5 5 10;15 14 9;16 11 8;12 17 7;13 18 6;... 20 15 5;17 16 4;17 18 3;18 17 2;19 18 1;19 20 2;... 5 5 8; 21 16 3;17 22 4;18 22 5;22 18 6;18 23 7;... 19 24 8;20 25 9;21 22 8;22 21 7;23 24 6;10 10 8;... 24 23 5;24 25 4]; grPlot(V,E); % начальный граф title('\bfНачальный граф со взвешенными ребрами') На рис. 5 показан скриншот для исходного графа, полученный после описанных шагов программы . Рис. 5 Исходный граф со взвешенными ребрами Сначала для сравнения решим невзвешенную задачу. В этом случае процедура строит первое встретившееся остовное дерево. nMST=grMinSpanTree(E(:,1:2)); % покрывающее дерево fprintf('Количество ребер в покрывающем дереве = %d\n',length(nMST)); fprintf('Общий вес = %d\n',sum(E(nMST,3))); grPlot(V,E(nMST,:)); % покрывающее дерево title('\bfПокрывающее дерево') На рис. 6 представлен скриншот для остовного, но не минимального дерева, в котором количество ребер 24 и их общий вес 114. Теперь получим минимальное остовное дерево и сравним результаты: количество ребер в минимальном остовном дереве = 24; общий вес = 81. nMST=grMinSpanTree(E); % минимальное покрывающее дерево fprintf('Количество ребер в минимальном покрывающем дереве = %d\n',... length(nMST)); fprintf('Общий вес = %d\n',sum(E(nMST,3))); grPlot(V,E(nMST,:)); % минимальное покрывающее дерево title('\bfМинимальное покрывающее дерево') На рис. 7 представлен скриншот для минимального остовного дерева, в котором количество ребер 24 и их общий вес 81. Таким образом, разработанная программа позволяет решить задачу о минимальном остовном дереве. Количество ребер в покрывающем дереве = 24 Общий вес = 114 Рис. 6. Скриншот работы программы при получении остовного, но не минимального дерева Количество ребер в минимальном покрывающем дереве = 24 Общий вес = 81 Рис. 7. Скриншот работы программы при получении минимального остовного дерева Заключение Проблема построения минимального остовного дерева достаточно разносторонняя, известна давно и продолжает исследоваться и сегодня. В настоящей работе представлен только базовый алгоритм. Задача построения минимального остовного дерева встречается в различных областях. Интересным ее применением является проблема построения смешанного остовного дерева: построить для графа дерево со свойствами минимального остовного дерева и дерева кратчайших путей. Другой важной задачей является быстрое обновление минимального остовного дерева при изменении графа. Здесь стоит отметить, что задача о минимальном остовном дереве является упрощением реальности. В самом деле, если соединяемые объекты находятся в вершинах единичного квадрата, разрешается соединять любые его вершины, и стоимость строительства пропорциональна его длине, то минимальное покрывающее дерево будет состоять из трех сторон квадрата. Между тем все его четыре вершины можно соединить двумя пересекающимися диагоналями, суммарная длина которых будет равна 2√2, что меньше 3 в первом случае. Список использованной литературы 1. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2005. — 1296 с. 2. Мартынов Н.Н. Matlab 7. Элементарное введение. М: "Кудиц-Образ", 2005г, 416 стр. EAN: 9785957900481 3. Потемкин В. Вычисления в среде MATLAB. Диалог-МИФИ. 2004. 4. Потемкин В. Система MATLAB. Справочное пособие. Диалог-МИФИ, 1997. Содержание ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Основные определения и понятия теории графов . . . . . . . 2 Оптимизационные задачи на графах . . . . . . . . . . . . . . 4 Алгоритм построения минимального остова . . . . . . . . . . 7 Реализация жадного алгоритма поиска минимального остовного дерева на MatLab . . . . . . . . . . . . . . . . . . . 8 Тестирование работы программы поиска минимального остовного дерева . . . . . . . . . . . . . . . . . . . . . . . . 12 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Список использованной литературы . . . . . . . . . . . . . 18 18 V4 V3 V1 V2 V1 V1 V1 V1 V1 V4 V1 V1 V3 V2 V3 V4 V3 V1 V4

Список литературы [ всего 4]

Список использованной литературы 1. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2005. — 1296 с. 2. Мартынов Н.Н. Matlab 7. Элементарное введение. М: "Кудиц-Образ", 2005г, 416 стр. EAN: 9785957900481 3. Потемкин В. Вычисления в среде MATLAB. Диалог-МИФИ. 2004. 4. Потемкин В. Система MATLAB. Справочное пособие. Диалог-МИФИ, 1997. список литературы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
© Рефератбанк, 2002 - 2022