Xem mẫu
- Cấu trúc dữ liệu và giải thuật
Bài 4: Kỹ thuật quay lui (Backtracking)
Lecturer: PhD. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
1 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- Bài 4. Kỹ thuật quay lui
Backtracking
Nội dung:
4.1. Khái niệm về kỹ thuật quay lui (6)
4.2. Bài toán 8 con hậu - Eight Queen Problem (7)
4.3. Bài toán mã đi tuần - Knight Tour Problem (5)
4.4. Bài toán chiếc ba lô - Knapsack Problem (6)
Tham khảo:
1. Lecture 11 – Backtracking.htm
2 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.1. Khái niệm kỹ thuật quay lui (1/6)
Kỹ thuật quay lui là quá trình phân tích từ trên xuống
trong không gian tìm kiếm.
Trong trường hợp tổng quát, giả sử lời giải là một
vector:
a = (a[1], a[2], …, a[n])
trong đó, mỗi phần tử a[i] chọn từ tập hữu hạn S[i]
(các khả năng của a[i]).
3 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.1. Khái niệm kỹ thuật quay lui (2/6)
Ta s ẽ giải quyết bài toán với kích thước k, có dạng:
a = (a[1], a[2], …, a[k])
và cố gắng mở rộng bằng việc thêm phần tử tiếp theo
vào trong vector.
Sau khi thêm phần tử, kiểm tra xem có thể thực hiện
tiếp được không.
Nếu vẫn có khả năng mở rộng, tiếp tục thực hiện;
Nếu không, xóa phần tử a[k] và làm lại bài toán từ tập
S[k].
4 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.1. Khái niệm kỹ thuật quay lui (3/6)
Gọi S[1], tập các khả năng của a tại bước đầu tiên.
k=1
While k > 0 do
While S[k][] do (*advance*)
a[k] = an element in S[k]
If (a[1], a[2],…, a[k]) is solution, print it!
k=k+1
Tính S[k], tập khả năng của a tại bước k.
k = k - 1 (*backtrack*)
5 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.1. Khái niệm kỹ thuật quay lui (4/6)
Sub Backtrack(a, k)
If a is a solution, get it
Else
k = k +1
compute S[k]
While S[k][] do
a[k] = an element in S[k]
S[k] = S[k] – a[k]
Backtrack(a, k)
End Sub
6 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.1. Khái niệm kỹ thuật quay lui (5/6)
Kỹ thuật đệ quy có thể được dùng trong kỹ thuật
quay lui (đơn giản trong ứng dụng).
Kỹ thuật quay lui chắc chắn đúng khi liệt kê các khả
năng có thể.
Để tăng hiệu quả của kỹ thuật, có thể cắt bớt
không gian tìm kiếm.
7 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.1. Khái niệm kỹ thuật quay lui (6/6)
Trong phần này, giải quyết một số bài toán, có sử dụng
kỹ thuật quay lui:
Bài toán 8 hậu - Eight Queen Problem.
Bài toán mã đi tuần - Knight Tour Problem.
Bài toán chiếc ba lô - Knapsack Problem.
8 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.2. Eight Queen Problem (1/7)
Bài toán: đặt 8 con hậu trên bàn cờ sao cho không có 2 con
hậu nằm trên cùng một hàng, cột và hàng ngang.
Một lời giải Không phải lời giải
9 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.2. Eight Queen Problem (2/7)
Thực hiện:
• Trạng thái: Sắp đặt từ 0 đến 8
con hậu lên bàn cờ.
• Trạng thái khởi tạo: không có
con hậu nào đặt lên bàn cờ.
• Đặt từng con hậu lên bàn cờ.
• Kiểm tra kết quả: 8 con hậu đã
đặt lên bàn cờ, không có con
hậu nào ăn được nhau.
648 cách đặt 8 con hậu
10 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.2. Eight Queen Problem (3/7)
Một vài cách đặt 8 con hậu lên bàn cờ (trong số 92 lời giải)
11 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.2. Eight Queen Problem (4/7)
Ý tưởng:
Mỗi lần đệ quy, tìm cách đặt 1 con hậu lên một cột (hoặc
hàng) riêng.
Với mỗi lần gọi, tình trạng bàn cờ đã biết (các con hậu đã
đặt)
Nếu tại một cột, không đặt được con hậu mới, con hậu ở
cột (hàng) đó được bỏ ra khỏi bàn cờ và chuyển xuống
cột (hàng) trước đó.
12 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.2. Eight Queen Problem (5/7)
Nếu xét theo cột, tại một cột, tất cả các hàng đã
xét, quay trở lại bước trước đó (xét cột trước).
Nếu con hậu không đặt được lên cột i, khi đó
không thử trên cột i+1, quay lại cột i-1, bỏ con
hậu đã đi sai.
Với cách tiếp cận này, có thể giảm bớt phép thử.
13 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.2. Eight Queen Problem (6/7)
#include "stdio.h" // In ma tran chua cac con hau
#include "conio.h" void printMatrix(int a[][N], int n) {
#include "math.h" int i, j;
#define N 8
for(i=0; i
- 4.2. Eight Queen Problem (6/7)
// Kiem tra xem con hau tiep theo co the dat o hang // Bai toan N hau
// row, cot col khong void N_Queens(int a[][N], int n, int row) {
bools feasible(int a[][N], int n, int row, int col) int j;
{
if(row < n) {
int i;
for(j=0; j
- 4.3. Knight Tour Problem (1/5)
16 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.3. Knight Tour Problem (2/5)
Bài toán:
Trên bàn cờ 8 × 8 có một con mã (cách đi được
định nghĩa thông thường).
Bắt đầu từ một góc của bàn cờ và thăm tất cả các
ô cờ khác (63 ô cờ còn lại), sao cho mỗi ô cờ chỉ
đến 1 lần.
Bài toán này được gọi là “mã đi tuần”.
17 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.3. Knight Tour Problem (3/5)
Cách tiếp cận bài toán:
Có nhiều cách tiếp cận để giải bài
toán này.
Một trong số đó là cách giải của J.C.
Warnsdorff được đưa ra năm 1823.
Theo cách của J.C. Warnsdorff, con
mã đi theo theo thứ tự được mã hóa
(quy ước cách đi theo hình vẽ).
Từ một vị trí, con mã có thể đi tối đa
đến 8 vị trí khác. Tùy theo vị trí trên
bàn cờ, các vị trí có thể này được mã
hóa theo thứ tự từ 1 đến 8.
18 @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 4.3. Knight Tour Problem (4/5)
#include "stdio.h" for(m=0;m
- 4.3. Knight Tour Problem (5/5)
void knight(int a[][M], int n, int row, int col, int num) printf("\nNhan Enter de chon ket qua khac, nhan
{ ESC de thoat!\n");
// tim vi tri ke tiep if(char c=getch()==27)
// vi tri ke tiep co gia nho nhat exit(1);
// vi tri hien tai la (row,col) }
int i; else
for(i=0; i=0 && newrow=0
&& newcol
nguon tai.lieu . vn
