zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 4: Kỹ thuật quay lui (Backtracking)

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:29

Báo xấu

65
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 4: Kỹ thuật quay lui (Backtracking)" với những kiến thức khái niệm về kỹ thuật quay lui, bài toán 8 con 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 4: Kỹ thuật quay lui (Backtracking)

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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.