“Overlapping subproblems”的意思、由来-开放百科全书

词条 Overlapping subproblems

释义

Fibonacci Sequence Example in C
See also
References

In computer science, a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems.^[1]^[2]

^[3]

For example, the problem of computing the Fibonacci sequence exhibits overlapping subproblems. The problem of computing the nth Fibonacci number F(n), can be broken down into the subproblems of computing F(n − 1) and F(n − 2), and then adding the two. The subproblem of computing F(n − 1) can itself be broken down into a subproblem that involves computing F(n − 2). Therefore, the computation of F(n − 2) is reused, and the Fibonacci sequence thus exhibits overlapping subproblems.

A naive recursive approach to such a problem generally fails due to an exponential complexity. If the problem also shares an optimal substructure property, dynamic programming is a good way to work it out.

Fibonacci Sequence Example in C

Consider the following C code:

#include

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\", i, fibMem[i - 1]);    }

}

int main(void) {

printFibonacci();

return 0;

}

/* Output:

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

When executed, the fibonacci function computes the value of some of the numbers in the sequence many times over, following a pattern which can be visualized by this diagram:

f(5) = f(4) + f(3) = 5

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

However, we can take advantage of memoization and change the fibonacci function to make use of fibMem like so:

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;

}

This is much more efficient because if the value r has already been calculated for a certain n and stored in fibMem[n - 1], the function can just return the stored value rather than making more recursive function calls. This results in a pattern which can be visualized by this diagram:

f(5) = f(4) + f(3) = 5

| |
| |
| |
| f(1) = 1
|

The difference may not seem too significant with an N of 5, but as its value increases, the complexity of the original fibonacci function increases exponentially, whereas the revised version increases more linearly.

References

1. ^[https://books.google.com/books?id=NLngYyWFl_YC&pg=PA15&dq=introduction+to+algorithms&psp=1&sig=jX-xfEDWJU3PprUwH8Qfxidli6M#PPP1,M1 Introduction to Algorithms], 2nd ed., (Cormen, Leiserson, Rivest, and Stein) 2001, p. 327. {{ISBN|0-262-03293-7}}.
2. ^[https://books.google.com/books?id=jUF9BAAAQBAJ&dq=introduction+to+algorithms+3rd+edition&hl=en&sa=X&ved=0CD8Q6AEwAmoVChMIjZyx4N7HxwIVjDs-Ch1mjAqh,M1 Introduction to Algorithms], 3rd ed., (Cormen, Leiserson, Rivest, and Stein) 2014, p. 384. {{ISBN|9780262033848}}.
3. ^[https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-13/ Dynamic Programming: Overlapping Subproblems, Optimal Substructure], MIT Video.

1 : Dynamic programming

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Fibonacci Sequence Example in C

See also

References