4. Không gian trạng thái của bài toán.

                        Kkhông gian trạng thái là tập tất cả các trạng thái có thể có và tập các toán tử  của bài toán.

Không gian trạng thái là một bộ bốn, Ký hiệu: K= (T, S, G, F). Trong đó,

T: tập tất cả các trạng thái có thể có của bài toán

S: trạng thái đầu

G: tập các trạng thái đích

F: tập các toán tử

Ví dụ 1. Không gian trạng thái của bài toán đong nước là bộ bốn T, S, G, F xác đinh như sau:

                        T = { (x,y) / 0 <= x <= m; 0 <= y <= n }

                        S = (0,0)

                        G = { (x,k) hoặc (k,y) / 0 <= x <= m; 0 <= y <= n}

                        F = Tập các thao tác đong đầy, đổ ra hoặc đổ sang bình khác thực hiện trên một bình.

Ví dụ 2.  Không gian trạng thái của bài toán Tháp Hà nội với n = 3:

                   T = { (x1, x2, x3)/ xi Î {1, 2, 3} }

                   S = (1, 1, 1)

                   G = {(3, 3, 3)}

                   F = Tập các khả năng có thể chuyển đĩa đã xác định trong phần trước.

Ví dụ 3. Không gian trạng thái của bài toán trò chơi 8 số:

                    T = { (aij)3x3 / 0<= aij <= 8 và aij <> akl với i<> j hoặc k <> l}

                    S = Ma trận xuất phát của bài toán,

                    G = Ma trận cuối cùng của bài toán (các số nằm theo vị trí yêu cầu)

                    F = {fl, fr, fu, fd}

Tìm kiếm lời giải trong không gian trạng thái là quá trình tìm kiếm xuất phát từ trạng thái ban đầu, dựa vào toán tử chuyển trạng thái để xác định các trạng thái tiếp theo cho đến khi gặp được trạng thái đích.

1.3.         Ưu và nhược điểm của phương pháp tìm kiếm rộng.

1.3.1.  Ưu điểm.

·        Kỹ thuật tìm kiếm rộng là kỹ thuật vét cạn không gian trạng thái bài toán vì vậy sẽ tìm được lời giải nếu có.

·        Đường đi tìm được đi qua ít đỉnh nhất.

1.4.2.  Nhược điểm.

·        Tìm kiếm lời giải theo thuật toán đã định trước, do vậy tìm kiếm một cách máy móc; khi không có thông tin hổ trợ cho quá trình tìm kiếm, không nhận ra ngay lời giải.

·        Không phù hợp với không gian bài oán kích thước lớn. Đối với loại bài toán này, phương pháp tìm rộng đối mặt với các nhu cầu:

-         Cần nhiều bộ nhớ theo số nút cần lưu trữ.

-         Cần nhiều công sức xử lý các nút, nhất là khi các nhánh cây dài, số nút tăng.

-         Dễ thực hiện các thao tác không thích hợp, thừa, đưa đến việc tăng đáng kể số nút phải xử lý.

·      Không hiệu qủa nếu lời giải ở sâu. Phương pháp này không phù hợp cho trường hợp có nhiều đường dẫn đến kết quả nhưng đều sâu.

·      Giao tiếp với người dùng không thân thiện. Do duyệt qua tất cả các nút, việc tìm kiếm không tập trung vào một chủ đề.

Ưu và nhược điểm của phương pháp tìm kiếm sâu.

2.4.1. Ưu điểm.

·        Nếu bài toán có lời giải, phương pháp tìm kiếm sâu bảo đảm tìm ra lời giải.

·        Kỹ thuật tìm kiếm sâu tập trung vào đích, con người cảm thấy hài lòng khi các câu hỏi tập trung vào vấn đề chính.

·        Do cách tìm của kỹ thuật này, nếu lời giải ở rất sâu, kỹ thuật tìm sâu sẽ tiết kiệm thời gian.

2.4.2. Nhược điểm.

·        Tìm sâu khai thác không gian bài toán để tìm lời giải theo thuật toán đơn giản một cách cứng nhắc. Trong quá trình tìm nó không có thông tin nào hổ trợ để phát hiện lời giải. Nếu chọn nút ban đầu không thích hợp có thể không dẫn đến đích của bài toán.

·        Không phù hợp với không gian bài toán lớn, kỹ thuật tìm kiếm sâu có thể không đến lời giải trong khoảng thời gian vừa phải.