Çakışan alt problemler - Overlapping subproblems
Gelen bilgisayar bilimleri , bir sorun olduğu söyleniyor altproblemleri örtüşen sorun birkaç kez yeniden veya sorun için yinelemeli bir algoritma defalarca ziyade her zaman yeni altproblemleri üreten aynı subproblem çözer olan alt problemlerden ayrılabilir eğer.
Örneğin, işlem problemi Fibonacci dizisi örtüşen altproblemleri sergiler. İşlem problemi n inci Fibonacci sayı F ( n ), bilgi işlem alt problemler ayrılmış olabilir F ( n - 1) ve F ( n - 2), ve daha sonra iki ilave edilmesi. Hesaplama subproblem F ( n - 1) kendisi bilgisayar içerir bir subproblem ayrılmış olabilir F ( n - 2). Bu nedenle, hesaplama, F ( n - 2) yeniden kullanılır, ve Fibonacci sekansı böylece sergiler altproblemleri binmektedir.
Saf bir yinelemeli bir soruna bir yaklaşım, genellikle, bir nedeniyle başarısız üstel karmaşıklığı . Sorun da paylaşırsa optimum altyapı özelliği, dinamik programlama onu yürütmek için iyi bir yoldur.
C Fibonacci Dizisi ÖRNEK
Aşağıdaki düşünün C kodu:
#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 */
Çalıştırıldığında, fibonacci
işlev, bu diyagram ile görselleştirilebilir bir desen ardından defalarca sırayla bazı numaralar değerini hesaplar:
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
Ancak, biz yararlanabilirsiniz memoization ve değişim fibonacci
faydalanmak için işlevini fibMem
şöyle:
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;
}
Değer çünkü eğer bu çok daha verimlidir r
zaten kesin hesaplanmıştır n
ve saklanan fibMem[n - 1]
, fonksiyon sadece daha fazla özyinelemeli fonksiyon çağrıları yapmak yerine saklanan değer döndürebilir. Bu, bu diyagram ile görselleştirilebilir bir desen ortaya çıkar:
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
Fark, sahip çok önemli görünmeyebilir N
5, ama değeri arttıkça, orijinal karmaşıklığı fibonacci
fonksiyonu daha doğrusal olarak gözden geçirilmiş versiyon artar ise, katlanarak artar.
Ayrıca bakınız
Referanslar
- ^ Algoritmalarına Giriş , 2. baskı., (Cormen, Leiserson, Rivest ve Stein) 2001, s. 327. ISBN 0-262-03293-7 .
- ^ Algoritmalarına Giriş , 3rd ed., (Cormen, Leiserson, Rivest ve Stein) 2014, s. 384. ISBN 9780262033848 .
- ^ Dinamik Programlama: altproblemleri, Optimal Altyapı Çakışan , MİT video.