- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Нахождение потока минимальной стоимости презентация
Содержание
- 1. Нахождение потока минимальной стоимости
- 2. Введение Сетевые и графовые модели охватывают довольно
- 3. Постановка задачи Сколько ящиков Вы сможете транспортировать
- 4. Методы решения Задача о потоке минимальной стоимости
- 5. Используемый метод решения Улучшение предыдущего алгоритма: используя
- 6. Статистика и анализ статистики
- 7. Статистика и анализ статистики
- 8. Пример работы программы. Алгоритм Беллмана-Форда
- 9. Пример работы программы. Алгоритм Дейкстры
- 10. Заключение В нашей исследовательской работе были выявлены
- 11. Список используемой литературы Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн,
Слайд 1Исследовательский проект
на тему:
«Нахождение потока минимальной стоимости»
Выполнили:
Заляев Айрат
Назипова Люция
гр. 11-204
Слайд 2Введение
Сетевые и графовые модели охватывают довольно большой класс задач, встречающихся при
исследовании целого ряда проблем в транспорте, связи и других областях. Характерной особенностью задач, решаемых с помощью теории графов, является большая размерность поля данных. Поэтому возникает необходимость использования методов оптимизации, которые позволяют экономить вычислительные ресурсы и обеспечивают их гибкость по отношению к изменениям исходных данных.
Слайд 3Постановка задачи
Сколько ящиков Вы сможете транспортировать в аэропорт в день, учитывая
пропускную способность дорог, при этом, чтобы общее расстояние маршрутов было минимальным? Необходимо найти оптимальный маршрут перевозки – оптимальный поток в графе.
Слайд 4Методы решения
Задача о потоке минимальной стоимости может быть решена, используя линейное программирование.
Найти
любой поток данной величины, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Беллмана - Форда.
Использовать модификацию алгоритма Форда — Фалкерсона, в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.
Использовать модификацию алгоритма Форда — Фалкерсона, в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.
Слайд 5Используемый метод решения
Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к
задаче без отрицательных рёбер, после чего вместо алгоритма Беллмана-Форда воспользоваться алгоритмом Дейкстры. Алгоритм Беллмана-Форда придётся применить лишь на самом первом шаге.
Сложность - O(N^2*M*logM)
Сложность - O(N^2*M*logM)
Слайд 10Заключение
В нашей исследовательской работе были выявлены основные методы решения задачи на
потоках, освоены и применены оптимизационные алгоритмы, а также разобрана реализация этих алгоритмов на языке Java. Подводя итоги, можно отметить следующее: применение аппарата теории графов к решению различных классов задач на первый взгляд выглядит довольно громоздким, но его наглядность и рациональность определяют широту использования в различных сферах производства.
Слайд 11Список используемой литературы
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ /
Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с.
Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. М.: Высшая школа, 1976. — 392 с.
Гончаров Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. М.: ФОРУМ: ИНФРА-М, 2003. — 128 с.
Логинов Б.М. Введение в дискретную математику. М.: Калуга, 1998. — 423 с.
Майника Э. Алгоритмы оптимизации на сетях. М.: Мир, 1981. — 323 с.
Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.
Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. М.: Высшая школа, 1976. — 392 с.
Гончаров Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. М.: ФОРУМ: ИНФРА-М, 2003. — 128 с.
Логинов Б.М. Введение в дискретную математику. М.: Калуга, 1998. — 423 с.
Майника Э. Алгоритмы оптимизации на сетях. М.: Мир, 1981. — 323 с.
Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.
