Các phương pháp giải quyết vấn đề

Trong phần này, chúng ta chỉ ra một agent có thể hành động như thế nào bằng cách đặt ra mục tiêu và xem xét chuỗi các hành động mà có thể đạt được những mục tiêu này. Một mục tiêu và tập các phương tiện để đạt được mục tiêu được gọi là vấnđề. Quá trình khám phá các phương tiện có thể làm được gì gọi là tìmkiếm. Chúng ta cho thấy tìm kiếm có thể thực hiệhie và những giới hạn của nó..

Giải quyết bài toán bằng cách tìm kiếm

Chúng ta xem một agent quyết định phải làm gì? như thế nào? bằng cách xem xét có hệ thống kết quả các chuỗi hành động mà nó thực hiện.

Hãy tưởng tượng các agent của chúng ta ở trong thành phố Arad, Rumani đang thực hiện một chuyến du lịch. Agent đã có vé để bay đến Bucarét vào ngày hôm sau. Vé máy bay không thể trả lại được, visa của agent chuẩn bị hết hạn, và kể từ ngày mai sẽ không còn chỗ trong 6 tuần tới. Phạm vi thực hiện của agent chứa nhiều yếu tố khác ngoài chi phí tiền vé máy bay và có một điều không mong muốn là có thể bị trục xuất. Chẳng hạn, agent muốn cải thiện nước da rám nắng của mình, học thêm tiếng Rumani, đi chơi đâu đó vv… Tất cả những yếu tố này có thể gợi ra vô số các hành động.

Agent đưa ra mục tiêu: lái xe tới Bucarét, và xem những thành phố nào cần phải đếcaa, xuất phát từ Arad. Có ba con đường ra khỏi Arad, một đường đến Sibiu, một đường đến Timisoara và một đến Zerind. Tất cả các con đường này đều không đến Bucaret, vì vậy trừ khi agent nắm rõ bản đồ Rumani, agent sẽ không biết phải đi con đường nào tiếp theo. Nói cách khác, agent không biết hành động nào là tốt nhất trong các hành động. Nếu agent không có các kiến thức trợ giúp, nó sẽ bị tắc (không tìm ra được đường đi tiếp theo). Cách tốt nhất nó có thể làm là chọn ngẫu nhiên một trong các hành động.

Giả thiết agent có một bản đồ Rumani, hoặc trên giấy hoặc trong trí nhớ. Mục đích của bản đồ là cung cấp cho agent các thông tin về các trạng thái mà nó có thể đến và những hành động mà nó có thể thực hiện. Agent có thể sử dụng thông tin này để xem xét các các đoạn của hành trình mang tính giả thiết là: khi nó tìm ra một con đường trên bản đồ từ Arad tới Bucaret, nó có thể đạt mục tiêu bằng cách thực hiện các hành động tương ứng với các chặng của hành trình. Sau đó agent lựa chọn các giá trị chưa biết để quyết định phải làm gì bằng cách kiểm tra chuỗi các hành động khác nhau dẫn đến các trạng thái đã biết; sau đó chọn hành động tốt nhất. Quá trình tìm kiếm một chuỗi các hành động như vậy được gọi là tìm kiếm. Giải thuật tìm kiếm coi một vấn đề như dữ liệu vào và đáp số là một giải pháp dưới dạng chuỗi hành động. Khi một giải pháp được tìm thấy, các hành động mà nó đề xuất có thể được tiến hành. Điều này được gọi là giai đoạn thực hiện.

Trong phần này, chúng ta sẽ tìm hiểu quá trình xác định bài toán chi tiết hơn. Trước tiên, ta xem xét khối lượng kiến thức mà agent có thể có sử dụng để hướng đến các hành động của nó và trạng thái mà nó phải đi qua. Điều này phụ thuộc vào sự nhận thức của agent với môi trường của nó như thế nào thông qua kết quả giác quan và hành động của nó. Chúng ta biết có bốn loại bài toán khác nhau: bài toán một trạng thái đơn giản; bài toán đa trạng thái; bài toán ngẫu nhiên và bài toán thăm dò

Những vấn đề (bài toán) xác định rõ ràng và các giải pháp

Một vấn đề là một tập hợp các thông tin mà agent sử dụng để quyết định phải làm gì. Chúng ta bắt đầu bằng cách phân loại các thông tin cần thiết dùng cho định nghĩa bài toán đơn trạng thái.

Các yếu tố cơ bản của việc định nghĩa một bài toán là các trạng thái và các hành động. Để xác định được chúng một cách chính xác, chúng ta cần các yếu tố sau:

Trạng thái ban đầu của agent.Tập các hành động có thể đối với agent. Thuật ngữ thao tác (operation) được sử dụng để mô tả một hành động trong ngữ cảnh là trạng thái nào nó sẽ đến nếu thực hiện hành động trong từ một trạng thái đặc biệt. (Một công thức sử dụng hàm S. Cho trước trạng thái x, S(x)cho trạng thái có thể đi tới từ x bằng bất cứ một hành động đơn).

Định nghĩa: không gian trạng thái của vấn đề: là tập các trạng thái có thể đạt được bằng chuỗi hành động bất kỳ xuất phát từ trạng thái ban đầu. Một hành trình trong không gian trạng thái là tập các hành động tuỳ ý xuất phát từ trạng thái này đến trạng thái khác.

Yếu tố tiếp theo của vấn đề như sau: tiêu chuẩn kiểm tra trạng thái hiện thời là trạng thái đích (mục tiêu)? Việc kiểm tra đơn giản chỉ là để nhằm kiểm tra xem chúng ta đã đi tới một trong các trạng thái mục tiêu hay chưa. Thỉnh thoảng mục tiêu được xác định bởi một thuộc tính trừu tượng thay vì một tập đếm được các trạng thái. Chẳng hạn, trong môn đánh cờ, mục tiêu là đi tới một trạng thái gọi là “chiếu tướng”, khi tướng của đối phương sẽ bị ăn bất kể đối phương đi như thế nào ở bước kế tiếp.

Cuối cùng, chọn giải pháp thích hợp nhất, dù có nhiều giải pháp tới đích. Ví dụ, chúng ta có thể thích những hành trình có ít hành động hoặc các hành động có chi phí thấp.

Hàm chi phí đường đi là hàm được gán chi phí cho một đường đi. Trong tất cả các trường hợp chi phí của đường đi là tổng các chi phí của các hành động đơn dọc theo đường đi. Hàm chi phí đường đi thường được ký hiệu là hàm g. Trạng thái ban đầu, tập toán tử, thủ tục kiểm tra mục tiêu và hàm chi phí đường đi xác định một vấn đề. Về mặt tự nhiên, chúng ta có thể xác định một kiểu dữ liệu để biểu diễn các vấn đề:

Kiểu dữ liệu bài toán

Các thành phần:Trạng thái ban đầu,các toán tử, kiểm tra mục tiêu

Giải quyết vấn đề

Hiệu quả của tìm kiếm có thể đo được theo ít nhất ba chỉ tiêu Thứ nhất, có tìm thấy một giải pháp nào không? Thứ hai, đó có phải là một giải pháp tốt không (giải pháp có chi phí đường đi thấp)? Thứ ba, chi phí tìm kiếm với thời gian tìm kiếm và bộ nhớ yêu cầu để tìm một giải pháp là bao nhiêu? Chi phí toàn bộ của việc tìm kiếm là tổng chi phí đường đi và chi phí tìm kiếm (S).

Đối với vấn đề tìm đường đi từ Arad đến Bucarét, chi phí đường đi tỷ lệ thuận với tổng độ dài của đường, cộng thêm chi phí do sự cố dọc đường. Chi phí tìm kiếm phụ thuộc vào các tình huống. Trong môi trường tĩnh, nó bằng không vì phạm vi thực hiện là độc lập với thời gian. Nếu phải cấp tốc đến Bucarét, môi trường là bán động bởi vì việc cân nhắc lâu hơn sẽ làm chi phí nhiều hơn. Trong trường hợp này, chi phí tìm kiếm có thbi ì ến thiên xấp xỉ tuyến tính với thời gian tính toán(ít nhất với một khoảng thời gian nhỏ). Do đó, để tính toán tổng chi phí, chúng ta cần phải bổ sung thêm các giá trị là dặm và mili giây. Điều này không phải luôn dễ dàng bởi vì không có một “tỷ lệ trao đổi chính thức” giữa hai đại lượng này. Agent bằng cách nào đó phải quyết định những tài nguyên nào sẽ dành cho việc tìm kiếm và những tài nguyên nào dành cho việc thực hiện. Đối với những vấn đề có không gian trạng thái rất nhỏ, dễ dàng tìm ra giải pháp với chi phí đường đi thấp nhất. Nhưng đối với những vấn đề phức tạp, lớn, cần phải thực hiện một sự thoả hiệp- agent có thể tìm kiếm trong một thời gian dài để tìm ra giải pháp tối ưu hoặc agent có thể tìm kiếm trong một thời gian ngắn hơn và nhận được một giải pháp với chi phí đường đi cao hơn một chút. Chọn lựa trạng thái và hành động.

Bây giờ chúng ta có các định nghĩa mới, chúng ta hãy bắt đầu sự điều tra các vấn đề của chúng ta với một vấn đề khá dễ như sau: “ Lái xe từ Arad đến Bucarét sử dụng các con đường trên bản đồ” Một không gian trạng thái có xấp xỉ 20 trạng thái, mỗi trạng thái được xác định bởi vị trí, được ghi rõ là một thành phố. Như vậy, trạng thái ban đầu là “ở Arad” và kiểm tra mục tiêu là “đây có phải là Bucarét không?”. Các toán hạng tương ứng với việc lái dọc theo các con đường giữa các thành phố.

Các bài toán ví dụ

Phạm vi của các môi trường nhiệm vụ mà có thể được mô tả đặc điểm bởi các vấn đề được định nghĩa rõ ràng là rất rộng lớn. Chúng ta có thể phân biệt giữa cái gọi là các bài toán trò chơi, mà nhằm để minh hoạ hay thực hành rất nhiều các phương pháp giải quyết vấn đề, và cái gọi là các bài toán thuộc thế giới thựcmà sẽ là các vấn đề khó khăn hơn và mọi người thực sự quan tâm đến các giải pháp để giải quyết các vấn đề này. Trong phần này, chúng ta sẽ đưa ra ví dụ cho cả hai loại vấn đề đó. Các vấn đề đồ chơi tất nhiên có thể mô tả một cách chính xác, ngắn gọn. Điều đó có nghĩa là các nhà nghiên cứu khác nhau có thể dễ dàng sử dụng các vấn đề này để so sánh việc thực hiện của các giải thuật. Ngược lại, các vấn đề thế giới thực lại không thể có một sự miêu tả một cách đơn giản, nhưng chúng ta sẽ cố gắng đưa ra một cách chung nhất về sự mô tả chính xác các vấn đề này.

Các bài toán Trò chơi

Trò chơi 8 quân cờ (Cờ ta canh)

Một ví dụ của trò chơi 8 quân cờ được chỉ ra trong hình 1, gồm một bảng kích thước 3 x 3 với 8 quân cờ được đánh số từ 1 đến 8 và một ô trống. Một quân cờ đứng cạnh ô trống có thể đi vào ô trống. Mục tiêu là tiến tới vị trí các quân cờ như ở trong hình bên phải. Một mẹo quan trọng cần chú ý là thay vì dùng các toán tử như “ chuyển quân cờ số 4 vào ô trống”, sẽ tốt hơn nếu có các toán tử như “ ô trống thay đổi vị trí với quân cờ chuyển sang bên trái của nó”, bởi vì loại toán tử thứ hai này sẽ ít hơn. Điều đó sẽ giúp chúng ta có các khái niệm như sau:

• Các trạng thái: một sự mô tả trạng thái chỉ rõ vị trí của mỗi quân cờ trong 8 quân cờ ở một trong 9 ô vuông. Để có hiệu quả, sẽ có ích nếu trạng thái bao gồm cả vị trí của ô trống.
• Các toán tử: ô trống di chuyển sang trái, phải, lên trên, đi xuống.
• Kiểm tra mục tiêu: trạng thái khớp với hình dạng chỉ ra
• Chi phí đường đi: mỗi bước đi chi phí là 1, vì vậy chi phí đường đi bằng độ dài của đường đi.

Một ví dụ của trò chơi 8 quân cờ

Trò chơi 8 quân cờ thuộc về loại trò chơi trượt khối. Lớp trò chơi này được biết đến có mức độ hoàn thành NP, vì vậy chúng ta không mong muốn tìm được các phương pháp tốt hơn các thuật toán tìm kiếm đã được mô tả trong chương này và trong các chương tiếp theo. Trò chơi 8 quân cờ và sự mở rộng của nó, trò chơi 15 quân cờ là những vấn đề kiểm tra tiêu chuẩn đối với các giải thuật tìm kiếm trong AI.

Bài toán 8 quân hậu

Mục tiêu của bài toán 8 quân hậu là đặt 8 con hậu trên một bàn cờ vua sao cho không con nào ăn con nào. (Một con hậu sẽ ăn bất cứ con nào nằm trên cùng hàng, cùng cột hoặc cùng đường chéo với nó). Hình 2 chỉ ra một giải pháp cố gắng để giải quyết bài toán nhưng không thành công: con hậu ở cột bên phải nhất bị con hậu ở trên cùng bên trái chiếu.

Mặc dầu các giải thuật đặc biệt hiệu quả tồn tại để giải quyết bài toán này và tập các bài toán tổng quát n con hậu, nó thực sự vẫn là vấn đề rất thú vị dùng để kiểm tra các giải thuật tìm kiếm. Có hai hai loại phương pháp chính. Phương pháp gia tăng bao gồm việc đặt các con hậu từng con một, trong khi phương pháp trạng thái hoàn thành lại bắt đầu với 8 con hậu trên bàn cờ và tiến hành di chuyển các con hậu. Trong cả hai phương pháp, người ta không quan tâm đến chi phí đường đi do chỉ tính đến trạng thái cuối cùng: các giải thuật do đó chỉ được so sánh về chi phí tìm kiếm. Như vậy, chúng ta có việc kiểm tra mục tiêu và chi phí đường đi như sau:

Hình 2 Gần như là một giải pháp đối với bài toán 8 con hậu. ( Giải pháp thực sự được dành cho bạn đọc như một bài tập . )

Một giải pháp với bài toán 8 con hậu

- Kiểm tra mục tiêu: 8 con hậu trên bàn cờ, không con nào ăn con nào

- Chi phí đường đi: bằng không

- Cũng có các trạng thái và các toán tử có thể khác

Hãy xem xét sự công thức hoá

- Các trạng thái: bất cứ sự sắp xếp của từ 0 đến 8 con hậu trên bàn cờ

- Các toán tử: thêm một con hậu vào bất cứ ô nào

- Trong cách công thức hoá này, chúng ta có 648 dãy có thể để thử. Một sự lựa chọn khôn khéo sẽ sử dụng thực tế là việc đặt một con hậu vào ô mà nó đã bị chiếu sẽ không thành công bởi vì việc đặt tất cả các con hậu còn lại sẽ không giúp nó khỏi bị ăn(bị con hậu khác chiếu). Do vậy chúng ta có thể thử cách công thức hoá sau:

- Các trạng thái: là sự sắp xếp của 0 đến 8 con hậu mà không con nào ăn con nào

- Các toán tử: đặt một con hậu vào cột trống bên trái nhất mà nó không bị ăn bởi bất cứ con hậu nào khác.

Dễ thấy rằng các hành động đã đưa ra chỉ có thể tạo nên các trạng thái mà không có sự ăn lẫn nhau; nhưng đôi khi có thể không có hành động nào. Tính toán nhanh cho thấy chỉ có 2057 khả năng có thể để xếp thử các con hậu. Công thức hoá đúng đắn sẽ tạo nên một sự khác biệt rất lớn đối với kích thước của không gian tìm kiếm. Các sự xem xét tương tự cũng sẽ được áp dụng cho cách công thức hoá trạng thái đầy đủ. Chẳng hạn, chúng ta có thể thiết lập vấn đề như sau:

- Các trạng thái: là sự sắp xếp của 8 con hậu, mỗi con trên một cột.

- Các toán tử: di chuyển bất cứ con hậu nào bị chiếu tới một ô khác trên cùng cột.

Cách công thức này sẽ cho phép các giải thuật cuối cùng tìm ra một giải pháp, nhưng sẽ là tốt hơn nếu di chuyển tới ô bị chiếu.

Các bài toán thế giới thực

Tìm kiếm đường đi

Chúng ta đã xem việc tìm kiếm đường đi được định nghĩa như thế nào bằng các thuật ngữ chỉ các vị trí xác định và các phép di chuyển dọc theo các đường nối giữa chúng. Các giải thuật tìm kiếm đường đi được sử dụng trong rất nhiều các ứng dụng, như tìm đường đi trong các mạng máy tính , trong các hệ thống tư vấn du lịch tự động, và trong các hệ thống lập kế hoạch cho các chuyến du lịch bằng máy bay. ứng dụng cuối cùng có lẽ phức tạp hơn, bởi vì du lịch bằng máy bay có chi phí đường đi rất phức tạp, liên quan đến vấn đề tiền nong, chất lượng ghế ngồi, thời gian trong ngày, loại máy bay, các giải thưởng cho các lộ trình bay thường xuyên, v.v Hơn nữa, các hành động trong bài toán không có kết quả được biết đầy đủ: các chuyến bay có thể đến chậm hay đăng ký trước quá nhiều, có thể bị mất liên lạc, sương mù hoặc sự bảo vệ khẩn cấp có thể gây ra sự trì hoãn.

Bài toán người bán hàng rong và các chuyến du lịch

Hãy xét bài toán kinh điển sau: “ Thăm tất cả các thành phố mỗi thành phố thăm ít nhất một lần, khởi hành và kết thúc ở Bucaret”. Điều này rất giống với tìm kiếm đường đi, bởi vì các toán tử vẫn tương ứng với các chuyến đi giữa các thành phố liền kề. Nhưng đối với bài toán này, không gian trạng thái phải ghi nhận nhiều thông tin hơn. Ngoài vị trí của agent, mỗi trạng thái phải lưu lại được các thành phố mà agent đã đi qua. Như vậy, trạng thái ban đầu sẽ là “ ở Bucaret: đã thăm{Bucaret}.”, một trạng thái trung gian điển hình sẽ là “ ở Vaslui: đã thăm {Bucaret, Urziceni, Vaslui}.” và việc kiểm tra mục tiêu sẽ kiểm tra xem agent đã ở Bucaret chưa và tất cả 20 thành phố đã được viếng thăm xong toàn bộ chưa.

Bài toán người bán hàng rong (TSP) là một bài toán du lịch nổi tiếng trong đó mỗi thành phố phải được viếng thăm đúng chính xác một lần. Mục đích là tìm hành trình ngắn nhất. 6 Bài toán có độ phức tạp NP(Karp,1972), nhưng đã có một sự cố gắng rất lớn nhắm cải thiện khả năng của các thuật toán TSP. Ngoài các chuyến đi đã được lập kế hoạch cho người bán hàng rong, những thuật toán này đã được sử dụng cho các nhiệm vụ như lập kế hoạch cho sự dịch chuyển của các mũi khoan trên trên bảng mạch một cách tự động.

Bài toán hành trình ngắn nhất - ứng dụng nguyên lý tham lam (Greedy)

Bài toán: Hãy tìm một hành trình cho người giao hàng đi qua n điểm khác nhau, mỗi điểm đi qua một lần và trở về điểm xuất phát sao cho tổng chiều dài đoạn đường cần đi là ngắn nhất. Giả sử rằng có con đường nối trực tiếp từ giữa hai điểm bất kỳ.

Tất nhiên là có thể giải bài toán này bằng cách liệt kê tất cả các con đường có thể đi, tính chiều dài của mỗi con đường đó rồi tìm con đường có chiều dài ngắn nhất. Tuy nhiên cách giải này có độ phức tạp O(n!) Do đó, khi số đại lý tăng thì số con đường phải xét sẽ tăng lên rất nhanh.

Một cách đơn giản hơn nhiều cho kết quả tương đối tốt là ứng dụng thuật toán heuristic ứng dụng nguyên lý tham lam Greedy. Tư tưởng của thuật giải như sau:

• Điểm khởi đầu, ta liệt kê tất cả các quãng đường từ điểm xuất phát cho đến đại lý rồi chọn đi theo con đường ngắn nhất.

• Khi đã đi đến một đại lý chọn đi đến đại lý kế tiếp cũng theo nguyên tắc trên. Nghĩa là liệt kê tất cả các con đường từ đại lý ta đang đứng đến những đại lý chưa đến. Chọn con đường ngắn nhất. Lặp lại quá trình này cho đến lúc không còn đại lý nào để đi

Bài toán phân việc - ứng dụng của nguyên lý thứ tự

Bài toán: Một công ty nhận được hợp đồng gia công m chi tiết máy J1, J2, … Jm. Công ty có n máy gia công lần lượt là P1, P2, … Pn. Mọi chi tiết đều có thể gia công trên bất kỳ máy gia công nào. Một khi đã gia công một chi tiết trên một máy, công việc sẽ tiếp tục cho đến lúc hoàn thành, không thể bị cắt ngang. Để gia công một việc J1 trên một máy bất kỳ ta cần dùng thời gian tương ứng là t1. Nhiệm vụ của công ty là làm sao để gia công xong toàn bộ n chi tiết trong thời gian sớm nhất.

Chúng ta xét bài toán trong trường hợp có 3 máy P1, P2, P3 và sáu công việc với thời gian là t1 = 2 , t2 = 5, t3 = 8, t4 = 1, t5 = 5, t6 = 1. Có một giải pháp được đặt ra là: Tại thời điểm t = 0, ta tiến hành gia công chi tiết J2 trên máy P1, J5 trên máy P2 và J1 tại P3. Tại thời điểm t = 2 công việc J1 được hoàn thành, trên máy P3 ta gia công tiếp chi tiết J4. Trong lúc đó, hai máy P1 và P2 vẫn đang thực hiện công việc đầu tiên của mình … Theo vậy sau đó máy P3 sẽ tiếp tục hoàn thành nốt các công việc J6 và J3. Thời gian hoàn thành công việc là 12. Ta thấy phương án này đã thực hiện công việc một cách không tốt. Các máy P1 và P2 có quá nhiều thời gian rảnh.

Thuật toán tìm phương án tối ưu L0 cho bài toán này theo kiểu vét cạn có độ phức tạp cỡ O(mn) (với m là số máy và n là số công việc). Bây giờ ta xét đến một thuật giải Heuristic rất đơn giản (độ phức tạp O(n)) để giải bài toán này:

• Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công
• Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều thời gian nhất.

Với tư tưởng như vậy ta hoàn toàn có thể đưa ra một phương án tối ưu L*, thời gian thực hiện công việc bằng 8, đúng bằng thời gian thực hiện công việc J3

Điều khiển Robot

Điều khiển robot là sự tổng quát hoá của bài toán tìm đường đi đã được miêu tả lúc trước. Thay vì một tập các lộ trình rời rạc, một robot có thể di chuyển trong một không gian liên tiếp với (về mặt nguyên lý) một bộ vô hạn các hành động và trạng thái có thể. Để đơn giản, robot tròn di chuyển trên một mặt phẳng, không gian bản chất là hai chiều. Khi robốt có cánh tay và chân mà phải được điều khiển, không gian tìm kiếm trở nên đa chiều. Cần có các kỹ thuật tiên tiến để biến không gian tìm kiếm trở nên hữu hạn. Ngoài sự phức tạp của bài toán còn ở chỗ các robot thật sự phải xử lý các lỗi trong việc đọc thông tin sensor và các bộ điều khiển động cơ.

Sắp xếp dãy

Sự lắp ráp tự động các đối tượng phức tạp được thực hiện bởi rôbốt lần đầu tiên đã được tiến hành bởi robot Freddy (Michie,1972). Sự phát triển kể từ đó khá chậm chạp nhưng chắc chắn nó rất cần cho những nơi lắp ráp phức tạp như lắp ráp điện tử. Trong các bài toán lắp ráp, vấn đề là tìm một thứ tự để lắp ráp các phần của một sản phẩm. Nếu như lựa chọn sai một thứ tự, sẽ không thể lắp thêm một số các bộ phận của sản phẩm nếu như không phải dỡ bỏ một số bộ phận đã lắp ráp lúc trước đó. Kiểm tra một bước trong dãy để đảm bảo tính khả thi là một bài toán tìm kiếm hình học phức tạp rất gần với điều khiển robot. Như vậy, việc sinh ra những bước kế vị hợp lý là khâu đắt nhất trong dây truyền lắp ráp và việc sử dụng các giải thuật tốt để làm giảm việc tìm kiếm là điều cần thiết.

Tìm kiếm các giải pháp

Chúng ta đã xem xét cách làm thế nào để xác định một vấn đề, và làm thế nào để công nhận một giải pháp. Phần còn lại – tìm kiếm một giải pháp- được thực hiện bởi một phép tìm kiếm trong không gian trạng thái. ý tưởng là để duy trì và mở rộng một tập các chuỗi giải pháp cục bộ. Trong phần này, chúng ta chỉ ra làm thế nào để sinh ra những chuỗi này và làm thế nào để kiểm soát được chúng bằng cách sử dụng các cấu trúc dữ liệu hợp lý.

Khởi tạo các chuỗi hành động

Ví dụ để giải quyết bài toán tìm đường đi từ Arad đến Bucaret, chúng ta bắt đầu với trạng thái đầu là Arad. Bước đầu tiên là kiểm tra xem nó có phải là trạng thái đích hay không. Rõ ràng là không, nhưng việc kiểm tra là rất quan trọng để chúng ta có thể giải quyết những việc bị chơi xỏ như “ bắt đầu ở Arad, đi đến Arad”. Do nó không phải là trạng thái đích, chúng ta cần phải xem xét một số trạng thái khác. Điều này được thực hiện bằng cách áp dụng các toán tử cho trạng thái hiện thời, do đó xây dựng nên một tập các trạng thái mới. Quá trình này được gọi là sự mở rộng trạng thái. Trong trường hợp này, chúng ta có ba trạng thái mới, “ở Sibiu”,”ở Timisoara” và “ở Zerind” bởi vì có một đường đi một bước trực tiếp từ Arad đến ba thành phố này. Nếu như chỉ có duy nhất một khả năng, chúng ta sẽ chọn khả năng đó và tiếp tục đi tiếp. Nhưng bất cứ khi nào mà có nhiều khả năng lựa chọn, chúng ta phải quyết định sẽ chọn phương án nào để đi tiếp.

Đây chính là vấn đề cốt yếu của việc tìm kiếm – lựa chọn một vị trí và để các lựa chọn còn lại cho việc lựa chọn sau này nếu như sự lựa chọn đầu tiên không đưa đến một giải pháp. Giả sử chúng ta chọn Zezind. Chúng ta kiểm tra xem nó đã phải là trạng thái đích chưa (nó chưa phải trạng thái đích), và sau đó mở rộng nó để có “ ở Arad “ và “ở Oradea”. Như thế chúng ta có thể chọn một trong hai trạng thái này, hoặc là quay lại và chọn Sibiu hay Timisoara. Chúng ta tiếp tục chọn , kiểm tra và mở rộng cho đến khi tìm được một đường đi, hoặc cho đến khi không còn trạng thái nào nữa để mở rộng. Việc lựa chọn trạng thái nào để mở rộng trước tiên do chiến lược tìm kiếm quyết định.

Các chiến lược tìm kiếm

Công việc chủ yếu của việc tìm kiếm đã chuyển sang việc tìm kiếm một chiến lược tìm kiếm đúng đắn đối với một vấn đề. Trong sự nghiên cứu của chúng ta về lĩnh vực này, chúng ta sẽ đánh giá các chiến lược bằng các thuật ngữ của bốn tiêu chuẩn sau:

- Tính hoàn thành: chiến lược có bảo đảm tìm thấy một giải pháp khi có một vấn đề

- Độ phức tạp thời gian: chiến lược mất bao lâu để tìm ra một giải pháp?

- Độ phức tạp không gian(dung lượng bộ nhớ): chiến lược đó cần bao nhiêu dung lượng bộ nhớ cần thiết để thực hiện việc tìm kiếm.

- Tính tối ưu: chiến lựơc có tìm được giải pháp có chất lượng cao nhất khi có một số các giải pháp khác nhau?

Phần này sẽ nói đến 6 chiến lược tìm kiếm mà được sử dụng dưới tiêu đề tìm kiếm không đủ thông tin (uninformed search). Thuật ngữ này có nghĩa là không có các thông tin về số các bước hay chi phi đường đi từ trạng thái hiện tại cho tới đích – tất cả những gì chúng có thể làm là phân biệt một trạng thái đích với một trạng thái không phải là trạng thái đích. Tìm kiếm không có thông tin đầy đủ đôi khi còn được gọi là tìm kiếm mù (blind search).

Tìm kiếm theo chiều rộng

Một chiến lược tìm kiếm đơn giản là tìm kiếm theo chiều rộng. Trong chiến lược này, nút gốc được mở rộng trước tiên, sau đó đến lượt tất cả các nút mà được sinh ra bởi nút gốc được mở rộng, và sau đó tiếp đến những nút kế tiếp của chúng và cứ như vậy. Nói một cách tổng quát, tất cả các nút ở độ sâu d trên cây tìm kiếm được mở rộng trước các nút ở độ sâu d+1. Tìm kiếm theo chiều rộng có thể được thực hiện bằng cách gọi giải thuật general-search với một hàm hàng đợi mà đưa các trạng thái mới được sinh ra vào cuối của hàng đợi, đứng sau tất cả các trạng thái mà đã được sinh ra trước nó:

Tìm kiếm trên một cây nhị phân đơn giản

Tìm kiếm theo chiều rộng là một chiến lược rất có phương pháp (có hệ thống) bởi vì nó xem xét tất cả các đường đi có độ dài bằng 1 trước, sau đó đến tất cả những đường đi có độ dài bằng 2, và cứ như vậy. Hình 3 chỉ ra quá trình của sự tìm kiếm trên một cây nhị phân đơn giản. Nếu như có một giải pháp, tìm kiếm theo chiều rộng đảm bảo sẽ tìm được nó, và nếu có nhiều giải pháp, tìm kiếm theo chiều rộng sẽ luôn tìm ra trạng thái đích nông nhất trước tiên. Dưới thuật ngữ của 4 tiêu chuẩn, tìm kiếm theo chiều rộng là hoàn thành, và nó được cung cấp một cách tối ưu chi phí đường dẫn bằng một hàm tăng của độ sâu các nút.

Chúng ta phải xem xét thời gian và dung lượng bộ nhớ nó sử dụng để hoàn thành một cuộc tìm kiếm. Để làm điều này, chúng ta xem xét một không gian trạng thái có tính giả thiết trong đó mỗi trạng thái có thể được mở rộng để tạo ra các trạng thái mới b. Chúng ta nói rằng yếu tố phân nhánh của những trạng thái này (và của cây tìm kiếm) là b. Gốc của cây tìm kiếm sinh ra b nút ở mức đầu tiên, mỗi nút đó lại sinh ra thêm b nút, và sẽ có cả thảy b2 nút ở mức thứ hai. Mỗi một nút này lại sinh ra thêm b nút, tạo ra b3 nút ở mức thứ ba, và cứ như vậy. Bây giờ chúng ta giả sử rằng giải pháp cho bài toán này có độ dài đường đi là d, như vậy số nút tối đa được mở rộng trước khi tìm thấy một giải pháp là:

1 + b + b2 + b3 +.. . . + b d

Đây là số nút tối đa, nhưng giải pháp có thể được tìm thấy ở bất cứ điểm nào thuộc mức có độ sâu là d. Do đó, trong trường hợp tốt nhất , số lượng các nút sẽ ít hơn.

Tìm kiếm với chi phí thấp nhất

Phép tìm kiếm theo chiều rộng tìm được trạng thái đích, nhưng trạng thái này có thể không phải là giải pháp có chi phí thấp nhất đối với một hàm chi phí đường đi nói chung. Tìm kiếm với chi phí thấp nhất thay đổi chiến lược tìm kiếm theo chiều rộng bằng cách luôn luôn mở rộng nút có chi phí thấp nhất (được đo bởi công thức tính chi phí được đi g(n)), thay vì mở rộng nút có độ sâu nông nhất. Dễ thấy rằng tìm kiếm theo chiều rộng chính là tìm kiếm với chi phí thấp nhất với g(n)= DEPTH(n).

Khi đạt được những điều kiện nhất định, giải pháp đầu tiên được tìm thấy sẽ đảm bảo là giải pháp rẻ nhất, do nếu như có một đường đi khác rẻ hơn, nó đã phải được mở rộng sớm hơn và như vậy nó sẽ phải được tìm thấy trước. Việc quan sát các hành động của chiến lược sẽ giúp giải thích điều này. Hãy xem xét bài toán tìm đường đi. Ván đề là đi từ S đến G, và chi phí của mỗi toán tử được ghi lại. Đầu tiên chiến lược sẽ tiến hành mở rộng trạng thái ban đầu, tạo ra đường đi tới A, B và C. Do đường đi tới A là rẻ nhất, nó sẽ tiếp tục được mở rộng, tạo ra đường đi SAG mà thực sự là một giải pháp, mặc dù không phải là phương án tối ưu. Tuy nhiên, giải thuật không công nhận nó là một giải pháp, bởi vì nó chi phí là 11, và nó bị che bởi đường đi SB có chi phí là 5 ở trong hàng đợi. Dường như thật là xấu hổ nếu sinh ra một giải pháp chỉ nhằm chôn nó ở sâu trong hàng đợi, nhưng điều đó là cần thiết nếu chúng ta muốn tìm một giải pháp tối ưu chứ không đơn thuần là tìm bất cứ giải pháp nào. Bước tiếp theo là mở rộng SB, tạo ra SBG, và nó là đường đi rẻ nhất còn lại trong hàng đợi, do vậy mục tiêu được kiểm tra và đưa ra một giải pháp.

Phép tìm kiếm chi phí ít nhất tìm ra giải pháp rẻ nhất thoả mãn một yêu cầu đơn giản: Chi phí của một đường đi phải không bao giờ giảm đi khi chúng ta đi dọc theo đường đi. Nói cách khác, chúng ta mong muốn rằng

g(Successor(n))≥ g(n) với mọi nút n.

Giới hạn đối với chi phí đường đi không được giảm thực sự sẽ là vấn đề cần quan tâm nếu chi phí đường đi của một nút là tổng chi phí của các toán tử mà tạo nên đường đi. Nếu như mọi toán tử có một chi phí không âm, thì chi phí của đường đi không bao giờ có thể giảm đi khi chúng ta đi dọc theo đường đi và phép tìm kiếm với chi phí giống nhau có thể tìm được đường đi rẻ nhất mà không cần kiểm tra hết toàn bộ cây. Nhưng nếu một số toán tử có chi phí âm thì chẳng có một cách tìm kiếm nào khác ngoài một phép tìm kiếm toàn bộ tất cả các nút để tìm ra giải pháp tối ưu, bởi vì chúng ta sẽ không bao giờ biết được rằng khi nào một đường đi sẽ chuyển sang một bước với chi phí âm cao và do đó trở thành đường đi tốt nhất trong tất cả các đường đi, bất kể là nó dài bao nhiêu và chi phí thế nào.

Tìm kiếm chiều sâu

Tìm kiếm theo chiều sâu luôn luôn mở rộng một trong các nút ở mức sâu nhất của cây. Chỉ khi phép tìm kiếm đi tới một điểm cụt (một nút không phải đích mà không có phần mở rộng), việc tìm kiếm sẽ quay lại và mở rộng đối với những nút nông hơn. Chiến lược này có thể được thực hiện bởi General-search với một hàm hàng đợi mà luôn đưa các trạng thái mới được sinh ra vào trước hàng đợi. Do nút được mở rộng là sâu nhất, các nút kế tiếp của nó thậm chí sẽ sâu hơn và khi đó sẽ trở thành sâu nhất. Quá trình tìm kiếm được minh hoạ trong hình 4.

Tìm kiếm theo chiều sâu

Phép tìm kiếm theo chiều sâu yêu cầu dung lượng bộ nhớ rất khiêm tốn. Như hình vẽ cho thấy, nó chỉ cần phải lưu một đường duy nhất từ gốc tới nút lá, cùng với các nút anh em với các nút trên đường đi chưa được mở rộng còn lại. Đối với một không gian trạng thái với hệ số rẽ nhánh b và độ sâu tối đa m, phép tìm kiếm theo chiều sâu chỉ yêu cầu lưu trữ bm nút, ngược lai so với bd nút mà phép tìm kiếm theo chiều rộng yêu cầu trong trường hợp mục tiêu nông nhất ở độ sâu d.

Độ phức tạp thời gian của phép tìm kiếm sâu là O(bm). Đối với những vấn đề mà có rất nhiều giải pháp, phép tìm kiếm sâu có thể nhanh hơn tìm kiếm rộng, bởi vì nó có một cơ hội tốt tìm ra một giải pháp chỉ sau khi khám phá một phần nhỏ của toàn bộ không gian. Tìm kiếm theo chiều rộng sẽ vẫn phải tìm tất cả các đường đi có độ sâu d-1 trước khi xem xét bất cứ đường đi nào có độ sâu d. Phép tìm kiếm theo chiều sâu vẫn cần thời gian O(bm) trong trường hợp tồi nhất.

Mặt hạn chế của phép tìm kiếm sâu là nó có thể bị tắc khi đi theo một đường sai. Rất nhiều bài toán có các cây tìm kiếm rất sâu, thậm chí vô hạn, vì vậy tìm kiếm sâu sẽ không bao giờ có thể quay trở lại được một trong các nút gần đỉnh của cây sau khi có một sự lựa chọn sai. Phép tìm kiếm sẽ luôn luôn tiếp tục đi xuống mà không quay trở lại, thậm chí khi có một giải pháp ở mức rất nông tồn tại. Như vậy đối với những bài toán này, phép tìm kiếm sâu sẽ hoặc là bị sa lầy trong một vòng lặp vô hạn và không bao giờ đưa ra một giải pháp, hoặc là cuối cùng nó có thể đưa ra một đường đi giải pháp mà dài hơn so với phương án tối ưu. Điều đó có nghĩa là phép tìm kiếm theo chiều sâu là không hoàn thành và không tối ưu. Bởi vì điều này, cần tránh sử dụng phép tìm kiếm sâu cho các cây tìm kiếm có độ sâu tối đa là vô hạn hoặc rất sâu.

Việc thực hiện phép tìm kiếm sâu với general-search là khá tầm thường:

Người ta thường thực hiện phép tìm kiếm sâu cùng với một hàm đệ qui mà gọi tới chính nó ở lần lượt mỗi con của nó. Trong trường hợp này, hàng đợi được lưu trữ hoàn toàn trong không gian địa phương của mỗi lần gọi trong ngăn xếp gọi.

Tìm kiếm theo độ sâu giới hạn

Tìm kiếm theo độ sâu giới hạn tránh các bẫy mà tìm kiếm theo chiều sâu mắc phải bằng cách đặt một giới hạn đối với độ sâu tối đa của đường đi. Giới hạn này có thể được thực hiện với một giải thuật tìm kiếm theo độ sâu giới hạn đặc biệt hoặc sử dụng các giải thuật tìm kiếm tổng quát với các toán tử theo dõi độ sâu. Chẳng hạn, trên bản đồ Rumani, có 20 thành phố, vì vậy chúng ta biết rằng nếu như có một giải pháp, thì nó phải có độ dài nhiều nhất là bằng 19. Chúng ta có thể thực hiệnviệc giới hạn độ sâu bằng cách sử dụng các toán tử dưới dạng “ Nếu bạn ở thành phố A và vừa đi một đoạn đường ít hơn 19 bước, thì khởi tạo một trạng thái mới ở thành phố B với độ dài đường đi lớn hơn 1”. Với tập các toán tử mới này, chúng ta đảm bảo tìm thấy giải pháp nếu nó tồn tại, nhưng chúng ta vẫn không đảm bảo tìm thấy giải pháp ngắn nhất trước tiên: phép tìm kiếm theo chiều sâu giới hạn là hoàn thành nhưng không tối ưu. Nếu chúng ta chọn một giới hạn độ sâu mà quá nhỏ, thì phép tìm kiếm theo chiều sâu giới hạn thậm chí không hoàn thành. Độ phức tạp về không gian và thời gian của phép tìm kiếm theo chiều sâu giới hạn tương đương với phép tìm kiếm sâu. Nó mất O(bl) thời gian và O(bl) không gian, với l là giới hạn độ sâu.

Tìm kiếm lặp dần (Iterative Deepening Search)

Thành phần khó khăn của tìm kiếm theo độ sâu giới hạn đem lại một giới hạn khá tốt. Chúng ta lấy 19 như là một giới hạn độ sâu “hiển nhiên” cho bài toán Rumani, nhưng thực ra nếu chúng ta nghiên cứu kỹ bản đồ, chúng ta sẽ thấy rằng bất cứ thành phố nào cũng có thể đi đến được từ bất kỳ thành phố nào khác với nhiều nhất là 9 bước. Con số này, được biết đến như là đường kính của không gian trạng thái , cho chúng ta một giới hạn độ sâu tốt hơn, và đưa đến một phép tìm kiếm theo độ sâu giới hạn hiệu quả hơn. Tuy nhiên, đối với hầu hết các bài toán, chúng ta chỉ biết một giới hạn độ sâu tốt sau khi đã giải quyết xong bài toán.

Giải thuật tìm kiếm lặp sâu dần

Phép tìm kiếm lặp sâu dần là một chiến lược né tránh vấn đề lựa chọn giới hạn độ sâu tốt nhất và cố gằng thử tất cả các giơí hạn độ sâu có thể: đầu tiên thử độ sâu bằng 0, sau đó độ sâu bằng 1, tiếp theo là 2, và cứ như vậy. Về mặt hiệu quả, việc lặp sâu dần kết hợp lợi ích của cả hai phép tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng. Đây là phương pháp tối ưu và đầy đủ, giống như phép tìm kiếm theo chiều rộng, nhưng chỉ yêu cầu bộ nhớ rất ít như phép tìm kiếm sâu yêu cầu. Thứ tự mở rộng các trạng thái tương tự với tìm kiếm rộng, ngoại trừ việc một số trạng thái được mở rộng nhiều lần.

Phép tìm kiếm lặp sâu dần có thể dường như là hơi lãng phí, bởi vì có rất nhiều trạng thái được mở rộng nhiều lần. Tuy nhiên, đối với hầu hết các bài toán, tổng chi phí của sự mở rộng nhiều lần này thực ra khá nhỏ. Bằng trực giác, có thể thấy rằng trong một cây tìm kiếm theo luật số mũ, hầu hết tất cả các nút là ở mức thấp nhất, vì vậy việc các mức ở bên trên được mở rộng nhiều lần sẽ không thành vấn đề lắm. nhắc lại rằng số lần mở rộng trong phép tìm kiếm theo độ sâu giới hạn tới độ sâu d với hệ số phân nhánh b là:

1+ b + b 2 + ….+ bd - 2 + b d - 1 + bd

Cụ thể, cho b=10, và d=5 thì số lần mở rộng là :

1+1 0 +10 0 +1000+10.0 0 0+100 . 00 0 = 111.111

Trong phép tìm kiếm lặp sâu dần, các nút ở mức dưới cùng được mở rộng một lần, những nút ở trên mức dưới cùng được mở rộng hai lần, và cứ như vậy đến gốc của cây tìm kiếm sẽ được mở rộng d+1 lần. Do đó tổng số lần mở rộng trong một phép tìm kiếm lặp sâu dần là :

( d +1 ) 1 + ( d ) b + ( d -1 ) b 2 + …. . + 3bd - 2 + 2b d -1 + 1 bd

Và cụ thể lại cho b=10, và d=5 thì số lần mở rộng là :

6+5 0 +40 0 +3000+20.0 0 0+10 0 00 0 = 123.456

Như vậy chúng ta thấy, một phép tìm kiếm lặp sâu dần từ độ sâu1 xuống tới độ sâu d chỉ mở rộng nhiều hơn khoảng11% số nút so với phép tìm kiếm theo chiều rộng hay phép tìm kiếm theo chiều sâu tới độ sâu d khi hệ số phân nhánh b=10. Hệ số phân nhánh càng cao, tổng số các trạng thái được mở rộng lặp lại (nhiều lần) càng thấp, nhưng thậm chí khi hệ số phân nhánh là 2, phép tìm kiếm lặp sâu dần chỉ mở rộng số trạng thái nhiều gấp hai so với một phép tìm kiếm theo chiều rộng đầy đủ. Điều đó có nghĩa rằng độ phức tạp thời gian của phép tìm kiếm lặp sâu dần vẫn là O(bd), độ phức tạp không gian là O(bd). Nói chung, lặp sâu dần là phép tìm kiếm được tham khảo đến khi có một không gian tìm kiếm lớn và độ sâu của giải pháp là không biết trước.

Tìm kiếm tiến lùi

Ý tưởng của phép tìm kiếm tiến lùi là thực hiện đồng thời hai phép tìm kiếm: tìm kiếm từ trạng thái đầu về phía trước và tìm kiếm ngược lại từ trạng thái đích, và dừng lại khi hai phép tìm kiếm này gặp nhau.

Đối với những bài toán mà hệ số rẽ nhánh là b ở cả hai hướng, phép tìm kiếm tiến lùi có thể đưa lại một sự khác biệt rất lớn. Nếu chúng ta vẫn giả sử rằng có một giải pháp ở độ sâu d, thì giải pháp sẽ được tìm thấy sau O(2bd/2) = O(bd/2) bước, bởi vì mỗi phép tìm kiếm tiến và lùi chỉ phải đi một nửa quãng đường. Xét ví dụ cụ thể, với b=10 và d=6, phép tìm kiếm rộng sinh ra 1.111.111 nút, trong khi đó phép tìm kiếm tiến lùi thành công khi mỗi hướng ở độ sâu bằng 3, tại thời điểm 2.222 nút đã được tạo ra. Điều này về mặt lý thuyết nghe rất hấp dẫn. Chúng ta cần phải xem xét một số vấn đề trước khi thực hiện giải thuật.

Câu hỏi chính là, tìm kiếm lùi từ đích có nghiã là như thế nào? Chúng ta định nghĩa các nút tổ tiên (predecessor) của một nút n là tất cả các nút mà có nút n là nút kế vị (successor). Phép tìm kiếm lùi có nghĩa là sinh ra những nút tổ tiên liên tiếp bắt đầu từ nút đích.

Khi tất cả các toán tử là có thể đảo ngược, các tập kế vị và tập tổ tiên là giống hệt nhau. Tuy nhiên, đối với một số bài toán, việc tính toán các phần tử tổ tiên là rất khó khăn.

Con số O(bd/2)của độ phức tạp thừa nhận rằng quá trình kiểm tra sự giao nhau của hai biên giới có thể được thực hiện trong một khoảng thời gian không đổi (như vậy, nó không phụ thuộc vào số trạng thái). Điều này thường có thể thu được với một bảng băm. Để hai phép tìm kiếm cuối cùng sẽ gặp nhau, tất cả các nút của ít nhất một trong hai phép tìm kiếm phải được lưu giữ trong bộ nhớ (giống như với trường hợp của phép tìm kiếm rộng). Điều này có nghĩa là độ phức tạp không gian của phép tìm kiếm tiến lùi không có đủ thông tin là O(bd/2).

So sánh các chiến lược tìm kiếm

Tiêu chuẩn	Tìm kiếm theo chiều rộng	Tìm kiếm chi phí thấp nhất	Tìm kiếm theo độ sâu	Tìm kiếm theo độ sâu giới hạn	Tìm kiếm lặp sâu dần	Tìm kiếm tiến lùi
Thời gian Không gian Có tối ưukhông?Có hoàn thành?	bd bd Có Có	bd bd Có Có	bm bm Không Không	bl bl KhôngCó, nếu l ≥ d	bd bd Có Có	bd/2bd/2CóCó
Đánh giá các chiến lược tìm kiếm, b là hệ số phân nhánh, d là độ sâu của giải pháp; m là độ sâu tối đa của cây tìm kiếm; l là giới hạn độ sâu

Cho đến lúc này, chúng ta đã xét tất cả các vấn đề ngoại trừ còn một trong những vấn đề phức tạp nhất của quá trình tìm kiếm, đó là: khả năng lãng phí thời gian do việc mở rộng các trạng thái mà đã gặp và đã được mở rộng trước đó trên một số đường đi. Đối với một số bài toán, khả năng này không bao giờ xảy ra, mỗi trạng thái chỉ được đi đến theo một con đường. Việc xác định chính xác vấn đề bài toán 8 con hậu rất có tác dụng, đó là mỗi trạng thái chỉ có thể nhận được thông qua một đường đi.

Đối với rất nhiều bài toán, các trạng thái bị lặp lại là điều không thể tránh khỏi. Điều này có ở tất cả các bài toán mà các toán tử là có thể đảo ngược, như các bài toán tìm đường đi và bài toán những nhà truyền giáo và những kẻ ăn thịt người. Các cây tìm kiếm cho những bài toán này là vô hạn, nhưng nếu chúng ta tỉa bớt một số trạng thái lặp lại, chúng ta có thể cắt cây tìm kiếm xuống còn kích thước hữu hạn, chỉ sinh ra một phần của cây mà mở rộng đồ thị không gian trạng thái. Thậm chí khi cây là hữu hạn, việc tránh các trạng thái lặp có thể dẫn đến một sự suy giảm theo cấp số mũ chi phí tìm kiếm. Một ví dụ kinh điển được mô tả ở hình 4. Không gian chỉ chứa m+1 trạng thái, với m là độ sâu tối đa. Do cây bao gồm mỗi đường đi có thể trong không gian, nó có 2m nhánh.

Các phương pháp tìm kiếm có đầy đủ thông tin

Phần trước đã chỉ ra rằng các chiến lược tìm kiếm không đầy đủ thông tin có thể tìm thấy giải pháp đối với các bài toán bằng cách tạo ra một cách có hệ thống các trạng thái mới và kiểm tra chúng với mục tiêu. Điều không may là, những chiến lược này rõ ràng là không có hiệu quả trong hầu hết các trường hợp. Phần này cho một chiến lược tìm kiếm có thêm hiểu biết (có đủ thông tin the- một chiến lược sử dụng các tri thực đặc thù đối với bài toán - có thể tìm các giải pháp một cách hiệu quả hơn như thế nào. Phần này cũng chỉ ra các bài toán tối ưu có thể được giải quyết.

Phương pháp tìm kiếm tốt nhất (Best-first)

Một phương pháp tìm kiếm tốt nhất sử dụng các giải thuật tìm kiếm tổng quát

Trong chương trước, chúng ta đã tìm thấy một số cách để áp dụng các tri thức cho qui trình xác định rõ ràng chính xác một vấn đề bằng các thuật ngữ về trạng thái và các toán tử. Tuy nhiên, khi chúng ta được đưa cho một bài toán mà được chỉ rõ cụ thể, các sự lựa chọn của chúng ta là có giới hạn. Nếu chúng ta sử dụng giải thuật tìm kiếm tổng quát, thì cách duy nhất có thể áp dụng được tri thức là hàm "hàng đợi”, hàm quyết định nút nào sẽ được mở rộng tiếp theo. Thông thường, tri thức để quyết định điều này được cung cấp bởi một hàm định giá trả về một số có nghĩa mô tả sự mong muốn được mở rộng nút. Khi các nút được xếp thứ tự để nút nào có định giá tốt nhất sẽ được mở rộng trước. Chiến lược như vậy được gọi là phép tìm kiếm tốt nhất (best-first). Nó có thể được cài đặt trực tiếp với tìm kiếm tổng quát, như hình 2.6.

Tên gọi “tìm kiếm tốt nhất” là phép tìm kiếm quan trọng nhưng không chính xác. Nếu chúng ta mở rộng nút tốt nhất trước tiên, đó không phải là phép tìm kiếm - đó là một cách đi thẳng đến mục tiêu. Điều có thể làm là chọn nút tỏ ra là tốt nhất theo hàm giá. Nếu hàm giá là rõ, thì nút này sẽ là nút tốt nhất. Trong thực tế, hàm giá thỉnh thoảng có sai sót và việc tìm kiếm bị lạc đường. Tuy nhiên, chúng ta sẽ dùng tên “tìm kiếm tốt nhất”, vì tên “tìm kiếm vẻ ngoài tốt nhất“ có vẻ không tiện.

Khi có một họ giải thuật tìm kiếm tổng quát với các hàm theo thứ tự khác nhau, tồn tại một họ các giải thuật tìm kiếm tốt nhất với các hàm giá khác nhau. Vì mục đích là tìm kiếm các giải pháp có chi phí thấp, những giải thuật này sử dụng phướng pháp đánh giá các chi phí của giải pháp và cố gắng tối thiểu nó. Chúng ta có một phương pháp đo: sử dụng chi phí đường đi gđể quyết định đường đi nào sẽ mở. Tuy nhiên, phương pháp này không tìm trực tiếp về phía đích. Để làm chụm phép tìm kiếm, phương pháp kết hợp một số cách đánh giá chi phí đường đi từ một trạng thái tới trạng thái đích gần nhất. Xét hai phương pháp cơ bản. Phương pháp thứ nhất mở nút gần đích nhất. Phương pháp thứ hai mở nút ở đường đi có chi phí ít nhất.

Tối thiểu hoá chi phí đánh giá để đi tới mục tiêu: phép tìm kiếm tham lam

Một trong những chiến lược tìm kiếm tốt nhất trước đơngiản nhất là tối thiểu chi phí ước lượng để đi tới mục tiêu. Đó là, nút mà trạng thái của nó được đánh giá là gần với trạng thái mục tiêu nhất luôn luôn được mở rộng trước. Đối với hầu hết các bài toán, chi phí của việc đi tới đích từ một trạng thái nào đó có thể được ước lượng nhưng không thể xác định chính xác. Một hàm mà tính toán những ước lượng chi phí như vậy được gọi là hàm heuristic và thường được biểu diễn bằng chữ cái h:

h(n) = chi phí ước lượng của đường đi rẻ nhất từ trạng thái ở nút n tới trạng thái đích. Một phép tìm kiếm tốt nhất trước mà sử dụng h để lựa chọn nút mở rộng tiếp theo được gọi là phương pháp tìm kiếm tham lam(greedy search), vì các lý do mà chúng ta sẽ thấy rõ ràng sau đây. Cho một hàm heuristic h, phép tìm kiếm tham lam có thể được thực hiện như sau:

Nói một cách chính thức, h có thể là bất cứ hàm nào. Chúng ta sẽ chỉ yêu cầu là h(n) = 0 nếu n là một mục tiêu.

Để hình dung một hàm heuristic là như thế nào, chúng ta cần chọn một bài toán điển hì