การค้นแบบดีที่สุด

การค้นแบบดีที่สุด (อังกฤษ: 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 คือ ความสูงของต้นไม้ที่ลึกที่สุด

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

อ้างอิง

1. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
2. -- 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