Câu hỏi Sự khác biệt giữa backtracking và đệ quy?


Sự khác biệt giữa backtracking và đệ quy là gì? Chương trình này hoạt động như thế nào?

void generate_all(int n)
 {
    if(n<1) printf("%s\n", ar);
    else{
            ar[n-1]='0';        //fix (n)th bit as '0'
            generate_all(n-1);  //generate all combinations for other n-1 positions.
            ar[n-1]='1';        //fix (n)th bit as '1'
            generate_all(n-1);  //generate all combinations for other n-1 positions.
    }

14
2017-10-31 08:58


gốc


Tôi nghĩ bạn nên làm cho câu hỏi của bạn rõ ràng hơn một chút. ar thậm chí không được định nghĩa trong mã bạn cung cấp. - Ashe
câu hỏi tuyệt vời! đệ quy như bạn hiển thị nó, phục vụ như là cơ chế thực hiện để đếm đầy đủ tất cả các kết quả có thể; thay vì chỉ in ở trường hợp cơ bản, thêm một bài kiểm tra, một bản in có điều kiện khi kiểm tra được thông qua, và bảo lãnh tùy chọn, và bạn đã có cho mình một mini-Prolog cho một vấn đề cụ thể nướng trong. - Will Ness


Các câu trả lời:


Câu hỏi đó giống như hỏi sự khác nhau giữa xe hơi và người DeLorean là gì.

Trong chức năng đệ quy, hãy tự gọi cho đến khi đạt đến một vỏ cơ sở.

Trong backtracking bạn sử dụng đệ quy để khám phá tất cả các khả năng cho đến khi bạn nhận được kết quả tốt nhất cho vấn đề.

Có thể hơi khó hiểu, tôi đính kèm một số văn bản từ đây:

"Khái niệm, bạn bắt đầu ở gốc cây, cây có thể có một số lá tốt và một số lá xấu, mặc dù nó có thể là lá là tất cả tốt hoặc tất cả xấu. Bạn muốn để có được một lá tốt. Tại mỗi nút , bắt đầu với gốc, bạn chọn một trong những đứa con của nó để di chuyển đến, và bạn giữ nó cho đến khi bạn đến một cái lá.

Giả sử bạn nhận được một lá xấu. Bạn có thể quay lại để tiếp tục tìm kiếm một chiếc lá tốt bằng cách thu hồi lựa chọn gần đây nhất của bạn và thử tùy chọn tiếp theo trong bộ tùy chọn đó. Nếu bạn hết các tùy chọn, hãy thu hồi lựa chọn đã đưa bạn đến đây và thử một lựa chọn khác tại nút đó. Nếu bạn kết thúc ở gốc với không có tùy chọn còn lại, không có lá tốt để được tìm thấy. "

Điều này cần một ví dụ.

enter image description here

Đoạn mã của bạn chỉ đơn giản là đệ quy, vì bạn không bao giờ quay lại nếu kết quả không phù hợp với mục tiêu của bạn.


19
2017-10-31 09:17





Đệ quy mô tả sự kêu gọi của cùng chức năng mà bạn đang ở. Ví dụ điển hình của một hàm đệ quy là giai thừa, tức là một cái gì đó như

int fact(int n) {
    int result;
    if(n==1) return 1;
    result = fact(n-1) * n;
    return result;
}

Những gì bạn thấy ở đây là thực tế gọi chính nó. Đây được gọi là đệ quy. Bạn luôn luôn cần một điều kiện làm cho đệ quy dừng lại. Đây rồi if(n==1) kết hợp với thực tế là n sẽ luôn giảm mỗi khi nó được gọi (fact(n-1))

Quay lại là một thuật toán cố gắng tìm một giải pháp cho các tham số. Nó xây dựng các ứng cử viên cho giải pháp và từ bỏ những người không thể đáp ứng các điều kiện. Một ví dụ điển hình cho một công việc để giải quyết sẽ là Tám Queens Puzzle. Backtracking cũng thường được sử dụng trong Neuronal Networks.

Chương trình bạn mô tả sử dụng đệ quy. Tương tự như hàm giai thừa, nó làm giảm đối số bằng 1 và kết thúc nếu n <1 (vì sau đó nó sẽ in ar thay vì làm phần còn lại).


10
2017-10-31 09:15





Theo hiểu biết của tôi, backtracking là một thuật toán, giống như tất cả các thuật toán khác, như BFS và DFS, nhưng đệ quy và lặp lại là các phương thức, chúng ở mức cao hơn các thuật toán, ví dụ, để triển khai DFS, bạn có thể sử dụng đệ quy , mà là khá trực quan, nhưng bạn cũng có thể sử dụng lặp với một chồng, hoặc bạn cũng có thể nghĩ đệ quy và lặp lại chỉ là phương pháp để hỗ trợ các thuật toán của bạn.


1
2018-06-17 02:08