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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

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

SearchInNode.jpg

เป็นตัวอย่างของการค้นหาแบบดีที่สุดก่อน ขั้นตอนนี้เริ่มจากตอน 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. }
    

ตัวอย่างการทำงาน[แก้]

GraphBFS.jpg BestFirstSearch.jpg

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

Pic1BFS.jpg

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

Best first search มีประสิทธิภาพเชิงเวลาเป็น O (bm) [4]

b คือ จำนวนปมลูกเฉลี่ยในแต่ละปม
m คือ ความสูงของต้นไม้ที่ลึกที่สุด

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

อ้างอิง[แก้]

  1. Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
  2. แม่แบบ:Russell Norvig 2003 -- Chapter 4
  3. http://www.it.uu.se/edu/course/homepage/ai/vt05/sok.pdf
  4. Book Reference: Artificial Intelligence: A Modern Approach, 4.1