Лекция 35. Модульный перебор

1. Теория принятия решений Модульный перебор

Лекция № 35

2. Классификация вычислительных задач

• Все вычислительные задачи, используемые при принятии
решений, можно условно разделить на две группы:
• Задачи, для которых существуют эффективные алгоритмы
решения, время поиска которыми решения полиномиально
связано с размерностью задачи (например алгоритм Джонсона,
алгоритм Прима).
• Задачи, для которых не существуют эффективные алгоритмы
решения, время поиска решения этих задач перебором
экспоненциально связано с размерностью задачи (например
задача коммивояжера, задача о ранце, решаемые переборными
алгоритмами).

3. Характеристики переборных алгоритмов

Полный перебор гарантирует глобально оптимальное решение задач дискретной
оптимизации, для задач с булевыми переменными время перебора Т1 = k1∙n∙2ⁿ, nчисло булевых переменных. Для задач оптимального упорядочения Т1 = k1∙n!, nчисло различных объектов в перестановке.
• Методы неявного перебора (динамическое программирование, методы типа
ветвей и границ, поиск с возвратом) требуют времени Т2 на анализ в диапазоне
(2∙n ÷ 2∙(2ⁿ -1)) векторов переменных.
• Назначение методов неявного перебора – сокращение времени поиска глобально
оптимальных решений задач дискретного программирования.
• Величина выигрыша от применения методов неявного перебора η = Т1 / Т2.
Основной инструмент сокращения времени поиска решения методами неявного
перебора – отказ от анализа «бесперспективных» векторов переменных.

4. Основная идея модульного перебора:

• Сокращение времени поиска решения за счет
сокращения объема повторяющихся
вычислений: они хранятся в памяти и
используются по мере надобности.

5. Стадии модульного перебора

• Две стадии модульного перебора:
• 1. Объединение векторов переменных в модули
и их заполнение.
• 2. Использование модулей для перебора.

6. Первая стадия модульного перебора: объединение векторов переменных в модули и их заполнение.

• Два шага первой (подготовительной) стадии
модульного перебора:
• 1. Все компоненты перебора объединяются в m
непересекающихся групп и запоминаются в m
модулях.
• 2. Для каждой компоненты каждого модуля
вычисляется и запоминается «ее» часть исследуемых
функций.

7. Вторая стадия модульного перебора:

• Два шага второй стадии модульного перебора:
• 1. Использование содержимого модулей для
генерации всех возможных значений исследуемых
функций.
• 2. Обработка полученных значений с учетом
специфики задачи.

8. Основные отличия модульного перебора от методов неявного перебора

• 1. Предсказуемость величины выигрыша во времени
перебора по сравнению с традиционным полным перебором.
• 2. Универсальность метода, т.е. возможность его применения
при решении переборных задач не только с дискретными , но
и с непрерывными переменными, таких, как поиск корней
уравнения, вычисление интегралов, определение
экстремальных значений функций на заданных интервалах
значений переменных.

9. Модульный перебор для функций одной переменной

10. Основная идея модульного перебора:

• Модульный перебор – это такая технология
перебора вариантов, в которой сокращение
времени поиска решения достигается за счет
сокращения объема повторяющихся
вычислений: они накапливаются в памяти и
используются по мере надобности.

11. Общая схема перебора для задач с функцией одной переменной

1. Ввод числа n значений переменной x, их верхней a и нижней b границы,
точности вычислений d, функции F(x).
2. Переменная i пробегает значения от 1 до n, причем при каждом
фиксированном i вычисляются величины x = a + (b-a)∙ i/n и F(x),
3. На основании функций F(x) на каждой итерации вычисляется величина у1,
отражающая специфику задачи.
4. Переменная i пробегает значения от 1 до n/2, причем при каждом
фиксированном i вычисляются величины x = a + (b-a)∙ i/(n/2) и F(x).
5. На основании функций F(x) на каждой итерации вычисляется величина у2,
отражающая специфику задачи.
6. Вычисляется величина, характеризующая точность d = |y1 – y2|.
7. Перебор завершен.

12. Блок схема перебора

Ввод n, a, b, F(x)
j=1
i=1
x = a + (b-a)∙ i/n
Вычисление F(x)
i=1 +i
Нет
i>n
Да
Вычисление у1
Да
n=n/2
j=2
j=1
Нет
Конец алгоритма
Печать у1, у2, d.
d = |y1 – y2|
Вычисление у2

13. Пример 1: программная реализация на QB перебора применительно к поиску максимума функции y = exp(-x)∙|(sin(x))|, где a≤х≤b

100 input n, a, b
110 S1 = 0
120 S2 = 0
130 FOR i = 1 TO n
140 GOSUB 250
Поиск максимума y = exp(-x)∙|(sin(x))| по n значениям переменной х
150 IF S1 < y THEN S1 = y
160 NEXT i
170 FOR i = 1 TO n STEP 2
180 GOSUB 250
Поиск максимума y = exp(-x)∙|(sin(x))|по n/2 значениям переменной х
190 IF S2 < y THEN S2 = y
200 NEXT i
210 d = ABS(S1 – S2)
Оценка точности вычислений
220 PRINT S1; S2; d
240 END
250 x = a-(b-a) * i /n
260 y = EXP(-x) * ABS(SIN(x))
270 RETURN
Подпрограмма вычисления функции F(x)

14. Пример 2: программная реализация на QB перебора применительно к вычислению интеграла функции y = exp(-x)∙|(sin(x))|, на

интервале a≤х≤b
100 input n, a, b
110 S1 = 0
120 S2 = 0
130 FOR i = 1 TO n
140 GOSUB 250
Поиск суммы значений y = exp(-x)∙|(sin(x))| по n значениям переменной х
150 IF S1 < y THEN S1 = y
160 NEXT I
165 S1=S1*(b-a)/n
170 FOR i = 1 TO n STEP 2
180 GOSUB 250