Цель этой статьи — познакомить читателя с четырьмя главными алгоритмическими парадигмами: полный поиск, жадные алгоритмы, разделяй и властвуй, и динамическое программирование. Многие алгоритмические проблемы можно сопоставить с одной из этих категорий, мастерство в каждой повысит ваш уровень программирования.
Статья написана с точки зрения спортивного программирования. В конце статьи вы найдёте материалы для обучения или повышения навыков программирования с помощью соревнований.
Полный поиск
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Заключение
В статье был рассмотрены лишь базовые алгоритмы. Больше информации по алгоритмам вы всегда можете найти у нас на сайте.
Перевод статьи «Algorithms in C++»
Сергей Ринг