như tittle , tuy là nó hơi không đươc tối ưu nhưng nếu trong 1 miềng không gian các lời giải không quá lớn thì có phải quay lui là cách làm đơn giản nhất để tìm ra được kết quá đúng ko ạ , và khi em giải các bài kiểu quay lui thì em thấy cách phân tích lời giải của nó giống với tìm kiếm theo chiều sâu , vậy 2 cái này có cùng 1 cách giải quyết vấn đề ạ ?
Mọi bài toán kiểu liệt kê thì đều có thể dùng quay lui để giải?
Đúng rồi bạn. Quay lui luôn cho ra lời giải đúng nhưng với input nhỏ, có thể kết hợp nhánh cận để giảm running time xuống, nhưng nhìn chung vẫn rất lớn, đpt thường làm hàm mũ hoặc giai thừa.
3 Likes
Đúng vì miễn sao duyệt qua được tất cả các cấu hình khả dĩ là được.
Hơi khác ở chỗ DFS có lưu các trạng thái cũ để tránh rơi vào chu trình (đi vòng vòng). Còn quay lui là dùng cho tree.
4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?