tailieunhanh - Thuật toán và giải thuật - Hoàng Kiếm Part 6

Ứng dụng A* để giải bài toán Ta- canh Các chiến lược tìm kiếm lai Tổng quan về trí tuệ nhân tạo chế tạo được những cổ máy thông minh như con người ( thậm trí thông minh hơn con người) là một mơ ước cháy bỏng của loài người hàng trăm năm nay | . Ứng dụng A để giải bài toán Ta-canh Bà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ài toá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ằm cạ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ật giả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 di chuyể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ải bằ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ỗi trạ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 12 . Các chiến lược tìm kiếm lai Chú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 theo chiề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ái cự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ưới hai chiều sau 37 Sưu tầm bởi Chiều khả năng quay lui R là khả năng cho phép quay lại để xem xét những