การค้นหาตามค่าดีสุด

การค้นแบบดีที่สุด (อังกฤษ: Best first search) คือขั้นตอนวิธีในการค้นหาในกราฟ เป็นการนำข้อดีของการค้นหาตามแนวกว้าง และการค้นหาตามแนวลึกมารวมกัน โดยการค้นหาแบบดีที่สุด จะเลือกจุดยอดที่มีค่าดีสุดซึ่งอาศัยฮิวริสติกฟังก์ชัน ในการหา

ฮิวริสติกฟังก์ชัน ใช้หลักการของ ขั้นตอนวิธีแบบละโมบ เป็นการคาดเดาอย่างมีเหตุผลแต่อาจไม่ใช่คำตอบที่สมบูรณ์ โดยจะแปลงจากสถานะปัจจุบันไปเป็นตัวเลข ซึ่งตัวเลขนี้จะบ่งบอกว่าเข้าใกล้เป้าหมายมากน้อยเพียงใด ซึ่งฮิวริสติกฟังก์ชันจะช่วยบอกว่าควรไปในทิศทางใด ถ้าฟังก์ชันดีก็จะกระจายโหนดน้อยเข้าสู่เป้าหมายได้ไว ถ้าฟังก์ชันไม่ดีอาจค้นหาผิด ได้คำตอบที่ไม่ดีที่สุด หรือคำตอบผิดไปเลยก็ได้ โดยเฉลี่ยแล้วจะค้นหาได้ดีกว่าการค้นหาตามแนวกว้างและการค้นหาตามแนวลึก

หรือก็คือ การค้นหาแบบดีที่สุดเป็นกระบวนการค้นหาข้อมูลที่ได้นำเอาข้อดีของทั้งการค้นหาตามแนวลึกและการค้นหาตามแนวกว้าง มารวมกันเป็นวิธีการเดียว โดยที่แต่ละขั้นของการค้นหาในโหนดลูกนั้น การค้นหาแบบดีที่ดีก่อนจะเลือกเอา โหนดที่ดีที่สุด (most promising) และการที่จะทราบว่าโหนดใดดีที่สุดนี้สามารถทำได้โดยอาศัยฮิวริสติกฟังก์ชัน ซึ่งฮิวริสติก ฟังก์ชันนี้จะทำหน้าที่เหมือนตัววัดผล และให้ผลของการวัดนี้ออกมาเป็นคะแนน

การท่องไปในต้นไม้ค้นหาแบบดีที่สุด

เป็นตัวอย่างของการค้นหาแบบดีที่สุดก่อน ขั้นตอนนี้เริ่มจากตอน 1 สร้างโหนดราก (root node) ในขั้นตอน 2 สร้างโหนดลูก B และ C แล้วตรวจสอบโหนด B และ C ด้วยฮิวริสติกฟังก์ชัน ได้ผลออกมาเป็นคะแนนคือ 3 และ 1 ตามลำดับ จากนั้นให้เลือกโหนด C เป็นโหนดต่อไปที่เราสนใจ เพราะมีค่าน้อยกว่า แล้วสร้างโหนด ลูกให้กับโหนด C ในขั้นตอน 3 ได้โหนด D และ E แล้วตรวจสอบคะแนนได้ 4 และ 6 ตามลำดับ จากนั้นทำการเปรียบเทียบค่าของโหนดท้ายสุด หรือเทอร์มินอลโหนด (terminal node) ทุกโหนดว่าโหนดใดมีค่าดีที่สุด ในที่นี้จะต้องเลือกโหนด B เพราะมีคะแนนเพียง 3 (เลือกคะแนนต่ำสุด) แล้วสร้างโหนดลูกตามขั้นตอน 4 ได้ F และ G แล้วตรวจสอบคะแนนได้ 6 และ 5 คะแนนตามลำดับ ทำเช่นนี้เรื่อย ๆ จนพบคำตอบหรือจนไม่สามารถ สร้างโหนดต่อไปได้อีก (หมายเหตุ ในการเลือกนี้จะเลือกค่ามากสุด หรือน้อยสุดก็ได้ ขึ้นอยู่กับลักษณะของปัญหา)

รหัสเทียมแสดงการทำงาน

1. Open = priority queue
   

2. Open.add (sourceNode)
   

3. Close = empty list
   

4. While (!Open.empty () ) {
   

5. N = Open.removeBestNode
   

6. Close.add (N)
   

7. If (N == targetNode) {
   

8. Backtrack Parent to Path
   

9. Return Path
   

10. }
    

11. For (A is each adjacency node of N) {
    

12. Open.add (A)
    

13. If (!Close.exist (A) ) {
    

14. H = Heuristic (A)
    

15. Open.add (H)
    

16. Parent[A] = N
    

17. }else{
    

18. If (New path is better)
    

19. Parent[A]=N
    

20. Update cost
    

21. }
    

22. }
    

23. }
    

ตัวอย่างการทำงาน

จากรูปและรหัสเทียมด้านบนจะได้รายการของ Open และ Close ดังนี้

การวิเคราะห์ประสิทธิภาพเชิงเวลา

Best first search มีประสิทธิภาพเชิงเวลาเป็น O (b^m)

b คือ จำนวนปมลูกเฉลี่ยในแต่ละปม

m คือ ความสูงของต้นไม้ที่ลึกที่สุด

โดยฮิวริสติกฟังก์ชันที่ดีจะช่วยให้ประสิทธิภาพการทำงานดีขึ้น แต่ถ้าฮิวริสติกฟังก์ชันไม่ดีก็จะทำให้การค้นหาช้าหรืออาจไม่เจอคำตอบเลยก็ได้