Использование методов неявного перебора для решения экстремальных задач на графах

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

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №2

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №3

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №4

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №5

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №6

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №7

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №8

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №9

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №10

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №11

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №12

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №13

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №14

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №15

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №16

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №17

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №18

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №19

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №20

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №21

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №22

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №23

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №24

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №25

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №26

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №27

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №28

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №29

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №30

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №31

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №32

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №33

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №34

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №35

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №36

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №37

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №38

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №39

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №40

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №41

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №42

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №43

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №44

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №45

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №46

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №47

Использование методов неявного перебора для решения экстремальных задач на графах, слайд №48

Содержание ▲

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

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

Слайд 1

Описание слайда:

Использование методов неявного перебора для решения экстремальных задач на графах Лекция 8 Поиск минимальных разрезов на взвешенных ориентированных сильносвязных графах с помощью МВГ

Слайд 2

Описание слайда:

СОДЕРЖАНИЕ: Часть 1. Текущий контроль Часть 2. Общие черты методов типа ветвей и границ. Часть 3. Методы типа ветвей и границ, осуществляющие поиск минимального разреза на сильносвязном взвешенном ориентированном графе фронтальным спуском по дереву ветвлений с помощью «наивных» методов вычисления оценок. Часть 4. Методы типа ветвей и границ, осуществляющие поиск минимального разреза на сильносвязном взвешенном ориентированном графе фронтальным спуском с учетом циркуляции на графе. Часть 5. Методы типа ветвей и границ, осуществляющие поиск решения задачи о минимальном разрезе на сильносвязном взвешенном ориентированном графе фронтальным спуском по дереву ветвлений, как задачи оптимального упорядочения вершин графа.

Слайд 3

Описание слайда:

Часть 1. Текущий контроль Решить три задачи, пользуясь методом типа ветвей и границ, осуществляющим фронтальный поиск по дереву ветвлений:

Слайд 4

Описание слайда:

ЧАСТЬ 2: МЕТОДЫ ТИПА ВЕТВЕЙ И ГРАНИЦ Две обязательные компоненты методов типа ветвей и границ: Построение дерева ветвления (выбор стратегии ветвления). Выбор методов вычисления оценок (зависит от специфики задачи).

Слайд 5

Описание слайда:

ИДЕЯ МЕТОДОВ ТИПА ВЕТВЕЙ И ГРАНИЦ Все множество планов решаемой задачи разбивается на ряд подмножеств. Для планов каждого подмножества вычисляется наилучшая оценка. На основании оценок отбрасываются те подмножества планов, которые заведомо не могут содержать наилучшего решения, а оставшиеся исследуются.

Слайд 6

Описание слайда:

СТРАТЕГИИ ВЕТВЛЕНИЯ Приняты две основные стратегии построения дерева ветвлений: Фронтальный спуск по дереву ветвлений. Движение по дереву ветвлений с возвратом.

Слайд 7

Описание слайда:

ЧАСТЬ 3 МЕТОДЫ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИЕ ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ ФРОНТАЛЬНЫМ СПУСКОМ ПО ДЕРЕВУ ВЕТВЛЕНИЙ

Слайд 8

Описание слайда:

ИДЕЯ ФРОНТАЛЬНОГО СПУСКА ПО ДЕРЕВУ ВЕТВЛЕНИЙ Три основных шага построения дерева ветвлений фронтальным спуском: 1. На множестве висячих вершин построенной части дерева выбирается вершина с наилучшей оценкой. 2. Ветвление осуществляется из вершины, выбранной на предыдущем шаге. 3. Если выбранной вершине отвечает случай, когда в базис введены все переменные, то алгоритм закончен – оптимальный план найден.

Слайд 9

Описание слайда:

ИЛЛЮСТРАЦИЯ К РЕАЛИЗАЦИИ ФРОНТАЛЬНОГО СПУСКА ПО ДЕРЕВУ ВЕТВЛЕНИЙ

Слайд 10

Описание слайда:

ПРИМЕР № 1: ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ -ИСХОДНЫЕ ДАННЫЕ Исходный граф G(X,U):

Слайд 11

Описание слайда:

ПРИМЕР № 1: ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – ПОСТРОЕНИЕ ДЕРЕВА ВЕТВЛЕНИЙ

Слайд 12

Описание слайда:

ПАРАМЕТРЫ ПОИСКА РЕШЕНИЯ В ПРИМЕРЕ 1 Число вычисленных оценок: 12. Число итераций: 6. Число операций сравнения: 21

Слайд 13

Описание слайда:

Достоинства и недостатки фронтального спуска по дереву ветвлений Достоинства: шанс на неполный перебор, первый же полный допустимый план является глобально оптимальным. Недостатки: по мере спуска по дереву ветвлений растет: число оценок, хранимых в памяти; затраты времени на их сравнение при выборе направления спуска.

Слайд 14

Описание слайда:

САМОСТОЯТЕЛЬНО Определить минимальный разрез на сильносвязном орграфе G(X,U), пользуясь методом типа ветвей и границ, осуществляющим фронтальный спуск по дереву ветвлений:

Слайд 15

Описание слайда:

ИСПОЛЬЗОВАНИЕ ЦИРКУЛЯЦИЙ ДЛЯ УТОЧНЕНИЯ ОЦЕНКИ Теорема В.Н. Буркова: Величина максимальной циркуляции не превышает величины минимального разреза. Пусть: U’ – подмножество удаляемых из графа G(X,U) дуг; G’(X,U\U’) – граф, полученный после удаления дуг подмножества U’; S(G’) – некоторая циркуляция на G’(X,U’); Δ(G’) – нижняя граница величины разреза, включающего дуги подмножества U’. Тогда справедливо:

Слайд 16

Описание слайда:

ВЫЧИСЛЕНИЕ МАКСИМАЛЬНОЙ ЦИРКУЛЯЦИИ НА ГРАФЕ 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).

Слайд 17

Описание слайда:

ПОИСК МАКСИМАЛЬНОЙ ЦИРКУЛЯЦИИ НА ОРГРАФЕ G(X,U) Исходный граф G(X,U):

Слайд 18

Описание слайда:

ПРИМЕР № 2: ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – НАЧАЛО ПОСТРОЕНИЯ ДЕРЕВА ВЕТВЛЕНИЙ И ВЫЧИСЛЕНИЕ ОЦЕНОК С УЧЕТОМ ЦИРКУЛЯЦИЙ НА ГРАФЕ ПРИМЕРА 1.

Слайд 19

Описание слайда:

ПРИМЕР № 2: ЗАВЕРШЕНИЕ ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – ПОСТРОЕНИЕ ДЕРЕВА ВЕТВЛЕНИЙ И ВЫЧИСЛЕНИЕ ОЦЕНОК С УЧЕТОМ ЦИРКУЛЯЦИЙ НА ГРАФЕ ПРИМЕРА 1.

Слайд 20

Описание слайда:

ПАРАМЕТРЫ ПОИСКА РЕШЕНИЯ В ПРИМЕРЕ 2 (вычисление уточненных оценок) Число вычисленных оценок: 10. Число итераций: 5. Число операций сравнения: 5.

Слайд 21

Описание слайда:

ДОСТОИНСТВА И НЕДОСТАТКИ ФРОНТАЛЬНОГО СПУСКА Достоинства: - гарантия глобально оптимального решения; - первый же выбранный полный план отвечает минимальному разрезу. Недостатки: - высокие требования к памяти используемого компьютера; - большие затраты времени на сравнение оценок.

Слайд 22

Описание слайда:

САМОСТОЯТЕЛЬНО Определить минимальный разрез на сильносвязном орграфе G(X,U), пользуясь: а) методом типа ветвей и границ, осуществляющим фронтальный спуск по дереву ветвлений; б) задачей о максимальной циркуляции для вычисления оценок.

Слайд 23

Описание слайда:

Решить самостоятельно, пользуясь МВГ, реализующим фронтальный спуск по дереву ветвлений

Слайд 24

Описание слайда:

ЧАСТЬ 4 МЕТОДЫ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИЕ ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ ДВИЖЕНИЕМ ПО ДЕРЕВУ ВЕТВЛЕНИЙ С ВОЗВРАТОМ

Слайд 25

Описание слайда:

ОСНОВНЫЕ ЭТАПЫ СТРАТЕГИИ ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА НА ДЕРЕВЕ ВЕТВЛЕНИЙ С ВОЗВРАТОМ В памяти компьютера постоянно присутствуют две величины: одна оценка Δ выбранного направления движения и текущее значение рекорда R. Если Δ меньше R, то осуществляется спуск по дереву ветвлений (расширение базиса), в противном случае – подъем (последняя введенная в базис переменная покидает его). Поиск завершается, когда алгоритм возвращается в стартовую вершину.

Слайд 26

Описание слайда:

АЛГОРИТМ ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ МЕТОДОМ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИЙ ДВИЖЕНИЕ ПО ДЕРЕВУ ВЕТВЛЕНИЙ С ВОЗВРАТОМ – ШАГИ 1 – 7. Шаг 1. R = +∞ Шаг 2. Каждой дуге графа G(X,U) присваивается уникальный индекс i (0

Слайд 27

Описание слайда:

ПРОДОЛЖЕНИЕ АЛГОРИТМА ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ МЕТОДОМ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИМ ДВИЖЕНИЕ ПО ДЕРЕВУ ВЕТВЛЕНИЙ С ВОЗВРАТОМ – ШАГИ 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 и вектор переменных, оптимальны.

Слайд 28

Описание слайда:

ПРИМЕР 3: ИСПОЛЬЗОВАНИЕ «ГРУБЫХ» МЕТОДОВ ВЫЧИСЛЕНИЯ ОЦЕНОК

Слайд 29

Описание слайда:

ИТОГИ ПОИСКА РЕШЕНИЯ В ПРИМЕРЕ 3 Число вычисленных оценок – 20 Число итераций – 20 Число операций сравнения - 20

Слайд 30

Описание слайда:

САМОСТОЯТЕЛЬНО Определить минимальный разрез на сильносвязном орграфе G(X,U), пользуясь методом типа ветвей и границ, осуществляющим поиск с возвратом по дереву ветвлений с «наивным» методом вычисления оценки.

Слайд 31

Описание слайда:

ПРИМЕР 4: ИСПОЛЬЗОВАНИЕ ЦИРКУЛЯЦИЙ ДЛЯ УТОЧНЕНИЯ ОЦЕНКИ

Слайд 32

Описание слайда:

ИТОГИ ПОИСКА РЕШЕНИЯ В ПРИМЕРЕ 4 Число вычисленных оценок – 10 Число итераций – 10 Число операций сравнения - 10

Слайд 33

Описание слайда:

ДОСТОИНСТВА И НЕДОСТАТКИ СТРАТЕГИИ, РЕАЛИЗУЮЩЕЙ ПОИСК С ВОЗВРАТОМ Достоинства: гарантия глобально оптимального решения; возможность прервать поиск и получить локально оптимальное решение; Низкие требования к памяти компьютера; Одна операция сравнения на каждой итерации. Недостатки: Даже после определения оптимального подмножества дуг, удаление которых разрывает все контуры графа, алгоритм продолжает поиск, чтобы убедиться в том, что полученное решение является глобально оптимальным.

Слайд 34

Описание слайда:

САМОСТОЯТЕЛЬНО Определить минимальный разрез на сильносвязном орграфе G(X,U), пользуясь методом типа ветвей и границ, осуществляющим поиск с возвратом по дереву ветвлений с уточнением оценки с помощью циркуляций:

Слайд 35

Описание слайда:

Решить самостоятельно, пользуясь уточненными оценками и МВГ, реализующим поиск с возвратом

Слайд 36

Описание слайда:

Часть 5. Методы типа ветвей и границ, осуществляющие поиск решения задачи о минимальном разрезе на сильносвязном взвешенном ориентированном графе фронтальным спуском по дереву ветвлений, как задачи оптимального упорядочения.

Слайд 37

Описание слайда:

Лемма 1 Любой перестановке вершин π сильносвязного графа G(X,U) отвечает подмножество дуг U’, идущих справа налево и являющихся разрезом.

Слайд 38

Описание слайда:

Содержательная и формальная постановки задачи

Слайд 39

Описание слайда:

Решить, пользуясь МВГ, осуществляющим фронтальный спуск по дереву ветвлений, задачу о минимальном разрезе на сильносвязном графе, как задачу оптимального упорядочения вершин

Слайд 40

Описание слайда:

Итерация № 1

Слайд 41

Описание слайда:

Итерация № 2

Слайд 42

Описание слайда:

Итерация № 3

Слайд 43

Описание слайда:

Итерация № 4

Слайд 44

Описание слайда:

Итерация № 5

Слайд 45

Описание слайда:

Итерация № 6

Слайд 46

Описание слайда:

Итерация № 7

Слайд 47

Описание слайда:

Вопрос Задача была решена за 7 итераций, сколько бы потребовалось итераций для ее решения полным перебором всех перестановок?

Слайд 48

Описание слайда:

самостоятельно Решить задачу о минимальном разрезе в сильносвязном графе G(X,U) методом типа ветвей и границ, как задачу оптимального упорядочения вершин, если граф задан матрицей М: M =