PDA

View Full Version : Thuật toán quay lui và các bài toán ứng dụng



emsi_epu_it
04-10-2012, 04:48 PM
Trong quá trình giải quyết một số bài toán, nảy sinh tình huống là có nhiều cách khác nhau để giải quyết cùng một vấn đề, nhưng không có cách nào dẫn tới giải pháp. Sau khi thử cách này không được ta quay sang thử cách tiếp theo để tìm lời giải . Tuy nhiên cần phải đảm bảo rằng, việc quay trở lại là có thể và ta có thể thử tất cả các khả năng. Kĩ thuật này được gọi là quay lui.
Thuật toán quay lui cho phép ta thử một cách có hệ thống tất cả các đường đi từ một điểm xuất phát cho trước sau khi một vài trong số những đường đi trước đó chẳng dẫn đi đến đâu cả. Sử dụng thuật toán quay lui ta luôn luôn có thể quay trở lại một vị trí nơi cung cấp các khả năng khác nhau để giải quyết bài toán thành công .
Mặt khác trong thực tế, ta thường gặp các bài toán với yêu cầu tìm kiếm tất cả các phương án, hay liệt kê mọi cấu hình thoả mãn một điều kiện nào đó như : liệt kê dãy nhị phân có độ dài n, liệt kê các hoán vị của n phần tử,liệt kê các cách sắp xếp n quân hậu trên bàn cờ n x n sao cho các quân hậu không ăn được nhau, . Nếu không dùng thuật toán quay lui thì chúng ta sẽ gặp rất nhiều khó khăn trong việc giải quyết những bài toán như trên.
Hơn thế nữa chương trình cài đặt theo phương pháp quay lui vừa dễ cài đặt, ngắn gọn, chương trình dễ hiểu, sáng sủa. Cùng với tốc độ phát triển phần cứng hiện nay thì phương pháp quay lui sẽ ngày càng được được sử dụng phổ biến.
Do những ưu điểm và tầm quan trọng của nó nên hôm nay mình sẽ đưa các bạn đên với:
“ THUẬT TOÁN QUAY LUI VÀ CÁC BÀI TOÁN ỨNG DỤNG”.

Thuật toán quay lùi (backtracking)
1.Mở đầu
• Sự cần thiết của thuật toán
Có một số bài toán chỉ rõ: trong một tập các đối tượng cho trước thì có bao nhiêu đối tượng thỏa mãn những điều kiện nhất đinh.
Bài toán đó gọi là bài toán đếm.
Trong lớp các bài toán đếm có những bài yêu cầu chỉ rõ nhưng cấu hình tím được thỏa mãn những điều kiện cho trước.
Bài toán đưa ra các cấu hình trên gọi là bài toán liệt kê.
• Để giải bài toán liệt kê thì ta cần phải xác định được một thuật toán có thế xây dựng được lần lượt tất cả các cấu hình thỏa mãn điều kiện
• Có nhiều phương pháp liệt kê,nhưng các phương pháp này luôn phải thỏa mãn hai điều kiện:
+ Không được lặp lại một cấu hình nào
+ Không được bỏ sốt một cấu hình nào
2.Giới thiệu thuật toán
• Có rất nhiều thuật toán dung để giải bài toán liệt kê,trong đó thuật toán quay lùi là một thuật toán phổ biến và hay được dung nhất.
• Thuật toán quay lùi 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
• Định nghĩa thuật toán quay lùi:
Quay lui (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.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.

Giả sử cấu hình cần liệt kê có dạng x[1..n], khi đó thuật toán quay lùi được thực hiện qua các bước:
1. Xét tất cả các giá trị x[1] có thể nhận,thử cho x[1] nhận lần lượt các giá trị đó.Và với mỗi giá trị thử gán cho x[1] ta sẽ .
2. Xét tất cả các giá trị x[2] có thể nhận,lại thử cho x[2] nhận lần lượt các giá trị đó.Và cứ như vậy với x[2],x[3]…
3. Xét tất cả các giá trị x[n] có thể nhận,lại thử cho x[n] nhận lần lượt các giá trị đó.Rồi ta đưa ra cấu hình tìm được là : { x[1],x[2],x[3],…,x[n] }.
• .Kết luận:
Trên phương diện quy nạp ta có thể thấy,thuật toán quay lùi liệt kế các cấu hình n phần tử dạng x[1..n] bằng cách thử cho x[1] nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gán cho x[2] thì bài toán lại trở thành liệt kê tiếp cấu hình của n-1 phần tử x[2..n], và cứ thế cho đến khi liệt kê cấu hình n-n+1 phần tử x[n] ta có được tất cả các cấu hình thỏa màn điều kiện

3.Mô hình thuật toán
void try(int i)
{ Thủ tục chọn a[i]
int j,k;
for ( Tạo các giá trị j có thể gán cho a[i] )
{
Thử cho ( a[i]=j ;)
if(i==( Chỉ số cuối cùng trong cấu hình))
{
Khi đó in ra cấu hinh tìm được
}
else
{
(Ghi nhận việc cho x[i] nhận cấu hình nếu cần )
try(i+1); Gọi đệ quy để chọn tiếp x[i+1]
(Bỏ việc ghi nhận việc thử x[i] nếu cần )
}
}
}
• . Thuật toán quay lùi sẽ được bắt đầu bàng lời gọi try(0) trong hàm main.

5.Mô tả thuật toán
Mô tả thuật toán quay lùi bằng cây quay lùi : Hình 1

143

Mô tả bằng đệ quy. Hình 2.


142