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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Использование методов типа ветвей и границ для решения экстремальных задач на графах, слайд №1Использование методов типа ветвей и границ для решения экстремальных задач на графах, слайд №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
Скачать

Содержание ▲

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

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

Слайд 1


Использование методов типа ветвей и границ для решения экстремальных задач на графах Лекция 12 Поиск минимальных разрезов на взвешенных ориентированных сильносвязных графах
Описание слайда:
Использование методов типа ветвей и границ для решения экстремальных задач на графах Лекция 12 Поиск минимальных разрезов на взвешенных ориентированных сильносвязных графах

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


ЧАСТЬ 2 МЕТОДЫ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИЕ ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ ФРОНТАЛЬНЫМ СПУСКОМ ПО ДЕРЕВУ ВЕТВЛЕНИЙ
Описание слайда:
ЧАСТЬ 2 МЕТОДЫ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИЕ ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ ФРОНТАЛЬНЫМ СПУСКОМ ПО ДЕРЕВУ ВЕТВЛЕНИЙ

Слайд 7


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

Слайд 8


ИЛЛЮСТРАЦИЯ К РЕАЛИЗАЦИИ ФРОНТАЛЬНОГО СПУСКА ПО ДЕРЕВУ ВЕТВЛЕНИЙ
Описание слайда:
ИЛЛЮСТРАЦИЯ К РЕАЛИЗАЦИИ ФРОНТАЛЬНОГО СПУСКА ПО ДЕРЕВУ ВЕТВЛЕНИЙ

Слайд 9


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

Слайд 10


ПРИМЕР № 1: ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – ПОСТРОЕНИЕ ДЕРЕВА ВЕТВЛЕНИЙ
Описание слайда:
ПРИМЕР № 1: ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – ПОСТРОЕНИЕ ДЕРЕВА ВЕТВЛЕНИЙ

Слайд 11


ПРИМЕР № 1: ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – ИТЕРАЦИИ 7 - 10
Описание слайда:
ПРИМЕР № 1: ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – ИТЕРАЦИИ 7 - 10

Слайд 12


ПАРАМЕТРЫ ПОИСКА РЕШЕНИЯ В ПРИМЕРЕ 1 Число вычисленных оценок: 12. Число итераций: 6. Число операций сравнения: 21 Два верных ответа: z(3,2)=z(3,1)=1; R=7; z(2,3)=z(1,3)=1; R=7.
Описание слайда:
ПАРАМЕТРЫ ПОИСКА РЕШЕНИЯ В ПРИМЕРЕ 1 Число вычисленных оценок: 12. Число итераций: 6. Число операций сравнения: 21 Два верных ответа: z(3,2)=z(3,1)=1; R=7; z(2,3)=z(1,3)=1; R=7.

Слайд 13


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

Слайд 14


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

Слайд 15


ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ: НАЙТИ РАЗРЕЗ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ номер задания- справа от матрицы
Описание слайда:
ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ: НАЙТИ РАЗРЕЗ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ номер задания- справа от матрицы

Слайд 16


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

Слайд 18


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

Слайд 19


ПРИМЕР № 2: ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – НАЧАЛО ПОСТРОЕНИЯ ДЕРЕВА ВЕТВЛЕНИЙ И ВЫЧИСЛЕНИЕ ОЦЕНОК С УЧЕТОМ ЦИРКУЛЯЦИЙ НА ГРАФЕ ПРИМЕРА 1.
Описание слайда:
ПРИМЕР № 2: ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – НАЧАЛО ПОСТРОЕНИЯ ДЕРЕВА ВЕТВЛЕНИЙ И ВЫЧИСЛЕНИЕ ОЦЕНОК С УЧЕТОМ ЦИРКУЛЯЦИЙ НА ГРАФЕ ПРИМЕРА 1.

Слайд 20


ПРИМЕР № 2: ЗАВЕРШЕНИЕ ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – ПОСТРОЕНИЕ ДЕРЕВА ВЕТВЛЕНИЙ И ВЫЧИСЛЕНИЕ ОЦЕНОК С УЧЕТОМ ЦИРКУЛЯЦИЙ НА ГРАФЕ ПРИМЕРА 1.
Описание слайда:
ПРИМЕР № 2: ЗАВЕРШЕНИЕ ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА В БИСВЯЗНОМ ОРГРАФЕ – ПОСТРОЕНИЕ ДЕРЕВА ВЕТВЛЕНИЙ И ВЫЧИСЛЕНИЕ ОЦЕНОК С УЧЕТОМ ЦИРКУЛЯЦИЙ НА ГРАФЕ ПРИМЕРА 1.

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


САМОСТОЯТЕЛЬНО 2 Найти минимальный разрез на орграфе, приведенном в списке персональных заданий, пользуясь: Методом типа ветвей и границ, осуществляющим фронтальный спуск по дереву ветвлений; Циркуляциями на этом графе для уточнения оценок. Сравнить число вершин полученного дерева ветвлений.
Описание слайда:
САМОСТОЯТЕЛЬНО 2 Найти минимальный разрез на орграфе, приведенном в списке персональных заданий, пользуясь: Методом типа ветвей и границ, осуществляющим фронтальный спуск по дереву ветвлений; Циркуляциями на этом графе для уточнения оценок. Сравнить число вершин полученного дерева ветвлений.

Слайд 25


ЧАСТЬ 3 МЕТОДЫ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИЕ ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ ДВИЖЕНИЕМ ПО ДЕРЕВУ ВЕТВЛЕНИЙ С ВОЗВРАТОМ
Описание слайда:
ЧАСТЬ 3 МЕТОДЫ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИЕ ПОИСК МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ ДВИЖЕНИЕМ ПО ДЕРЕВУ ВЕТВЛЕНИЙ С ВОЗВРАТОМ

Слайд 26


ОСНОВНЫЕ ЭТАПЫ СТРАТЕГИИ ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА НА ДЕРЕВЕ ВЕТВЛЕНИЙ С ВОЗВРАТОМ В памяти компьютера постоянно присутствуют две величины: одна оценка Δ выбранного направления движения и текущее значение рекорда R. Если Δ меньше R, то осуществляется спуск по дереву ветвлений (расширение базиса), в противном случае – подъем (последняя введенная в базис переменная покидает его). Поиск завершается, когда алгоритм возвращается в стартовую вершину.
Описание слайда:
ОСНОВНЫЕ ЭТАПЫ СТРАТЕГИИ ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА НА ДЕРЕВЕ ВЕТВЛЕНИЙ С ВОЗВРАТОМ В памяти компьютера постоянно присутствуют две величины: одна оценка Δ выбранного направления движения и текущее значение рекорда 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.
Описание слайда:
АЛГОРИТМ ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ МЕТОДОМ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИЙ ДВИЖЕНИЕ ПО ДЕРЕВУ ВЕТВЛЕНИЙ С ВОЗВРАТОМ – ШАГИ 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 и вектор переменных, оптимальны.
Описание слайда:
ПРОДОЛЖЕНИЕ АЛГОРИТМА ПОИСКА МИНИМАЛЬНОГО РАЗРЕЗА НА БИСВЯЗНОМ ГРАФЕ МЕТОДОМ ТИПА ВЕТВЕЙ И ГРАНИЦ, ОСУЩЕСТВЛЯЮЩИМ ДВИЖЕНИЕ ПО ДЕРЕВУ ВЕТВЛЕНИЙ С ВОЗВРАТОМ – ШАГИ 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 и вектор переменных, оптимальны.

Слайд 29


ПРИМЕР 3: ИСПОЛЬЗОВАНИЕ «ГРУБЫХ» МЕТОДОВ ВЫЧИСЛЕНИЯ ОЦЕНОК
Описание слайда:
ПРИМЕР 3: ИСПОЛЬЗОВАНИЕ «ГРУБЫХ» МЕТОДОВ ВЫЧИСЛЕНИЯ ОЦЕНОК

Слайд 30


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

Слайд 31


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

Слайд 32


ПРИМЕР 4: ИСПОЛЬЗОВАНИЕ ЦИРКУЛЯЦИЙ ДЛЯ УТОЧНЕНИЯ ОЦЕНКИ
Описание слайда:
ПРИМЕР 4: ИСПОЛЬЗОВАНИЕ ЦИРКУЛЯЦИЙ ДЛЯ УТОЧНЕНИЯ ОЦЕНКИ

Слайд 33


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

Слайд 34


ИСПОЛЬЗОВАНИЕ ЦИРКУЛЯЦИЙ ДЛЯ УТОЧНЕНИЯ ОЦЕНКИ И ЗАВЕРШЕНИЯ ПОИСКА
Описание слайда:
ИСПОЛЬЗОВАНИЕ ЦИРКУЛЯЦИЙ ДЛЯ УТОЧНЕНИЯ ОЦЕНКИ И ЗАВЕРШЕНИЯ ПОИСКА

Слайд 35


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

Слайд 36


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

Слайд 37


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

Слайд 38


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию