logo search
shpori (1) / shpori (1)

24.Метод локального поиска и поиска с запретами. Задача о максимальном разрезе.

Алгоритм локального поиска:

Идея: Построить какое-то решение и стараться его улучшить до тех пор, пока это возможно.

1) Для каждого решения S задачи определим его окрестность N(S) – мн-во решений близких к S.

2) Найдём какое-то начальное решение S0.

3) Посмотрим решения из N(S0), если найдем решение S N(S0), такое что w(S) < w(S0), то положим S= S0 и снова повторим 3, если не найдём , то стоп. Фактически алгоритм локального поиска ищет локальный оптимум. Качество этого алгоритма зависит от того, как определяются окрестности решений.

Алгоритм 2-замены для задачи о коммивояжере.

Вибираем два несмежных ребра и заменяем их другими так чтобы снова получился гамильтонов цикл, всего таких соседей: n(n-3)/2 – число способов выбрать 2 пары вершин из всех.

Локальный поиск для задачи о max разрезе.

Вход: граф G=(V,E)

Найти: рабиение мн-ва V на 2 подмн-ва A и B такое, что число рёбер между A и B максимально.

Мн-во решений – все разбиения (A,B), окрестность решения (A,B) – это все разбиения вида: (A\{v}, B объединение {v}) и (A объединение{v}, B \{v}).

Т-ма. Алгоритм локального поиска для задачи о макс разрезе имеет гарантированную оценку точности 2.

Док-во. Пусть m число ребер графа G, opt – оптимальное решение задачи, k – решение задачи, найденное алгоритмом локального поиска. Очевидно, что opt≤m, поэтому достаточно показать, что k≥m/2. Пусть (A,B) – найденное алгоритмом разбиение, ma – число ребер, оба конца которых лежат в A, mb – число ребер, оба конца которых лежат в B. m= ma+ mb+k

v – вершина графа , Na(v) – вершины смежная с v, которые лежат в A, Nb(v) - вершины смежная с v, которые лежат в B.

Т.к. (A,B) – локальный оптимум, то дляv A, | Na(v)| ≤ |Nb(v)|. v B, | Nb(v)| ≤ |Na(v)|.

Просуммируем эти неравенства по всем v A и по всем v B.

∑v из A| Na(v)|-∑v из A| Nb(v)|=2ma-k≤0

∑v из B| Nb(v)|-∑v из В Na(v)|=2mb-k≤0

Сложим оба выражения, получим: ma+ mb-k≤0.

m= ma+ mb+k

ma+ mb=m-k

m-2k≤0.

Алгоритм поиска с запретами(Tabu search)

Позволяет алгоритму выбраться из локального оптиума

Пусть алгоритм локального поиска за последние r шагов построил решение si-r , si-r+1 ,…..si , sj+1 N(sj) для решения si определяет список запретов Tabu(si). Следующее решение si+1 ищем как лучшее решение из множества N(si)\ Tabu(si) Множество Tabu(si) определяется по r предыдущем решений таким образом, чтобы исключить из рассмотрения те фрагменты решений , которые уже меняются на последних шагах алгоритмов.

Пример Задача о раскраске графа

Вход: граф G=(V,E) и нат. число k.

Вопрос: можно ли раскрасить вершины графа в к цветов? (можно ли разбить мн-во вершин графа на k нез. мн-в?)

Решения – все функции c:V(G) ® {1,2,…,k}

Вход: граф G=(V,E) и натуральное число k

Найти: функцию copt:V(G) ® {1,2,…,k}такую, что

w(copt) = |{uvÎE(G) : c(u)=c(v)}| минимальна количество ребер, концы которых покрашены в один цвет, минимально.

Пусть с=(с1,…,сn) – некоторое решение .Окрестность N(c) – это множество функций c’ = (c’1,…,c’n), получающихся из c следующим образом: берем ребро abÎE такое,что с(a)=c(b)и перекрашиваем вершину a в другой цвет. Пусть мы перекрасили вершину a в цвет ii Tabu на ближайшие r итераций – множество функций с таких, что с(a) = i Tabu на ближайшие r итераций – множество раскрасок, в которых 1 покрашена в красный цвет