Полный поиск, жадность, разделяй и властвуй, динамическое программирование
Вступление
Цель этой статьи - познакомить читателя с четырьмя основными алгоритмическими парадигмами: полный поиск, жадные алгоритмы, разделяй и властвуй и динамическое программирование. Многие алгоритмические проблемы можно отнести к одной из этих четырех категорий, и мастерство в каждой из них сделает вас лучшим программистом.
Эта статья написана с точки зрения соревновательного программирования. В справочном разделе вы найдете ресурсы, которые помогут вам начать или улучшить свои навыки программирования с помощью соревнований по программированию.
Полный поиск
Полный поиск (также известный как перебор или рекурсивный поиск с возвратом) - это метод решения проблемы путем обхода всего пространства поиска в поисках решения. Во время поиска мы можем обрезать те части поискового пространства, которые, как мы уверены, не приводят к требуемому решению. В соревнованиях по программированию полный поиск, скорее всего, приведет к превышению временного лимита (TLE), однако это хорошая стратегия для небольших проблем ввода.
Пример полного поиска: проблема 8 ферзей
Наша цель - разместить 8 ферзей на шахматной доске так, чтобы никакие две ферзя не атаковали друг друга. В самом наивном решении нам нужно было бы перечислить 64 и выбрать 8 ~ 4B возможностей. Лучшее наивное решение - понять, что мы можем поместить каждую ферзя в отдельный столбец, что дает 8⁸ ~ 17M возможностей. Мы можем добиться большего, поместив каждого ферзя в отдельный столбец и отдельную строку, что приведет к 8 ~ 40К допустимым перестановкам строк. В приведенной ниже реализации мы предполагаем, что каждый ферзь занимает отдельный столбец, и вычисляем допустимый номер строки для каждой из 8 ферзей.
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
//row[8]: row # for each queen
//TC: traceback counter
//(a, b): 1st queen placement at (r=a, c=b)
int row[8], TC, a, b, line_counter;
bool place(int r, int c)
{
// check previously placed queens
for (int prev = 0; prev < c; prev++)
{
// check if same row or same diagonal
if (row[prev] == r || (abs(row[prev] — r) == abs(prev — c)))
return false;
}
return true;
}
void backtrack(int c)
{
// candidate solution; (a, b) has 1 initial queen
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”);
}
//try all possible rows
for (int r = 0; r < 8; r++)
{
if (place(r, c))
{
row[c] = r; // place a queen at this col and row
backtrack(c + 1); //increment col and recurse
}
}
}
int main()
{
scanf(“%d”, &TC);
while (TC--)
{
scanf(“%d %d”, &a, &b); a--; b--; //0-based indexing
memset(row, 0, sizeof(row)); line_counter = 0;
printf(“SOLN COLUMN\n”);
printf(“ # 1 2 3 4 5 6 7 8\n\n”);
backtrack(0); //generate all possible 8! candidate solutions
if (TC) printf(“\n”);
}
return 0;
}
Для TC = 8 и начальной позиции ферзя в (a, b) = (1,1) приведенный выше код дает следующий результат:
SOLN COLUMN # 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
что указывает на то, что есть четыре возможных размещения, учитывая начальную позицию ферзя (r = 1, c = 1). Обратите внимание, что использование рекурсии позволяет более легко сократить пространство поиска по сравнению с итеративным решением.
Жадные алгоритмы
Жадный алгоритм на каждом шаге делает локально оптимальный выбор в надежде в конечном итоге достичь глобально оптимального решения. Жадные алгоритмы часто полагаются на жадную эвристику, и часто можно найти примеры, в которых жадные алгоритмы не могут достичь глобального оптимума.
Жадный пример: дробный рюкзак
Жадная задача о рюкзаке состоит в том, чтобы выбрать, какие предметы поместить в рюкзак ограниченной вместимости W, чтобы максимизировать общую стоимость предметов ранца, где каждый предмет имеет связанный вес и ценность. Мы можем определить жадную эвристику как отношение ценности элемента к весу элемента, то есть мы хотели бы жадно выбирать элементы, которые одновременно имеют высокую ценность и низкий вес, и сортировать элементы на основе этого критерия. В задаче о дробном рюкзаке нам разрешено брать доли предмета (в отличие от ранца 0–1).
#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
{ //add a fraction of the next item
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; // total knapsack weight
Item arr[] = {{60, 10}, {100, 20}, {120, 30}}; //{value, weight}
int n = sizeof(arr) / sizeof(arr[0]);
cout << “greedy fractional knapsack” << endl;
cout << “maximum value: “ << fractional_knapsack(W, arr, n);
cout << endl;
return 0;
}
Поскольку сортировка - самая дорогостоящая операция, алгоритм выполняется за O (n log n) времени. Учитывая пары (значение, вес) из трех элементов: {(60, 10), (100, 20), (120, 30)} и общую емкость W = 50, приведенный выше код дает следующий результат:
greedy fractional knapsack maximum value: 240
Мы видим, что входные элементы отсортированы по убыванию соотношения стоимость / стоимость, после жадного выбора элементов 1 и 2 мы берем 2/3 части элемента 3 для общего значения 60 + 100 + (2/3) 120. = 240.
Разделяй и властвуй
Разделяй и властвуй (D&C) - это метод, который разделяет проблему на более мелкие, независимые подзадачи, а затем объединяет решения каждой из подзадач.
Примеры техники «разделяй и властвуй» включают алгоритмы сортировки, такие как быстрая сортировка, сортировка слиянием и сортировка по куче, а также двоичный поиск.
Пример D&C: двоичный поиск
Классическое использование двоичного поиска - поиск значения в отсортированном массиве. Сначала мы проверяем середину массива, чтобы узнать, содержит ли он то, что мы ищем. Если это так или больше нет пунктов для рассмотрения, мы останавливаемся. В противном случае мы решаем, находится ли ответ слева или справа от среднего элемента, и продолжаем поиск. Поскольку размер области поиска уменьшается вдвое после каждой проверки, сложность алгоритма составляет 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; //not found
}
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 input array
sort(v.begin(), v.end());
int idx;
idx = bsearch(v, 0, v.size(), query);
if (idx != -1)
cout << "custom binary_search: found at index " << idx;
else
cout << "custom binary_search: not found";
return 0;
}
Приведенный выше код дает следующий результат:
custom binary_search: found at index 4
Обратите внимание: если элемент запроса не найден, но мы хотели бы найти первую запись не меньше, чем запрос, или первую запись, большую, чем запрос, мы можем использовать STL lower_bound и upper_bound.
Динамическое программирование
Динамическое программирование (DP) - это метод, который разделяет проблему на более мелкие перекрывающиеся подзадачи, вычисляет решение для каждой подзадачи и сохраняет его в таблице DP. Окончательное решение считывается из таблицы DP.
Ключевые навыки в освоении динамического программирования - это способность определять состояния проблемы (записи в таблице DP) и отношения или переходы между состояниями. Затем, определив базовые случаи и рекурсивные отношения, можно заполнить таблицу DP сверху вниз или снизу вверх.
При нисходящем DP таблица заполняется рекурсивно по мере необходимости, начиная сверху и спускаясь к более мелким подзадачам. В восходящем DP таблица заполняется итеративно, начиная с самых мелких подзадач и используя их решения для наращивания и поиска решений более крупных подзадач. В обоих случаях, если подзадача уже встречалась, ее решение просто ищется в таблице (в отличие от пересчета решения с нуля). Это резко снижает вычислительные затраты.
Пример DP: биномиальные коэффициенты
Мы используем пример биномиальных коэффициентов, чтобы проиллюстрировать использование DP сверху вниз и снизу вверх. Приведенный ниже код основан на рекурсии для биномиальных коэффициентов с перекрывающимися подзадачами. Пусть C (n, k) обозначает n, выберите k, тогда мы имеем:
Base case: C(n,0) = C(n,n) = 1
Recursion: 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)
Мы можем реализовать DP сверху вниз и снизу вверх следующим образом:
#include <iostream>
#include <cstring>
using namespace std;
#define V 8
int memo[V][V]; //DP table
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)
{
// top-down DP
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)
{
// bottom-up DP
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("Top-down DP:\n");
memset(memo, -1, sizeof(memo));
int nCk1 = binomial_coeffs1(n, k);
print_table(memo);
printf("C(n=%d, k=%d): %d\n", n, k, nCk1);
printf("Bottom-up DP:\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) приведенный выше код дает следующий результат:
Top-down DP: -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 Bottom-up DP: 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), а пространственная сложность - O (n * k). В случае DP сверху вниз решения подзадач сохраняются (запоминаются) по мере необходимости, тогда как в DP снизу вверх вся таблица вычисляется, начиная с базового случая. Примечание: для печати был выбран небольшой размер таблицы DP (V = 8), рекомендуется гораздо больший размер таблицы.
Код
Весь код доступен по адресу: https://github.com/vsmolyakov/cpp
Чтобы скомпилировать код C ++, вы можете выполнить следующую команду:
>> g++ <filename.cpp> --std=c++11 -Wall -o test >> ./test
Заключение
Существует ряд отличных ресурсов для изучения алгоритмов. Я очень рекомендую книгу Стивена Халима [1] о соревновательном программировании. В дополнение к классическому руководству по разработке алгоритмов [2] и CLRS [3]. Существует ряд веб-сайтов с серьезными проблемами кодирования, некоторые из которых упомянуты в [4]. Кроме того, [5] содержит фантастический набор алгоритмов и простых для понимания реализаций. Отличный ресурс, если вы создаете свою собственную библиотеку или участвуете в соревнованиях по программированию.
Надеюсь, эта статья окажется для вас полезной. Удачного кодирования !!
использованная литература
- Стивен Халим, «Соревновательное программирование», 3-е издание, 2013 г.
- Стивен Скиена, «Руководство по разработке алгоритмов», Springer, 2011 г.
- Томас Кормен и др., «Введение в алгоритмы», MIT Press, 2009 г.
- Https://medium.freecodecamp.org/the-10-most-popular-coding-challenge-websites-of-2016-fb8a5672d22f
- Https://www.geeksforgeeks.org/
