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

การค้นแบบดีที่สุด () คือขั้นตอนวิธีในการค้นหาในกราฟ เป็นการนำข้อดีของการค้นหาตามแนวกว้าง และการค้นหาตามแนวลึกมารวมกัน โดยการค้นหาแบบดีที่สุด จะเลือกจุดยอดที่มีค่าดีสุดซึ่งอาศัยฮิวริสติกฟังก์ชัน ในการหาPearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.

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

หรือก็คือ การค้นหาแบบดีที่สุดเป็นกระบวนการค้นหาข้อมูลที่ได้นำเอาข้อดีของทั้งการค้นหาตามแนวลึกและการค้นหาตามแนวกว้าง มารวมกันเป็นวิธีการเดียว โดยที่แต่ละขั้นของการค้นหาในโหนดลูกนั้น การค้นหาแบบดีที่ดีก่อนจะเลือกเอา โหนดที่ดีที่สุด (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 คะแนนตามลำดับ ทำเช่นนี้เรื่อย ๆ จนพบคำตอบหรือจนไม่สามารถ สร้างโหนดต่อไปได้อีก
(หมายเหตุ ในการเลือกนี้จะเลือกค่ามากสุด หรือน้อยสุดก็ได้ ขึ้นอยู่กับลักษณะของปัญหา)

 รหัสเทียมแสดงการทำงาน 
Open = priority queue
Open.add (sourceNode)
Close = empty list
While (!Open.empty () ) {
N = Open.removeBestNode
Close.add (N)
If (N == targetNode) {
Backtrack Parent to Path
Return Path
}
For (A is each adjacency node of N) {
Open.add (A)
If (!Close.exist (A) ) {
H = Heuristic (A)
Open.add (H)
Parent[A] = N
}else{
If (New path is better)
Parent[A]=N
Update cost
}
}
}

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

400px
400px

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

 การวิเคราะห์ประสิทธิภาพเชิงเวลา 
Best first search มีประสิทธิภาพเชิงเวลาเป็น O (bm) Book Reference: Artificial Intelligence: A Modern Approach, 4.1
 b คือ จำนวนปมลูกเฉลี่ยในแต่ละปม
 m คือ ความสูงของต้นไม้ที่ลึกที่สุด
โดยฮิวริสติกฟังก์ชันที่ดีจะช่วยให้ประสิทธิภาพการทำงานดีขึ้น แต่ถ้าฮิวริสติกฟังก์ชันไม่ดีก็จะทำให้การค้นหาช้าหรืออาจไม่เจอคำตอบเลยก็ได้

 อ้างอิง 

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:ขั้นตอนวิธีการค้นหา