Ключевые алгоритмические парадигмы с примерами на C++

Цель этой статьи — познакомить читателя с четырьмя главными алгоритмическими парадигмами: полный поиск, жадные алгоритмы, разделяй и властвуй, и динамическое программирование. Многие алгоритмические проблемы можно сопоставить с одной из этих категорий, мастерство в каждой повысит ваш уровень программирования.

Статья написана с точки зрения спортивного программирования. В конце статьи вы найдёте материалы для обучения или повышения навыков программирования с помощью соревнований.

Полный поиск

Complete search (он же «грубая сила» или «рекурсивный откат») — метод решения задачи путем пересечения всего пространства поиска. Точнее на протяжении всего алгоритма мы отсекаем те части пространства поиска, которые, как мы считаем, не приведут к требуемому решению. На соревнованиях по спортивному программированию использование Complete Search скорее всего приведёт к превышению лимита времени (Time Limit Exceeded — TLE), однако, это хорошая стратегия для задач с небольшим объёмом входных данных.

Пример: Задача с 8 ферзями

Нам нужно расположить на шахматной доске 8 ферзей так, чтобы ни один ферзь не нападал на другого. В наиболее простом решении нам придётся перебрать 64 млрд комбинаций и выбрать 8–4 млрд возможных расстановок. Также неплохой вариант — поставить каждого ферзя в отдельную колонну, что сводит число возможностей к 8? — ~17 млн. Но лучше всего поставить каждого ферзя в отдельный ряд и в отдельную колонну. Это приведёт к 8! — 40 тыс. возможных комбинаций. В приведённой ниже реализации мы предполагаем, что каждый ферзь занимает отдельный столбец, и вычисляем номер строки для каждого из 8 ферзей.

#include <cstdlib> #include <cstdio> #include <cstring>  using namespace std;  // row[8]: номер строки для каждого ферзя // TC: счётчик TraceBack // (a, b): расположение первого ферзя от (r=a, c=b) int row[8], TC, a, b, line_counter;  bool place(int r, int c) {      // Проверяем ранее размещённых ферзей    for (int prev = 0; prev < c; prev++)    {        // Проверяем, совпадают ли строки или диагонали        if (row[prev] == r || (abs(row[prev] - r) == abs(prev - c)))            return false;    }    return true; }  void backtrack(int c) {    // Возможное решение; первый ферзь имеет координаты a и b    if (c == 8 && row[b] == a)    {        printf("%2d %d", ++line_counter, row[0] + 1);        for (int j = 1; j < 8; j++) printf(" %d", row[j] + 1);        printf(" ");    }    // Пробуем все возможные строки    for (int r = 0; r < 8; r++)    {        if (place(r, c))        {            row[c] = r; // место ферзя в этом столбце и в этой строке            backtrack(c + 1); // следующий столбец и рекурсия        }    } }  int main() {     scanf("%d", &TC);     while (TC--)     {        scanf("%d %d", &a, &b);        a--; b--; // индексируем с нуля         memset(row, 0, sizeof(row));        line_counter = 0;        printf("РЕШ	СТОЛБЕЦ ");        printf(" # 1 2 3 4 5 6 7 8  ");        backtrack(0); // генерируем все 8! возможных решений        if (TC) printf(" ");     }     return 0; }

Для TC = 8 и начальной позиции ферзя в (a, b) = (1, 1), приведённый выше код выводит следующее:

РЕШ        СТОЛБЕЦ #    1 2 3 4 5 6 7 8 1    1 5 8 6 3 7 2 4 2    1 6 8 3 7 4 2 5 3    1 7 4 6 8 2 5 3 4    1 7 5 8 2 4 6 3

Он указывает, что всего возможно 4 расстановки, принимающих начальное положение ферзя в (r = 1, c = 1).

Использование рекурсии позволяет легче выделить пространство поиска в сравнении с итерационным решением.

Жадный алгоритм

Данный алгоритм на каждом шаге делает локально оптимальный выбор, надеясь в итоге получить глобально оптимальное решение.

Пример: Дробный Рюкзак

Задача состоит в том, чтобы выбрать, какие предметы, имеющие вес и стоимость, поместить в рюкзак ограниченной ёмкости W, да так, чтобы максимизировать общую ценность его содержимого. Мы можем определить соотношение стоимости предмета к его весу, т. е. с «жадностью» выбирать предметы, имеющие высокую стоимость, но в то же время маленький вес, а затем сортировать их по этим критериям. В задаче с дробным рюкзаком нам разрешено брать дробные части предмета.

#include <iostream> #include <algorithm>  using namespace std;  struct Item {    int value, weight;    Item(int value, int weight) : value(value), weight(weight) { } };  bool cmp(struct Item a, struct Item b) {    double r1 = (double) a.value / a.weight;    double r2 = (double) b.value / b.weight;    return r1 > r2; }  double fractional_knapsack(int W, struct Item arr[], int n) {    sort(arr, arr + n, cmp);    int cur_weight = 0; double tot_value = 0.0;    for (int i = 0; i < n; ++i)    {        if (cur_weight + arr[i].weight <= W)        {            cur_weight += arr[i].weight;            tot_value += arr[i].value;        }          else        {   // Добавляем часть следующего предмета            int rem_weight = W - cur_weight;            tot_value += arr[i].value *                        ((double) rem_weight / arr[i].weight);                                break;        }    }    return tot_value; } int main() {    int W = 50; // вместительность рюкзака    Item arr[] = {{60, 10}, {100, 20}, {120, 30}}; // {стоимость, вес}    int n = sizeof(arr) / sizeof(arr[0]);    cout << "жадный дробный рюкзак" << endl;    cout << "максимальная ценность: " << fractional_knapsack(W, arr, n);    cout << endl;    return 0; } 

Поскольку сортировка — самая дорогая операция, алгоритм работает за время O(n log n). Принимая в формате (стоимость, вес) три пары предметов — {(60, 10), (100, 20), (120, 30)} — и итоговую вместительность рюкзака W = 50, приведённый выше код выводит следующее:

жадный дробный рюкзак максимальная ценность: 240

Мы можем заметить, что ввод предметов отсортирован с уменьшающим коэффициентом стоимость/вес. Выбрав два целых предмета 1 и 2, мы берём ? от третьего предмета.
Итоговая ценность = 60 + 100 + (2/3) * 120 = 240.

Разделяй и Властвуй

Разделяй и Властвуй — стратегия, подразумевающая, что задача разделяется на независимые подзадачи и затем каждая из них решается.

Примеры этой стратегии — быстрая сортировка, сортировка слиянием и пирамидальная сортировка, а также бинарный поиск.

Пример: Бинарный поиск

Чаще всего бинарный поиск (бинпоиск) используют, чтобы найти элемент в отсортированном массиве. Мы начинаем искать с середины массива. Если находим то, что нужно, или если больше нечего рассматривать, мы останавливаемся. В противном случае мы решаем, в каком направлении — вправо или влево от середины — мы должны продолжить поиск. Так как пространство поиска после каждой проверки делится на два, то время выполнения алгоритма — O(log n).

#include <algorithm> #include <vector> #include <iostream>  using namespace std;  int bsearch(const vector<int> &arr, int l, int r, int q) {    while (l <= r)    {        int mid = l + (r-l)/2;        if (arr[mid] == q) return mid;               if (q < arr[mid]) { r = mid - 1; }        else              { l = mid + 1; }    }    return -1; // не нашли }  int main() {    int query = 10;    int arr[] = {2, 4, 6, 8, 10, 12};    int N = sizeof(arr) / sizeof(arr[0]);    vector<int> v(arr, arr + N);       // Сортируем входной массив    sort(v.begin(), v.end());    int idx;    idx = bsearch(v, 0, v.size(), query);    if (idx != -1)        cout << "бинарный поиск: нашли по индексу " << idx;       else        cout << "бинарный поиск: не нашли";    return 0; } 

Код выводит следующее:

бинарный поиск: нашли по индексу 4

Если искомый элемент не найден, но мы хотим найти ближайший элемент меньше или больше запроса, то можно использовать функции STL lower_bound() и upper_bound().

Динамическое программирование

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

Ключевая особенность динамического программирования — способность определять состояние записей в таблице и отношения или перемещения между записями.
Затем, определив базовые и рекурсивные случаи, можно заполнить таблицу сверху вниз или снизу вверх.

В нисходящем ДП таблица будет заполнена рекурсивно, по мере необходимости, начиная сверху и спускаясь к меньшим подзадачам. В восходящем ДП таблица будет заполняться по порядку, начиная с меньших подзадач и с использованием их решений для того чтобы подниматься выше и находить решения для бо?льших задач. В обоих случаях если решение данной подзадачи уже встречалось, оно просто ищется в таблице. И это значительно снижает вычислительные затраты.

Пример: Биноминальные коэффициенты

Мы используем пример биноминальных коэффициентов, чтобы проиллюстрировать использование нисходящего и восходящего ДП. Код ниже основан на рекурсиях для биноминальных коэффициентов с перекрывающимися подзадачами. Обозначим через C(n, k) количество выборок из n по k, тогда имеем:

Базовый случай: C(n, 0) = C(n, n) = 1
Рекурсия: C(n, k) = C(n-1, k-1) + C(n-1, k)

У нас есть несколько перекрывающихся подзадач. Например, для C(n = 5, k = 2)рекурсивное дерево будет следующим:

                              C(5, 2)                      /                                    C(4, 1)                            C(4, 2)            /                              /                  C(3, 0)   C(3, 1)             C(3, 1)             C(3, 2)                 /                 /                  /               C(2, 0)  C(2, 1)      C(2, 0) C(2, 1)    C(2, 1)  C(2, 2)                   /                    /           /                  C(1, 0)  C(1, 1)    C(1, 0)  C(1, 1) C(1, 0)  C(1, 1) 

Мы можем реализовать нисходящее и восходящее ДП следующим образом:

#include <iostream> #include <cstring>  using namespace std;  #define V 8  int memo[V][V]; // таблица  int min(int a, int b) { return (a < b) ? a : b; }  void print_table(int memo[V][V]) {    for (int i = 0; i < V; ++i)    {        for (int j = 0; j < V; ++j)        {            printf(" %2d", memo[i][j]);               }        printf(" ");    } }  int binomial_coeffs1(int n, int k) {    // Нисходящее ДП    if Нk == 0 || k == n) return 1;     if (memo[n][k] != -1) return memo[n][k];    return memo[n][k] = binomial_coeffs1(n-1, k-1) +                             binomial_coeffs1(n-1, k); }  int binomial_coeffs2(int n, int k) {       // Восходящее ДП    for (int i = 0; i <= n; ++i)     {               for (int j = 0; j <= min(i, k); ++j)        {                       if (j == 0 || j == i)            {                               memo[i][j] = 1;            }             else            {                memo[i][j] = memo[i-1][j-1] + memo[i-1][j];                             }        }    }    return memo[n][k]; }   int main() {    int n = 5, k = 2;    printf("Нисходящее ДП: ");    memset(memo, -1, sizeof(memo));    int nCk1 = binomial_coeffs1(n, k);    print_table(memo);    printf("C(n = %d, k = %d): %d  ", n, k, nCk1);       printf("Восходящее ДП: ");    memset(memo, -1, sizeof(memo));    int nCk2 = binomial_coeffs2(n, k);    print_table(memo);    printf("C(n = %d, k = %d): %d ", n, k, nCk2);       return 0; }

При C(n = 5, k = 2) код выше выводит следующее:

Нисходящее ДП: -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  2 -1 -1 -1 -1 -1 -1 -1  3  3 -1 -1 -1 -1 -1 -1  4  6 -1 -1 -1 -1 -1 -1 -1 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 C(n = 5, k = 2): 10  Восходящее ДП:  1 -1 -1 -1 -1 -1 -1 -1  1  1 -1 -1 -1 -1 -1 -1  1  2  1 -1 -1 -1 -1 -1  1  3  3 -1 -1 -1 -1 -1  1  4  6 -1 -1 -1 -1 -1  1  5 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 C(n = 5, k = 2): 10 

Временная и пространственная сложность будут выражены как O(n * k).

В случае нисходящего ДП решения подзадач накапливались по мере необходимости, в то время как в восходящем ДП таблица заполнялась начиная с базового случая.

Примечание. Для печати был выбран маленький размер таблицы, рекомендуется брать намного больший размер.

Код

Весь код доступен здесь. Чтобы скомпилировать код на C++, можете воспользоваться командой:

$ g++ <filename.cpp> --std=c++11 -Wall -o test $ ./test

Заключение

В статье был рассмотрены лишь базовые алгоритмы. Больше информации по алгоритмам вы всегда можете найти у нас на сайте.

Источник: tproger.ru

Комментарии: