Нахождение потока минимальной стоимости - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Нахождение потока минимальной стоимости, слайд №1

Нахождение потока минимальной стоимости, слайд №2

Нахождение потока минимальной стоимости, слайд №3

Нахождение потока минимальной стоимости, слайд №4

Нахождение потока минимальной стоимости, слайд №5

Нахождение потока минимальной стоимости, слайд №6

Нахождение потока минимальной стоимости, слайд №7

Нахождение потока минимальной стоимости, слайд №8

Нахождение потока минимальной стоимости, слайд №9

Нахождение потока минимальной стоимости, слайд №10

Нахождение потока минимальной стоимости, слайд №11

Нахождение потока минимальной стоимости, слайд №12

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Нахождение потока минимальной стоимости. Доклад-сообщение содержит 12 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 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 с.