Содержание
- 2. Декомпозиция пространства решений Множество возможных вариантов решения М разбивается в соответствии с принципом формирования результата на
- 3. Декомпозиция пространства решений Принцип разбиения пространства решений связан с видом преобразований, которые необходимо выполнить над графом
- 4. Декомпозиция в ширину Все множество возможных вариантов решения M разбивается на подмножества первого уровня Mi1 такие,
- 5. Декомпозиция в ширину Рассмотрим задачу поиска всех простых цепей (маршрутов) из вершины х1 в вершину x4
- 6. Таким образом на первом шаге (на 2-ом уровне дерева решений) множество М разбивается на три непересекающихся
- 7. Декомпозиция в глубину с возвращением Все множество возможных вариантов решения M разбивается на подмножества М1 и
- 8. Декомпозиция в глубину с возвращением Выделим на 1-ом шаге из множества М подмножество М1, включив в
- 9. Стратегии декомпозиции пространства решений Отметим, что декомпозиция в ширину и в глубину с возвращением приводит к
- 10. Стратегии декомпозиции пространства решений Рассмотренные стратегии лежат в основе решения многих задач дискретной математики. Укажем некоторые
- 11. Глубинное или d-дерево Вершина xj ∈ F1xi называется потомком вершины xi, сама вершина xi – отцом
- 12. Глубинное или d-дерево На рисунке (б) показано глубинное дерево неориентированного графа G~(X, U) (а) для случая,
- 13. Глубинное или d-дерево ориентированного графа Глубинное дерево может строиться и в ориентированном графе. На рис. а
- 14. Глубинное или d-дерево ориентированного графа В этом дереве дуги графа разбиты на четыре класса: Древесные дуги,
- 15. Дерево поиска в ширину (b-дерево) Является частным случаем построения дерева декомпозиции в ширину, а именно –
- 16. Дерево поиска в ширину (b-дерево) Для каждой вершины путь до нее из корня является одним из
- 17. Особенности просмотра в глубину с возвращением и в ширину в ориентированном графе В ориентированных графах d
- 18. Вычислительная сложность просмотра в глубину с возвращением и в ширину Просмотр графа как в глубину с
- 19. 4.2 Поиск решения с использованием оценочной функции В практике проектирования обычно необходимо найти одно решение, наилучшее
- 20. Оценка варианта в процессе генерации Существование некоторой оценки, позволяющей с некоторой достоверностью судить о том, содержит
- 21. Особенности оценочных функций Оценочные функции могут быть определены: на любых подмножествах вариантов; на некоторых подмножествах вариантов.
- 22. Особенности оценочных функций Различают два вида оценочной функции: отсекающую оценку, которая достоверно указывает, что исследу-емое подмножество
- 23. Выбор оценочных функций Выбор оценочной функции – один из самых сложных и ответственных этапов подготовки задачи
- 24. Выбор оценочных функций В качестве отсекающей оценки для большинства комбинаторно-оптимизационных задач может выступать опорное решение, т.
- 25. Способы отсечения ветвей дерева решений Можно выделить четыре основных способа отсечения ветвей. 1. Для подножеств, соответствующих
- 26. Способы отсечения ветвей дерева решений 3. Сравнение оценки (нижней – Fн(Mi) или верхней – Fв(Mi) границы)
- 27. Невычисляемая отсекающая оценка Вырожденным случаем оценочной функции является невычисляемая отсекающая оценка, например, некоторое заранее сформулированное условие.
- 28. Задача о кодовом замке Если комбинация не подходит, либо ее или некоторое множество комбинаций нет смысла
- 29. 4.3 Жадный метод Этот метод осуществляет поиск решения задачи в процессе декомпозиции по методу в ширину.
- 30. Жадный метод если оценка выбора является отсекающей, т.е. с вероятностью, равной единице, позволяет судить о том,
- 31. Пример. Алгоритм Прима построения остовного дерева минимального веса Алгоритм реализует жадный метод поиска решения: на первом
- 32. Пример. Алгоритм Прима построения остовного дерева минимального веса Теоретически доказано, что выбор на каждом шаге ребра
- 33. Разбиение задачи на подзадачи Разбиение задачи на подзадачи определяется видом решения (остовное дерево, кусок графа и
- 34. 4.4 Поиск в ширину и в глубину с возвращением Последовательное получение решений при декомпозиции как в
- 35. Поиск в ширину и в глубину с возвращением В ходе решения, если возможно, уточняется значение отсекающей
- 36. 4.4.1 Поиск в глубину с возвращением Поиск в глубину с возвращением рассмотрим на примере задачи нахождения
- 37. Поиск в глубину с возвращением На рисунке показан ориентированный граф (а), две ветви дерева решений (б)
- 38. Поиск в глубину с возвращением Ребро, соединяющее две вершины дерева решений, будет соответствовать ребру графа G→,
- 39. 4.4.2 Поиск в ширину Задачу коммивояжера можно решать и методом поиска в ширину. На рисунке показано
- 40. 4.4.3 Метод параллельного поиска множество решений разбивается на подмножества 1-го уровня, каждая вершина которого становится началом
- 41. Метод параллельного поиска В зависимости от специфики задачи подмножества разных ветвей могут быть как пересекающимися, так
- 42. 4.5 Метод ветвей и границ Универсальный, хотя и достаточно сложный, метод точного решения широкого круга комбинаторно-оптимизационных
- 43. Метод ветвей и границ В качестве оценки перспективности ветви используется верхняя Fв(Mi) или нижняя Fн(Mi) границы
- 44. Способы отсечения Можно выделить три основных способа отсечения ветвей: По результатам сравнения оценок сверху или снизу
- 45. Способы отсечения 2. По результатам сравнения оценок сверху и снизу, например, если в задаче на минимум
- 46. Выбор принципа разбиения и оценочной функции Точность оценки зависит от принципа разбиения множества вариантов на подмножества
- 47. Способы ветвления Разбиение множества вариантов на подмножества по методу в ширину и выбор вершины ветвления по
- 48. Способы ветвления 3. Комбинация двух рассмотренных способов. Например, строится одна ветвь. Далее развитие дерева решений происходит
- 49. Пример. Задача нахождения простой цепи (маршрута) минимальной длины между заданными вершинами графа Принцип разбиения: последовательное включение
- 50. Построение оценочной функции Вначале в качестве нижней границы используем сумму длин ребер построенного фрагмента. Ветвление по
- 51. Построение оценочной функции (2) Конструирование оценочных функций должно базироваться на анализе сущности задачи (в данном случае
- 52. Построение оценки верхней границы Сконструированная функция не возрастает; ее значение в конечных вершинах равно значению целевой
- 53. Построение оценки нижней границы Сконструированная функция не убывает; ее значение в конечных вершинах равно значению целевой
- 54. Дерево решений с оценками Для конкретного графа и выбранных оценочных функций количество просматриваемых вершин зависит от
- 55. Поиск маршрута максимальной длины при ветвлении в ширину и выборе вершины ветвления по максимуму верхней границы
- 56. Поиск маршрута максимальной длины при последовательном ветвлении и порядке построения ветвей справа налево В данном случае
- 57. Поиск маршрута максимальной длины при последовательном ветвлении и порядке построения ветвей слева направо В данном случае
- 58. Поиск маршрута минимальной длины при ветвлении в ширину и выборе вершины ветвления по минимуму нижней границы
- 59. Поиск маршрута минимальной длины при последовательном ветвлении справа налево В данном случае будут исследованы не все
- 60. Поиск маршрута минимальной длины при последовательном ветвлении слева направо x1 Fн=5 x2 1 Fн=7 x4 8
- 61. 4.6 Метод Дейкстры В настоящее время в специальной литературе с разной степенью детализации описан алгоритм Дейкстры
- 62. Метод Дейкстры 2. Подзадачи не могут быть сформированы заранее, так как зависят от структуры исследуемого графа
- 63. Метод Дейкстры Задача: поиск маршрута (простой цепи) минимальной длины из некоторой исходной точки в заданную конечную.
- 64. Метод Дейкстры Оценочная функция в каждой вершине дерева – суммарная длина ребер уже построенного фрагмента маршрута
- 65. Метод Дейкстры Докажем,что задача обладает свойством оптимальности – любая часть кратчайшего пути сама есть кратчайший путь.
- 66. Метод Дейкстры Обозначим начальную вершину маршрута xН, а конечную xК. Количество только тех маршрутов, которые проходят
- 67. Идея алгоритма Дейкстры Тогда, если xi – начальная вершина, xj – конечная вершина, xk –промежуточная вершина,
- 68. 4.7 Метод Форда-Фалкерсона Этот метод является обобщением широко известного алгоритма того же названия. Метод является основой
- 69. Метод Форда-Фалкерсона Моделью сети является ориентированный граф G→(X, ), где f функция, значение которой показывает количество
- 70. Метод Форда-Фалкерсона если c(uj) = f(uj), то удаляется ребро uj, соединяющее вершину xi с вершиной xk,
- 71. Метод Форда-Фалкерсона Метод в целом заключается в следующем: 1. Задается начальное состояние сети: в графе сети
- 72. Метод Форда-Фалкерсона 3. В графе сети G→ суммарный поток F увеличивается на ∆f. Значения передаваемого потока
- 73. Метод Форда-Фалкерсона Пример поиска максимального потока в сети. Рисунок иллюстрирует поиск максимального потока в сети, приведенной
- 74. Метод Форда-Фалкерсона Деревья поиска дополняющего пути
- 75. Метод Форда-Фалкерсона Дерево поиска дополняющего пути Методом Форда-Фалкерсона за полиномиальное время может быть решена, например, задача
- 76. 4.8 Метод динамического программирования Динамическое программирование решает задачу, объединяя решение подзадач и выбирая лучший вариант из
- 77. Метод динамического программирования Идея метода: решение идет от малых подзадач к большим; возможные (допустимые) решения получаются
- 78. Пример. Вычисление произведения матриц Рассмотрим вычисление произведения n матриц M = М1 × М2 × …
- 79. Пример. Вычисление произведения матриц Процесс перебора всех порядков, в которых можно вычислить произведения всех матриц с
- 80. Пример. Вычисление произведения матриц Возможны следующие порядки умножения трех матриц: 1) M1, M2, M3: M1×(M2 ×
- 81. Пример. Вычисление произведения матриц Возможные порядки умножения четырех матриц: (M1×(M2×M3))×M4 с оценкой m1,2,3,4= 2200; M1×((M2×M3)× M4)
- 82. Пример. Вычисление произведения матриц Объединением деревьев свертки будет граф возможных порядков умножения матриц последовательности. На рисунке
- 83. Пример. Вычисление произведения матриц На последующих рисунках показаны первый, второй и третий шаги процесса решения задачи.
- 84. Количество операций вычислений произведений Mi × Mi+1 ×… × Mj Разбиение исходной задачи на подзадачи, количество
- 85. 4.9 Метод итерационного улучшения Метод выполняет ограниченный и нередко упорядоченный перебор вариантов решения, генерируя их из
- 86. Метод итерационного улучшения - парные обмены Положим для определенности, что лучшему варианту решения задачи соответствует минимум
- 87. Парные обмены После перестановки элемента xi в Х2, а xj в Х1, получим вариант решений k1
- 88. Парные обмены Такой итерационный процесс может привести к нахождению только локального оптимума (FL,kL). Пройти локальный оптимум
- 89. Групповой обмен Рассмотрим один из способов определения группы. Для всех пар вершин xi∈X1 и xj∈X2 определяют
- 90. Групповой обмен (2) Обмен любой пары вершин не улучшает значение критерия. Перенос вершин х1 и х2
- 91. Характеристика метода итерационного улучшения Алгоритмы, реализующие итерационный метод, требуют значительно больше машинного времени, чем алгоритмы по
- 92. 4.10 Генетический метод Все рассмотренные ранее методы основаны на детерминированном поиске решения. Если оценочная функция не
- 93. Сущность генетического метода Задается начальная популяция и рассчитываются значения локальной целевой функции. Выбирается лучшее решение и
- 94. Пример генерационного цикла получения строки из 8 двоичных символов с максимальным количеством единиц Популяция состоит из
- 95. Характеристика генетического метода Алгоритмы, реализующие генетический метод, гарантируют получение лишь приближенного решения. Обладая достоинствами детерминированных алгоритмов
- 96. 4.11 Метод параллельно-последовательной n-арной свертки Метод предназначен для объединения элементов множества X в некоторые подмножества. В
- 97. Метод параллельно-последовательной свертки При объединении подмножеств (элементов) происходит отсечение других вариантов состава подмножеств. Очевидно, что точность
- 98. Метод параллельно-последовательной свертки Возможны два варианта окончания процесса свертки: процесс заканчивается, когда все элементы множества свернуты
- 99. Метод параллельно-последовательной свертки Процесс свертки можно наглядно представить в виде дерева, в котором вершины j-го уровня
- 100. Двоичная свертка Различают уравновешенную и неурав-новешенную двоичную свертку. При уравновешенной или параллельной двоичной свертке вновь образован-ный
- 101. Характеристика метода двоичной свертки Метод двоичной свертки не гарантирует нахождение точного решения. Действительно, пусть на некотором
- 102. Алгоритм сортировки слияниями Алгоритм реализует метод двоичной свертки и является точным. Попарно сравнивая числа исходного множества,
- 103. Характерные особенности метода двоичной свертки при сортировке слияниями критерий слияния подмножеств – их принадлежность к одному
- 105. Скачать презентацию