Đệ quy và không đệ quy

Duyệt đệ quy và không đệ quy

Nguyễn Duy Hàm

Phương pháp duyệt là một trong những phương pháp cơ bản để giải các bài toán trong Tin

học nhất là bài toán hữu hạn. Một khó khăn của pương pháp này là khi số cấu hình phải

duyệt trở lên quá lớn, nếu chúng ta không có phương án duyệt tốt sẽ không đáp ứng tốt

được yêu cầu của bài toán.

Khi tính toán việc cài đặt phương pháp duyệt ta thường nghĩ ngay tới mô hình quay lui.

Quay lui là mô hình có thể đảm bảo cho nguyên tắc không trùng lặp và bỏ sót của phương

pháp duyệt. Nội dung chính của phương pháp này là từng bước xây dựng dần các thành

phần của phương án bằng cách thử các khả năng có thể, nếu tồn tại một phương án chấp

nhận được thì tiến hành bước tiếp, nếu không thì lùi lại bước trước đó để xây dựng lại

phương án đó với các khả năng chưa được thử.

Giả sử một cấu hình là một véc tơ gồm n thành phần (x1, x2, x3,... xn) phải thỏa mãn một

điều kiện nào đó. Cụ thể mô hình này như sau:

Tại bước thứ i ta đã xây dựng xong i-1 thành phần (x1, x2,... xn-1), bây giờ ta phải xác

định thành phần thứ i của phương án. Lần lượt xét tất cả các khả năng của xi, lúc này xảy

ra các trường hợp sau:

+ Có một khả năng j thoả mãn ->xi được xác định theo khả năng này. Nếu i=n thì ta được

một nghiệm. Ngược lại i< tie^?p bu+o+?c ha`nh tie^?n>

+ Không có một khả năng nào chấp nhận được cho x1 -> lùi lại bước trước để xác định lại

thành phần xi-1.

Mô hình quay lui được tổ chức theo đệ quy dưới dạng giả mã như sau:

Procedure Duyet(i:Type_var);

Var j: Type_var;

Begin

For j do

If Then

Begin

[Ghi nhân trạng thái mới]