5. Discussion question
Tại sao vét cạn luôn là phương pháp tiếp cận đầu tiên để giải bài toán?
Tăng tốc độ vét cạn bao gồm những chiến thuật nào?
Theo bạn, giới hạn của việc áp dụng vét cạn cho các bài toán tổ hợp là bao nhiêu và vì sao?
Lấy ví dụ trong thực tế (cuộc sống, công việc) bạn đã áp dụng thuật toán vét cạn. Cách bạn tăng tốc các xử lý.
6. Homework
2.1.0 Homework
Dựa theo 2.0 Các khái niệm cơ bản, các bài tập nên dựa theo chiến lược sau cho việc áp dụng thuật toán vét cạn:
Cách liệt kê các cấu hình và cách xác thực một cấu hình (thuật toán vét cạn)
Không gian tìm kiếm (phân tích thời gian giải thuật)
Mã giả
Tinh chế từng bước mã giả → code
Kiểm thử (xây dựng các bộ test + chạy thử và tìm lỗi + submit lên hệ thống)
Các nhận xét để tăng tốc vét cạn (giảm không gian tìm kiếm hoặc sắp xếp lại không gian tìm kiếm)
Áp dụng cách thức tăng tốc → code (có thể áp dụng tinh chế từng bước)
Kiểm thử (chạy thử và tìm lỗi + submit lên hệ thống)
Lời giải cùng giải thích sẽ được cung cấp trước buổi học 2.2 Binary Search & Divide and Conquer (Thuật toán tìm kiếm nhị phân và chia để trị)
Bài 1: Tìm một số trong mảng đã sắp xếp và dịch phải - easy level
https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
Cho một mảng sắp xếp tăng dần đã bị dịch phải n bước, tìm xem liệu một số cho trước có nằm trong mảng này không
Ví dụ: cho mảng [1 2 3 4 5 6]
Dịch 1 bước ta có: [6 1 2 3 4 5]
Dịch 4 bước ta có: [3 4 5 6 1 2]
Dịch 6 bước ta có mảng ban đầu
Điều kiện:
Độ dài mảng: 1 <= n <= 5000
Phần tử của mảng: -10^4 <= A[i] <= 10 ^ 4
Bài 2: Tìm chuỗi con palindrome dài nhất - easy level
https://leetcode.com/problems/longest-palindromic-substring/
Chuỗi palindrome là chuỗi mà viết xuôi hay ngược đều giống nhau, ví dụ: “aba” , “tnt”
Cho một chuỗi kí tự s, tìm chuỗi con dài nhất của s sao cho chuỗi này là palindrome
Độ dài của chuỗi s nằm trong khoảng từ 1 đến 1000
Bài 3: REPROAD - easy level
https://www.spoj.com/problems/REPROAD/
Tóm tắt đề bài:
Cho một con đường dài N (5 <= N <= 10000) gồm các đoạn 0 (bị hỏng, không di chuyển được) và 1 (di chuyển được); và số K (0<=K<=N).
Bài toán cho phép sửa một đoạn đường bị hỏng (sửa 0 thành 1). Có tối đa K lần sửa.
In ra chiều dài lớn nhất của quãng đường di chuyển được (số các số 1 liên tiếp) với K lần sửa.
Input
Tổng số lượng phép thử là T (1 <= T <= 20) được cho trên dòng đầu tiên.
Mỗi phép thử được cho trên 2 dòng, dòng đầu tiên của mỗi phép thử là chiều dài N (5 <= N <= 10000) của con đường và số lần sửa tối đa K (0 <= K <= N), cách nhau bởi 1 dấu cách trắng.
Dòng tiếp theo mô tả trạng thái của từng đoạn đường (0 hoặc 1), 2 số cạnh nhau được ngăn cách bởi 1 dấu cách trắng.
Output
Hãy in đáp án của mỗi phép thử trên 1 dòng.
Bài 4: SOLIT - hard level
https://www.spoj.com/problems/SOLIT/
Tóm tắt đề bài:
Cho một bàn cờ 8x8 ô, đánh số từ 1 đến 8 (từ trên xuống dưới, từ trái sang phải).
Trên bàn cờ có 4 quân cờ khác nhau. Mỗi quân cờ có thể di chuyển:
- Di chuyển theo hướng Trên/Dưới/Trái/Phải sang ô còn trống ngay bên cạnh.
- Nếu ô bên cạnh đã có một quân cờ, nhảy qua ô này đến ô còn trống tiếp theo (trên cùng hướng di chuyển) nếu ô đó còn trống.
Bàn cờ A có 4 quân cờ.
Bàn cờ B có 4 quân cờ.
Xác định xem với tối đa 8 lần di chuyển các quân cờ trên bàn cờ A, có thể làm bàn cờ A và bàn cờ B có các quân cờ ở vị trí giống nhau hay không?
Input
Tổng số lượng phép thử là T được cho trên dòng đầu tiên.
Mỗi phép thử được cho trên 2 dòng, dòng đầu tiên của mỗi phép thử là tọa độ các quân cờ (a[2j-1] và a[2j] (1 <= j <= 4) lần lượt là hàng và cột của quân cờ thứ j) của bàn cờ A, cách nhau bởi dấu cách trắng.
Dòng tiếp theo là tọa độ các quân cờ của bàn cờ B, cách nhau bởi dấu cách trắng.
Output
Hãy in đáp án của mỗi phép thử trên 1 dòng dưới dạng:
Case #i: K
Bài 5: BURGLARY - medium level
https://www.spoj.com/problems/BURGLARY/
Tóm tắt đề bài:
Cho 1 mảng N (1<=N<=30) các số tự nhiên (mỗi số nằm trong khoảng từ 0 đến 1e9) và một số D (0<=D<=3*1e10).
Chọn K số bất kì trong mảng N sao cho tổng của các số này bằng D.
- Nếu chỉ có 1 cách chọn duy nhất, in ra số k
- Nếu có nhiều cách chọn khác nhau (nhiều số k khác nhau thỏa mãn đề bài), in "AMBIGIOUS"
- Nếu không có cách chọn nào, in "IMPOSSIBLE"
Input
Tổng số lượng phép thử là T (1 <= T <= 20) được cho trên dòng đầu tiên.
Mỗi phép thử được cho trên 2 dòng, dòng đầu tiên của mỗi phép thử là N và D, cách nhau bởi 1 dấu cách trắng.
Dòng tiếp theo mô tả các giá trị trong mảng, 2 số cạnh nhau được ngăn cách bởi 1 dấu cách trắng.
Output
Hãy in đáp án của mỗi phép thử trên 1 dòng dưới dạng:
Case #i: K
7. Xem thêm:
2.1.2 Thuật toán quay lui (backtracking)
1. Thuật toán quay lui
Thuật toán quay lui 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 cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.
GIả sử cấu hình cần liệt kê có dạng (x1, x2, ..., x(n)). Khi đó thuật toán quay lui thực hiện qua các bước sau:
1> Xét tất cả cá giá trị x1 có thể nhận, thử cho x1 lần lượt nhận các giá trị đó. Với mỗi giá trị thử gán cho x1 ta sẽ tiến hành bước 2.
2> Xét tất cả cá giá trị x2 có thể nhận, thử cho x2 lần lượt nhận các giá trị đó. Với mỗi giá trị thử gán cho x2 ta sẽ tiến hành các khả năng chọn cho x3... cứ tiếp tục như vậy cho đến bước n
.........
n> Xét tất cả cá giá trị x(n) có thể nhận, thử cho x(n) lần lượt nhận các giá trị đó. Với mỗi giá trị thử gán cho x(n) ta sẽ thông báo cấu hình tìm được (x1, x2, ..., x(n)).
Trên phương diện quy nạp, ta có thể nói rằng thuật toán quay lui liệt kê các cấu hình n phần tử dạng (x1, x2, ..., x(n)) bằng cách thử cho x1 nhận lần lượt các giá trị có thể. Với mỗi giá trị gán cho x1 lại liệt kê cấu hình n-1 phần tử (x2, x3, ..., x)n)).
Mô hình của thuật toán quay lui có thể mô tả như sau:
void try(int i) {
for (v: {tập giá trị V mà có thể gán cho x[i]}) {
x[i] = v;
if (i == n) {
thông báo cấu hình tìm được;
}
else {
mark[v] = true; //Ghi nhận việc x[i] nhận giá trị v nếu cần
try(i + 1);
mark[v] = false; //Bỏ việc ghi nhận x[i] nhận giá trị v nếu cần
}
}
}
Thuật toán quay lui sẽ bắt đầu bằng lời gọi try(1);
2. Liệt kê các dãy nhị phân độ dài n (bài toán 4)
Dãy nhị phân đội dài n được biểu diễn dưới dạng (x1, x2, ..., x(n)). Ta sẽ liệt kê dãy này bằng cách dùng các giá trị {0 , 1} gán cho x(i). Với mỗi giá trị thử gán cho x(i) ta thử lại các giá trị có thể gán cho x(i+1).
Ta có chương trình liệt kê các dãy nhị phân độ dài n bằng thuật toán quay lui như sau:
void try(int i) {
for (int v = 0; v <= 1; ++v) {
x[i] = j;
if (i == n)
print(x);
else
try(i + 1);
}
}
Khi n =3, cây tìm kiếm quay lui sẽ như sau:
(star) Với dãy tam phân, tứ phân, ... n phân thì việc áp dụng cũng chỉ đơn giản là thay tập giá trị V. Với nhị phân V = {0 , 1}, tam phân V = {0 , 1, 2}, .... n phân V = {0 , 1, ..., n}
3. Liệt kê các tập con k phần tử (bài toán 2)
Để liệt kê tập con k phần tử của tập {1, 2, ..., n}, ta có thể đưa về liệt kê các cấu hình (x1, x2, ...., x(k)) với x1 < x2 < .... < x(k).
Ta có nhận xét:
x(k) ≤ n
x(k-1) ≤x(k) - 1 ≤ n -1
....
x(i) ≤ n - k + i
....
x1 ≤ n -k + 1
Từ đó suy ra x(i-1) + 1 ≤ x(i) ≤ n - k + i (1 ≤ i ≤ k), ở đây giả thiết chúng ta có thêm 1 số x0 khi xét i = 1.
Như vậy ta sẽ xét tất cả các cách chọn x1 từ 1 (x0 + 1) đến n - k + 1, với mỗi giá trị đó xét tất cả các lựa chọn x2 từ x1+1 đến n - k + 2, ...., cứ như vậy đến x(k) thì ta có cấu hình cần liệt kê.
Ta có chương trình liệt kê các tập con k phần tử bằng thuật toán quay lui như sau:
void try(int i) {
for (int v = x[i - 1] + 1; v <= n - k + i; ++v) {
x[i] = v;
if (i == k)
print(x);
else
try(i+1);
}
}
4. Liệt kê các chỉnh hợp không lặp chập k (bài toán số 3)
Để liệt kê các chính hợp không lặp chập k của tập {1, 2, ..., n} ta có thể đưa về liệt kê các cấu hình (x1, x2, ...., x(k)) với các x(i) khác nhau từng đôi một.
Như vậy hàm try(i) xét tất cả các khả năng chọn từ 1 đến n mà các giá trị này chưa bị các phần tử đứng trước chọn. Muốn xem phần tử nào chưa được chọn thì chúng ta sử dụng mảng đánh dấu.
Khởi tạo một mảng c1, c2, ..., c(n) kiểu boolean. C(i) cho biết giá trị i có còn tự do hay đã bị chọn rồi.
Ban đầu, tất cả giá trị trong mảng c là TRUE, có nghĩa là đang tự do.
Tại bước chọn các giá trị có thể của x(i), ta chỉ xét những giá trị đang tự do.
Trước khi gọi đệ quy tìm x(i+1) <try(i + 1)>, ta cần đặt giá trị v vừa gán cho x(i) là đã bị chọn, có nghĩa là đặt c(v) = FALSE để các bước tiếp theo try(i+1), try(i+1),... không chọn phải giá trị đó nữa.
Sau khi gọi đệ quy tìm x(i+1) <try(i + 1)>, nghĩa là chúng ta chuẩn bị gán một giá trị khác cho x(i) thì chúng ta đặt lại giá trị v vừa thử thành tự do, có nghĩa là c(v) = TRUE.
Tại bước i = k, ta không cần đánh dấu vì sau đó không còn bước nào nữa cả, việc của chúng ta là in ra cấu hình.
Ta có chương trình liệt kê các dãy nhị phân độ dài n bằng thuật toán quay lui như sau:
void try(int i) {
for (int v = 1; v <= n; ++v) {
if (c[v]) { //giá trị v đang tự do
x[i] = v;
if (i == k) // Nếu đã chọn đến bước thứ k thì chỉ cần in ra
print(x);
else {
c[v] = false; // đánh dấu giá trị v đã được lựa chọn
try(i+1);
c[v] = true; // bỏ đánh dấu, giá trị v trở thành tự do vì x[i] sắp được thử một các chọn khác.
}
}
}
}
5. Liệt kê các hoán vị (bài toán số 1)
Bài toán liệt kê các hoán vị chính là bài toán liệt kê các chỉnh hợp lặp chập k với k = n. Do đó, việc thực hiện không khác gì phần 4. Do k = n nên ta thay điều kiện i == k bằng i ==n là được.
void try(int i) {
for (int v = 1; v <= n; ++v) {
if (c[v]) { //giá trị v đang tự do
x[i] = v;
if (i == n) // Nếu đã chọn đến bước thứ n thì chỉ cần in ra
print(x);
else {
c[v] = false; // đánh dấu giá trị v đã được lựa chọn
try(i+1);
c[v] = true; // bỏ đánh dấu, giá trị v trở thành tự do vì x[i] sắp được thử một các chọn khác.
}
}
}
}
6. Discussion question
Khi nào thì cần ghi nhận việc phần tử thứ i được gán giá trị v, khi nào không?
So sánh thứ tự liệt kê của backtracking và tuần tự (nằm trong 2.1 Exhaustive search (Thuật toán vét cạn)) cho bài toán liệt kê các chỉnh hợp không lặp chập k.
Sự khác nhau cơ bản trong cách sử dụng của cách liệt kê bằng backtracking và tuần tự là gì?
Thay đổi cách cài đặt các chương trình trên để thuật toán dừng khi liệt kê đến một cấu hình định trước.
2.1.3 Kỹ thuật nhánh cận
1. Cơ sở lý thuyết
Bài toán tối ưu
Một trong những bài toán đặt ra trong thực tế là tìm ra một nghiệm thỏa mãn một số điều kiện nào đó, và nghiệm đó là tốt nhất theo mội số chỉ tiêu cụ thể (ví dụ bài tìm min, max). Việc nghiên cứu lời giải các bài toán tối ưu thuộc về lĩnh vực quy hoạch toán học. Tuy nhiên có nhiều trường hợp chúng ta chưa thể xây dựng được một thuật toán nào thực sự hữu hiệu để giải bài toán. Mà tới nay chúng ta vẫn phải dùng mô hình liệt kê toàn bộ các cấu hình để đánh giá và tìm ra cấu hình tốt nhất.
Sự bùng nổ tổ hợp
Mô hình thuật toán quay lui là tìm kiếm trên một cây phân cấp. Giả sử rằng mỗi nút sẽ có k lựa chọn, thì cây n cấp sẽ có n^m lá. Do vậy nếu ta có thao tác thừa trong việc chọn giá trị cho nút thì sẽ phải trả giá rất lớn về chi phí thực thi. Khi đó, một vấn đề đặt ra là trong quá trình liệt kê lời giải chúng ta cần tận dụng những thông tin đã tìm được để loại bỏ sớm những phương án không tối ưu. Kỹ thuật đó gọi là kỹ thuật đánh giá nhánh cận trong tiến trình quay lui.
2. Mô hình kỹ thuật nhánh cận
Dựa trên mô hình thuật toán quay lui, ta xây dựng mô hình như sau:
void init() {
Khởi tạo một cầu hình bất kỳ BEST_CONFIG;
}
void try(int i) {
for (v : {tập giá trị có thể cho x[i]) {
x[i] = v;
if (việc thử còn hy vọng để tìm ra cấu hình tốt hơn BEST_CONFIG) {
if (i == k) { //Nếu i là phần tử cuối cùng trong cấu hình
cập nhật BEST_CONFIG;
}
else {
mark[v] = true; //Ghi nhận việc x[i] nhận giá trị V nếu cần
try(i+1);
mark[v] = false; //Bỏ ghi nhận việc thử cho x[i] nếu cần
}
}
}
}
Kỹ thuật nhánh cận thêm vào cho thuật toán quay lui khả năng đánh giá từng bước. Nếu tại bước thứ i mà việc thử gán giá trị cho x(i) không có hi vọng tìm thấy cấu hình tốt hơn BEST_CONFIG thì thử ngay giá trị khác mà không cần gọi đệ quy bước tiếp hay ghi nhận kết quả. Nghiệm của bài toán sẽ được làm tốt dần, bởi vì khi ta tìm ra một cấu hình mới tốt hơn BEST_CONFIG, ta sẽ không in ra kết quả ngay mà cập nhập BEST_CONFIG bằng cấu hình mới vừa tìm được.
3. Discussion question
Dùng kỹ thuật nhánh cận để giải bài toán người giao hàng. https://www.spoj.com/PTIT/problems/BCTSP/
Dùng kỹ thuật nhánh cận để giải bài toán Knapsack. https://www.spoj.com/problems/KNAPSACK/
Video: https://drive.google.com/drive/folders/1-92wNzSETMXSIDQgaPsei2OrKGBeaUDx?usp=sharing
