Презентация Использование методов типа ветвей и границ для решения экстремальных задач на графах онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Использование методов типа ветвей и границ для решения экстремальных задач на графах абсолютно бесплатно. Урок-презентация на эту тему содержит всего 38 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Использование методов типа ветвей и границ для решения экстремальных задач на графах
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:38 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:260.43 kB
- Просмотров:99
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
Содержание слайда: СОДЕРЖАНИЕ:
Часть 1. Общие черты методов типа ветвей и границ.
Часть 2. Методы типа ветвей и границ, осуществляющие поиск минимального разреза на сильносвязном взвешенном ориентированном графе фронтальным спуском по дереву ветвлений с помощью «наивных» методов вычисления оценок.
Часть 3. Методы типа ветвей и границ, осуществляющие «поиск с возвратом» минимального разреза на сильносвязном взвешенном ориентированном графе.
№4 слайд
Содержание слайда: ИДЕЯ МЕТОДОВ ТИПА ВЕТВЕЙ И ГРАНИЦ
Все множество планов решаемой задачи разбивается на ряд подмножеств.
Для планов каждого подмножества вычисляется наилучшая оценка.
На основании оценок отбрасываются те подмножества планов, которые заведомо не могут содержать наилучшего решения, а оставшиеся исследуются.
№7 слайд
Содержание слайда: ИДЕЯ ФРОНТАЛЬНОГО СПУСКА ПО ДЕРЕВУ ВЕТВЛЕНИЙ
Три основных шага построения дерева ветвлений фронтальным спуском:
1. На множестве висячих вершин построенной части дерева выбирается вершина с наилучшей оценкой.
2. Ветвление осуществляется из вершины, выбранной на предыдущем шаге.
3. Если выбранной вершине отвечает случай, когда в базис введены все переменные, то алгоритм закончен – оптимальный план найден.
№13 слайд
Содержание слайда: Достоинства и недостатки фронтального спуска по дереву ветвлений
Достоинства: шанс на неполный перебор, первый же полный допустимый план является глобально оптимальным.
Недостатки: по мере спуска по дереву ветвлений растут:
число оценок, хранимых в памяти;
затраты времени на их сравнение при выборе направления спуска.
№16 слайд
Содержание слайда: ИСПОЛЬЗОВАНИЕ ЦИРКУЛЯЦИЙ ДЛЯ УТОЧНЕНИЯ ОЦЕНКИ
Теорема В.Н. Буркова: Величина максимальной циркуляции не превышает величины минимального разреза.
Пусть: U’ – подмножество удаляемых из графа G(X,U) дуг; G’(X,U\U’) – граф, полученный после удаления дуг подмножества U’; S(G’) – некоторая циркуляция на G’(X,U’); Δ(G’) – нижняя граница величины разреза, включающего дуги подмножества U’.
Тогда справедливо:
№17 слайд
Содержание слайда: ВЫЧИСЛЕНИЕ МАКСИМАЛЬНОЙ ЦИРКУЛЯЦИИ НА ГРАФЕ G(X,U)
Формальная постановка задачи определения S(G’):
Контуры на графе:
a1 = {1,3,1};
a2 = {2,3,2};
a3 ={1,3,2,1}.
где - k – й контур множества A(G’);
r(i,j) – пропускная способность дуги (i,j);
s - циркуляция в контуре ;
A(i,j) – множество контуров, проходящих
через дугу (i,j).
№22 слайд
Содержание слайда: ДОСТОИНСТВА И НЕДОСТАТКИ ФРОНТАЛЬНОГО СПУСКА
Достоинства:
- гарантия глобально оптимального
решения;
- первый же выбранный полный план
отвечает минимальному разрезу.
Недостатки:
- высокие требования к памяти
используемого компьютера;
- большие затраты времени на сравнение
оценок.
№24 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО 2
Найти минимальный разрез на орграфе, приведенном в списке персональных заданий, пользуясь:
Методом типа ветвей и границ, осуществляющим фронтальный спуск по дереву ветвлений;
Циркуляциями на этом графе для уточнения оценок.
Сравнить число вершин полученного дерева ветвлений.
№26 слайд
Содержание слайда: ОСНОВНЫЕ ЭТАПЫ СТРАТЕГИИ ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА НА ДЕРЕВЕ ВЕТВЛЕНИЙ С ВОЗВРАТОМ
В памяти компьютера постоянно присутствуют две величины: одна оценка Δ выбранного направления движения и текущее значение рекорда R.
Если Δ меньше R, то осуществляется спуск по дереву ветвлений (расширение базиса), в противном случае – подъем (последняя введенная в базис переменная покидает его).
Поиск завершается, когда алгоритм возвращается в стартовую вершину.
№27 слайд
Содержание слайда: АЛГОРИТМ ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ МЕТОДОМ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИЙ ДВИЖЕНИЕ ПО ДЕРЕВУ ВЕТВЛЕНИЙ С ВОЗВРАТОМ – ШАГИ 1 – 7.
Шаг 1. R = +∞
Шаг 2. Каждой дуге графа G(X,U) присваивается уникальный индекс i (0<i<│U│+1) и переменная zi .
Шаг 3. i = 1
Шаг 4. zi = 1
Шаг5. Одним из рассмотренных в части 1 методов вычисляется оценка Δ.
Шаг 6. Если Δ < R, то перейти к шагу 7, нет – к шагу 10
Шаг 7. Если все ограничения удовлетворяют, то
перейти к шагу 8, нет к шагу 10.
№28 слайд
Содержание слайда: ПРОДОЛЖЕНИЕ АЛГОРИТМА ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ МЕТОДОМ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИМ ДВИЖЕНИЕ ПО ДЕРЕВУ ВЕТВЛЕНИЙ С ВОЗВРАТОМ – ШАГИ 8 – 15.
Шаг 8. Если i = n, то перейти к шагу 9, нет – к шагу 14
Шаг 9. R = F, печать R и вектора
Шаг 10. Если zi = 1, то перейти к шагу 11, нет – к шагу 13.
Шаг 11. zi = 0, перейти к шагу 5.
Шаг 12. Если i = 1, то перейти к шагу 15, нет к шагу 13.
Шаг 13. i = i - 1, перейти к шагу 10.
Шаг 14. i = i + 1, перейти к шагу 4.
Шаг 15. Конец алгоритма. Последние выданные на печать значения R и вектор переменных, оптимальны.
№36 слайд
Содержание слайда: ДОСТОИНСТВА И НЕДОСТАТКИ СТРАТЕГИИ, РЕАЛИЗУЮЩЕЙ ПОИСК С ВОЗВРАТОМ
Достоинства:
гарантия глобально оптимального решения;
возможность прервать поиск и получить локально оптимальное решение;
Низкие требования к памяти компьютера;
Одна операция сравнения на каждой итерации.
Недостатки:
Даже после определения оптимального подмножества дуг, удаление которых разрывает все контуры графа, алгоритм продолжает поиск, чтобы убедиться в том, что полученное решение является глобально оптимальным.
Скачать все slide презентации Использование методов типа ветвей и границ для решения экстремальных задач на графах одним архивом:
-
Использование методов неявного перебора для решения экстремальных задач на графах
-
Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ
-
Многообразие схем. Информационные модели на графах. Использование графов при решении задач
-
Решение простейших задач линейного программирования графическим методом
-
Использование графов при решении задач. 9 класс
-
Решение задач с использованием оператора циклов
-
Решение задач с использованием условного оператора
-
Решение задач в Mathcad и Excel. Использование функции IF (ЕСЛИ). Лабораторная работа 1
-
Решение задач линейного программирования графическим методом
-
Работа по решению любой задачи с использованием компьютера