Экспериментальное сравнение трудоемкости двух алгоритмов решения задачи построения наибольшего паросочетания минимального веса в двудольном графе

Краткая выдержка из текста работы (Аннотация)

Цель дипломной работы заключалась в написании программы, реализующей два алгоритма решения задачи построения наибольшего паросочетания минимального веса в двудольном графе и проведении экспериментальной оценки трудоемкости этих двух алгоритмов. Один из алгоритмов использует алгоритм решения транспортной задачи.

Для этого необходимо было:

1. Разобраться в предложенных алгоритмах решения задачи;

2. Создать программу для решения задачи и проведения экспериментов;

3. Провести сравнение и проанализировать полученные результаты.

Содержание работы

Введение..3

1. Цель работы.5

2. Основные определения и обозначения.6

3. Постановка задачи о назначении...8

4. Алгоритм решения задачи построения наибольшего паросочетания минимального веса...9

5. Постановка транспортной задачи13

6. Решение транспортной задачи.14

7. Сведение задачи о назначении к транспортной задаче.17

8. Реализация программы.18

9. Текст программы..23

10. Эксперименты.50

Заключение..187

Список литературы.188

Использованная литература

1. Бахтин А.Е., Колоколов А.А., Коробкова З.В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978. 160с.
2. Диниц Е.А. О решении двух задач о назначении: - в книге: Исследования по дискретной оптимизации.-М.: Наука, 1976, с.333-348
3. Заботин И.Я., Фазылов В.Р., Шульгина О.Н. Алгоритмы решения оптимизационных задач на графах: Учебное пособие. Казань: Казанский государственный университет им. В.И.Ульянова-Ленина, 2006. 68с.
4. Заботин И.Я. Лекции по линейному программированию: Учебное пособие. Казань: Издательство Казанского университета, 1985. 98с.
5. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. 323с.

Другие похожие работы

• Контрольная - 11 задач по высшей математике
• Контрольная - 10 задач по курсу высшая математика
• Контрольная - Анализ сети СМО
• Контрольная - 4 задачи по высшей математике
• Курсовая - Линейное и динамическое программирование
• Контрольная - 18 задач по высшей математике
• Дипломная - Функциональный метод решения неравенств
• Контрольная - Вычислительная математика
• Учебник - Симплес
• Контрольная - Для заданного на рисунке графа постройте минимальное остовное дерево, применив алгоритм Прима (построение начинать с вершины Е). В ответе укажите порядок в