ĐỊNH NGHĨA TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI

Một không gian trạng thái (state space) được biểu diễn bằng một nhóm gồm bốn yếu tố [N, A, S, GD], trong đó:

N (node) là tập hợp các nút hay các trạng thái của đồ thị. Tập này tương ứng với các trạng thái trong quá trình giải bài toán.

A (arc) là tập các cung (hay các liên kết) giữa các nút. Tập này tương ứng với các bước trong quá trình giải bài toán.

S (Start) là một tập con không rỗng của N, chứa (các) trạng thái ban đầu của bài toán.

GD (Goal Description) là một tập con không rỗng của N, chứa (các) trạng thái đích của bài toán. Các trạng thái trong GD được mô tả theo một trong hai đặc tính:

• Đặc tính có thể đo lường được các trạng thái gặp trong quá trình tìm kiếm.
• Đặc tính của đường đi được hình thành trong quá trình tìm kiếm.

Đường đi của lời giải (solution path) là đường đi qua đồ thị này từ một nút trong S đến một nút trong GD.

Một đích có thể mô tả như một trạng thái, như bảng thắng cuộc trong trò chơi Tic - tac - toe hay một cấu hình đích trong trò đố 8 ô. Nhưng mặt khác, đích cũng có thể được mô tả như một đặc tính nào đó của chính đường đi lời giải.

Trong bài toán di chuyển của người bán hàng (hình 3.6 và 3.7), quá trình tìm kiếm sẽ kết thúc khi tìm được đường đi ngắn nhất qua tất cả các nút của đồ thị. Trong bài toán phân tích ngữ pháp, đường đi của quá trình phân tích thành công đối với một câu sẽ cho biết rõ điểm kết thúc.

Các cung của không gian trạng thái tương ứng với các bước trong quá trình giải bài toán, và các đường đi qua không gian này sẽ biểu diễn các lời giải trong các giai đoạn hoàn thành khác nhau. Các đường đi sẽ được khảo sát, bắt đầu từ trạng thái xuất phát và tiếp tục đi xuyên qua đồ thị, cho đến khi gặp được một mô tả đích thỏa mãn hoặc đến khi không đi được nữa. Việc tạo ra các trạng thái mới trên đường đi sẽ được thực hiện bằng cách áp dụng các thao tác, như “các di chuyển hợp lệ” trong trò chơi hay quy tắc suy diễn trong bài toán logic và trong hệ chuyên gia chẳng hạn, vào các trạng thái hiện hữu trên đường đi.

Nhiệm vụ của thuật toán tìm kiếm là tìm ra đường đi lời giải trong một không gian bài toán như vậy. Thuật toán tìm kiếm phải lưu vết các đường đi dẫn từ nút xuất phát đến nút đích, vì các đường đi này chứa hàng loạt thao tác dẫn đến lời giải của bài toán. Một đặc trưng phổ biến của đồ thị, đồng thời là vấn đề phát sinh khi thiết kế thuật toán tìm kiếm trên đồ thị, là đôi khi tiếp cận một trạng thái nào đó bằng nhiều đường đi khác nhau.

Thí dụ 3.1: Trò chơi tic–tac-toe

Cách biểu diễn không gian trạng thái của Tic-tac-toe như trong hình 2.1. Trạng thái xuất phát là một bảng rỗng, và đích kết thúc (hay mô tả đích) là một trạng thái dạng bảng có 3 ô x trong một hàng, một cột, hay một đường chéo (giả sử đích là một thắng cuộc đối với X). Đường đi từ trạng thái xuất phát đến trạng thái đích sẽ cho ta hàng loạt nước đi cho một ván thắng.

Các trạng thái trong không gian này là các cách sắp xếp tập hợp {ô rỗng, X, O} trong chín ô trống của trạng thái bắt đầu, như vậy ta sẽ có 3⁹ cách sắp xếp, nhưng hầu hết chúng không bao giờ xảy ra trong một ván chơi thực tế. Các cung sẽ được tạo ra bởi các nước đi đúng luật trong cuộc chơi, sau khi luân phiên đặt X và O vào một vị trí chưa dùng đến. Không gian trạng thái này là một đồ thị chứ không phải một cây, vì có thể đạt đến một số trạng thái nằm ở mức thứ ba và các mức sâu hơn bằng các đường đi khác nhau. Tuy vậy không có vòng lặp nào trong không gian trạng thái này vì các cung có hướng của đồ thị không cho phép đi lại một nước đã đi, nghĩa là không được phép “đi ngược trở lại” một cấu trúc một khi đã đi đến trạng thái nào đó. Do đó, không cần phải kiểm tra về vòng lặp trong việc tạo ra đường đi. Một cấu trúc đồ thị có đặc tính như vậy gọi là đồ thị có hướng không lặp lại (directed acyclic graph), hay DAG và phổ biến trong các quá trình tìm kiếm không gian trạng thái.

Việc biểu diễn không gian trạng thái cho chúng ta một phương tiện để xác định mức độ phức tạp của bài toán. Trong Tic-Tac-Toe có chín cách đi đầu tiên với tám khả năng có thể xảy ra đối với mỗi cách đi đó; tiếp theo là bảy khả năng có thể xảy ra nữa cho từng cách đi ở lượt thứ hai, … Như vậy có tất cả 9 x 8 x 7 x … hay 9! đường đi khác nhau có thể được tạo ra. Mặc dù máy tính hoàn toàn có đủ khả năng thăm dò hết số lượng đường đi này (362880), nhưng nhiều bài toán quan trọng có mức độ phức tạp theo qui luật số mũ hay giai thừa với qui mô lớn hơn nhiều. Cờ vua có 10¹²⁰ cách đi có thể xảy ra cho một ván chơi, cờ đam có 10⁴⁰ cách đi, một số trong đó có thể không bao giờ xảy ra ở một ván chơi thực tế. Các không gian này rất khó hoặc không thể nào khảo sát cho đến hết được. Chiến lược tìm kiếm đối với một không gian lớn như vậy thường phải dựa vào các heuristic để làm giảm bớt mức độ phức tạp cho quá trình tìm kiếm.

Thí dụ 3.2: Trò đố 8 ô

Nguyên bản của trò chơi là trò đố 15 ô như hình 3.3, có 15 viên gạch đánh số khác nhau được đặt vừa vào 16 ô vuông theo bảng. Có một ô vuông để trống nên các viên gạch đó có thể di chuyển loanh quanh để tạo ra các sắp xếp khác nhau. Mục tiêu là tìm ra một chuỗi bước di chuyển các viên gạch vào ô trống để sắp xếp bảng thành một cấu hình đích nào đó. Không gian trạng thái bài toán đủ lớn để xem xét (16! nếu các trạng thái đối xứng được xem xét riêng biệt).

Hình 3.3 - Trò đố 15 ô và 8 ô

Trò đố 8 ô là một phiên bản với kích thước 3 x 3 của trò đố 15 ô, vì nó tạo ra không gian trạng thái nhỏ hơn so với trò đố 15 ô nên thường được dùng cho nhiều ví dụ. Các cách di chuyển đúng luật là:

• Di chuyển ô trống lên phía trên (Up)
• Di chuyển ô trống về bên phải (Right)
• Di chuyển ô trống xuống phía dưới (Down)
• Di chuyển ô trống về bên trái (Left)

Để áp dụng một di chuyển, phải bảo đảm rằng không di chuyển ô trống ra ngoài bảng. Do đó, tất cả bốn cách di chuyển này không phải lúc nào cũng có thể áp dụng. Nếu đã xác định một trạng thái xuất phát và một trạng thái đích thì có thể đưa ra một sơ đồ không gian trạng thái của quá trình giải toán. Giống như trò chơi Tic-tac-toe không gian trạng thái của trò đố 8 ô cũng là một đồ thị (với hầu hết các trạng thái đều có nhiều nút cha), nhưng khác Tic-tac-toe là có vòng lặp. Mô tả đích (GD) của không gian trạng thái này là một trạng thái cụ thể, tức một cấu hình bảng cụ thể nào đó. Khi tìm được trạng thái này trên đường đi, quá trình tìm kiếm kết thúc. Đường đi từ trạng thái xuất phát đến trạng thái đích là dãy các bước di chuyển theo yêu cầu.

Hình 3.4 – Không gian trạng thái trong trò đố 8 ô.

Thí dụ 3.3: Đường đi của người bán hàng

Giả sử có một người bán hàng phải giao hàng cho năm thành phố và sau đó phải quay về nhà. Đích của bài toán là tìm con đường ngắn nhất cho người giao hàng đó đi đến từng thành phố, rồi quay về thành phố xuất phát. Hình 3.5 cho một trường hợp của bài toán này.

Hình 3.5 – Một ví dụ của bài toán TSP

Các nút trong đồ thị biểu diễn các thành phố, và mỗi cung đều được ghi kèm một trọng số cho biết phí tổn đi lại trên cung đó. Chi phí này có thể là số km phải di chuyển bằng ô tô hay giá vé máy bay giữa hai thành phố. Để thuận tiện, chúng ta giả thiết người bán hàng sống ở thành phố A và sẽ quay về đây, mặc dù giả thiết này chỉ giảm từ bài toán n thành phố xuống bài toán (n-1) thành phố.

Hình 3.6 – Không gian trạng thái cho quá trình tìm kiếm đường đi (TSP)

Đường đi [A,D,C,B,E,A], với chi phí tương ứng 450 km là ví dụ về một con đường có thể đi. Mô tả đích yêu cầu một con đường có chi phí thấp nhất. Chú ý rằng mô tả đích này là một đặc tính của toàn bộ con đường, không phải là một trạng thái đơn lẻ. Đây là mô tả đích dạng thứ hai trong định nghĩa về tìm kiếm trong không gian trạng thái đã nói ở trên.