предисловие
В этой главе мы представим два других часто используемых алгоритма:динамическое программированиеа такжекак дела. Динамическое программирование часто сравнивают с инверсией рекурсии, а жадные алгоритмы — лучший выбор для решения многих задач оптимизации. Ниже мы подробно изучим эти два алгоритма.
динамическое программирование
Почему динамическое программирование иногда считают противоположностью рекурсии? Это потому, что рекурсия разбивает проблему сверху и решает всю проблему, решая все способы разбить ее на мелкие проблемы. Решение динамического программирования решает проблему снизу, удаляя все мелкие проблемы, а затем объединяя их в общее решение, которое решает большую проблему в целом.
Использование рекурсии для решения задач просто, но неэффективно. Многие языки, включая JavaScript, не могут эффективно интерпретировать рекурсивный код в машинный код, хотя написанная программа кратка, эффективность выполнения низка. Но это не значит, что использование рекурсии — это плохо, просто императивные и объектно-ориентированные языки программирования недостаточно хорошо реализуют рекурсию, потому что в них нет рекурсии как возможности расширенного программирования.
Последовательность Фибоначчи
Последовательность Фибоначчи определяется как следующая последовательность:
0，1，1，2，3，5，8，13，21，34，55，......
Видно, что при n >= 2n = an - 1 + an - 2. Эта числовая последовательность имеет очень долгую историю, она использовалась итальянским математиком Фибоначчи в 700 году нашей эры для описания роста кроликов в идеальных условиях.
Нетрудно видеть, что эту последовательность можно представить простой рекурсивной функцией.
function fibo (n) {
if (n <= 0) return 0;
if (n === 1) return 1;
return fibo(n - 1) + fibo(n - 2);
}
Этот метод реализации очень требователен к производительности, когда величина n достигает уровня тысячи, программа становится очень медленной и даже теряет отклик. Если вы используете динамическое программирование, чтобы начать с самой простой подзадачи, которую оно может решить, эффект будет совсем другим. Здесь мы сначала используем массив для доступа к результатам каждой подзадачи, что удобно для последующего использования.
function fibo (n) {
if (n <= 0) return 0;
if (n <= 1) return 1;
var arr = [0, 1];
for (var i = 2; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
Внимательные студенты обнаружили, что массив здесь можно удалить и заменить локальными переменными, чтобы сэкономить много места в памяти.
function fibo (n) {
if (n <= 0) return 0;
if (n <= 1) return 1;
var res, a = 0, b = 1;
for (var i = 2; i <= n; i++) {
res = a + b;
a = b;
b = res;
}
return res;
}
Есть ли способ реализовать это более лаконично? Ответ — да, я могу сохранить еще одну переменную.
function fibo (n) {
if (n <= 0) return 0;
if (n <= 1) return 1;
var a = 0, b = 1;
for (var i = 2; i <= n; i++) {
b = a + b;
a = b - a;
}
return b;
}
найти самую длинную общую подстроку
Другая проблема, решаемая с помощью динамического программирования, — найти самую длинную общую подстроку двух строк. Например, в словах raven и havoc самая длинная общая подстрока — «av». Поиск самой длинной общей подстроки часто используется в генетике для описания молекул ДНК с использованием инициалов оснований в нуклеотидах.
Мы можем использовать грубую силу, чтобы решить эту проблему, но это кажется неуклюжим.
function maxSubString (str1, str2) {
if (!str1 || !str2) return '';
var len1 = str1.length,
len2 = str2.length;
var maxSubStr = '';
for (var i = 0; i < len1; i++) {
for (var j = 0; j < len2; j++) {
var tempStr = '',
k = 0;
while ((i + k < len1) && (j + k < len2) && (str1[i + k] === str2[j + k])) {
tempStr += str1[i + k];
k++;
}
if (tempStr.length > maxSubStr.length) {
maxSubStr = tempStr;
}
}
}
return maxSubStr;
}
Мы не расширяем алгоритм динамического программирования для поиска самой длинной общей подстроки, заинтересованные студенты могут перейти по следующим ссылкам:
- Найдите самую длинную общую подстроку двух строк
- Динамическое программирование: найти самую длинную общую подпоследовательность / самую длинную общую подпоследовательность
проблема с рюкзаком
Задача о рюкзаке — классическая задача исследования алгоритмов. Представьте, что вы вор сейфа, и вы открыли сейф, полный экзотических сокровищ, но вам нужно положить эти сокровища в один из ваших маленьких рюкзаков. Предметы в сейфах различаются по размеру и стоимости. Вы хотите, чтобы общая стоимость ребенка в вашем рюкзаке была наибольшей.
Конечно, перебор может решить эту проблему, но динамическое программирование будет более эффективным. Ключевая идея использования динамического программирования для решения задачи о рюкзаке состоит в том, чтобы вычислить максимальную стоимость каждого предмета, загруженного в рюкзак, до тех пор, пока рюкзак не будет заполнен.
Если в нашем примере в сейфе 5 предметов, то их размеры 3, 4, 7, 8, 9, а их номиналы 4, 5, 10, 11, 13, а объем рюкзака равен 16, тогда правильным решением будет выбрать третий и пятый элементы, общий размер которых равен 16, а их общее значение равно 23.
Таблица 1: Задача с рюкзаком 0-1
| предмет | A | B | C | D | E |
|---|---|---|---|---|---|
| стоимость | 4 | 5 | 10 | 11 | 13 |
| размер | 3 | 4 | 7 | 8 | 9 |
Во-первых, давайте посмотрим, как решить эту проблему рекурсивно:
function knapsack (capacity, objectArr, order) {
if (order < 0 || capacity <= 0) {
return 0;
}
if (arr[order].size > capacity) {
return knapsack(capacity, objectArr, order - 1);
}
return Math.max(arr[order].value + knapsack(capacity - arr[order].size, objectArr, order - 1),
knapsack(capacity, objectArr, order - 1));
}
console.log(knapsack(16, [
{value: 4, size: 3},
{value: 5, size: 4},
{value: 10, size: 7},
{value: 11, size: 8},
{value: 13, size: 9}
], 4)); // 23
Чтобы повысить эффективность работы программы, мы могли бы также изменить рекурсивную реализацию на динамическое программирование. Для этой задачи существует специальный термин: задача о рюкзаке 0-1. Проблема рюкзака 0-1, решение dp всегда беспокоило многих новичков, большинство людей узнают об этом один раз и однажды забудут, поэтому на этот раз мы очень стараемся помнить об этом.
Обратите внимание, что прорыв в понимании задачи о рюкзаке 0-1 заключается в понимании значения «0-1».Здесь для каждого предмета либо взять (1), либо оставить (0).
Основная идея
0-1 подструктура задачи о рюкзаке: для выбора данного i-го предмета необходимо сравнить оптимальное решение подзадачи, образованное выбором i-го предмета, и оптимальное решение подзадачи без выбора i-го предмета. Разделите ее на две подзадачи, сравните выбор и выберите лучшую.
еслиf[i][w]представляет максимальное значение, которое можно получить, поместив первые i предметов в рюкзак вместимостью w. Тогда его уравнение перехода состояния:
f[i][w] = max{ f[i-1][w], f[i-1][w-w[i]]+v[i] }
где w[i] — вес i-го предмета, а v[i] — стоимость i-го предмета.
function knapsack (capacity, objectArr) {
var n = objectArr.length;
var f = [];
for (var i = 0; i <= n; i++) {
f[i] = [];
for (var w = 0; w <= capacity; w++) {
if (i === 0 || w === 0) {
f[i][w] = 0;
} else if (objectArr[i - 1].size <= w) {
var size = objectArr[i - 1].size,
value = objectArr[i - 1].value
f[i][w] = Math.max(f[i - 1][w - size] + value, f[i - 1][w]);
} else {
f[i][w] = f[i - 1][w];
}
}
}
return f[n][capacity];
}
И пространственная, и временная сложность вышеуказанных методов равны O(nm), где n — количество предметов, а m — вместимость рюкзака. Временная сложность не подлежит оптимизации, но пространственная сложность может быть оптимизирована до O(m). Сначала мы должны переписать уравнение перехода состояния:
f[w] = max{ f[w], f[w-w[i]]+v[i] }
Пожалуйста, посмотрите пример кода:
function knapsack (capacity, objectArr) {
var n = objectArr.length;
var f = [];
for (var w = 0; w <= capacity; w++) {
for (var i = 0; i < n; i++) {
if (w === 0) {
f[w] = 0;
} else if (objectArr[i].size <= w) {
var size = objectArr[i].size,
value = objectArr[i].value
f[w] = Math.max(f[w - size] + value, f[w] || 0);
} else {
f[w] = Math.max(f[w] || 0, f[w - 1]);
}
}
}
return f[capacity];
}
как дела
Алгоритм динамического программирования, изученный ранее, может быть использован для оптимизации решений, найденных субоптимальными алгоритмами — эти решения обычно реализуются на основе рекурсивных решений. Для многих задач динамическое программирование является излишним, и часто бывает достаточно простого алгоритма.
Жадный алгоритм является относительно простым алгоритмом. Жадный алгоритм всегда будет выбирать текущее оптимальное решение, не задумываясь о том, повлияет ли этот выбор на выбор в будущем. Использование жадного алгоритма обычно показывает, что разработчик хочет сделать ряд локально «оптимальных» вариантов, которые приводят к окончательному общему «оптимальному» выбору. Если это так, алгоритм даст оптимальное решение, в противном случае он даст субоптимальное решение. Однако для многих задач поиск оптимального решения является громоздким и нецелесообразным, поэтому достаточно жадного алгоритма.
проблема с рюкзаком
Если предметы, помещенные в рюкзак, являются смежными по своей природе, то задача о рюкзаке может быть решена с помощью жадного алгоритма. Другими словами, предмет нельзя считать дискретно, например ткань или золотой песок. Если используемые предметы являются смежными, то стоимость предмета может быть определена просто путем деления цены единицы предмета на единицу объема. Оптимальным в этом случае является загрузка предмета с наибольшим значением первым, пока этот предмет не будет заполнен или рюкзак не будет полон, а затем предмет со следующим наибольшим значением, пока этот предмет также не будет заполнен или рюкзак не будет полон, так что аналогия . Мы называем этот тип вопроса "Часть проблемы рюкзака".
Таблица 2: Частичные проблемы с рюкзаком
| предмет | A | B | C | D | E |
|---|---|---|---|---|---|
| стоимость | 50 | 140 | 60 | 60 | 80 |
| размер | 5 | 20 | 10 | 12 | 20 |
| соотношение | 10 | 7 | 6 | 5 | 4 |
Причина, по которой мы не можем решить проблему дискретных элементов с помощью жадного алгоритма, заключается в том, что мы не можем поместить «половину телевизора» в рюкзак. другими словами,Жадный алгоритм не может решить задачу о рюкзаке 0-1, потому что в задаче о рюкзаке 0-1 вы должны положить весь предмет или ничего.
function knapsack (capacity, objectArr) {
// 首先按性价比排序, 高 -> 低
objectArr.sort(function (a, b) {
return parseFloat(b.value / b.size) - parseFloat(a.value / a.size);
});
// 记录物品个数
var n = objectArr.length;
// 记录已经选中尺寸，已选最大的最大价值
var selected = 0,
maxValue = 0;
for (var i = 0; i < n && selected < capacity; i++) {
var size = objectArr[i].size,
value = objectArr[i].value;
if (size <= capacity - selected) {
maxValue += value;
selected += size;
} else {
// 计算比例
maxValue += value * ((capacity - selected) / size);
selected = capacity;
}
}
return maxValue;
}