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