Bài toán tìm đường đi từ A đến B qua E (hoặc) 2) Bài toán tìm đường đi từ A đến b qua G. Mỗi một trong hai bài toán trên lại có thể phân nhỏ như sau 1) Bài toán tìm đường đi từ A đến B qua E được quy về: Tìm đường đi từ A đến E (và) Tìm đường đi từ E đến B. 2) Bài toán tìm đường đi từ A đến B qua G được quy về: Tìm đường đi từ A đến G (và) | toán tìm đường đi từ A đến B được quy về 1 Bài toán tìm đường đi từ A đến B qua E hoặc 2 Bài toán tìm đường đi từ A đến b qua G. Mỗi một trong hai bài toán trên lại có thể phân nhỏ như sau 1 Bài toán tìm đường đi từ A đến B qua E được quy về Tìm đường đi từ A đến E và Tìm đường đi từ E đến B. 2 Bài toán tìm đường đi từ A đến B qua G được quy về Tìm đường đi từ A đến G và Tìm đường đi từ G đến B. Quá trình rút gọn vấn đề như trên có thể biểu diễn dưới dạng đồ thị đồ thị và hoặc trong hình . ở đây mỗi bài toán tìm đường đi từ một thành phố tới một thành phố khác ứng với một trạng thái. Các trạng thái kết thúc là các trạng thái ứng với các bài toán tìm đường đi chẳng hạn từ A đến C hoặc từ D đến E bởi vì đã có đường nối A với C nối D với E. Đồ thị và hoặc Không gian trạng thái mô tả việc quy vấn đề về các vấn đề con có thể biểu diễn dưới dạng đồ thị định hướng đặc biệt được gọi là đồ thị và hoặc. Đồ thị này được xây dựng như sau Mỗi bài toán ứng với một đỉnh của đồ thị. Nếu có một toán tử quy một bài toán về một bài toán khác chẳng hạn R a b thì trong đồ thị sẽ có cung gán nhãn đi từ đỉnh a tới đỉnh b. Đối với mỗi toán tử quy một bài toán về một số bài toán con chẳng hạn R a b c d ta đưa vào một đỉnh mới a1 đỉnh này biểu diễn tập các bài toán con b c d và toán tử R a b c d được biểu diễn bởi đồ thị hình . Ví dụ Giả sử chúng ta có không gian trạng thái sau Trạng thái ban đầu bài toán cần giải là a. Tập các toán tử quy gồm R1 a d e f R2 a d k R3 a g h R4 d b c R5 f i Rô f c j R7 k e l R8 k h Tập các trạng thái kết thúc các bài toán sơ cấp là T b c e j l . Hình Một đồ thị và hoặc Không gian trạng thái trên có thể biểu diễn bởi đồ thị và hoặc trong hình . Trong đồ thị đó các đỉnh chẳng hạn a1 a2 a3 được gọi là đỉnh và các đỉnh chẳng hạn a f k được gọi là đỉnh hoặc. Lý do là đỉnh a1 biểu diễn tập các bài toán d e f và a1 được giải quyết nếu d và e và f được giải quyết. Còn tại đỉnh a ta có các toán tử R1 R2 R3 quy bài toán a về các bài .
