วันศุกร์ที่ 21 สิงหาคม พ.ศ. 2558
การค้นหา
จุดเริ่มต้นคือstart state พิจารนาสถานะเป้าหมาย goal state ถ้าไม่ใช่ต้องหาเป้าหมายต่อไป การค้นหาต้องค้นหาจากระยะทางที่ใกล้ที่สุดก่อน ทำให้ค้นหาง่ายขึ้น
ส่วนประกอบการค้นหา
โครงสร้างข้อมูลของต้นไม้ค้นหาSearch tree ต้องประกอบด้วยจุดต่อnodeแต่ละจุดต่อประกอบด้วยมั้ง
1.state=สถานะที่ต้องมีการเชื่อมโยง
2.parent node=จุดต่อม่าย
3.operation=การดำเนินการ
4.depth node=ความลึกของจุดต่อ จำนวนชั้นจุดต่อ
5.path cost=ค่าระยะทาง
1.state=สถานะที่ต้องมีการเชื่อมโยง
2.parent node=จุดต่อม่าย
3.operation=การดำเนินการ
4.depth node=ความลึกของจุดต่อ จำนวนชั้นจุดต่อ
5.path cost=ค่าระยะทาง
การวัดความสำเร็จการค้นหา
ประกอบด้วยเกณฑ์ข้อสรุป
1.Completeness ค้นพบคำตอบไหม?
2.Time complexity เวลาค้นหา
3.Space complexity จำนวนหน่วยความจำที่ใช้ในการจำจุดต่อจุด
4. Optimality มีประสิทธิภาพ?
1.Completeness ค้นพบคำตอบไหม?
2.Time complexity เวลาค้นหา
3.Space complexity จำนวนหน่วยความจำที่ใช้ในการจำจุดต่อจุด
4. Optimality มีประสิทธิภาพ?
ค้นหามี2แบบ ค้นหาแบบสม่ำเสมอ การค้นหาแบบแจ้งให้ทราบ
การค้นหาแบบสม่ำเสมอ uniform search
1.การค้นหาแบบกว้าง breadth first search เป็นการค้นหาเริ่มจากราก ค้นหาไปยังจุดต่อลูก ถ้าความสูงของต้นไม้มีค่าเท่ากับ dการค้นหาจะd+1 สามารถเขียนโปรแกรมโดยใช้คิว ค้นหาจะประสบความสำเร็จต่อเมื่อสถานะที่ต้องการค้นหาอยู่แบบตื้นๆ ค้นหาแนวกว้างจะสมบูรณ์ ต่อเมื่อจำนวนครั้งมีไม่มากนัก ขึ้นอยู่กับชั้นของจุดต่อ
1.การค้นหาแบบกว้าง breadth first search เป็นการค้นหาเริ่มจากราก ค้นหาไปยังจุดต่อลูก ถ้าความสูงของต้นไม้มีค่าเท่ากับ dการค้นหาจะd+1 สามารถเขียนโปรแกรมโดยใช้คิว ค้นหาจะประสบความสำเร็จต่อเมื่อสถานะที่ต้องการค้นหาอยู่แบบตื้นๆ ค้นหาแนวกว้างจะสมบูรณ์ ต่อเมื่อจำนวนครั้งมีไม่มากนัก ขึ้นอยู่กับชั้นของจุดต่อ
2. การค้นหาแนวลึก depth first searchโดยเริ่มจากจุดราก แล้วค้นหาไปยังลูกที่ลึกที่สุดทางซ้ายมือก่อน แล้วค้นต่อลูกทางขวามือ bเป็นจำนวนจุดต่อในแต่ละชั้นและmเท่ากับจำนวนชั้น
Depth first search ใช้หน่วยความจำน้อยกว่าการค้นหาในbreadth first search เพราะว่ามีการเก็บข้อมูลเฉพาะในวิถีที่พิจารณาเท่านั้น ในขณะที่การค้นหาแนวกว้างต้องเก็บข้อมูลทุกจุดต่อในแต่ละระดับครั้งละ 1ระดับ ทุกสถานะก่อนจะพิจารณาระดับหนึ่ง การค้นหาแนวกว้างจะไม่ถูกกักอยู่ในสถานที่วนซ้ำ เหมือนกันการค้นหาแนวลึก เกิดได้ถ้าถ้าไม่มีการเก็บข้อมูลของสถานะที่ได้ผ่านมาแล้ว แต่ถ้าหากปัญหานั้นมีผลเฉลยนั้นมีหลายผลเฉลย การค้นหาแนวกว้างจะได้ผลเฉลยที่ระยะที่สั้นที่สุด ซึ่งระยะทางจำนวนใช้กฎในขณะที่การค้นหาแนวลึกได้ผลเฉลี่ยที่มากกว่า เพราะว่าเพราะว่าผลเฉลยที่ระยะสั้นที่สุดไม่ได้ถูกนำพิจารณาในการค้นหานั้น
3.การค้นหาจำกัดความลึก depth limited search เป็นการกำหนดค่าความลึก ของเส้นทางเอาไว้โดยกำหนดในขั้นตอนวิธีในขณะค้นหาเลยก็ได้ เช่น แผนที่ประเทศไทย77จังหวัด ค่าสูงสุดของการค้นหาคือ19ชั้น จากการกำหนดนี้รับรองว่าต้องค้นพบผลลัพธ์ แต่จะไม่รองรับว่าจะค้นพบระยะทางที่สั้นที่สุดก่อน ซึ่งถ้ากำหนดระยะทางสิ้นสุดสั้นเกินไปก็จะค้นไม่พบ เวลาและการใช้เนื้อที่การค้นคล้ายกับก่รค้นหาแนวลึก
Depth first search ใช้หน่วยความจำน้อยกว่าการค้นหาในbreadth first search เพราะว่ามีการเก็บข้อมูลเฉพาะในวิถีที่พิจารณาเท่านั้น ในขณะที่การค้นหาแนวกว้างต้องเก็บข้อมูลทุกจุดต่อในแต่ละระดับครั้งละ 1ระดับ ทุกสถานะก่อนจะพิจารณาระดับหนึ่ง การค้นหาแนวกว้างจะไม่ถูกกักอยู่ในสถานที่วนซ้ำ เหมือนกันการค้นหาแนวลึก เกิดได้ถ้าถ้าไม่มีการเก็บข้อมูลของสถานะที่ได้ผ่านมาแล้ว แต่ถ้าหากปัญหานั้นมีผลเฉลยนั้นมีหลายผลเฉลย การค้นหาแนวกว้างจะได้ผลเฉลยที่ระยะที่สั้นที่สุด ซึ่งระยะทางจำนวนใช้กฎในขณะที่การค้นหาแนวลึกได้ผลเฉลี่ยที่มากกว่า เพราะว่าเพราะว่าผลเฉลยที่ระยะสั้นที่สุดไม่ได้ถูกนำพิจารณาในการค้นหานั้น
3.การค้นหาจำกัดความลึก depth limited search เป็นการกำหนดค่าความลึก ของเส้นทางเอาไว้โดยกำหนดในขั้นตอนวิธีในขณะค้นหาเลยก็ได้ เช่น แผนที่ประเทศไทย77จังหวัด ค่าสูงสุดของการค้นหาคือ19ชั้น จากการกำหนดนี้รับรองว่าต้องค้นพบผลลัพธ์ แต่จะไม่รองรับว่าจะค้นพบระยะทางที่สั้นที่สุดก่อน ซึ่งถ้ากำหนดระยะทางสิ้นสุดสั้นเกินไปก็จะค้นไม่พบ เวลาและการใช้เนื้อที่การค้นคล้ายกับก่รค้นหาแนวลึก
4.การค้นหาแบบทีดีที่สุดก่อน(ฺBest-first search)เป็นกระบวนการค้นหาข้อมูลที่นำเอาข้อดีbreadth first searchกับdepth first searchมารวมกันเป็นวิธีการเดียว ดดยแต่ละขั้นค้นหาในโหนดลูกนั้น เลือกเอาโหนดทที่ดีที่สุด(most promising)
