Перекрывающиеся подзадачи

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

Например, проблема вычисления последовательности Фибоначчи имеет перекрывающиеся подзадачи. Задачу вычисления n-го числа Фибоначчи F ( n ) можно разбить на подзадачи вычисления F ( n - 1) и F ( n - 2), а затем их сложения. Подзадачу вычисления F ( n − 1) можно разбить на подзадачу, которая включает в себя вычисление F ( n − 2). Следовательно, вычисление F ( n - 2) используется повторно, и, таким образом, последовательность Фибоначчи демонстрирует перекрывающиеся подзадачи.

Наивный рекурсивный подход к такой проблеме обычно терпит неудачу из-за экспоненциальной сложности . Если проблема также имеет оптимальные свойства подструктуры , динамическое программирование — хороший способ ее решить.

Пример последовательности Фибоначчи в C

Рассмотрим следующий код C :

#include <stdio.h>

#define N 5

static int fibMem[N];

int fibonacci(int n) {
	int r = 1;
	if (n > 2) {
		r = fibonacci(n - 1) + fibonacci(n - 2);
	}
	fibMem[n - 1] = r;
	return r;
}

void printFibonacci() {
    int i;
    for (i = 1; i <= N; i++) {
        printf("fibonacci(%d): %d\n", i, fibMem[i - 1]);
    }
}

int main(void) {
    fibonacci(N);
	printFibonacci();
	return 0;
}

/* Output:
    fibonacci(1): 1
    fibonacci(2): 1
    fibonacci(3): 2
    fibonacci(4): 3
    fibonacci(5): 5 */

При выполнении fibonacci Функция вычисляет значение некоторых чисел в последовательности много раз, следуя шаблону, который можно визуализировать с помощью этой диаграммы:

f(5) = f(4) + f(3) = 5
       |      |
       |      f(3) = f(2) + f(1) = 2
       |             |      |
       |             |      f(1) = 1
       |             |
       |             f(2) = 1
       |
       f(4) = f(3) + f(2) = 3
              |      |
              |      f(2) = 1
              |
              f(3) = f(2) + f(1) = 2
                     |      |
                     |      f(1) = 1
                     |
                     f(2) = 1

Однако мы можем воспользоваться преимуществами мемоизации и изменить fibonacci функция, позволяющая использовать fibMem вот так:

int fibonacci(int n) {
	int r = 1;
	if (fibMem[n - 1] != 0) {
		r = fibMem[n - 1];
	} else {
		if (n > 2) {
			r = fibonacci(n - 1) + fibonacci(n - 2);
		}
		fibMem[n - 1] = r;
	}
	return r;
}

Это гораздо более эффективно, поскольку если значение r уже рассчитано на определенный n и хранится в fibMem[n - 1], функция может просто вернуть сохраненное значение, а не выполнять дополнительные рекурсивные вызовы функций. В результате получается закономерность, которую можно визуализировать с помощью этой диаграммы:

f(5) = f(4) + f(3) = 5
       |      |
       f(4) = f(3) + f(2) = 3
              |      |
              f(3) = f(2) + f(1) = 2
                     |      |
                     |      f(1) = 1
                     |
                     f(2) = 1

Разница может показаться не слишком значительной, если N 5, но по мере увеличения его значения сложность оригинала fibonacci Функция увеличивается экспоненциально, тогда как пересмотренная версия увеличивается более линейно.

См. также

• Динамическое программирование