TAILIEUCHUNG - 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. | 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. 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ìm kiế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ếu chú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ớn nhỏ 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ìm kiế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ác hướ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 án như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. . Ứ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á đon 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 .

• Kỹ thuật lập trình
• máy tính
• mạng máy tính
• internet
• phần mềm
• ứng dụng
• lập trình
• dữ liệu
• SQL
• PHP
• AutoIT
• Phần cứng máy tính
• lắp ráp máy tính
• sửa chữa máy tính
• lỗi máy tính
• hệ thống mạch máy tính
• điện máy tính
• Tài liệu máy tính