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

Перевод статьи «Algorithms in 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("\n");
   }
   // Пробуем все возможные строки
   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("РЕШ\tСТОЛБЕЦ\n");
       printf(" # 1 2 3 4 5 6 7 8\n\n");
       backtrack(0); // генерируем все 8! возможных решений
       if (TC) printf("\n");
    }
    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.

Читайте также: Оценка сложности алгоритмов, или Что такое О(log n)

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

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

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

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

Чаще всего бинарный поиск (бинпоиск) используют, чтобы найти элемент в отсортированном массиве. Мы начинаем искать с середины массива. Если находим то, что нужно, или если больше нечего рассматривать, мы останавливаемся. В противном случае мы решаем, в каком направлении — вправо или влево от середины — мы должны продолжить поиск. Так как пространство поиска после каждой проверки делится на два, то время выполнения алгоритма — 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("\n");
   }
}

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("Нисходящее ДП:\n");
   memset(memo, -1, sizeof(memo));
   int nCk1 = binomial_coeffs1(n, k);
   print_table(memo);
   printf("C(n = %d, k = %d): %d\n\n", n, k, nCk1);
  
   printf("Восходящее ДП:\n");
   memset(memo, -1, sizeof(memo));
   int nCk2 = binomial_coeffs2(n, k);
   print_table(memo);
   printf("C(n = %d, k = %d): %d\n", 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

Заключение

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