{"blocks":[{"type":"paragraph","data":{"text":"Цель этой статьи — познакомить читателя с четырьмя главными алгоритмическими парадигмами: полный поиск, жадные алгоритмы, разделяй и властвуй, и динамическое программирование. Многие алгоритмические проблемы можно сопоставить с одной из этих категорий, мастерство в каждой повысит ваш уровень программирования."}},{"type":"paragraph","data":{"text":"Статья написана с точки зрения спортивного программирования. В конце статьи вы найдёте материалы для обучения или повышения навыков программирования с помощью соревнований."}},{"type":"header2","data":{"level":2,"text":"Полный поиск"}},{"type":"paragraph","data":{"text":"Complete search (он же «грубая сила» или «рекурсивный откат») — метод решения задачи путем пересечения всего пространства поиска. Точнее на протяжении всего алгоритма мы отсекаем те части пространства поиска, которые, как мы считаем, не приведут к требуемому решению. На соревнованиях по спортивному программированию использование Complete Search скорее всего приведёт к превышению лимита времени (Time Limit Exceeded — TLE), однако, это хорошая стратегия для задач с небольшим объёмом входных данных."}},{"type":"header3","data":{"level":3,"text":"Пример: Задача с 8 ферзями"}},{"type":"paragraph","data":{"text":"Нам нужно расположить на шахматной доске 8 ферзей так, чтобы ни один ферзь не нападал на другого. В наиболее простом решении нам придётся перебрать 64 млрд комбинаций и выбрать 8–4 млрд возможных расстановок. Также неплохой вариант — поставить каждого ферзя в отдельную колонну, что сводит число возможностей к 8⁸ — ~17 млн. Но лучше всего поставить каждого ферзя в отдельный ряд и в отдельную колонну. Это приведёт к 8! — 40 тыс. возможных комбинаций. В приведённой ниже реализации мы предполагаем, что каждый ферзь занимает отдельный столбец, и вычисляем номер строки для каждого из 8 ферзей."}},{"type":"code","data":{"code":"#include \r\n#include \r\n#include \r\n\r\nusing namespace std;\r\n\r\n// row[8]: номер строки для каждого ферзя\r\n// TC: счётчик TraceBack\r\n// (a, b): расположение первого ферзя от (r=a, c=b)\r\nint row[8], TC, a, b, line_counter;\r\n\r\nbool place(int r, int c)\r\n{ \r\n // Проверяем ранее размещённых ферзей\r\n for (int prev = 0; prev < c; prev++)\r\n {\r\n // Проверяем, совпадают ли строки или диагонали\r\n if (row[prev] == r || (abs(row[prev] - r) == abs(prev - c)))\r\n return false;\r\n }\r\n return true;\r\n}\r\n\r\nvoid backtrack(int c)\r\n{\r\n // Возможное решение; первый ферзь имеет координаты a и b\r\n if (c == 8 && row[b] == a)\r\n {\r\n printf(\"%2d %d\", ++line_counter, row[0] + 1);\r\n for (int j = 1; j < 8; j++) printf(\" %d\", row[j] + 1);\r\n printf(\"\\n\");\r\n }\r\n // Пробуем все возможные строки\r\n for (int r = 0; r < 8; r++)\r\n {\r\n if (place(r, c))\r\n {\r\n row[c] = r; // место ферзя в этом столбце и в этой строке\r\n backtrack(c + 1); // следующий столбец и рекурсия\r\n }\r\n }\r\n}\r\n\r\nint main()\r\n{\r\n scanf(\"%d\", &TC);\r\n while (TC--)\r\n {\r\n scanf(\"%d %d\", &a, &b);\r\n a--; b--; // индексируем с нуля\r\n\r\n memset(row, 0, sizeof(row));\r\n line_counter = 0;\r\n printf(\"РЕШ\\tСТОЛБЕЦ\\n\");\r\n printf(\" # 1 2 3 4 5 6 7 8\\n\\n\");\r\n backtrack(0); // генерируем все 8! возможных решений\r\n if (TC) printf(\"\\n\");\r\n }\r\n return 0;\r\n}","language":"cpp lazy-code"}},{"type":"paragraph","data":{"text":"Для TC = 8 и начальной позиции ферзя в (a, b) = (1, 1), приведённый выше код выводит следующее:"}},{"type":"code","data":{"code":"РЕШ СТОЛБЕЦ\r\n# 1 2 3 4 5 6 7 8\r\n1 1 5 8 6 3 7 2 4\r\n2 1 6 8 3 7 4 2 5\r\n3 1 7 4 6 8 2 5 3\r\n4 1 7 5 8 2 4 6 3","language":"bash lazy-code"}},{"type":"paragraph","data":{"text":"Он указывает, что всего возможно 4 расстановки, принимающих начальное положение ферзя в (r = 1, c = 1)."}},{"id":"7679b6c2-81cb-4660-9f08-ae24567245ce","type":"banner-blank","data":{}},{"type":"paragraph","data":{"text":"Использование рекурсии позволяет легче выделить пространство поиска в сравнении с итерационным решением."}},{"type":"header2","data":{"level":2,"text":"Жадный алгоритм"}},{"type":"paragraph","data":{"text":"Данный алгоритм на каждом шаге делает локально оптимальный выбор, надеясь в итоге получить глобально оптимальное решение."}},{"type":"header3","data":{"level":3,"text":"Пример: Дробный Рюкзак"}},{"type":"paragraph","data":{"text":"Задача состоит в том, чтобы выбрать, какие предметы, имеющие вес и стоимость, поместить в рюкзак ограниченной ёмкости W, да так, чтобы максимизировать общую ценность его содержимого. Мы можем определить соотношение стоимости предмета к его весу, т. е. с «жадностью» выбирать предметы, имеющие высокую стоимость, но в то же время маленький вес, а затем сортировать их по этим критериям. В задаче с дробным рюкзаком нам разрешено брать дробные части предмета."}},{"type":"code","data":{"code":"#include \r\n#include \r\n\r\nusing namespace std;\r\n\r\nstruct Item {\r\n int value, weight;\r\n Item(int value, int weight) : value(value), weight(weight) { }\r\n};\r\n\r\nbool cmp(struct Item a, struct Item b) {\r\n double r1 = (double) a.value / a.weight;\r\n double r2 = (double) b.value / b.weight;\r\n return r1 > r2;\r\n}\r\n\r\ndouble fractional_knapsack(int W, struct Item arr[], int n)\r\n{\r\n sort(arr, arr + n, cmp);\r\n int cur_weight = 0; double tot_value = 0.0;\r\n for (int i = 0; i < n; ++i)\r\n {\r\n if (cur_weight + arr[i].weight <= W)\r\n {\r\n cur_weight += arr[i].weight;\r\n tot_value += arr[i].value;\r\n } \r\n else\r\n { // Добавляем часть следующего предмета\r\n int rem_weight = W - cur_weight;\r\n tot_value += arr[i].value *\r\n ((double) rem_weight / arr[i].weight); \r\n break;\r\n }\r\n }\r\n return tot_value;\r\n}\r\nint main()\r\n{\r\n int W = 50; // вместительность рюкзака\r\n Item arr[] = {{60, 10}, {100, 20}, {120, 30}}; // {стоимость, вес}\r\n int n = sizeof(arr) / sizeof(arr[0]);\r\n cout << \"жадный дробный рюкзак\" << endl;\r\n cout << \"максимальная ценность: \" << fractional_knapsack(W, arr, n);\r\n cout << endl;\r\n return 0;\r\n}","language":"cpp lazy-code"}},{"type":"paragraph","data":{"text":"Поскольку сортировка — самая дорогая операция, алгоритм работает за время O(n log n). Принимая в формате (стоимость, вес) три пары предметов — {(60, 10), (100, 20), (120, 30)} — и итоговую вместительность рюкзака W = 50, приведённый выше код выводит следующее:"}},{"type":"code","data":{"code":"жадный дробный рюкзак\r\nмаксимальная ценность: 240","language":"bash lazy-code"}},{"type":"paragraph","data":{"text":"Мы можем заметить, что ввод предметов отсортирован с уменьшающим коэффициентом стоимость/вес. Выбрав два целых предмета 1 и 2, мы берём ⅔ от третьего предмета.
Итоговая ценность = 60 + 100 + (2/3) * 120 = 240."}},{"type":"hint","data":{"fullWidth":true,"text":"Читайте также: Оценка сложности алгоритмов, или Что такое О(log n)"}},{"type":"header2","data":{"level":2,"text":"Разделяй и Властвуй"}},{"type":"paragraph","data":{"text":"Разделяй и Властвуй — стратегия, подразумевающая, что задача разделяется на независимые подзадачи и затем каждая из них решается."}},{"type":"paragraph","data":{"text":"Примеры этой стратегии — быстрая сортировка, сортировка слиянием и пирамидальная сортировка, а также бинарный поиск."}},{"type":"header3","data":{"level":3,"text":"Пример: Бинарный поиск"}},{"type":"paragraph","data":{"text":"Чаще всего бинарный поиск (бинпоиск) используют, чтобы найти элемент в отсортированном массиве. Мы начинаем искать с середины массива. Если находим то, что нужно, или если больше нечего рассматривать, мы останавливаемся. В противном случае мы решаем, в каком направлении — вправо или влево от середины — мы должны продолжить поиск. Так как пространство поиска после каждой проверки делится на два, то время выполнения алгоритма — O(log n)."}},{"type":"code","data":{"code":"#include \r\n#include \r\n#include \r\n\r\nusing namespace std;\r\n\r\nint bsearch(const vector &arr, int l, int r, int q)\r\n{\r\n while (l <= r)\r\n {\r\n int mid = l + (r-l)/2;\r\n if (arr[mid] == q) return mid;\r\n \r\n if (q < arr[mid]) { r = mid - 1; }\r\n else { l = mid + 1; }\r\n }\r\n return -1; // не нашли\r\n}\r\n\r\nint main()\r\n{\r\n int query = 10;\r\n int arr[] = {2, 4, 6, 8, 10, 12};\r\n int N = sizeof(arr) / sizeof(arr[0]);\r\n vector v(arr, arr + N);\r\n \r\n // Сортируем входной массив\r\n sort(v.begin(), v.end());\r\n int idx;\r\n idx = bsearch(v, 0, v.size(), query);\r\n if (idx != -1)\r\n cout << \"бинарный поиск: нашли по индексу \" << idx; \r\n else\r\n cout << \"бинарный поиск: не нашли\";\r\n return 0;\r\n}","language":"cpp lazy-code"}},{"type":"paragraph","data":{"text":"Код выводит следующее:"}},{"type":"code","data":{"code":"бинарный поиск: нашли по индексу 4","language":"bash lazy-code"}},{"type":"paragraph","data":{"text":"Если искомый элемент не найден, но мы хотим найти ближайший элемент меньше или больше запроса, то можно использовать функции STL lower_bound() и upper_bound()."}},{"type":"header2","data":{"level":2,"text":"Динамическое программирование"}},{"type":"paragraph","data":{"text":"Динамическое программирование (ДП) — это техника, которая разделяет задачу на маленькие пересекающиеся подзадачи, считает решение для каждой из них и сохраняет его в таблицу. Окончательное решение считывается из таблицы."}},{"type":"paragraph","data":{"text":"Ключевая особенность динамического программирования — способность определять состояние записей в таблице и отношения или перемещения между записями.
Затем, определив базовые и рекурсивные случаи, можно заполнить таблицу сверху вниз или снизу вверх."}},{"type":"paragraph","data":{"text":"В нисходящем ДП таблица будет заполнена рекурсивно, по мере необходимости, начиная сверху и спускаясь к меньшим подзадачам. В восходящем ДП таблица будет заполняться по порядку, начиная с меньших подзадач и с использованием их решений для того чтобы подниматься выше и находить решения для бо́льших задач. В обоих случаях если решение данной подзадачи уже встречалось, оно просто ищется в таблице. И это значительно снижает вычислительные затраты."}},{"type":"header3","data":{"level":3,"text":"Пример: Биноминальные коэффициенты"}},{"type":"paragraph","data":{"text":"Мы используем пример биноминальных коэффициентов, чтобы проиллюстрировать использование нисходящего и восходящего ДП. Код ниже основан на рекурсиях для биноминальных коэффициентов с перекрывающимися подзадачами. Обозначим через C(n, k) количество выборок из n по k, тогда имеем:"}},{"id":"582e250d-7309-4c7d-b935-0aa589db6e22","type":"banner-blank","data":{}},{"type":"paragraph","data":{"text":"Базовый случай: C(n, 0) = C(n, n) = 1
Рекурсия: C(n, k) = C(n-1, k-1) + C(n-1, k)"}},{"type":"paragraph","data":{"text":"У нас есть несколько перекрывающихся подзадач. Например, для C(n = 5, k = 2) рекурсивное дерево будет следующим:"}},{"type":"code","data":{"code":"C(5, 2)\r\n / \\\r\n C(4, 1) C(4, 2)\r\n / \\ / \\\r\n C(3, 0) C(3, 1) C(3, 1) C(3, 2)\r\n / \\ / \\ / \\\r\n C(2, 0) C(2, 1) C(2, 0) C(2, 1) C(2, 1) C(2, 2)\r\n / \\ / \\ / \\\r\n C(1, 0) C(1, 1) C(1, 0) C(1, 1) C(1, 0) C(1, 1)","language":"bash lazy-code"}},{"type":"paragraph","data":{"text":"Мы можем реализовать нисходящее и восходящее ДП следующим образом:"}},{"type":"code","data":{"code":"#include \r\n#include \r\n\r\nusing namespace std;\r\n\r\n#define V 8\r\n\r\nint memo[V][V]; // таблица\r\n\r\nint min(int a, int b) { return (a < b) ? a : b; }\r\n\r\nvoid print_table(int memo[V][V])\r\n{\r\n for (int i = 0; i < V; ++i)\r\n {\r\n for (int j = 0; j < V; ++j)\r\n {\r\n printf(\" %2d\", memo[i][j]); \r\n }\r\n printf(\"\\n\");\r\n }\r\n}\r\n\r\nint binomial_coeffs1(int n, int k)\r\n{\r\n // Нисходящее ДП\r\n if Нk == 0 || k == n) return 1; \r\n if (memo[n][k] != -1) return memo[n][k];\r\n return memo[n][k] = binomial_coeffs1(n-1, k-1) + \r\n binomial_coeffs1(n-1, k);\r\n}\r\n\r\nint binomial_coeffs2(int n, int k)\r\n{ \r\n // Восходящее ДП\r\n for (int i = 0; i <= n; ++i) \r\n { \r\n for (int j = 0; j <= min(i, k); ++j)\r\n { \r\n if (j == 0 || j == i)\r\n { \r\n memo[i][j] = 1;\r\n } \r\n else\r\n {\r\n memo[i][j] = memo[i-1][j-1] + memo[i-1][j]; \r\n }\r\n }\r\n }\r\n return memo[n][k];\r\n} \r\n\r\nint main()\r\n{\r\n int n = 5, k = 2;\r\n printf(\"Нисходящее ДП:\\n\");\r\n memset(memo, -1, sizeof(memo));\r\n int nCk1 = binomial_coeffs1(n, k);\r\n print_table(memo);\r\n printf(\"C(n = %d, k = %d): %d\\n\\n\", n, k, nCk1);\r\n \r\n printf(\"Восходящее ДП:\\n\");\r\n memset(memo, -1, sizeof(memo));\r\n int nCk2 = binomial_coeffs2(n, k);\r\n print_table(memo);\r\n printf(\"C(n = %d, k = %d): %d\\n\", n, k, nCk2);\r\n \r\n return 0;\r\n}","language":"cpp lazy-code"}},{"type":"paragraph","data":{"text":"При C(n = 5, k = 2) код выше выводит следующее:"}},{"type":"code","data":{"code":"Нисходящее ДП:\r\n-1 -1 -1 -1 -1 -1 -1 -1\r\n-1 -1 -1 -1 -1 -1 -1 -1\r\n-1 2 -1 -1 -1 -1 -1 -1\r\n-1 3 3 -1 -1 -1 -1 -1\r\n-1 4 6 -1 -1 -1 -1 -1\r\n-1 -1 10 -1 -1 -1 -1 -1\r\n-1 -1 -1 -1 -1 -1 -1 -1\r\n-1 -1 -1 -1 -1 -1 -1 -1\r\nC(n = 5, k = 2): 10\r\n\r\nВосходящее ДП:\r\n 1 -1 -1 -1 -1 -1 -1 -1\r\n 1 1 -1 -1 -1 -1 -1 -1\r\n 1 2 1 -1 -1 -1 -1 -1\r\n 1 3 3 -1 -1 -1 -1 -1\r\n 1 4 6 -1 -1 -1 -1 -1\r\n 1 5 10 -1 -1 -1 -1 -1\r\n-1 -1 -1 -1 -1 -1 -1 -1\r\n-1 -1 -1 -1 -1 -1 -1 -1\r\nC(n = 5, k = 2): 10","language":"bash lazy-code"}},{"type":"paragraph","data":{"text":"Временная и пространственная сложность будут выражены как O(n * k)."}},{"type":"paragraph","data":{"text":"В случае нисходящего ДП решения подзадач накапливались по мере необходимости, в то время как в восходящем ДП таблица заполнялась начиная с базового случая."}},{"type":"paragraph","data":{"text":"Примечание Для печати был выбран маленький размер таблицы, рекомендуется брать намного больший размер."}},{"type":"header2","data":{"level":2,"text":"Код"}},{"type":"paragraph","data":{"text":"Весь код доступен здесь. Чтобы скомпилировать код на C++, можете воспользоваться командой:"}},{"type":"code","data":{"code":"$ g++ --std=c++11 -Wall -o test\r\n$ ./test","language":"bash lazy-code"}},{"type":"header2","data":{"level":2,"text":"Заключение"}},{"type":"paragraph","data":{"text":"В статье был рассмотрены лишь базовые алгоритмы. Больше информации по алгоритмам вы всегда можете найти у нас на сайте."}}]}

Ошибка в настройках сайта