Page 0 of 84 Võ Văn Tr - CQB | Confidential MỤC LỤC Phương pháp duyệt Chuyên đề 1. Duyệt vét cạn..................................................................................................................1 Chuyên đề 2. Duyệt nhánh cạnh ..................................................................................................... 12 Chuyên đề 3. Duyệt ưu tiên............................................................................................................... 24 Tìm kiếm nhị phân Chuyên đề 4. Tìm kiếm nhị phân và ứng dụng......................................................................... 27 Xử lý bít Chuyên đề 5. Xử lý bit.......................................................................................................................... 30 Quy hoạch động Chuyên đề 6. Quy hoạch động cơ bản .......................................................................................... 36 Chuyên đề 7. Quy hoạch động trạng thái.................................................................................... 49 Đồ thị Chuyên đề 8. Tìm kiếm theo chiều rộng ..................................................................................... 58 Chuyên đề 9. Tìm kiếm theo chiều sâu........................................................................................ 69 Võ Văn Tr - CQB | Confidential PHƯƠNG PHÁP DUYỆT Chuyên đề 1. Duyệt vét cạn - Backtracking Quay lui, vét cạn, thử sai, duyệt… là một số tên gọi tuy không đồng nghĩa nhưng cùng chỉ một phương pháp trong tin học: tìm nghiệm của một bài toán bằng cách xem xét tất cả các phương án có thể. Đối với con người phương pháp này thường không khả thi vì số phương án cần kiểm tra lớn. Tuy nhiên đối với máy tính, nhờ tốc độ xử lý nhanh, máy tính có thể giải rất nhiều bài toán bằng phương pháp quay lui vét cạn. Người đầu tiên đề ra chiến lược này là nhà toán học người Mỹ Derrick Henry Lehmer (1905 – 1991) vào những năm 1950. Ưu điểm của phương pháp quay lui, vét cạn là luôn bảo đảm tìm ra nghiệm đúng, chính xác. Tuy nhiên, hạn chế của phương pháp này là thời gian thực thi lâu, độ phức tạp lớn. Về bản chất, tư tưởng của phương pháp này là thử từng khả năng cho đến khi tìm thấy lời giải đúng. Đó là một quá trình tìm kiếm theo độ sâu trong một tập các lời giải. Trong quá trình tìm kiếm, nếu gặp một hướng lựa chọn không thỏa mãn, ta quay lui, về điểm lựa chọn có các hướng khác và thử hướng lựa chọn tiếp theo. Khi đã thử hết tất cả các hướng lựa chọn xuất phát từ một điểm, ta quay lại điểm lựa chọn kế trước. Quá trình tìm kiếm kết thúc khi không còn hướng lựa chọn nào để thử. Chiến lược quay lui tương tự với tìm kiếm theo độ sâu nhưng tốn ít không gian nhớ hơn, thời gian tìm kiếm lại nhanh hơn. Mô hình thuật toán Backtracking: procedure try(i:integer); begin for <m i giá tr t có th gán cho xi> do begin <Th cho xi := t>; if <thành công> then <thông báo k t qu > else begin <Ghi nh n vi c xi nh n giá tr t>; <try(i+1)>; {th bư c đi ti p theo} <H y bư c đi th i (n u c n)>; end; end; end; 1. Bài tập 1: Liệt kê tất cả các dãy nhị phân có độ dài n. Page 2 of 84 Võ Văn Tr - CQB | Confidential Phân tích: Dãy nhị phân có độ dài n có dạng (x1, x2, …, xn) với xi ∈ {0, 1}, 1 ≤ ≤ . Như vậy, tại bước thứ i, ta tìm cách chọn giá trị cho biến x i. {Chuong trinh cai dat thuat toan de quy} {Liet ke tat ca cac cau hinh nhi phan co do dai n} Program BackTracking_ListsOfBinaryPermutations; Const n=3; var i,k:byte; h:array[1..20] of byte; Procedure Try(i:byte); var j:byte; begin for j:=0 to 1 do begin h[i]:=j; if i=n then begin for k:=1 to n do write(h[k]); writeln; end else Try(i+1); end; end; begin try(1); end. 2. Bài tập 2: Liệt kê tất cả các hoán vị của tập {1, 2, …, n} Phân tích: Các hoán vị của tập {1, 2, …, n} có dạng (x1, x2, …, xn) với xi ∈ {1, 2, … , }, 1 ≤ ≤ và xi # xj với mọi i, j. - Như vậy, việc xây dựng mỗi hoán vị được thực hiện qua n bước. - Bước thứ i ta chọn một số trong tập {1, 2, …, n} để đặt vào vị trí thứ i của hoán vị. - Tuy nhiên, ta chỉ chọn được số x i k