1-định nghĩa :

quay lui là một trong những kỹ thuật quan trọng nhất. Nó có thể được

áp dụng để thiết kế thuật toán tìm ra một nghiệm hoặc tất cả

các nghiệm của bài toán.

2-biểu diễn dữ liệu :

vẫn dùng phương pháp này để giải

các bài toán vì nó tối ưu, dễ hiểu, dễ diễn đạt,gần gũi với

toán học, và người sử dụng cũng dễ dàng nắm bắt tư tưởng

thuật toán.

3-các phép toán :

- tư tưởng :

• Tư tưởng chính của thuật toán này là việc xây dựng các thành phần lời giải bằng cách thử tất cả các khả năng có thể :

• Giả thiết 1 cấu hình là x1, x2, ..., xn. Giả sử đã xác định được i-1 thành phần x1, x2, ..., xi-1 ta cần xác định xi bằng cách duyệt tất cả các khả năng có thể đề cử cho nó. Với mỗi khả năng j kiểm tra xem j có chấp nhận được không?

- + Nếu chấp nhận, xác định xi theo j. Nếu i=n ta được một cấu hình. Ngược lại xác định xi+1.

- + Nếu hết các khả năng mà không có khả năng nào chấp nhận được thì quay lại bước trước để xác định lại xi-1.

Điểm quan trọng của thuật toán là phải ghi nhớ lại mỗi bước đã đi qua,những khả năng nào đã thử để tránh trùng lặp.Rõ ràng những thông tin này cần được lưu trữ theo cơ cấu ngăn xếp.Vì thế thuật toán này rất phù hợp việc sử dụng đệ qui

- thủ tục :

Thủ tục diễn tả thuật toán quay lui:

void try(int j) //Thử với bước đi thứ j;

{

for(int i=0;i<=n;i++)

if(chấp nhận i)

{

<ghi nhận xj theo i> ;

if(Hoàn thành) <ghi nhận cấu hình nghiệm> ;

else Try(j+1); //Nếu chưa kết thúc thử bước tiếp

<Xoá ghi nhớ> ;

}

}

• Phần quan trongng nhất trong thủ tục trên là việc đưa ra được một danh sách các khả năng đề cử và việc xác định được giá trị của biểu thức(chấp nhận i).