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

Презентация:



Advertisements
Похожие презентации
Введение в теорию сетевого планированияВведение в теорию сетевого планирования.
Advertisements

ПОТОКИ В СЕТЯХ. Определения Сеть - связный ориентированный граф G = (V, A) без петель и мультидуг, с 1 источником s V и 1 стоком t V. (Запретим одновременное.
Динамическое программирование (Dynamic Programming)
Основные понятия теории NP-полноты P NP?. Задачи распознавания свойств Класс задач распознавания свойств (ЗРС) – множество проблем, решением которых является.
Паросочетания и задача о назначениях. Определения Задан граф G = (V, E). Подмн. ребер M E является паросочетанием в G, если v V инцидентно 1 ребра из.
Тема 6. Транспортная логистика Презентация подготовлена преподавателем кафедры «Прикладной математики» Тесёлкиной Е.С.
Элементы теории матричных игр. Определения процесс принятия решений в конфликтных ситуациях… игры 2 (парные) и n 3 лиц. участники игры - игроки. Игра.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда.
Линейное программирование Задача теории расписаний.
Номер варианта выбирается по параметру зачетки d 10 соотв Задача Коммивояжёра Имеется n городов, занумерованных числами.
NP-полнота Основные NP-полные задачи. Задача «Независимое множество» Условие. Задан граф G=(V,E) и целое число k. Вопрос. Существует ли независимое множество.
1 Приближенные алгоритмы Комбинаторные алгоритмы.
АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ..
Подготовил Андреев Алексей. Задача о назначениях Задача о рюкзаке Задача коммивояжера Задача теории распределений Задача маршрутизации транспорта Задача.
Л АБОРАТОРНАЯ РАБОТА 6 Тема: Численные методы решения задачи Коши для обыкновенных дифференциальных уравнений.
Приближенные схемы Задачи теории расписаний. Полиномиальная приближенная схема (PTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется.
К созданию архитектуры поисковой системы в наборах документов. Горелов С.С. МГУ им. М.В. Ломоносова механико-математический факультет.
Классификация и регрессия Доклад по курсу Интеллектуальный анализ данных Закирова А.Р. 1.
1 Комбинаторные алгоритмы Задача о k-центрах. 2 Метрическая задача o k центрах Дано: Полный граф G = (V, E), стоимости ребер cost: E Q + такие, что для.
Транксрипт:

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

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

Метод ветвей и границ (МВГ) Ветвлением мн. 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 либо произвольное доп. решение, либо не известен.

Правила отсечения МВГ последовательно выполняет итерации (шаги). На очер. итер. выбирается и проверяется нек. не отсеченное мн. В результате оно либо отбрасывается (отсекается), либо разбивается на непустые подмн. < мощности (ветвится). Пусть 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 ).

Ветвление Если 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

Корректность алгоритма Теорема. Приведенный алгоритм МВГ находит решение задачи за конечное число шагов. Доказательство. Конечность алг. из след. 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 ), что противоречит предположению (*). (*)

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

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

МВГ для задачи КМ Задан полный граф 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

Ветвление Если 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

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

Вычисление НГ Функция удовлетворяет и 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) …

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

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

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

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

построения НГ для задачи КМ 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 является НГ для ц.ф. задачи КМ

построения НГ для задачи КМ 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

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

Аддитивный алгоритм Балаша (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

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

Упорядоченность решений при 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. решения частично упорядочены.

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

Правила отсечения Правило 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 вершины могут быть исключены.

Правила отсечения Правило 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.