Không gian trạng thái là tập hợp tất cả các cấu hình có thể có của một hệ thống. [1] Nó là một phép trừu tượng hữu ích để lập luận về hành vi của một hệ thống nhất định và được sử dụng rộng rãi trong lĩnh vực trí tuệ nhân tạo và lý thuyết trò chơi . Ví dụ, bài toán đồ chơi Thế giới chân không có một không gian trạng thái hữu hạn rời rạc trong đó có một số cấu hình giới hạn mà chân không và bụi bẩn có thể ở trong. Một hệ thống "bộ đếm", trong đó các trạng thái là các số tự nhiên bắt đầu từ 1 và được tăng dần theo thời gian [2] có không gian trạng thái rời rạc vô hạn. Vị trí góc của một con lắc không dấu [3] là một không gian trạng thái liên tục (và do đó vô hạn). Trong lý thuyết hệ động lực , một hệ rời rạc được xác định bởi hàm ƒ , không gian trạng thái của hệ có thể được mô hình hóa dưới dạng đồ thị có hướng trong đó mỗi trạng thái có thể của hệ động lực được biểu diễn bằng một đỉnh và có một cạnh hướng từ a đến b nếu và chỉ khi ƒ ( a ) = b . [4] Đây được gọi là biểu đồ trạng thái . Đối với hệ động lực liên tục xác định bởi hàm ƒ , không gian trạng thái của hệ là ảnh của ƒ . Không gian trạng thái rất hữu ích trong khoa học máy tính như một mô hình máy móc đơn giản. Về mặt hình thức, một không gian trạng thái có thể được định nghĩa là một bộ [ N , A , S , G ] trong đó: Một không gian trạng thái có một số thuộc tính chung: Ví dụ: Thế giới chân không có hệ số phân nhánh là 4, vì máy hút bụi có thể kết thúc ở 1 trong 4 hình vuông liền kề sau khi di chuyển (giả sử nó không thể ở trong cùng một hình vuông hoặc di chuyển theo đường chéo). Các vòng cung của Thế giới chân không là hai chiều, vì có thể đạt được bất kỳ hình vuông nào từ bất kỳ hình vuông liền kề nào và không gian trạng thái không phải là một cái cây vì có thể đi vào một vòng lặp bằng cách di chuyển giữa 4 hình vuông liền kề bất kỳ. Không gian trạng thái có thể là vô hạn hoặc hữu hạn, và rời rạc hoặc liên tục. Kích thước của không gian trạng thái cho một hệ thống nhất định là số lượng cấu hình có thể có của không gian. [3] Nếu kích thước của không gian trạng thái là hữu hạn thì việc tính kích thước của không gian trạng thái là một bài toán tổ hợp . [5] Ví dụ, trong câu đố Tám nữ hoàng , không gian trạng thái có thể được tính bằng cách đếm tất cả các cách có thể để đặt 8 quân cờ trên bàn cờ 8x8. Điều này cũng giống như việc chọn 8 vị trí mà không cần thay thế từ bộ 64, hoặc Con số này lớn hơn đáng kể so với số lượng cấu hình hợp pháp của các nữ hoàng, 92. Trong nhiều trò chơi, không gian trạng thái hiệu quả là nhỏ so với tất cả các trạng thái có thể truy cập / hợp pháp. Tính chất này cũng được quan sát thấy trong Cờ vua , nơi không gian trạng thái hiệu quả là tập hợp các vị trí có thể đạt được bằng các nước đi hợp pháp trò chơi. Điều này nhỏ hơn nhiều so với tập hợp các vị trí có thể đạt được bằng cách đặt tổ hợp các quân cờ có sẵn trực tiếp trên bàn cờ. Tất cả các không gian trạng thái liên tục có thể được mô tả bằng một hàm liên tục tương ứng và do đó là vô hạn. [3] Không gian trạng thái rời rạc cũng có thể có ( có thể đếm được ) kích thước vô hạn, chẳng hạn như không gian trạng thái của hệ thống "bộ đếm" phụ thuộc thời gian, [2] tương tự như hệ thống trong lý thuyết xếp hàng xác định số lượng khách hàng trong một hàng, sẽ có không gian trạng thái {0, 1, 2, 3, ...}.
Trạng thái hợp lệ trong không gian trạng thái của câu đố tám nữ hoàng
Chiến lược tìm kiếm mù có 2 thuật toán khá dễ nhớ: tìm kiếm theo chiều rộng (Breadth First Search – BFS) và tìm kiếm theo chiều sâu (Depth First Search – DFS). Đây là 2 thuật toán cơ bản của môn trí tuệ nhân tạo. Khi đã nắm được 2 thuật toán này, ta có thể dễ dàng mở rộng để cài đặt các thuật toán tốt hơn sau này. Tìm kiếm theo chiều rộng (BFS) Trên cây tìm kiếm, trạng thái ban đầu chính là node gốc của cây. BFS sẽ lần lượt duyệt tất cả các node ở cùng độ sâu trước, nếu không tìm thấy node đích thì BFS sẽ tiếp tục duyệt các node con ở độ sâu tiếp theo. Khi thuật toán BFS làm việc, ta có thể tưởng tượng nó như 1 vết dầu loang. Để có thể dễ hiểu hơn, ta sẽ xét đồ thị sau. Xem A là trạng thái ban đầu, hãy tìm đường biến đổi trạng thái A thành trạng thái K. Với yêu cầu này, ta xây dựng được cây tìm kiếm như bình b). Thuật toán BFS sẽ làm việc như sau:
(code sample – updating) Tìm kiếm theo chiều sâu (DFS) DFS khác với BFS ở chỗ nó duyệt các node theo chiều sâu dần. Cũng với yêu cầu như trên, DFS sẽ làm việc như sau:
(code sample – updating) Nhận xét Thuật toán tìm kiếm theo chiều rộng đảm bảo sẽ luôn tìm được nghiệm nếu bài toán có nghiệm. Trong khi đó thuật toán tìm kiếm theo chiều sâu không phải lúc nào cũng đảm bảo tìm thấy nghiệm. Tại sao lại như vậy? Nếu nhìn kỹ cách làm việc của 2 thuật toán, ta có thể thấy rằng tìm kiếm theo chiều sâu càng ngày càng đi sâu hơn theo nhánh đang duyệt. Vậy chuyện gì sẽ xảy ra nếu nhánh đó là nhánh vô hạn? Nghĩa là trong đồ thị có tồn tại 1 chu trình khiến cho việc phát triển trạng thái kề của trạng thái đang xét cứ lặp đi lặp lại trên 1 số trạng thái cố định. Ví dụ A→B, B→C, C→A. Rõ ràng tìm kiếm theo chiều sâu sẽ bị kẹt ở nhánh nãy mãi mãi mà không thể dừng lại được. Vì vậy, người ta khuyên rằng không nên áp dụng thuật toán tìm kiếm theo chiều sâu cho những đồ thị có tồn tại chu trình. Nhưng tìm kiếm theo chiều sâu lại có ưu điểm là có thể tìm thấy kết quả nhanh hơn tìm kiếm theo chiều rộng (trong nhiều trường hợp), không gian bộ nhớ cần cho việc lưu trữ cũng ít hơn. Vậy làm sao để áp dụng thuật toán này mà không bị gặp phải vấn đề về nhánh vô hạn? Bài viết tiếp theo sẽ đưa ra một số giải pháp cho vấn đề này. Thêm một vấn đề nữa đối với các chiến lược tìm kiếm mù đó là việc bùng nổ tổ hợp trong quá trình tìm kiếm. Càng về sau, số lượng trạng thái được chờ để xét càng nhiều, khiến cho thời gian tìm kiếm trở lên rất lớn. Hơn nữa, bùng nổ tổ hợp cũng khiến cho không gian lưu trữ cần phải lớn theo. Vậy làm sao để giải quyết vấn đề bùng nổ tổ hợp? Các thuật toán heuristic sẽ giúp ta giải quyết vấn đề này. Leave a comment
 Nếu đã học đồ thị, thuật toán Dijiktra… trong môn toán rời rạc, hẳn bạn cũng đã từng đặt ra những câu hỏi dạng như: “Đồ thị học để làm gì? Ứng dụng của nó thế nào mà mình lại phải học?”. Thông qua bài viết này, hi vọng bạn sẽ nhìn thấy được một ứng dụng cụ thể hữu ích của khái niệm đồ thị cũng như các khái niệm trừu tượng khác của môn toán rời rạc kia Dẫn nhập Có rất nhiều bài toán trong thực tế có thể được giải quyết bằng cách chuyển về dạng các bài toán tìm kiếm. Cụ thể hơn là tìm kiếm một hay một số đối tượng nào đó trong một tập lớn các đối tượng nhằm thỏa mãn yêu cầu nào đó của bài toán. Ví dụ: trong trò chơi cờ ca rô, mỗi lượt đi, ta có thể đánh ở nhiều vị trí khác nhau, nhưng ta cần phải tìm ra vị trí đánh sao cho cuối cùng ta là người giành chiến thắng. Trong lĩnh vực trí tuệ nhân tạo, vấn đề tìm kiếm lại trở nên cực kỳ quan trọng do ta phải thường xuyên đối đầu với các bài toán tìm kiếm. Biểu diễn vấn đề trong không gian trạng thái Để có thể thực hiện các thao tác tìm kiếm, ta cần phải xác định không gian tìm kiếm của bài toán. Ví dụ: không gian vectơ n chiều, không gian các đối tượng rời rạc… Có rất nhiều bài toán có thể được mô tả bằng khái niệm tập các trạng thái và toán tử (biến đổi trạng thái này thành trạng thái khác). Ví dụ: trên một bàn cờ, mỗi cách bố trí các quân cờ là một trạng thái và mỗi cách di chuyển của 1 quân cờ nào đó được xem như là 1 toán tử, do sau khi tiến hành 1 nước đi của 1 quân cờ bất kỳ thì nó ngay lập tức làm biến đổi trạng thái của bàn cờ. Và rất nhiều trạng thái khác nhau để quyết định ván cờ có tiếp tục nữa hay không (thắng, hòa, thua). Những trạng thái này được gọi là các trạng thái kết thúc. Vậy để biểu diễn một vấn đề nào đó trong không gian trạng thái ta cần xác định: – Trạng thái ban đầu (khởi đầu cho việc tìm kiếm). – Tập các toán tử, mỗi toán tử mô tả cách biến đổi trạng thái này sang trạng thái khác. – Tập các trạng thái kết thúc (các trạng thái đích). Việc tìm kiếm sẽ ngừng khi gặp trạng thái này. Phân loại các giải thuật tìm kiếm trên không gian trạng thái Có thể phân các giải thuật tìm kiếm trên không gian trạng thái thành 2 loại: – Tìm kiếm mù Tìm kiếm không theo sự hướng dẫn nào, phạm vi tìm kiếm được phát triển liên tục cho đến khi gặp trạng thái đích.
– Tìm kiếm theo kinh nghiệm (heuristic) Tìm kiếm theo một sự hướng dẫn nào đó nhằm lựa chọn trạng thái tốt nhất cho bước đi tiếp theo của quá trình tìm kiếm. Do đó, thời gian tìm kiếm sẽ ít hơn, không gian tìm kiếm cũng sẽ được rút gọn hơn. Có nhiều giải thuật giải quyết vấn đề theo hướng này: A*, AT, AKT, … Cây tìm kiếm Có thể xem quá trình tìm kiếm trong không gian trạng thái như việc xây dựng một cây tìm kiếm. Trong đó, các node của cây chính là các trạng thái của không gian trạng thái, node gốc là trạng thái ban đầu. Mỗi chiến lược tìm kiếm sẽ có cách duyệt cây tìm kiếm khác nhau. Leave a comment |
