14.Методы сокращения перебора. Эвристические алгоритмы. Метод ветвей и границ
..docМетоды сокращения перебора
Вычислительная сложность перебора с возвратом экспоненциальная, поэтому необходимо сокращать перебор. Основные методы сокращения перебора:
-
Эвристические алгоритмы
-
Метод ветвей и границ
-
Динамическое программирование
Эвристические алгоритмы
Для некоторых задач перебора существуют точные или приближенные полиномиальные алгоритмы решения. Они называются эвристическими алгоритмами.
Идея – выбор очередного элемента решения исходя из определенного критерия – обычно критерия оптимальности. Такие алгоритмы часто называют жадными.
Точные жадные алгоритмы
-
Задан набор векторов. Найти максимальный базис.
Решение.
Добавляем в набор векторы, линейно-независимые с векторами, которые уже есть в наборе.
-
Задан набор заданий, которые нужно выполнить, для каждого известен срок выполнения и стоимость. Каждый день можно выполнять только одно задание. Нужно определить последовательность выполнения работ с максимальной стоимостью.
Решение.
Упорядочим задания в порядке убывания стоимости. Будем назначать очередное задание, если это возможно, на самый поздний свободный день до его срока выполнения. Если свободных дней для задания нет, то переходим к следующему заданию.
Приближенные жадные алгоритмы
-
Задача о рюкзаке. Упорядочим предметы в порядке убывания удельной стоимости. Будем класть в рюкзак предметы в этом порядке. Если при добавлении предмета масса будет превышена, он не добавляется.
-
Задача коммивояжера. Начиная с 1 города идем в ближайший город, где еще не были.
Метод ветвей и границ
При переборе обходим дерево вариантов.Идея метода – не проходить ветви дерева перебора, которые не приведут к решению задачи. Для этого оцениваются возможные границы решения.
Задача о рюкзаке
Procedure Search(k: integer; S: setNumb; SM,SC: integer);
begin
if k>n then begin
if (SC> MC) and (SM<=MaxM) then
Begin
MС:=SC; MR:=S;
end;
end
else begin
SumO:=SumO-M[k];
if (SM+M[k] <= MaxM) then
Search(k+1, S+[k], SM+M[k], SC+C[k]);
if (SC+ SumO >MC) then
Search(k+1,S,SM,SC);
SumO:=SumO+M[k];
end; end;