Thuật toán quay lui¶
Thuật toán quay lui (backtracking algorithm) là một phương pháp giải quyết vấn đề thông qua tìm kiếm vét cạn. Ý tưởng cốt lõi của nó là bắt đầu từ một trạng thái ban đầu và tìm kiếm vét cạn tất cả các lời giải khả thi. Khi tìm thấy một lời giải đúng, nó sẽ được ghi lại. Quá trình này tiếp tục cho đến khi tìm thấy lời giải hoặc tất cả các lựa chọn khả thi đã được thử mà không tìm thấy lời giải nào.
Thuật toán quay lui thường sử dụng tìm kiếm theo chiều sâu (depth-first search) để duyệt qua không gian lời giải. Trong chương "Cây nhị phân", chúng ta đã đề cập rằng các phép duyệt tiền thứ tự (preorder), trung thứ tự (inorder), và hậu thứ tự (postorder) đều thuộc về tìm kiếm theo chiều sâu. Tiếp theo, chúng ta sẽ xây dựng một bài toán quay lui sử dụng phép duyệt tiền thứ tự để dần hiểu cách thuật toán quay lui hoạt động.
Ví dụ 1
Cho một cây nhị phân, hãy tìm kiếm và ghi lại tất cả các nút có giá trị bằng \(7\), và trả về danh sách các nút này.
Đối với bài toán này, chúng ta thực hiện duyệt tiền thứ tự cây nhị phân và kiểm tra xem giá trị của nút hiện tại có bằng \(7\) hay không. Nếu có, chúng ta thêm nút đó vào danh sách kết quả res. Cài đặt liên quan được thể hiện trong hình và mã nguồn dưới đây:
Thử nghiệm và quay lui¶
Lý do nó được gọi là thuật toán quay lui là vì nó sử dụng các chiến lược "thử nghiệm" và "quay lui" khi tìm kiếm trong không gian lời giải. Khi thuật toán gặp một trạng thái mà nó không thể tiếp tục đi tiếp hoặc không thể tìm thấy lời giải thỏa mãn các ràng buộc, nó sẽ hoàn tác lựa chọn trước đó, quay trở lại trạng thái trước đó, và thử các lựa chọn khả thi khác.
Đối với Ví dụ 1, việc truy cập từng nút đại diện cho một "thử nghiệm", trong khi việc bỏ qua nút lá hoặc câu lệnh return đưa phép duyệt trở lại nút cha đại diện cho một "quay lui".
Đáng chú ý là quay lui không chỉ giới hạn ở việc hàm trả về. Để minh họa điều này, chúng ta hãy mở rộng Ví dụ 1 một chút.
Ví dụ 2
Trong một cây nhị phân, hãy tìm tất cả các nút có giá trị bằng \(7\), và trả về đường đi từ nút gốc đến các nút này.
Dựa trên mã nguồn của Ví dụ 1, chúng ta cần sử dụng một danh sách path để ghi lại đường đi của các nút đã truy cập. Khi chúng ta đến một nút có giá trị bằng \(7\), chúng ta sao chép path và thêm nó vào danh sách kết quả res. Sau khi quá trình duyệt hoàn tất, res sẽ chứa tất cả các lời giải. Mã nguồn như sau:
Trong mỗi "thử nghiệm", chúng ta ghi lại đường đi bằng cách thêm nút hiện tại vào path; trước khi "quay lui", chúng ta cần loại bỏ nút đó khỏi path, để khôi phục trạng thái trước thử nghiệm này.
Quan sát quá trình được hiển thị trong hình dưới đây, chúng ta có thể hiểu thử nghiệm và quay lui như là "tiến hành" và "hoàn tác", hai thao tác trái ngược nhau.
Cắt tỉa¶
Các bài toán quay lui phức tạp thường chứa một hoặc nhiều ràng buộc. Các ràng buộc thông thường có thể được sử dụng để "cắt tỉa".
Ví dụ 3
Trong một cây nhị phân, hãy tìm tất cả các nút có giá trị bằng \(7\) và trả về các đường đi từ nút gốc đến các nút này, nhưng yêu cầu các đường đi đó không được chứa nút có giá trị bằng \(3\).
Để đáp ứng ràng buộc trên, ** chúng ta cần thêm thao tác cắt tỉa**: trong quá trình tìm kiếm, nếu gặp nút có giá trị bằng \(3\), chúng ta sẽ quay lại sớm và không tiếp tục tìm kiếm nữa. Mã nguồn như sau:
"Cắt tỉa" là một thuật ngữ rất trực quan. Như thể hiện trong hình dưới đây, trong quá trình tìm kiếm, chúng ta "cắt tỉa" các nhánh tìm kiếm không đáp ứng ràng buộc, tránh được nhiều thử nghiệm vô nghĩa và từ đó cải thiện hiệu suất tìm kiếm.
Khung mã nguồn¶
Tiếp theo, chúng ta sẽ cố gắng trích xuất một khung mã nguồn tổng quát tập trung vào "thử nghiệm, quay lui và cắt tỉa" của thuật toán quay lui nhằm nâng cao tính tổng quát của mã nguồn.
Trong khung mã nguồn dưới đây, state đại diện cho trạng thái hiện tại của bài toán, và choices đại diện cho các lựa chọn khả thi trong trạng thái hiện tại:
def backtrack(state: State, choices: list[choice], res: list[state]):
"""Khung thuật toán quay lui"""
# Kiểm tra xem có phải là lời giải không
if is_solution(state):
# Ghi lại lời giải
record_solution(state, res)
# Ngừng tìm kiếm
return
# Duyệt qua tất cả các lựa chọn
for choice in choices:
# Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if is_valid(state, choice):
# Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
make_choice(state, choice)
backtrack(state, choices, res)
# Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undo_choice(state, choice)
/* Khung thuật toán quay lui */
void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) {
// Kiểm tra xem có phải là lời giải không
if (isSolution(state)) {
// Ghi lại lời giải
recordSolution(state, res);
// Ngừng tìm kiếm
return;
}
// Duyệt qua tất cả các lựa chọn
for (Choice choice : choices) {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if (isValid(state, choice)) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
makeChoice(state, choice);
backtrack(state, choices, res);
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undoChoice(state, choice);
}
}
}
/* Khung thuật toán quay lui */
void backtrack(State state, List<Choice> choices, List<State> res) {
// Kiểm tra xem có phải là lời giải không
if (isSolution(state)) {
// Ghi lại lời giải
recordSolution(state, res);
// Ngừng tìm kiếm
return;
}
// Duyệt qua tất cả các lựa chọn
for (Choice choice : choices) {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if (isValid(state, choice)) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
makeChoice(state, choice);
backtrack(state, choices, res);
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undoChoice(state, choice);
}
}
}
/* Khung thuật toán quay lui */
void Backtrack(State state, List<Choice> choices, List<State> res) {
// Kiểm tra xem có phải là lời giải không
if (IsSolution(state)) {
// Ghi lại lời giải
RecordSolution(state, res);
// Ngừng tìm kiếm
return;
}
// Duyệt qua tất cả các lựa chọn
foreach (Choice choice in choices) {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if (IsValid(state, choice)) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
MakeChoice(state, choice);
Backtrack(state, choices, res);
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
UndoChoice(state, choice);
}
}
}
/* Khung thuật toán quay lui */
func backtrack(state *State, choices []Choice, res *[]State) {
// Kiểm tra xem có phải là lời giải không
if isSolution(state) {
// Ghi lại lời giải
recordSolution(state, res)
// Ngừng tìm kiếm
return
}
// Duyệt qua tất cả các lựa chọn
for _, choice := range choices {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if isValid(state, choice) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
makeChoice(state, choice)
backtrack(state, choices, res)
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undoChoice(state, choice)
}
}
}
/* Khung thuật toán quay lui */
func backtrack(state: inout State, choices: [Choice], res: inout [State]) {
// Kiểm tra xem có phải là lời giải không
if isSolution(state: state) {
// Ghi lại lời giải
recordSolution(state: state, res: &res)
// Ngừng tìm kiếm
return
}
// Duyệt qua tất cả các lựa chọn
for choice in choices {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if isValid(state: state, choice: choice) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
makeChoice(state: &state, choice: choice)
backtrack(state: &state, choices: choices, res: &res)
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undoChoice(state: &state, choice: choice)
}
}
}
/* Khung thuật toán quay lui */
function backtrack(state, choices, res) {
// Kiểm tra xem có phải là lời giải không
if (isSolution(state)) {
// Ghi lại lời giải
recordSolution(state, res);
// Ngừng tìm kiếm
return;
}
// Duyệt qua tất cả các lựa chọn
for (let choice of choices) {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if (isValid(state, choice)) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
makeChoice(state, choice);
backtrack(state, choices, res);
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undoChoice(state, choice);
}
}
}
/* Khung thuật toán quay lui */
function backtrack(state: State, choices: Choice[], res: State[]): void {
// Kiểm tra xem có phải là lời giải không
if (isSolution(state)) {
// Ghi lại lời giải
recordSolution(state, res);
// Ngừng tìm kiếm
return;
}
// Duyệt qua tất cả các lựa chọn
for (let choice of choices) {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if (isValid(state, choice)) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
makeChoice(state, choice);
backtrack(state, choices, res);
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undoChoice(state, choice);
}
}
}
/* Khung thuật toán quay lui */
void backtrack(State state, List<Choice> choices, List<State> res) {
// Kiểm tra xem có phải là lời giải không
if (isSolution(state)) {
// Ghi lại lời giải
recordSolution(state, res);
// Ngừng tìm kiếm
return;
}
// Duyệt qua tất cả các lựa chọn
for (Choice choice in choices) {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if (isValid(state, choice)) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
makeChoice(state, choice);
backtrack(state, choices, res);
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undoChoice(state, choice);
}
}
}
/* Khung thuật toán quay lui */
fn backtrack(state: &mut State, choices: &Vec<Choice>, res: &mut Vec<State>) {
// Kiểm tra xem có phải là lời giải không
if is_solution(state) {
// Ghi lại lời giải
record_solution(state, res);
// Ngừng tìm kiếm
return;
}
// Duyệt qua tất cả các lựa chọn
for choice in choices {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if is_valid(state, choice) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
make_choice(state, choice);
backtrack(state, choices, res);
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undo_choice(state, choice);
}
}
}
/* Khung thuật toán quay lui */
void backtrack(State *state, Choice *choices, int numChoices, State *res, int numRes) {
// Kiểm tra xem có phải là lời giải không
if (isSolution(state)) {
// Ghi lại lời giải
recordSolution(state, res, numRes);
// Ngừng tìm kiếm
return;
}
// Duyệt qua tất cả các lựa chọn
for (int i = 0; i < numChoices; i++) {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if (isValid(state, &choices[i])) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
makeChoice(state, &choices[i]);
backtrack(state, choices, numChoices, res, numRes);
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undoChoice(state, &choices[i]);
}
}
}
/* Khung thuật toán quay lui */
fun backtrack(state: State?, choices: List<Choice?>, res: List<State?>?) {
// Kiểm tra xem có phải là lời giải không
if (isSolution(state)) {
// Ghi lại lời giải
recordSolution(state, res)
// Ngừng tìm kiếm
return
}
// Duyệt qua tất cả các lựa chọn
for (choice in choices) {
// Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if (isValid(state, choice)) {
// Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
makeChoice(state, choice)
backtrack(state, choices, res)
// Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undoChoice(state, choice)
}
}
}
### Khung thuật toán quay lui ###
def backtrack(state, choices, res)
# Kiểm tra xem có phải là lời giải không
if is_solution?(state)
# Ghi lại lời giải
record_solution(state, res)
return
end
# Duyệt qua tất cả các lựa chọn
for choice in choices
# Cắt tỉa: kiểm tra xem lựa chọn có hợp lệ không
if is_valid?(state, choice)
# Thử nghiệm: thực hiện lựa chọn và cập nhật trạng thái
make_choice(state, choice)
backtrack(state, choices, res)
# Quay lui: hoàn tác lựa chọn và khôi phục về trạng thái trước đó
undo_choice(state, choice)
end
end
end
Next, we solve Example 3 based on the framework code. The state state is the node traversal path, the choices choices are the left and right child nodes of the current node, and the result res is a list of paths:
Tiếp theo, chúng ta giải Ví dụ 3 dựa trên khung mã nguồn. Trạng thái state là đường đi duyệt qua các nút, lựa chọn choices là các nút con bên trái và bên phải của nút hiện tại, và kết quả res là danh sách các đường đi:
Theo yêu cầu của đề bài, chúng ta nên tiếp tục tìm kiếm sau khi tìm thấy một nút có giá trị bằng \(7\). Do đó, chúng ta cần loại bỏ câu lệnh return sau khi ghi lại lời giải. Hình dưới đây so sánh quá trình tìm kiếm có và không có câu lệnh return.
So với mã nguồn dựa trên phép duyệt tiền thứ tự, mã nguồn dựa trên khung thuật toán quay lui trông dài dòng hơn nhưng lại tổng quát hơn. Trên thực tế, nhiều bài toán quay lui có thể được giải quyết trong khung này. Chúng ta chỉ cần xác định state và choices cho bài toán cụ thể và hiện thực hóa từng phương thức trong khung.
Các thuật ngữ thường gặp¶
Để phân tích các bài toán thuật toán một cách rõ ràng hơn, chúng ta tóm tắt ý nghĩa của các thuật ngữ thường gặp dùng trong thuật toán quay lui và cung cấp các ví dụ tương ứng từ Ví dụ 3, như được hiển thị trong bảng dưới đây.
Bảng
| Thuật ngữ | Định nghĩa | Ví dụ 3 |
|---|---|---|
| Lời giải (solution) | Lời giải là một đáp án thỏa mãn các điều kiện cụ thể của bài toán; có thể có một hoặc nhiều lời giải | Tất cả các đường đi từ nút gốc đến các nút có giá trị bằng \(7\) thỏa mãn ràng buộc |
| Ràng buộc (constraint) | Ràng buộc là một điều kiện trong bài toán nhằm giới hạn tính khả thi của lời giải, thường được sử dụng để cắt tỉa | Các đường đi không chứa nút có giá trị bằng \(3\) |
| Trạng thái (state) | Trạng thái đại diện cho tình huống của bài toán tại một thời điểm nhất định, bao gồm các lựa chọn đã được thực hiện | Đường đi của các nút hiện đang được truy cập, tức là danh sách nút path |
| Thử nghiệm (attempt) | Thử nghiệm là quá trình khám phá không gian lời giải theo các lựa chọn có sẵn, bao gồm việc đưa ra lựa chọn, cập nhật trạng thái và kiểm tra xem có phải là lời giải không | Duyệt đệ quy các nút con bên trái (phải), thêm các nút vào path, kiểm tra xem giá trị của nút có bằng \(7\) hay không |
| Quay lui (backtracking) | Quay lui đề cập đến việc hoàn tác các lựa chọn trước đó và quay lại trạng thái trước đó khi gặp một trạng thái không thỏa mãn các ràng buộc | Dừng tìm kiếm khi đi qua hết các nút lá, kết thúc lượt truy cập nút, hoặc khi gặp nút có giá trị bằng \(3\); hàm trả về |
| Cắt tỉa (pruning) | Cắt tỉa là phương pháp tránh các đường đi tìm kiếm vô nghĩa dựa trên các đặc điểm và ràng buộc của bài toán, giúp cải thiện hiệu suất tìm kiếm | Khi gặp nút có giá trị bằng \(3\), không tiếp tục tìm kiếm |
Tip
Các khái niệm về bài toán, lời giải, trạng thái, v.v., là phổ biến và xuất hiện trong chia để trị, quay lui, quy hoạch động, thuật toán tham lam và các thuật toán khác.
Ưu điểm và hạn chế¶
Thuật toán quay lui về mặt bản chất là một thuật toán tìm kiếm theo chiều sâu thử nghiệm tất cả các lời giải khả thi cho đến khi tìm thấy lời giải thỏa mãn các điều kiện. Ưu điểm của phương pháp này là nó có thể tìm thấy tất cả các lời giải khả thi, và với các thao tác cắt tỉa hợp lý, nó đạt được hiệu suất cao.
Tuy nhiên, khi đối mặt với các bài toán có quy mô lớn hoặc phức tạp, hiệu suất chạy của thuật toán quay lui có thể không thể chấp nhận được.
- Thời gian: Thuật toán quay lui thường cần duyệt qua mọi khả năng trong không gian trạng thái, và độ phức tạp thời gian có thể đạt đến mức hàm mũ hoặc giai thừa.
- Không gian: Trong quá trình gọi đệ quy, trạng thái hiện tại cần được lưu lại (chẳng hạn như đường đi, các biến phụ trợ dùng cho việc cắt tỉa, v.v.), và khi độ sâu đệ quy lớn, nhu cầu không gian bộ nhớ có thể trở nên rất lớn.
Mặc dù vậy, thuật toán quay lui vẫn là giải pháp tốt nhất cho một số bài toán tìm kiếm và bài toán thỏa mãn ràng buộc nhất định. Đối với những bài toán này, vì chúng ta không thể dự đoán lựa chọn nào sẽ tạo ra lời giải hợp lệ, chúng ta bắt buộc phải duyệt qua tất cả các lựa chọn khả thi. Trong trường hợp này, chìa khóa là cách tối ưu hóa hiệu suất. Có hai phương pháp tối ưu hóa hiệu suất phổ biến.
- Cắt tỉa: Tránh tìm kiếm các đường đi chắc chắn không tạo ra lời giải, từ đó tiết kiệm thời gian và không gian.
- Tìm kiếm heuristic (heuristic search): Đưa vào các chiến lược hoặc giá trị ước lượng nhất định trong quá trình tìm kiếm để ưu tiên tìm kiếm các đường đi có nhiều khả năng tạo ra lời giải hợp lệ nhất.
Các ví dụ quay lui điển hình¶
Thuật toán quay lui có thể được sử dụng để giải quyết nhiều bài toán tìm kiếm, bài toán thỏa mãn ràng buộc và bài toán tối ưu hóa tổ hợp.
Bài toán tìm kiếm: Mục tiêu của các bài toán này là tìm các lời giải thỏa mãn điều kiện cụ thể.
- Bài toán hoán vị: Cho một tập hợp, tìm tất cả các hoán vị và tổ hợp có thể có.
- Bài toán tổng tập con: Cho một tập hợp và một tổng mục tiêu, tìm tất cả các tập con trong tập hợp có tổng các phần tử bằng tổng mục tiêu.
- Tháp Hà Nội: Cho ba cọc và một loạt các đĩa có kích thước khác nhau, di chuyển tất cả các đĩa từ cọc này sang cọc khác, mỗi lần chỉ di chuyển một đĩa và không bao giờ đặt đĩa lớn hơn lên trên đĩa nhỏ hơn.
Bài toán thỏa mãn ràng buộc: Mục tiêu của các bài toán này là tìm các lời giải thỏa mãn tất cả các ràng buộc.
- N-Queens (Bài toán N quân hậu): Đặt \(n\) quân hậu trên một bàn cờ kích thước \(n \times n\) sao cho chúng không tấn công lẫn nhau.
- Sudoku: Điền các số từ \(1\) đến \(9\) vào một lưới \(9 \times 9\) sao cho mỗi hàng, mỗi cột và mỗi lưới con \(3 \times 3\) không chứa các chữ số trùng lặp.
- Tô màu đồ thị: Cho một đồ thị vô hướng, tô màu mỗi đỉnh với số lượng màu tối thiểu sao cho các đỉnh kề nhau có màu khác nhau.
Bài toán tối ưu hóa tổ hợp: Mục tiêu của các bài toán này là tìm một lời giải tối ưu thỏa mãn các điều kiện nhất định trong không gian tổ hợp.
- Balo 0-1 (0-1 Knapsack): Cho một tập hợp các vật phẩm và một chiếc balo, mỗi vật phẩm có giá trị và trọng lượng. Dưới ràng buộc về sức chứa của balo, hãy chọn các vật phẩm sao cho tổng giá trị là lớn nhất.
- Bài toán người bán hàng du lịch (Traveling Salesman Problem): Xuất phát từ một điểm trong đồ thị, đi qua tất cả các điểm khác đúng một lần và quay trở lại điểm xuất phát, tìm đường đi ngắn nhất.
- Đồ thị con đầy đủ cực đại (Maximum Clique): Cho một đồ thị vô hướng, tìm đồ thị con đầy đủ lớn nhất, nghĩa là đồ thị con mà bất kỳ hai đỉnh nào cũng được nối với nhau bằng một cạnh.
Lưu ý rằng đối với nhiều bài toán tối ưu hóa tổ hợp, quay lui không phải là giải pháp tối ưu.
- Bài toán Balo 0-1 thường được giải quyết bằng quy hoạch động để đạt được hiệu suất thời gian cao hơn.
- Bài toán người bán hàng du lịch là một bài toán NP-khó nổi tiếng; các giải pháp phổ biến bao gồm thuật toán di truyền và thuật toán bầy kiến.
- Bài toán đồ thị con đầy đủ cực đại là một bài toán cổ điển trong lý thuyết đồ thị và có thể được giải quyết bằng các thuật toán heuristic như thuật toán tham lam.