Разбиение дискретного конечного множества элементов на основе кратчайшего остовного дерева
Задача дискретной математики о разбиении множества. Графовое представление связей между объектами. Анализ и тестирование алгоритма построения кратчайшего остовного дерева для ориентированного графа на основе решения задачи линейного программирования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | методичка |
| Язык | русский |
| Дата добавления | 15.01.2018 |
| Размер файла | 373,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Подобные документы
Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.
презентация [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
