Quay lui (khoa há»c máy tÃnh)
Bách khoa toà n thư mở Wikipedia
Quay lui (tiếng Anh: backtracking) là má»™t chiến lược tìm kiếm lá»i giải cho các bà i toán thá»a mãn rà ng buá»™c. NgÆ°á»i đầu tiên Ä‘á» ra thuáºt ngữ nà y (backtrack) là nhà toán há»c ngÆ°á»i Mỹ D. H. Lehmer và o những năm 1950.
Mục lục[giấu] |
[sá»a] Giải thÃch
Các bà i toán thá»a mãn rà ng buá»™c là các bà i toán có má»™t lá»i giải đầy đủ, trong đó thứ tá»± của các phần tá» không quan trá»ng. Các bà i toán nà y bao gồm má»™t táºp các biến mà má»—i biến cần được gán má»™t giá trị tùy theo các rà ng buá»™c cụ thể của bà i toán. Việc quay lui là để thá» tất cả các tổ hợp để tìm được má»™t lá»i giải. Thế mạnh của phÆ°Æ¡ng pháp nà y là nhiá»u cà i đặt tránh được việc phải thá» nhiá»u tổ hợp chÆ°a hoà n chỉnh, và nhỠđó giảm thá»i gian chạy.
Phương pháp quay lui có quan hệ chặt chẽ với tìm kiếm tổ hợp
[sá»a] Cà i đặt
Vá» bản chất, tÆ° tưởng của phÆ°Æ¡ng pháp 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 hợp các lá»i giải. Trong quá trình tìm kiếm, nếu ta 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 nÆ¡i có các hÆ°á»›ng khác và thá» hÆ°á»›ng lá»±a chá»n tiếp theo. Khi đã thá» hết các lá»±a chá»n xuất phát từ Ä‘iểm lá»±a chá»n đó, ta quay lại Ä‘iểm lá»±a chá»n trÆ°á»›c đó và thá» hÆ°á»›ng lá»±a chá»n tiếp theo tại đó. Quá trình tìm kiếm thất bại khi không còn Ä‘iểm lá»±a chá»n nà o nữa.
Quy trình đó thÆ°á»ng được cà i đặt bằng má»™t hà m đệ quy mà trong đó má»—i thể hiện của hà m lấy thêm má»™t biến và lần lượt gán tất cả các giá trị có thể cho biến đó, vá»›i má»—i lần gán trị lại gá»i chuá»—i đệ quy tiếp theo để thá» các biến tiếp theo. Chiến lược quay lui tÆ°Æ¡ng tá»± vá»›i tìm kiếm theo Ä‘á»™ sâu nhÆ°ng sá» dụng Ãt không gian bá»™ nhá»› hÆ¡n, nó chỉ lÆ°u giữ trạng thái của má»™t lá»i giải hiện tại và cáºp nháºt nó.
Äể tăng tốc quá trình tìm kiếm, khi má»™t giá trị được chá»n, trÆ°á»›c khi thá»±c hiện lá»i gá»i đệ quy, thuáºt toán thÆ°á»ng xóa bá» giá trị đó khá»i miá»n xác định của các biến có mâu thuẫn chÆ°a được gán (kiểm tra tiến - forward checking) và kiểm tra tất cả các hằng số để tìm các giá trị khác đã bị loại trừ bởi giá trị vừa được gán (lan truyá»n rà ng buá»™c - constraint propagation).
[sá»a] Heuristic
NgÆ°á»i ta thÆ°á»ng sá» dụng má»™t số phÆ°Æ¡ng pháp heuristic để tăng tốc cho quá trình quay lui. Do các biến có thể được xá» lý theo thứ tá»± bất kỳ, việc thá» các biến bị rà ng buá»™c chặt nhất (nghÄ©a là các biến có Ãt lá»±a chá»n vá» giá trị nhất) thÆ°á»ng có hiệu quả do nó tỉa cây tìm kiếm từ sá»›m (cá»±c đại hóa ảnh hưởng của lá»±a chá»n sá»›m hiện hà nh).
Các cà i đặt quay lui phức tạp thÆ°á»ng sá» dụng má»™t hà m biên, hà m nà y kiểm tra xem từ lá»i giản chÆ°a đầy đủ hiện tại có thể thu được má»™t lá»i giải hay không, nghÄ©a là nếu Ä‘i tiếp theo hÆ°á»›ng hiện tại thì liệu có Ãch hay không. NhỠđó, má»™t kiểm tra biên phát hiện ra các lá»i giải dở dang chắc chắn thất bại có thể nâng cao hiệu quả của tìm kiếm. Do hà m nà y hay được chạy, có thể tại má»—i bÆ°á»›c, nên chi phà tÃnh toán các biên cần tối hiểu, nếu không, hiệu quả toà n cục của thuáºt toán sẽ không được cải tiến. Các hà m kiểm tra biên được tạo theo kiểu gần nhÆ° các hà m heuristic khác: ná»›i lá»ng má»™t số Ä‘iá»u kiện của bà i toán.
[sá»a] Và dụ
Sá» dụng chiến lược 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.
[sá»a] PhÆ°Æ¡ng pháp
Giả thiết cấu hình cần liệt kê có dạng (x1,x2,...,xn). Khi đó thuáºt toán quay lui được thá»±c hiện qua các bÆ°á»›c sau:
- 1) Xét tất cả các giá trị x1 có thể nháºn, thá» cho x1 nháºn lần lượt các giá trị đó. Vá»›i má»—i giá trị thá» cho x1 ta sẽ:
- 2) Xét tất cả các giá trị x2 có thể nháºn, lại thá» cho x2 nháºn lần lượt các giá trị đó. Vá»›i má»—i giá trị thá» gán cho x2 lại xét tiếp các khả năng chá»n x3 ... cứ tiếp tục nhÆ° váºy đến bÆ°á»›c:
- n) Xét tất cả các giá trị xn có thể nháºn, thá» cho xn nháºn lần lượt các giá trị đó, thông báo cấu hình tìm được (x1,x2,...,xn).
[sá»a] Mô tả
Thuáºt toán quay lui có thể được mô tả bằng Ä‘oạn mã giả (pseudocode) sau:
{Thủ tục nà y thá» cho xi nháºn lần lượt các giá trị mà nó có thể nháºn}
procedure Try(i: Integer);
begin
for (má»i giá trị có thể gán cho xi) do
begin
<Thá» cho xi := V>;
if (xi là phần tỠcuối cùng trong cấu hình) then
<Thông báo cấu hình tìm được>
else
begin
<Ghi nháºn việc cho xi nháºn giá trị V (Nếu cần)>;
Try(i + 1); {Gá»i đệ qui để chá»n tiếp xi + 1}
<Nếu cần, bá» ghi nháºn việc thá» xi := V, để thá» giá trị khác>;
end;
end;
end;
(Thuáºt toán quay lui sẽ bắt đầu bằng lá»i gá»i Try(1);
)
Ta có thể trình bà y quá trình tìm kiếm lá»i giải quả thuáºt toán quay lui bằng cây sau:
[sá»a] Xem thêm
Tiếng Anh: