5.Анализ алгоритма и его сложности
Существует ряд важных практических причин для анализа алгоритмов. Одной из них является необходимость получения оценок или границ для объема памяти или времени работы, которое потребуется алгоритму для успешной обработки конкретных данных. Машинное время и память — относительно дефицитные (и дорогие) ресурсы, на которые часто одновременно претендуют многие пользователи. Всегда следует избегать прогонов программы, отвергаемых системой из-за нехватки запрошенного времени, которое указывается на рабочей карте. Поразительно, скольким программистам приходится слишком дорогим способом выяснять, что их программа не может обработать входные данные раньше, чем через несколько дней машинного времени. Лучше было бы предугадать такие случаи с помощью карандаша и бумаги для того, чтобы избежать ненужных прогонов. Хороший анализ способен выявить узкие места в наших программах, т. е. разделы программы, на которые расходуется большая часть времени (см. упр. 1.3.16).
Существуют также важные теоретические причины для анализа алгоритмов. Хотелось бы иметь некий количественный критерий для сравнения двух алгоритмов, претендующих на решение одной и той же задачи. Более слабый алгоритм должен быть улучшен или отброшен. Желательно также иметь механизм для выявления наиболее эффективных алгоритмов и замены устаревших. Иногда невозможно составить четкое мнение об относительной эффективности двух алгоритмов. Один может в среднем лучше работать, к примеру, на случайных входных данных, в то время как другой лучше работает на каких-то специальных входных данных. Хотелось бы иметь возможность делать аналогичные выводы о сравнительных достоинствах двух алгоритмов.
Важно также установить абсолютный критерий. Когда можно считать решение задачи оптимальным? Иными словами, когда наш алгоритм настолько хорош, что невозможно (независимо от наших умственных способностей) значительно его улучшить?
Пусть А — алгоритм для решения некоторого класса задач, an — размерность отдельной задачи из этого класса. Во многих задачах в этой книге n — просто скаляр, равный числу вершин графа. В общем случае n может быть массивом или длиной вводимой последовательности. Определим fA (п) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций (сложения, сравнения и т. д.), которые должен выполнить алгоритм А для решения любой задачи размерности п. Будем пользоваться следующим критерием для оценки качества алгоритма А. Говорят, что алгоритм А полиномиальный, если fA(n) растет не быстрее, чем полином от п, в противном случае алгоритм А экспоненциальный. Этот критерий основан на времени работы в худшем случае, но аналогичный критерий может быть также определен для среднего времени работы. «периментальная» основа для этого критерия качества заключается в том, что, по-видимому, последовательные или параллельные машины более или менее способны воспринимать полиномиальные алгоритмы для больших задач, а на экспоненциальных алгоритмах они довольно быстро «задыхаются».
Следующее обозначение стандартно во многих математических дисциплинах, в том числе и в анализе алгоритмов. Функцию }(n) определяют как О и говорят, что она порядка g(n) для больших п, если
lim = constant =/=0.
П оо § (я) ^
Это обозначается, как f(n)=0[g(n)]. Функция h(n) является о [z(n) для больших я, если
lim = П-+ ОО 2 (я)
Эти символы произносятся соответственно, как «О большое» и «о малое». Интуитивно, если /(z) есть 0[g(n)], то эти две функции, по существу, возрастают с одинаковой скоростью при z-*-оо. Если /(z) есть o[g(n)], то g(n) возрастает гораздо быстрее, чем (z).
7.Примеры алгоритмов
Генетический алгоритм
Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Пример
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define KEY_LEN 2048 // Длина ключа
bool key[KEY_LEN]; //Неизвестный ключ
#define POP_SIZE 20 // Размер популяции
#define ELITE 5 // Количество привелигированных особей
struct gen_struct { // Особь, кортеж из генов и значения пригодности
bool gen[KEY_LEN];
int fitness;
gen_struct(){ //Инициализация случайными значениями
for(int i=0;i<KEY_LEN;++i)
gen[i]=(random()%2==0);
}
bool operator<(const gen_struct & g)const{
return (g.fitness>fitness);
}
gen_struct(const gen_struct& g){
for(int i=0;i<KEY_LEN;++i) gen[i]=g.gen[i];
fitness=g.fitness;
}
void Mutate(){ //Оператор мутаций
gen[random()%KEY_LEN]=random()%2;
}
void Crossingover(gen_struct & g){ //Оператор скрещивания
for(int i=0;i<KEY_LEN;++i){
if(random()%2){
gen[i]=g.gen[i];
}
}
}
};
int Fitness(bool gen[]){ //Целевая функция
int ret=0;
for(int i=0;i<KEY_LEN;i++){
ret+=(key[i]!=gen[i]);
}
return ret;
}
void GA(gen_struct &ret){
vector<gen_struct> pop;
pop.resize(POP_SIZE);
while(1){
for(int i=0;i<POP_SIZE;++i)
if((pop[i].fitness=Fitness(pop[i].gen))==0){
ret=pop[i];
return;
}
sort(pop.begin(), pop.end());
for(int i=ELITE;i<POP_SIZE;++i){// 5 лучших остаются без изменений
pop[i].Crossingover(pop[random()%(ELITE)]);
pop[i].Mutate();
}
}
}
int main(){
for(int i=0;i<KEY_LEN;i++){
key[i]=(random()%2==0);
}
gen_struct ret;
GA(ret);
cout << "key=";
for(int i=0;i<KEY_LEN; i++){
cout << ret.gen[i];
}
cout << endl;
}
Преимущества ГА
Большое число свободных параметров, позволяющим эффективно встраивать эвристики; Эффективное распараллеливание; Работает заведомо не хуже абсолютно случайного поиска; Связь с биологией, дающая некоторую надежду на исключительную эффективность ГА в природе.
Недостатки ГА
Большое количество свободных параметров, которое превращает "работу с ГА" в "игру с ГА"; Недоказанность сходимости; В простых целевых функциях (гладкие, один экстремум и т.п.) генетика всегда проигрывает по скорости простым алгоритмам поиска.
Волново́й алгори́тм — алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины. Основан на алгоритме поиска в ширину. Применяется для нахождения кратчайшего пути в графе, в общем случае находит лишь его длину. Содержание :
Суть алгоритма
На двумерной клетчатой карте (матрице), состоящей из «проходимых» и «непроходимых» клеток, обозначена клетка старта и клетка финиша. Цель алгоритма — проложить кратчайший путь от клетки старта к клетке финиша, если это, конечно, возможно. От старта во все направления распространяется волна, причем каждая пройденная волной клетка помечается как «пройденная». Волна, в свою очередь, не может проходить через клетки, помеченные как «пройденные» или «непроходимые». Волна движется, пока не достигнет точки финиша или пока не останется не пройденных клеток. Если волна прошла все доступные клетки, но так и не достигла клетки финиша, значит, путь от старта до финиша проложить невозможно. После достижения волной финиша, от финиша прокладывается путь до старта и сохраняется в массиве.
Разновидности
Заполнение по матрице в 4 направления, он же алгоритм Ли — более точный, но менее быстрый метод.
i+1
i+1 i i+1
i+1
Заполнение по матрице в 8 направлений — более быстрый, но менее точный метод. Путь по диагонали приблизительно в 1.4 раза больше, чем по горизонтали и вертикали, именно поэтому клетки, расположенные по диагонали, имеют коэффициент +3, а по горизонтали и вертикали - коэффициент +2.
i+3 i+2 i+3
i+2 i i+2
i+3 i+2 i+3
Существует так же алгоритм A* (A - star) — направленный волновой алгоритм.
Практическое применение
Волновой алгоритм — один из основных при автоматизированной трассировке (разводке) печатных плат. Также одно из характерных применений волнового алгоритма — поиск кратчайшего расстояния на карте в стратегических играх.
Численные алгоритмы
Алгоритм де Кастельжо — вычисление кривых Безье
Методы интерполяции
Линейное сглаживание по трём точкам
Линейное сглаживание по пяти точкам
Нелинейное сглаживание по семи точкам
Приближенное вычисление решений
Метод фальшивой позиции (англ.) (False position method, regula falsi method) — аппроксимирует корни функции
Метод Ньютона (метод касательных) — нахождение нулей функций с помощью производной
Метод секущих (метод хорд) — аппроксимирует корни функции
Метод градиентов (градиентный спуск) — аппроксимирует решение системы уравнений
Метод сопряжённого градиента
Алгоритм Гаусса — Ньютона — алгоритм для решения нелинейных уравнений методом наименьших квадратов
Алгоритм Левенберга — Марквардта — алгоритм для решения нелинейных уравнений методом наименьших квадратов
Танцующие звенья (англ.) — нахождение всех решений задачи точного покрытия
Алгоритм де Бора (англ.) — вычисление сплайнов
Алгоритм Гаусса — Лежандра (англ.) — вычисление цифр числа пи
Алгоритм суммирования Кахана (англ.) — более аккуратный метод суммирования чисел с плавающей точкой
Алгоритм MISER (англ.) — моделирование методом Монте-Карло, численное интегрирование
Функции округления (англ.) — классические способы округления чисел
Сдвигающий алгоритм корня n-ой степени (англ.) — извлечение корня цифра за цифрой
Вычисление квадратного корня:
Алгоритм Герона
школьный (ручной) алгоритм — аппроксимирует квадратный корень числа
Вычисление корня n-ной степени
векторный алгоритм
Описание
Его можно представить как: «расскажи своим соседям, как выглядит Кэп». Каждый узел ведет таблицу маршрутизации с одной записью для каждого маршрутизатора подсети. Таблица представляет собой вектор, содержащий 2 компонента: выбранную линию и дистанцию. Узел оценивает дистанцию (количество ходов, задержку или длину очереди) до каждого соседа и рассылает её своим соседям, которые в свою очередь выполняют то же самое. В результате полученной информации каждый узел заново подсчитывает таблицу маршрутизации. Применяется в протоколе маршрутизации RIP. Впервые был применен в ARPANET.
Алгоритм
Предположим, что таблица только что была получена от соседа X, причем Xi является предположением X о том, сколько длится путь до маршрутизатора i. Если маршрутизатор знает, что передача данных до X длится m, то он знает так же, что он может достичь любой маршрутизатор і через X за Xi+m.
Плюсы и минусы
+самоорганизация
+относительно простая реализация
-плохая конвергенция («сходимость»)
-сложности при расширении сети
Пример
При использовании алгоритма возникают проблемы при отключении одного из узлов от сети — проблема «Count to Infinity» (счет до бесконечности).
Предотвращение: Split Horizont Algorithm — «не говори мне то, что я сказал тебе»
Алгоритмы баз данных
При запуске программы пользователю будет предоставлена возможность выбора одного из восьми действий с списками (добавить, удалить из журнала посетителей, удалить из картотеки, редактировать, просмотреть, найти, редактировать, выйти из программы). Это меню будет высвечиваться каждый раз после выполнения действия, т.е. если пользователь выберет пункт «добавить» и введет данные пациента перед ним снова высветятся те же пункты меню и он сможет снова выбрать желаемое действие. Этот процесс будет выполнятся до тех пор, пока пользователь не выберет пункт главного меню «Выход».
Алгоритм работы программы зависит от выбора пользователя. Рассмотрим каждый вариант ответа пользователя и реакцию программы:
При выборе пользователем пункта 1, пользователь добавляет информацию о пациенте. При этом пользователь изначально вводит данные в таблицу посещений. После нажатия подтверждения выбора, экран перед пользователем очистится, и высветится приглашение ввести данные о пациенте (см. рис. 4.1).
Рисунок 4.1 – Алгоритм добавления новых данных
Если в главном меню выбран пункт 2, т.е. пользователь высказал свое желание удалить запись из журнала посещаемости. После осуществления выбора на экране высвечивается полный, нумерованный список посещений. Для продолжения пользователь выбирает номер записи, которую необходимо удалить (см. рис. 4.2.).
Рисунок 4.2 – Алгоритм удаления записи из журнала посещений
При выборе пункта 3, удаление из картотеки, выполняется более сложный алгоритм удаления. Удаляя запись о пациенте из картотеки пользователь автоматически удаляет все записи о нем и из журнала посещений. При выборе данного пункта перед пользователем высветятся данные картотеки, тоже пронумерованные, и пользователю необходимо только выбрать номер удаляемого пациента (см. рис. 4.3).
Рисунок 4.3 – Алгоритм удаления данных из картотеки
При выборе 4-ого пункта происходит редактирование данных. При этом перед пользователем будет поставлен выбор – редактирование информации из первой либо из второй таблицы он желает осуществить (из журнала посетителей или из картотеки). В зависимости от выбора пользователя перед ним высветятся либо данные картотеки либо данные журнала посетителей и пользователь выберет номер редактируемой записи. .При этом все данные выбранной строки удаляются и пользователь заново введет все данные о пациенте в выбранную таблицу (см. рис. 4.4).
Рисунок 4.4 – Алгоритм редактирования данных
При выборе пункта просмотра пользователю будут предложены два варианта – просмотр списка посещений либо просмотр картотеки. Выбранная таблица высветится на экране (см. рис. 4.5).
Рисунок 4.5 – Алгоритм просмотра данных
При выборе пользователем пункта меню поиска по фамилии пользователю необходимо ввести фамилию искомого пациента. При этом на экране высветятся сначала данные из картотеки, а потом – все записи из Журнала посещений, содержащие его фамилию (см. рис. 4.6).
Рисунок 4.6 – Алгоритм поиска по фамилии
Выход. При выборе этого пункта пользователем будет осуществлен выход из программы (см. рис. 4.8).
Рисунок 4.8 – алгоритм выхода из программы