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

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

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

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
}
}
}

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

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

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

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

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

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

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