- •Тема 5. Методы разработки алгоритмов.
- •5.1 Метод «Разделяй и властвуй».
- •5.2 Метод подъема или метод локального поиска.
- •5.3 Метод «Жадный алгоритм».
- •5.4 Метод программирования «с отходом назад» (Back Tracing).
- •5.5 Эвристики.
- •5.6 Метод ветвей и границ.
- •5.8 Динамическое программирование.
- •5.9 Методы имитационного моделирования.
- •Тема 6. Параллельные алгоритмы.
- •6.1 Понятие параллельных алгоритмов.
- •6.2 Средства распараллеливания алгоритмов.
- •Тема 7. Генетические алгоритмы.
- •Тема 8. Алгоритмы восстановления зависимостей.
- •Часто бывает, что на время работы одного и того же алгоритма кроме размера задачи влияют другие параметры, вводимые пользователем.
Тема 5. Методы разработки алгоритмов.
Существует достаточно большое число методов разработки эффективных алгоритмов решения задач различных классов.
Наиболее часто используются следующие методы:
«Разделяй и властвуй» - метод декомпозиции, метод сведения задачи к подзадачам, метод частных целей.
Балансировка. Этот метод применим только к алгоритмам, к которым уже применялся 1-ый метод.
Динамическое программирование.
«Жадный» алгоритм.
Метод программирования «с отходом назад» (Back Tracing), программирование с отслеживанием.
Метод локального поиска.
Метод подъема.
Метод эвристики.
Метод рекурсии.
Моделирование задач.
5.1 Метод «Разделяй и властвуй».
При решении задачи необходимо ответить на следующие вопросы:
Известно ли решение для какой-либо части задачи и можно ли решить оставшуюся неизвестной часть.
Известны ли частные случаи решения задачи, и можно ли разработать алгоритм решения задачи для ограниченного подмножества исходных операндов.
Существует ли в задаче неясные моменты (раскрытие глубины задачи).
Существует ил похожая задача того же класса и решение для нее. Можно ли изменить алгоритм решения второй задачи для получения решения первой.
В основе метода «Разделяй и властвуй» лежит разбиение задачи на подзадачи (декомпозиция).
Первый шаг – это разделение задачи на К подзадач со сложностью 1/К.
Властвование – второй шаг алгоритма. Это – использование рекурсионного процесса разбиения подзадач на еще более мелкие подзадачи до тех пор, пока подзадачи n-го уровня разделения будут достаточно малы для их тривиального решения.
… … … …
Третий этап метода – склеивание множества решений отдельных подзадач в общее решение.
Использование этого метода требует, чтобы в процессе разбиения подзадачи не повторялись и не пересекались друг с другом. Если это условие не выполняется, то данный метод решения не применим к таким задачам.
Примерами решаемых этим методом задач являются:
сортировка слиянием;
нахождение максимального/минимального элемента массива;
умножение длинных целочисленных значений;
алгоритм быстрого преобразования Фурье;
алгоритм «Ханойская башня»;
составление графика проведения чемпионата.
Задача 5.1.1
Отсортировать массив из n чисел в порядке возрастания.
Обменная сортировка:
-
6
3
2
7
5
1
3
7
-
1
3
2
7
5
6
3
7
-
1
2
3
7
5
6
3
7
-
1
2
3
3
5
6
7
7
1 итерация
2 итерация
3 итерация
Общая формула временной сложности записывается рекуррентно:
T(n)=n*(n-1)/2=O(n2)
Приведенный алгоритм построен на основе метода «Разделяй и властвуй».
Недостаток: в приведенном алгоритме размеры подзадач на каждой итерации одинаковы, поэтому при больших n этот алгоритм неэффективен.
Для повышения эффективности алгоритмов, разработанных методом «Разделяй и властвуй», используется метод балансировки, который заключается в разбиении задачи на подзадачи равных размеров.
Например:
Алгоритм сортировки слиянием.
-
6
3
2
7
5
1
3
7
-
3
6
2
7
1
5
3
7
-
2
3
6
7
1
3
5
7
-
1
2
3
3
5
6
7
7
Вычислительная сложность этого алгоритма:
T2(n)=O(n*log(n)),
поэтому можно сделать вывод, что данный алгоритм также является рекурсивным.
Пример процедуры, реализующей этот алгоритм:
Procedure JointSort(P, R: integer;
var A, B: TArray);
var q: integer;
begin
if P=R then exit;
q:= (P+R) div2;
JointSort(P, q, A, B);
JointSort(q+1, R, B, A);
JointSort(P, q, R, B, A);
end;
Метод «Разделяй и властвуй» полезен, если задачу можно разбить на подзадачи за приемлемое время, а суммарный размер подзадач будет небольшим.
Если сумма размеров подзадач пропорциональна a*N, где а=const (a>1), то этот метод дает алгоритм с полиномиальной сложностью O(Nm).
Если разбиение задачи размером N приводит к N подзадачам, каждая из которых имеет сложность (N-1), то такой алгоритм будет иметь экспоненциальную сложность O(mN).
Задача 5.1.2
Составление сетевого графика выполнения работ.
Имеется комплекс взаимосвязанных работ N. Для каждой из работ задана трудоемкость выполнения. Имеется К рабочих. Требуется распределить рабочих по операциям таким образом, чтобы длительность выполнения всего комплекса работ была минимальной.
Примечание: не учитываются субъективные факторы, и невозможно перемещение рабочих с одной операции на другую в процессе выполнения.
Комплекс взаимосвязанных работ представляется в виде сетевого графика, где узлы графа – это события окончания предшествующих работ, дуги – работы.
Трудоемкость Ri,j характеризует затраты ресурсов на выполнение работы.
Пример сетевого графика:
L(0, М) – длительность выполнения работы. Эта величина определяется как совокупность возможных путей в графе
{I1, I2, I3}
В данном примере возможны 3 маршрута:
I1={(0, 1); (1, 3); (3, 5)}
I2={(0, 1); (1, 4); (4, 5)}
I3={(0, 2); (2, 4); (4, 5)}
I1=1+2+4=7 – «критический» путь Iкр.
I2=1+2+1=4
I1=2+3+1=6
Необходимо расставить по операциям заданное число рабочих.
Для случая, когда K=N задача является тривиальной.
Для KN имеется N(K-N) возможных вариантов расстановки.
Пусть N=7, К=10, тогда имеется 1296 вариантов размещения рабочих.
Решение этой задачи методом полного перебора вариантов неэффективно.
Используя метод «Разделяй и властвуй», разбивают исходную задачу на (К-N) последовательных подзадач. Затем решают вопрос о том, на какую операцию поставить 1-го свободного рабочего (для данного примера – 8-го рабочего). После этого размещают 2-го свободного рабочего, взяв за исходное ранее найденное решение и т.д.
Каждая из этих подзадач может быть сформулирована следующим образом: необходимо принять решение о добавлении одного работника на одну из работ комплекса, чтобы полученная расстановка минимизировала «критический» путь
Свободного рабочего размещают на одну из работ, входящих в «критический» путь, желательно, наиболее трудоемкую (здесь – (3, 5)).
Тогда получаем:
I1’=1+2+4/2=5 I3=6 Iкр
L(0, 5)=6
Поиск решения данным алгоритмом требует анализа не более N*(K-N) вариантов.