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

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

Например, проблема вычисления последовательности Фибоначчи показывает перекрывающиеся подзадачи. Задачу вычисления 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

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

Смотрите также

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

Ссылки