Thuật toán Gready Seach và toán biến đổi
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (137.24 KB, 2 trang )
Thuật toán Gready Seach và các bài toán biến đổi
Hoàng Anh Vũ
Chào các bạn!
Trong số báo tháng 10/2003, bạn Hoài Nam đã viết về các bài toán biến đổi và một
phương pháp để giải chúng. Trong bài viết này, tôi xin trình bày một phương pháp giải
khác để giải các bài toán đó, và một lớp các bài toán khác nữa.
Như các bạn đã biết, có 2 thuật toán tìm kiếm cơ bản là BFS và DFS. Từ 2 thuật toán đó,
người ta cải tiến để tối ưu chúng và tạo ra các thuật toán tốt hơn, ví dụ: leo đồi, A*, Gready
Search (tham lam- GS) .v.v. Sau đây tôi sẽ trình bày thuật toán GS, một thuật toán mà theo
tôi chạy rất tốt về mặt thời gian.
Khái niệm:
Hueristics là các dấu hiệu đặc trưng của bài toán cho phép nhanh chónh xác định lời giải.
Tôi chí trình bày với các bạn một hàm heuristics tiêu biểu đó là hàm theo giá trị Manhattan.
Khoảng cách Manhattan: hiểu một cách nôm na đó là tổng các khoảng cách theo chiều dọc
+ chiều ngang của mỗi ô số (nằm không đúng vị trí, hoặc đúng vị trí tùy vào quy ước của
người lập trình) so với trạng thái đích.
QUEUE: hàng đợi, hoạt động theo nguyên tắc FIFO(First In First Out).
Tôi trình bày thuật toán theo kiểu khử đệ quy:
Thuật toán:
*Từ thuật toán trên ta thấy, GS chỉ khác BFS ở sắp xếp toàn bộ mà thôi.
Dưới đây là một số ví dụ:
Ví dụ 1: (ví dụ của bạn Hoài Nam)Tôi xin nhắc lại để các bạn dễ theo dõi.
1 lưới đèn N*N bóng, mỗi bóng có 2 trạng thái: sang (1) và tắt (0). Mỗi hàng(cột) có 1
công tắc. Khi ấn sẽ thay đổI trạng thái của các bóng trên hàng (cột) đó. (0->1 và 1-> 0).
Nhiệm vụ là qua một số lần biến đổi, hãy đưa từ trạng thái nguồn về trạng thái đích.
Ví dụ:
Giải: Hàm Manhattan M[2*N] trong bài này là số các ô khác nhau giữa A và B. Hàm này
có 2*N giá trị, bằng tổng số hàng và số cột của ĂB).
For(I=1;I<=n;I++)
For(j=1;j<=n;j++){
If(A[I][j]!=B[I][j]) M[I]++; //theo hàng
If(A[j][I]!=B[j][I] ) M[N+I]++; //theo cột
}
Ta sắp xếp lại dãy M. Ta chỉ cần tìm giá trị lớn nhất của dãy M mà thôi, và lưu lại chỉ số
của nó.
For(I=2;I<=2*n;I++)
If(M[I]>M[1]){
Chiso=I; tam=M[I];M[I]=M[1];M[1]=tam;
}
Bây giờ, ta bật công tấc ở hàng chiso (hoặc cột chiso-N nếu chiso >N). Sau đó, ta cập nhập
lại dãy M. Thuật toán sẽ dừng khi M={0}.
Nhận xét: Thuật toán GS sẽ không cho ra lời giải tối ưu.
Ví dụ 2: Bài toán chuột tìm đường trong mê cung.
Cho một mê cung M*N, trong đó có vật cản. Từ một vị trí của chuột (x0,y0) cho trước, hãy
xác định một đường đi đến điểm (x1,y1).
Giải: Rõ ràng, để tìm lời giải tối ưu cho bài toán này, ta đã có thuật toán BFS. Nhưng đây
là thuật toán không khả thi vì thời gian chạy khá lâu. Trong trường hợp xấu nhất thì GS
cũng chính là BFS.
Hàm Manhattan trong bài toán này là: M[x,y]=abs[x1-x]+abs[y1-y], với x,y là vị trí hiện
tại của chuột. Ta dùng hàng đợi Queue để lưu trữ các vị trí có thể đến của chuột và cập
nhập lại tại mỗi bước theo thuật toán GS. Ta sắp xếp hàng đợi theo chiều tăng dần của M,
và cập nhập hàng đợi này sau mỗi bước. Nhớ là ta phải đánh dấu các điểm đã đến để tránh
lặp lại.
Tôi xin kết thúc bài viết của mình ở đây. GS không tối ưu như A*, nhưng vì khối lượng
tính toán ít hơn nên chạy nhanh hơn. Ví dụ 2 ở trên, tôi đã thử cài đặt đến 7 thuật toán và
đo thời gian. Tôi thấy GS chạy nhanh nhất nên giới thiệu với các bạn. Bài này chính là 1
phần của cuộc thi MicroMouse sắp diễn ra. Nếu bạn nào cần hiểu rõ hơn, hay cần source
code, xin gởi mail cho tôi ở địa chỉ: Bạn cũng có thể dùng thuật
toán này để viết một vài trò chơi đơn giản như 8-puzzles.v.v. Qua tạp chí, hi vọng được
học hỏi cùng bạn bè cả nước. Chào.
