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

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

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

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

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

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

#включают <stdio.h>#define N 5статический int fibMem[N];int Фибоначчи(int п) {	int р = 1;	если (п > 2) {		р = Фибоначчи(п - 1) + Фибоначчи(п - 2);	}	fibMem[п - 1] = р;	возвращаться р;}пустота printFibonacci() {    int я;    за (я = 1; я <= N; я++) {        printf("фибоначчи (% d):% d п", я, fibMem[я - 1]);    }}int главный(пустота) {    Фибоначчи(N);	printFibonacci();	возвращаться 0;}/* Выход:    фибоначчи (1): 1    фибоначчи (2): 1    фибоначчи (3): 2    фибоначчи (4): 3    фибоначчи (5): 5 * /

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

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

Однако мы можем воспользоваться мемоизация и изменить Фибоначчи функция использовать fibMem вот так:

int Фибоначчи(int п) {	int р = 1;	если (fibMem[п - 1] != 0) {		р = fibMem[п - 1];	} еще {		если (п > 2) {			р = Фибоначчи(п - 1) + Фибоначчи(п - 2);		}		fibMem[п - 1] = р;	}	возвращаться р;}

Это намного эффективнее, потому что если значение р уже рассчитан для определенного п и хранится в 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, но по мере увеличения его значения сложность оригинала Фибоначчи функция увеличивается экспоненциально, тогда как в обновленной версии возрастает более линейно.

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

Рекомендации

  1. ^ Введение в алгоритмы, 2-е изд., (Кормен, Лейзерсон, Ривест и Штайн) 2001, стр. 327. ISBN  0-262-03293-7.
  2. ^ Введение в алгоритмы, 3-е изд., (Cormen, Leiserson, Rivest, and Stein) 2014, стр. 384. ISBN  9780262033848.
  3. ^ Динамическое программирование: перекрывающиеся подзадачи, оптимальная подструктура, MIT Video.