При решении некоторых оптимизационных задач точное решение можно заменить приближенным.
2. Задача разлагается на более простые (дерево общего вида), которые решаются методом компьютерного поиска.
Корню дерева соответствует исходная задача.
· - корень
· · · - промежуточные
· · · · · · - листья
Листьям соответствуют легко решаемые элементарные задачи (в ЭВМ – элементарные логические операции).
Это называется деревом разложения задачи или деревом поиска. Полностью дерево строить необязательно. Достаточно на нем рассмотреть оптимальное решение с минимальными затратами.
Метод ветвей и границ.
Каждой дуге соответствует цена, зависящая от сложности промежуточного решения, которая влияет на выбор направления движения.
При нахождении np минимальной стоимости проверяем его на приемлимость и вновь расцепляем. Так до получения приемлимого решения (оно получится минимальной стоимости).
Поиск в ширину и поиск в глубину (по одной строке).
Возможно отсечения не устраивающих нас ветвей дерева.
Правила редуцирования – замена исходных данных более простыми с сохранением самой задачи, при этом полученное решение пригодно для исходной задачи. Существует множество редуционных правил.
Задача о кратчайшем покрытии.
М, QÍМ .
Задача: выбрать TÍQ : 1) U[T] = M. Каждый элемент M должен принадлежать хотя бы одному элементу из входящих в Т. 2) |T|=min.
М – множество специальностей.
Q ={q1, … , q2, …}, qi ÍM , qi – подмножество, которое определяет, какими специальностями обладают люди.
Как скомплектовать группу людей, содержащую min число людей и покрывающих все специальности? (ее матричная подстановка называется задачей о кратчайшем покрытии булевой матрицы).
Задача о кратчайшем покрытии.
Т.е. требуется найти min число столбцов, покрывающих все строки.
Принцип жадной стратегии. Без предварительного анализа и “предсказания” шагов.
1 1 0 Минимальное столбцовое покрытие
1 1 0 Жадный алгоритм: сначала 1, а потом 2 и 3.
1 0 1 Но min является 2 и 3.
1 0 1
0 1 0
0 0 1
Пошаговая оптимизация – аналог жадного алгоритма, не обеспечивающая (не гарантирующая) глобальной оптимизации.
Минимальный алгоритм:
Определяем, что столбец 2 и столбец 3 входят в ядро решения. Они покрывают все строки, значит задача решена.
Точный метод комбинированного поиска в общем слове.
Основан на дереве (дереве поиска).
1 0 1 1 0 Решение упрощенной
задачи должно быть решением
0 1 1 0 0 общей задачи. Каждая строка предъявлет свое условие.
1 1 1 0 0 Они находятя в отношении импликации.
0 0 0 1 1
Правило удаления поглощающих строк:
1 0 1 1 0
0 1 1 0 0 Можно выбросить при
поиске одного минимального
1 1 1 0 0 покрытия, но не всех.
0 0 0 1 1
Можно удалять поглощаемые столбцы.
1 1
0 1 1 0 Повторяем процедуру после удаления столбцов и строк в
2 0 1 1 0 0 nn.
4 0 0 0 1 1
c d
2 1 0 - циклический остаток матрицы.
4 0 1
Правильное приращение покрытия:
если строка содержит лишь одну1 => столбец включается в покрытие.
В соответствии с правилами индуцирования решение годится и для общей матрицы.
Входные столбцы удаляются со всеми покрываемыми строками. Правило ращепления: отыскивается min по числу 1 строка и поочередно рассматриваются столбцы, имеющие в этой строке 1.
Правило возврата: если найдено некоторое покрытие, но последний перебор ограничен => рассматриваем покрытие с мощностью < данного.
Разложение по минимальной строке.
a
b c d e f g h i
1 1 0 0 0 0 1 0 1 1
2 0 1 1 0 0 0 1 0 0 Ращепление по 4 строке:
3 0 0
1 1 0 1 0 0 1
4 1 0 0 1 1 0 0 0 0 1, 3, Q
5
0 0 1 0 0 0 1 1 1
4
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.