Методы неявного перебора. Рассмотрим общую постановку задачи дискретной оптимизации где n-мерный вектор x конечному мн. доп. решений D. Постановка задачи. - презентация

1 Методы неявного перебора

2 Рассмотрим общую постановку задачи дискретной оптимизации где n-мерный вектор x конечному мн. доп. решений D. Постановка задачи можно перебрать все решения и выбрать opt… В методах неявного перебора доп. мн. решений разбивается на не подмн. < мощности. Затем анализируется возможность исключения этих подмн., а также улучшения найденного доп. решения (рекорда). В результате возможно сокращение перебора доп. решений. Метод ветвей и границ Аддитивный алгоритм Балаша.

3 Метод ветвей и границ (МВГ) Ветвлением мн. d D наз. функцию b : d {d 1, …, d N }, d k d, d k, k = 1, …, N, разбивающую мн. d на несобственные подмн. Числовая функция H наз. нижней границей функционала f на мн. d, если: {x} – одноэлементное мн. Наз. рекордом, и обозн. его x 0, наилучшее из найденных доп. решение. Величина f(x 0 ) является верхней границей (ВГ) функционала задачи. Сначала рекорд x 0 либо произвольное доп. решение, либо не известен.

4 Правила отсечения МВГ последовательно выполняет итерации (шаги). На очер. итер. выбирается и проверяется нек. не отсеченное мн. В результате оно либо отбрасывается (отсекается), либо разбивается на непустые подмн. < мощности (ветвится). Пусть t 1, …, t L мн. не отсеченных подмн. решений. (первоначально L = 1, t 1 = D.) Мн. t i, 1 i L отсекается в одном из 2-х, последовательно проверяемых, случаев: a) если H(t i ) f(x 0 ); b) если H({t i }) = f(t i ) < f(x 0 ). Т.е. 1-элем. мн. отсекается всегда. Последнее неравенство имеет место, т.к. 1-элем. мн. не было удалено по критерию a). Значит, в случае b) происходит смена рекорда x 0 = t i и ВГ f(x 0 ).

5 Ветвление Если t 1,…,t M, M L не проверенные подмн., то: если M = 0, то x 0 opt реш. задачи, и алг. останавливается; если M > 0, то среди мн. t 1,…,t M выбираем перспективное подмн., пусть это t 1, и осуществляем его ветвление. Получим подмн. d 1,…,d N, t 2,…,t M, L=N+M 1. Перенумеруем эти подмн. числами 1, …, L и повторим шаг алг. d t1t1 tMtM d1d1 dNdN t2t2

6 Корректность алгоритма Теорема. Приведенный алгоритм МВГ находит решение задачи за конечное число шагов. Доказательство. Конечность алг. из след. 4 свойств: 1) На каж. шаге выбранное подмн. либо удаляется, либо разбивается на непустые подмн. < мощности. 2) 1-элем. мн. исключаются всегда. 3) Подмн. не проверяются > 1 раза. 4) Исходное мн. доп. решений D конечно. Докажем opt найденного решения. Предположим противное: после остановки алгоритма, рекорд x 0 не является opt решением задачи. Значит, на каком-то шаге opt решение x* было удалено вместе с нек. мн. t на основании правила а), т.е. H(t) f(x 0 ). Значит, f(x * ) H(t) f(x 0 ), что противоречит предположению (*). (*)

7 Реализация МВГ Если получение ВГ сопряжено с трудностями, тогда для быстрого нахождения рекорда следует применять схему одностороннего ветвления, когда разбивается мн. min мощности. 1-элем. мн. и доп. решение (1 рекорд) будут найдены быстро. Мн., имеющее min НГ, может с большой вероятностью содержать решение, близкое (по функционалу) к opt, что приведет к получению хорошего рекорда (и ВГ). Выбор такого мн. для дальнейшего разбиения определяет схему всестороннего ветвления. Если при реализации алг. критической является память, тогда схема одностороннего ветвления предпочтительнее.

8 Реализация МВГ Для решения МВГ конкретной задачи следует определить: способ представления подмн. решений; схему и способ ветвления; алг. вычисления НГ; метод нахождения рекорда. Время работы алг. зависит от многих факторов. Теоретически не исключен полный перебор решений. Практически же следует найти компромисс между точностью и сложностью вычисления НГ, что позволит найти решение, близкое к opt, за приемлемое время. Более точное вычисление НГ может позволить отсечь больше решений, но потребует и больше времени, что может привести к длительному выполнению 1 итерации.

9 МВГ для задачи КМ Задан полный граф G = (V, E), V = {1,…,n}. дуге (i, j) E приписана длина c ij 0. Требуется найти гамильтонов контур min длины. Подмн. решений представим 2 мн.: частичным маршрутом I = {i 1,…,i p }, списком J = {j 1,…,j q } V \{i 1,…,i p } запрещенных переходов из последнего города i p частичного маршрута. Положим: {i 1, …, i p } – простой путь из вершины i 1 в вершину i p ; f(i 1, …, i n ) – длина гамильтонова контура {i 1, …, i n, i 1 }; i 1 = 1. i1i1 i2i2 ipip j1j1 jqjq

10 Ветвление Если p < n – 1, то 0 q n – p – 2. Если же p = n – 1, то q = 0, т.е. мн. (I, J) определяют ед. решение. Функция ветвления b делит мн. гам. контуров (I, J), на 2 подмн. Для этого выбирается некоторая вершина i V = V \ (I J). Если кроме i в множестве V ! вершина k, то: I = {i 1, …, i p, i}, J =, а другое мн. I = {i 1, …, i p, k}, J =. Если в V > 2 эл., то 1 мн. I = {i 1, …, i p, i}, J =, а 2 мн. I = {i 1, …, i p }, J = {j 1, …, j q, i}. i1i1 ipip i k i1i1 ipip i

11 Вычисление НГ Введем матрицу где для незапрещенных дуг, идля запрещенных. Вычислим Лемма. Если {i 1, …, i n, i 1 } – гам. контур мн. (I, J), то f(i 1, …, i n ) H(I, J). Доказательство. Из определения i и j имеем: 0

12 Вычисление НГ Функция удовлетворяет и 2-му свойству НГ. H({x}) = f(x), т.к. в случае p=n 1, имеем n-1 = c n-1,n, n = c n1, 1 = 0, n = 0. Для произвольного мн. (I, J) можно найти доп. решение, например, используя жадный алгоритм: иди в ближайшую вершину, где еще не был, начиная с вершины p и учитывая запреты J… Выбор вершины i для ветвления мн. (I, J) …

13 – – – – – – – – – – H=154 f(1,3,2,5,4,1) =164 Пример

14 – – – – – H= – – – – – H=154 f(1,3,2,5,4,1) =164 Пример

15 – – – – – f(1,3,5,4,2,1)=160 Пример

16 f(1,3,2,5,4,1) =164 f(1,3,5,4,2,1)=160 Пример

17 построения НГ для задачи КМ 2-й способ построения НГ для задачи КМ Задача о назначениях. Имеется n работ и n исполнителей, c ij 0 – затраты, связанные с назначением i-го исп. на j-ю работу. Каждая работа должна быть выполнена 1 исполнителем, и каждый исполнитель должен выполнить 1 работу. Требуется назначить исп. на работы : общие затраты min. x ij =1, если исполнитель i назначен на работу j; x ij =0 в противном случае. T=O(n 3 ). Предположим, что c ij = длине перехода i j и положим c ii = +, i = 1, …, n. Z является НГ для ц.ф. задачи КМ

18 построения НГ для задачи КМ 3-й способ построения НГ для задачи КМ Пусть c ij =c ji, i, j=1,…,n. Рассмотрим произвольную в. i. На мн. V\{i} построим остовный граф T i min веса W(T i ). Пусть ребра (i, p) и (i, q) имеют min длину среди всех ребер, инцидентных i. Граф Q i = T i {(i, p)} {(i, q)} наз. 1-деревом для вершины i. Вес этого 1-дерева Q i, равный W(Q i )=W(T i )+c ip +c iq, является НГ длины min гам. цикла. Если выбрать вершину k: W 1 =W(Q k ) W(Q i ), i V, то W 1 является лучшей (наибольшей) НГ, получаемой с помощью 1-деревьев. T= O(n 3 ) i p q

19 – – 766 3– 48 4– 2 5– Пример построения 1-дерева НГ = 17

20 Аддитивный алгоритм Балаша (1) (2) Наз. решением мн. {x j : x j =1, j N 1 ; x j =0, j N\N 1, N={1,…,n}}. Решение является допустимым, if выполняются неравенства (2). Пусть 0 c 1 c 2 … c n. (if j : c j

21 Диаграмма 2 n решений разобьем на n+1 подмн. с номерами k=0,1,…,n: k-е подмножество содержит все решения с k переменными = 1 и n k переменными = 0.

22 Упорядоченность решений при k=0, подмн. решений состоит из 1 решения х = 0; при k=1, подмн. решений включает n решений, в которых x i =1; x j =0, j i; i=1,…,n; k-е подмножество состоит из На диаграмме каж. вершина, содержащая список N 1, представляет решение, в котором переменные с индексами из N 1 равны 1, а остальные – 0. Так вершина (1,3) соответствует решению x 1 =x 3 =1; x 2 =x 4 =0. решений. Если в диаграмме путь из u в v, то в. u наз. предшествующей для в. v, а v - следующей за u. решения частично упорядочены.

23 Алгоритм Алгоритм начинает работу с вершины х = 0. Затем просматривает след. за ней вершины. Перебор может быть сокращен на основе различных правил: Правило 1. Т.к. 0 c 1 c 2 … c n, то зн. ц.ф. при переходе к след. решению может только возрасти. если нек. вер. соответствует доп. решению, то след. за ней вершины исключаются. допустимое 7 след. решений исключены

24 Правила отсечения Правило 2. Пусть Z * min (рекордное) зн. ц.ф. на найденных доп. реш., Z Q – зн. ц.ф. в вершине V Q, где x j =1, j Q; x j =0, j N\Q. Если для некоторого r имеет место неравенство Z Q +c r >Z *, то достаточно проверять только те следующие вершины, в кот. x r =x r+1 =x n =0 (в силу неравенств 0 c 1 c 2 … c n ). Правило 3. Пусть вер. V Q задает реш. x j =1, j Q; x j =0, j N\Q. все след. в. должны иметь x j =1, j Q. Такие пер. наз. фиксированными для след. в. Остальные - свободными. Вершина V Q может оказаться недоп. из-за нек. неравенств (2). Пример. Q={1,2} и –x 1 –x 2 +x 3 +x 4 1. Даже, если у след. вершин переменные x 3 =x 4 =1, то данное неравенство не может быть выполнено. все след. за V Q вершины могут быть исключены.

25 Правила отсечения Правило 4. Для произвольной вер. V Q могут ограничения, кот. «заставят» фиксировать значения нек. свободных переменных. Пример. 3x 1 –x 2 –2x 3 =0, и вершина V Q определена переменными x 1 =1; x j =0, j=2,…,n. все след. вершины должны иметь фиксированные переменные x 2 =x 3 =1.