ผู้ใช้:Seighart

Best first search

Best first search คืออัลกอริทึมในการผ่านปมกราฟ เป็นการนำข้อดีของ Breadth first search และ Depth first search มารวมกัน โดย Best first search จะเลือก Node ที่มีค่าดีสุดซึ่งอาศัย heuristic function ในการหา

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

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

การท่องไปในต้นไม้ของ Best first search

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

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