Hướng dẫn quay lui trong python

Đã đăng vào thg 7 27, 2017 4:42 CH 4 phút đọc

Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Người đầu tiên đề ra thuật ngữ này [backtrack] là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

Tư tưởng

Dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.

Các bước trong việc liệt kê cấu hình dạng X[1...n]:

• Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
• Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]...tiếp tục như vậy cho tới bước:
• ...
• ....
• Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
• Thông báo cấu hình tìm được.

Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu[Depth-First Search].

Mô hình thuật toán

• Mã giả cho thuật toán quay lui.

Backtracking[k] {
	for[[Mỗi phương án chọn i[thuộc tập D]]] {
		if [[Chấp nhận i]] {
			[Chọn i cho X[k]];
			if [[Thành công]] {
				[Đưa ra kết quả];
			} else {
				Backtracking[k+1];
				[Bỏ chọn i cho X[k]];
			}
		}
	}
}

Ví dụ: Trò chơi Sudoku

Sudoku là một trò chơi khá phổ biến và chắc ai cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9x9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số ô vuông con cho trước [có điền sẵn số] và còn lại là trống. Hãy điền các số từ 1-9 vào các ô con lại sao cho: hàng ngang là các số khác nhau từ 1 đến 9, hàng dọc là các số khác nhau từ 1 đến 9, và mỗi khối 3x3 chính là các số khác nhau từ 1 đến 9. Sau đây là 1 ví dụ về đề bài và lời giải:

Áp dụng quay lui để giải bài toán sudoku. Ý tưởng: Mỗi bước tìm tập các giá trị khả dĩ để điền vào ô trống, và sau đó đệ quy để điền ô tiếp theo. Giả mã của thuật toán [ở đây chú ý mảng chỉ có kích thước 9×9×9]

void solveSudoku[int S[][9], int x, int y]{
    if[y == 9]{
        if[x == 8]{
            printSolution[S];
            exit[0];
        } else {
            solveSudoku[S, x+1,0];
        }
    } else if[S[x][y] == 0]{
        for [int k = 1; k  Giá trị sau chính là giá trị trước cộng thêm 1 [hoặc là giá trị trước trừ đi 1], giá trị kết thúc =1.
Sau đây là phần demo:
def giaiThua[n]:
  if n==0:    #điều kiện dừng thỏa
    return 1; #vì 0!=1 nên n==0 là vị trí kết thúc của đệ quy
  return n*giaiThua[n - 1]; #kiểu n*[n-1]*[n-2]…*1
              #hoặc: giaiThua[n-1]*n với kiểu 1*2*3*…*n

def main[]:
  n=int[input["Nhập n: "]]
  print["Giai thừa của",n,"là", giaiThua[n]];

main[]
Ví dụ 3:
In ra n
phần tử đầu tiên của dãy Fibonanci [1 1 2 3 5 8 13 21 34 …].
Phân tích: Hai phần tử đầu tiên của dãy là hai phần tử khởi tạo [1 1], bắt đầu từ phần tử thứ ba trở đi sẽ tuân theo quy tắc là phần tử sau bằng tổng của hai phần tử ngay trước nó cộng lại [ví dụ 13=5+8]. Công thức: n= [n-1] + [n-2]. Như vậy có nghĩa ta sẽ sử dụng được phương pháp đệ quy vì nó tuân theo cú pháp đệ quy.
Chương trình được viết như sau:
def fibo[n]:
  if[n==0 or n==1]: #nếu là hai phần tử đầu tiên của dãy [điều kiện dừng thỏa]
    return 1;       #thì sẽ có giá trị là 1
  return fibo[n-1] + fibo[n-2]; #nếu không thì tính giá trị của phần tử đó

def main[]:
  n=int[input["Nhập số phần tử cần xem của dãy Fibonacci: "]]
  print[n,"phần tử đầu tiên của dãy là:"];
  for i in range[0,n]:
    print[fibo[i]];

main[]
Kết
quả:
Nhập số phần tử cần xem của dãy Fibonacci: 10
10 phần tử đầu tiên của dãy là:
1
1
2
3
5
8
13
21
34
55