Thư Viện Câu Hỏi Phỏng Vấn

Question

Giải thuật Quay lui (Backtracking) khác gì so với duyệt vét cạn (Brute Force)? Giải thích cơ chế Pruning (Cắt tỉa nhánh)?

Senior

Answer 1

Brute Force (Vét cạn): Tạo ra tất cả các cấu hình/lời giải có thể có của bài toán, sau đó kiểm tra xem cấu hình nào thỏa mãn yêu cầu. Cách này sinh ra không gian trạng thái khổng lồ và cực kỳ chậm.

Backtracking (Quay lui): Xây dựng lời giải từng bước một cách có hệ thống. Tại mỗi bước, nếu phát hiện ra lời giải đang xây dựng dở dang chắc chắn không thể dẫn đến lời giải hợp lệ cuối cùng, thuật toán sẽ ngay lập tức dừng lại, hủy bỏ nhánh đó (quay lui) để thử phương án khác.

Pruning (Cắt tỉa nhánh): Là kỹ thuật áp dụng các điều kiện ràng buộc toán học hoặc logic để phát hiện sớm các nhánh không khả thi và loại bỏ chúng ngay lập tức từ gốc trước khi đi sâu vào đệ quy. Ví dụ trong bài toán N-Queens, nếu đặt quân hậu ở cột i bị trùng đường chéo với quân hậu trước đó, ta bỏ qua hoàn toàn việc thử đặt các quân hậu tiếp theo trên nhánh này. Cắt tỉa giúp giảm đáng kể thời gian chạy từ giai thừa/mũ xuống mức chấp nhận được trên thực tế.

Answer 2

Trong lập trình giải thuật với Backtracking, việc làm chủ Permutations yêu cầu lập trình viên hiểu rõ cấu trúc vật lý trong bộ nhớ và độ phức tạp tính toán:

Độ phức tạp: Luôn đánh giá Time Complexity (thời gian) và Space Complexity (không gian) tối ưu nhất (ví dụ: tối ưu từ O(n^2) xuống O(n log n)).
Trường hợp biên (Edge Cases): Xử lý kỹ các giá trị null, mảng rỗng, giá trị giới hạn cực đại/cực tiểu của kiểu dữ liệu.
Mã nguồn mẫu: Triển khai giải pháp rõ ràng, súc tích bằng các cấu trúc dữ liệu cơ bản, tránh lạm dụng bộ nhớ phụ khi không cần thiết.

Thư Viện Câu Hỏi Phỏng Vấn

Giải thuật Quay lui (Backtracking) khác gì so với duyệt vét cạn (Brute Force)? Giải thích cơ chế Pruning (Cắt tỉa nhánh)?

Làm thế nào để triển khai và tối ưu hóa thuật toán hoặc cấu trúc dữ liệu liên quan đến Permutations trong chủ đề Backtracking?