Содержание
- 2. Сети: Транспортные, электрические, коммуникационные Сетевое представление: ? мощное визуальное и концептуальное средство для представления отношений компонентов
- 3. Пример: Парк Кирова предназначен для экскурсий и пикников. Использование машин запрещено. Предусмотрена система дорог (для велосипедов
- 4. Система дорог для парка Кирова
- 5. Администрация парка сталкивается с тремя проблемами: - Определить маршрут от входа до станции T с наименьшим
- 6. Сеть = точки, соединенные линиями. Точки = узлы (вершины) – показаны окружностями. Линии = дуги (звенья,
- 7. Ориентированный путь= Последовательность дуг из узла i в узел j с направлением в узел j. Неориентированный
- 8. (A? B? C? E)= ориентированный путь (поток к E допустим). (B? C? A? D)= неориентированный путь
- 9. Два узла = связаны, если сеть содержит по крайней мере один неориентированный путь между ними. Связанные
- 10. Пропускная способность дуги = максимальное значение потока на ориентированной дуге. Узлы, либо сетевые генераторы потока, либо
- 11. Пример связующего дерева
- 12. ЗАДАЧА НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ В неориентированной и связанной сети с двумя особыми узлами (отправления и назначения).
- 13. Алгоритм нахождения кратчайшего пути: Цель n-ной итерации: Найти n-ный ближайший к началу узел (повторяем для n
- 14. Кандидаты для n-го ближайшего узла: Каждый решенный узел непосредственно соединенный звеном с одним или более нерешенным
- 15. Решение задачи кратчайшего пути на примере о парке Кирова: Администрации парка Кирова необходимо найти кратчайший путь
- 16. Tретья колонка (кандидаты на n-й узел) (нерешенные узлы с кратчайшим связующим звеном до решенного узла). Четвертая
- 17. Алгоритм нахождения кратчайшего пути на примере парка Кирова
- 18. Ввод для n-ной итерации: даны 5-й и 6-й столбцы для предыдущих итераций, где решенные узлы в
- 19. ЗАДАЧА МИНИМАЛЬНОГО СВЯЗУЮЩЕГО ДЕРЕВА Задача минимального связующего дерева имеет некоторое сходство с основной версией задачи нахождения
- 20. Минимальное связующее дерево: 1. Даны узлы сети, но не звенья. Вместо этого, учитываем потенциальные звенья и
- 21. Для сети с n узлами требуется только (n - 1) звено для обеспечения пути между каждой
- 22. Звенья в (b) охватывают сеть (т.е., сеть связана), но это не дерево, потому что есть два
- 23. Применение: 1. Проектирование телекоммуникационных сетей (волоконно-оптические сети, компьютерные сети, выделенные линии телефонных сетей, сети кабельного телевидения).
- 24. Связующее дерево для парка Кирова – только (с) – связующее дерево
- 25. Первый этап: выбор самого короткого звена к другому узлу, не думая о влиянии этого выбора на
- 26. Алгоритм минимального связующего дерева : 1. Произвольно выбираем любой узел, соединяем его с ближайшим отдельным узлом.
- 27. Применение минимального связующего дерева на примере парка Кирова: Руководство должно определить, под какими дорогами должны быть
- 28. Все узлы теперь связаны, так что это решение является оптимальным. Общая длина звеньев составляет 14 км.
- 36. ЗАДАЧА МАКСИМАЛЬНОГО ПОТОКА Третьей задачей, стоящей перед администрацией парка в пик сезона является составление маршрутов поездок
- 37. С учетом ограничений, одним из допустимых решений является отправка 7 трамваев / день, таким образом 5
- 38. 1. Поток через ориентированные и связанные сети начинается в исходном узле и заканчивается в узле-приемнике [вход
- 39. Задача о максимальном потоке на примере парка Кирова.
- 40. Применение: 1. Увеличить поток дистрибьюторской сети компании от своих заводов до заказчиков. 2. Увеличить поток сети
- 41. Для некоторых приложений, потоки сети начинаются в нескольких узлах и заканчиваются в нескольких узлах, но задача
- 42. Фиктивный источник = в узле начинается поток, который на самом деле начинается в другом узле. Для
- 43. Алгоритм: Задача о максимальном потоке = задача линейного программирования, решается симплекс-методом. Используется более эффективный алгоритм добавляемого
- 44. Число дуг рядом с узлом дает остаточную пропускную способность для потока из этого узла в другой
- 45. Минимальная остаточная пропускная способность = остаточная пропускная способность добавляемого пути(она представляет собой величину потока, которая допустимо
- 46. Алгоритм нахождения увеличивающего пути для задачи максимального потока: 1. Определить увеличивающий путь – находим в остаточной
- 47. При выполнении шага 1 часто будет присутствовать число альтернативных увеличивающих путей, из которых нужно выбрать один.
- 48. Применение алгоритма для задачи максимального потока парка Начинаем с исходной остаточной сети, назначаем новую остаточную сеть
- 49. Исходная остаточная сеть для задачи максимального потока парка Кирова.
- 51. Итерация 2: Назначим поток 3 для увеличивающего пути O? A? D? T. Получившаяся остаточная сеть имеет
- 52. Итерация 3: Назначим поток 1 для увеличивающего пути O? A? B? D? T. Итерация 4: Назначим
- 53. Итерация 5: Назначим поток 1 для увеличивающего пути O? C? E? D? T. Iteration 6: Назначим
- 54. Итерация 7: Назначим поток 1 для увеличивающего пути O? C? E? B? D? T. Получившаяся остаточная
- 55. Оптимальное решение для задачи максимальных потоков парка Кирова.
- 56. Текущая модель потоков: определяется - Накопленными заданными потоками, или - Сравнением конечных пропускных способностей с исходными
- 57. Нахождение увеличивающего пути: Определяем узлы, которые могут быть связаны с источником при помощи одной единственной дуги
- 58. Величина разреза = сумма пропускных способностей разрезанных ребер (в заданном направлении). Теорема минимального разреза максимального потока:
- 59. Процедура нахождения увеличивающего пути в итерации 7 задачи максимального потока парка Кирова.
- 61. Скачать презентацию