Thuật Toán Và Thuật Giải 10

Hình : h’ đánh giá cao h Đến đây chúng ta đã kết thúc việc bàn luận về thuật giải A*, một thuật giải linh động, tổng quát, trong đó hàm chứa cả tìm kiếm chiều sâu, tìm kiếm chiều rộng và những nguyên lý Heuristic khác. Chính vì thế mà người ta thường nói, A* chính là thuật giải tiêu biểu cho Heuristic.
Nội dung trích xuất từ tài liệu:
Thuật Toán Và Thuật Giải 10 Hình : h’ đánh giá cao hĐến đây chúng ta đã kết thúc việc bàn luận về thuật giải A*, một thuật giải linh động,tổng quát, trong đó hàm chứa cả tìm kiếm chiều sâu, tìm kiếm chiều rộng và nhữngnguyên lý Heuristic khác. Chính vì thế mà người ta thường nói, A* chính là thuật giảitiêu biểu cho Heuristic.A* rất linh động nhưng vẫn gặp một khuyết điểm cơ bản – giống như chiến lược tìmkiếm chiều rộng – đó là tốn khá nhiều bộ nhớ để lưu lại những trạng thái đã đi qua – nếuchúng ta muốn nó chắc chắn tìm thấy lời giải tối ưu. Với những không gian tìm kiếm lớnnhỏ thì đây không phải là một điểm đáng quan tâm. Tuy nhiên, với những không gian tìmkiếm khổng lồ (chẳng hạn tìm đường đi trên một ma trận kích thước cỡ 106 x 106) thìkhông gian lưu trữ là cả một vấn đề hóc búa. Các nhà nghiên cứu đã đưa ra khá nhiều cáchướng tiếp cận lai để giải quyết vấn đề này. Chúng ta sẽ tìm hiểu một số phương ánnhưng quan trọng nhất, ta cần phải nắm rõ vị trí của A* so với những thuật giải khác.III.10. Ứng dụng A* để giải bài toán Ta-canhBài toán Ta-canh đã từng là một trò chơi khá phổ biến, đôi lúc người ta còn gọi đây là bàitoán 9-puzzle. Trò chơi bao gồm một hình vuông kích thứơc 3x3 ô. Có 8 ô có số, mỗi ôcó một số từ 1 đến 8. Một ô còn trống. Mỗi lần di chuyển chỉ được di chuyển một ô nằmcạnh ô trống về phía ô trống. Vấn đề là từ một trạng thái ban đầu bất kỳ, làm sao đưađược về trạng thái cuối là trạng thái mà các ô được sắp lần lượt từ 1 đến 8 theo thứ tự từtrái sang phải, từ trên xuống dưới, ô cuối dùng là ô trống.Cho đến nay, ngoại trừ 2 giải pháp vét cạn và tìm kiếm Heuristic, người ta vẫn chưa tìmđược một thuật toán chính xác, tối ưu để giải bài toán này. Tuy nhiên, cách giải theo thuậtgiải A* lại khá đơn giản và thường tìm được lời giải (nhưng không phải lúc nào cũng tìmđược lời giải). Nhận xét rằng: Tại mỗi thời điểm ta chỉ có tối đa 4 ô có thể di chuyển. Vấnđề là tại thời điểm đó, ta sẽ chọn lựa di chuyển ô nào? Chẳng hạn ở hình trên, ta nên dichuyển (1), (2), (6), hay (7) ? Bài toán này hoàn toàn có cấu trúc thích hợp để có thể giảibằng A* (tổng số trạng thái có thể có của bàn cờ là n2! với n là kích thước bàn cờ vì mỗitrạng thái là một hoán vị của tập n2 con số).Tại một trạng thái đang xét Tk, đặt d(i,j)là số ô cần di chuyển để đưa con số ở ô (i,j) vềđúng vị trí của nó ở trạng thái đích.Hàm ước lượng h’ tại trạng thái Tk bất kỳ bằng tổng của các d(i,j) sao cho vị trí (i,j)không phải là ô trống.Như vậy đối với trạng thái ở hình ban đầu, hàm f(Tk) sẽ có giá trị là Fk=2+1+3+1+0+1+2+2=12III.11. Các chiến lược tìm kiếm laiChúng ta đã biết qua 4 kiểu tìm kiếm : leo đèo (LĐ), tìm theo chiều sâu (MC), tìm theochiều rộng (BR) và tìm kiếm BFS. Bốn kiểu tìm kiếm này có thể được xem như 4 tháicực của không gian liên tục bao gồm các chiến lược tìm kiếm khác nhau. Để giải thíchđiều này rõ hơn, sẽ tiện hơn cho chúng ta nếu nhìn một chiến lược tìm kiếm lời giải dướihai chiều sau : Chiều khả năng quay lui (R): là khả năng cho phép quay lại để xem xét những trạng thái xét đến trước đó nếu gặp một trạng thái không thể đi tiếp. Chiều phạm vi của sự đánh giá (S): số các trạng thái xét đến trong mỗi quyết định. Hình : Tương quan giữa các chiến lược leo đèo, quay lui và tốt nhấtTheo hướng R, chúng ta thấy leo đèo nằm ở một thái cực (nó không cho phép quay lạinhững trạng thái chưa được xét đến), trong khi đó tìm kiếm quay lui và BFS ở một tháicực khác (cho phép quay lại tất cả các hướng đi chưa xét đến). Theo hướng S chúng tathấy leo đèo và lần ngược nằm ở một thái cực (chỉ tập trung vào một phạm vi hẹp trên tậpcác trạng thái mới tạo ra từ trạng thái hiện tại) và BFS nằm ở một thái cực khác (trong khiBF xem xét toàn bộ tập các con đường đã có, bao gồm cả những con đường mới được tạora cũng như tất cả những con đường không được xét tới trước đây trước mỗi một quyếtđịnh).Những thái cực này được trực quan hóa bằng hình ở trên. Vùng in đậm biểu diễn một mặtphẳng liên tục các chiến lược tìm kiếm mà nó kết hợp một số đặc điểm của một trong bathái cực (leo đèo, chiều sâu, BFS) để có được một hòa hợp các đặc tính tính toán củachúng.Nếu chúng ta không đủ bộ nhớ cần thiết để áp dụng thuật toán BFS thuần túy. Ta có thểkết hợp BFS với tìm theo chiều sâu để giảm bớt yêu cầu bộ nhớ. Dĩ nhiên, cái giá mà taphải trả là số lượng các trạng thái có thể xét đến tại một bước sẽ nhỏ đi. Một loại kết hợpnhư thế được chỉ ra trong hình dưới. Trong hình này, thuật giải BFS được áp dụng tạiđỉnh của đồ thị tìm kiếm (biểu diễn bằng vùng tô tậm) và tìm kiếm theo chiều sâu đượcáp dụng tại đáy (biểu diễn bởi tam giác tô nhạt). Đầu tiên ta áp dụng BFS vào trạng tháiban đầu T0 một cách bình thường. BFS sẽ thi hành cho đến một lúc nào đó, số lượngtrạng thái được lưu trữ chiếm dụng một không gian bộ nhớ vượt quá một mức cho phépnào đó. Đến l ...