Sự khác nhau giữa đệ qui và qui hoạch động?

masterq1997 · November 23, 2015, 11:41am

Cho em hỏi sự khác nhau giữa đệ quy và qui hoạch động là như thế nào ??

Lúc học 12 thầy cô có nói về hai cái này nhưng em vẫn không hiểu rõ cho lắm. Liệu chúng có dính gì tới nhau không

nguyenchiemminhvu · November 23, 2015, 10:50am

đệ quy là một kỹ thuật gọi hàm.
quy hoạch động là một phương pháp giải bài toán loại bỏ đệ quy.

masterq1997 · November 23, 2015, 11:08am

anh có thể giải thích kĩ hơn được không ??

nguyenchiemminhvu · November 23, 2015, 2:26pm

Đệ quy là kỹ thuật tự gọi lại hàm định nghĩa nó.
Ví dụ bài toán tính giai thừa:

Mỗi lần gọi lại hàm, thì nó tạo ra bản sao của hàm đó ở một địa chỉ khác trong ram (nên tốn bộ nhớ).
Và nó còn bị lặp lại một số bước không cần thiết.

Quy hoạch động ra đời để loại bỏ sự dư thừa trong đệ quy.\

Đệ quy: https://vi.wikipedia.org/wiki/Đệ_quy

Quy hoạch động: https://vi.wikipedia.org/wiki/Quy_hoạch_động

masterq1997 · November 23, 2015, 2:08pm

ồ tks anh em đọc tài liệu thì có nói về đệ quy nhưng qui hoạch động thì không hiểu rõ lắm

DoTran1 · October 11, 2019, 3:47am

quan tâm, mấy hôm nay đọc QHĐ muốn nổ đầu, cao nhân nào thông não giùm với.
thanks

rogp10 · March 10, 2020, 6:30am

Đệ quy với bottom-up về cơ bản là hai chiều ngược nhau để áp dụng công thức truy hồi

Đệ quy đi từ cao xuống thấp đến trường hợp dừng (nếu tính tới đâu ghi tới đó - memoization - thì có thể dừng khi đã tính rồi, không bị trùng lắp)
Bottom-up đi từ trường hợp dừng lên tới đáp số cuối cùng.

QHĐ không phải tốn nhiều stack mem vì chỉ gọi hàm phụ lực, còn đệ quy thì gọi hàm nhiều depth có thể tăng tuyến tính làm sập stack

DoTran1 · October 11, 2019, 4:00am

vậy đáp số cuối cùng là gì vậy bạn? có phải cái mình đang tìm? nếu vậy làm sao biết được nó dừng khi nào để lấy ra đáp số cuối cùng?
bạn có thể nói rõ hơn k?
thanks

Sherly1001 · October 11, 2019, 9:37am

Ví dụ nhỏ cho bạn nè.

Lấy luôn dãy fibonacy. Đề là tính phần tử thứ i của dãy fibonacy.

Nếu đệ quy thì chỉ cần như này

int fib1(int n) {
    if (n < 3) return 1;
    return fib1(n - 1) + fib1(n - 2);
}

Như anh Rogp10 nó thì đệ quy nó đi từ cao xuống thấp. fib_n -> fib_{n - 1} -> fib_{n - 2} -> . . . -> fib₁.

Còn nếu như dùng QHD thì sẽ như này.

int fib2(int n) {
    int f1 = 1, f2 = 1;
    for (int i = 0; i < n - 2; i++) {
        f2 += f1;
        f1 = f2 - f1;
    }
    return f2;
}

Là từ fib₁ và fib₂ tính số fib_n .

Như trên nếu lặp for một lần sẽ được fib₃, 2 lần được fib₄, . . , k lần được fib_{k + 2}

Vậy đáp số cuối cùng sẽ có được sau n - 2 lần lặp.

DoTran1 · October 11, 2019, 10:11am

Cám ơn nhiều nha,
Bạn có thể giải thích giùm tôi cái bài toán “xếp balo” theo QHĐ được k?
Tôi đã đọc nhiều trên mạng mà vẫn chưa hiểu được.
Bài toán xếp balo là:
Balo có thể mang tối đa M kg.
Ta có n vật.
Mỗi vật có khối lượng mi bất kỳ, có giá trị (ví dụ tiền) là ti bất kỳ (m1, t1 có thể khác m2, t2)
Hỏi cần lấy vật nào để tổng khối lượng <= M; mà tổng tiền là lớn nhất.
Cám ơn rất nhiều.

Nobita1 · October 11, 2019, 10:58am

Mình nói thật, đa phần mọi người hay nhầm và lấy vị dụ thường hay xét vào chiều tiếp cận của đệ quy và QĐH.

Mình thấy như vậy là không nên:

Về cơ bản: Đệ quy là một kỹ thuật gọi hàm (chiến lược viết code )và QHĐ là một chiến lược giải bài tối ưu,

QHĐ bắt đầu với một trường hợp cơ sở và công thức truy hồi để tìm kiếm những trường hợp đã biết

Có 2 cách thực thi quy hoach động: dùng đệ quy và dùng vòng lặp: hai ví dụ fib1 và fib2 của bạn @Sherly1001 đã minh họa ở trên.

Trong đệ quy thì có chia làm 2 loại là đệ quy có nhớ và đệ quy không nhớ nữa:fib1 ở trên chính là đệ quy không nhớ và đệ quy có nhớ sẽ thế này:

#include <stdio.h>
#define MAX 100
int a[MAX] ;
// khởi tạo tất cả các phân tử của a = 0;
int fib3(int n) {
    if (n < 3) return a[n];
    if(a[n]) return a[n]
    a[n] =  fib3(n - 1) + fib3(n - 2);
    return a[n];
}

int main(int argc, char const *argv[])
{	
	a[1] = 1, a[2] = 1;
	fib3(10);
	printf("%d\n",a[10]);
	return 0;
}

Ở trên là nói về có nhớ hay không?

Ngoài ra đệ quy còn có nhiều loại , về cách thức nó được gọi, như đệ quy tuyến tính (ở trên) , đệ quy phi tuyến, đệ quy tương hỗ …v.vv.

Nên nhớ, không phải cái gì tự gọi đến chính nó cũng là đệ quy, vì gọi đến chính nó: thì backtracking cũng làm vậy, nhưng đó là 2 cách tiếp cận khác nhau tùy vào mục đích mình sử dụng mà gọi là backtracking hay đệ quy.

DoTran1 · October 11, 2019, 10:24am

Là bạn trên nói sai à? Bạn có thể giải thích kỹ hơn được k?
thanks

Sherly1001 · October 11, 2019, 10:52am

Chỗ này thì đúng rồi nè. mình chỉ lương theo vấn đề của topic thôi.

Nhưng hàm fib3() của bạn không thể gọi là đệ quy có nhớ được vì chưa khai thác được hết arr. Phải như này nè.

int arr[max] = {0};

int fib3(int n) {
  if (n < 2) return 1;
  if (arr[n]) return arr[n];
  arr[n] = fib(n - 1) + fib(n - 2);
  return arr[n];
}

Nobita1 · October 11, 2019, 10:54am

Chính xác, mình thiếu xót chỗ đấy. để mình sửa luôn ở bài đăng của mình

DoTran1 · October 16, 2019, 7:46am

hi @Sherly1001 & tất cả mn, bạn trả lời giùm 2 câu sau với

tôi hiểu là “QHĐ = đệ quy có nhớ”. Tôi hiểu đúng hay sai bạn?
Tôi tính giai thừa như sau có được coi là QHĐ không bạn?
// Đã edit lại sau khi đã hiểu sơ sơ về QHĐ
// Kết luận: QHĐ khác đệ quy có nhớ
Cám ơn rất nhiều!
code java:

public static void main(String[] args) {
	System.out.println(giaiThuaTheoQHD(5));
    System.out.println(giaiThuaTheoDeQui(5));
}
private static int giaiThuaTheoQHD(int n) {
	int []arr = new int [n + 1];
	if (n < 0) return -1;
    if (n < 2) return 1;
	arr[0] = 1;
	arr[1] = 1;
	for (int i = 2; i<=n; i++) {
		arr[i] = arr[i -1] * i;
	}
	return arr[n];
}
private static int max = 10;
private static int []arr = new int [max];
private static int giaiThuaTheoDeQui(int n) {
	if (n < 0) return -1;
	if (n == 0) return arr[0] = 1;
	if (n>0 && n<3) {
		return arr[n-1] = n;
	}
	if(arr[n-1] > 0) return arr[n-1];
	arr[n-1] = giaiThuaTheoDeQui(n-1) * n;
	return arr[n-1];
}

rogp10 · October 16, 2019, 4:31am

Như @Nobita1 đã trình bày, đó là hai khía cạnh khác nhau, chiến thuật so với kĩ thuật.

DoTran1 · October 16, 2019, 4:33am

à, tôi k có ý so sánh bằng bằng vậy, mà đang đơn giản hóa cách hiểu.
chiến thuật QHĐ là sẽ sử dụng kỹ thuật đệ quy có nhớ để xử lý 1 bài toán.
Thay lại ngôn từ vậy thì có đúng k bạn?
Thanks

rogp10 · March 10, 2020, 6:30am

Cũng vậy thôi bạn.

QHĐ gồm có hai tính chất

Optimal substructure: Đáp số của bài toán lớn là sự kết hợp đơn thuần của đáp số (những) bài toán con. Ví dụ: tam giác Sierpinski bậc n có tất cả bao nhiêu tam giác?
Overlapping substructure: Kết quả của bài toán con được sử dụng nhiều lần.

Kĩ thuật đệ quy có nhớ rất hạn chế ở chỗ công thức chỉ cần O(1) số (Fibo) mà cứ phải nhớ hết từ 1 đến n. Những bài QHĐ 2 tham số còn rõ rệt hơn, tính bằng số dòng trong ma trận QHĐ.

DoTran1 · October 16, 2019, 6:19am

Cám ơn, để tôi tìm hiểu thêm về chúng.