วันเสาร์ที่ 22 สิงหาคม พ.ศ. 2558
การแทนความรู้ (Knowledge Representation)
กำหนดปัญหา
หนึ่งวิธีการทั่วไปในการแก้ปัญหาในไอเพื่อลดปัญหาที่จะแก้ไขให้เป็นหนึ่งในค้นหากราฟ
การใช้วิธีการนี้เราจะต้องกำหนดปัญหาที่เกิดขึ้นโดยระบุ
การใช้วิธีการนี้เราจะต้องกำหนดปัญหาที่เกิดขึ้นโดยระบุ
- State space
- เริ่มต้นState
- เป้าหมาย
- การดำเนินการ
Stateแสดงทั้งหมด (และโดยเฉพาะอย่างยิ่งเท่านั้น)ด้านที่เกี่ยวข้องของปัญหาที่จะแก้ไขพื้นที่State
คือชุดของStateที่เป็นไปได้ทั้งหมด
เราถือว่าการกระทำที่มีกำหนดว่าเป็นเราทราบว่าหลังจากที่Stateกระทำที่เป็นดำเนินการ
นอกจากนี้เรายังคิดว่าการดำเนินการที่มีความต่อเนื่อง
กราฟที่1 กราฟแสดงถึงปัญหาที่เกิดขึ้น
กราฟที่2 การค้นหาจากต้นไม้ของกราฟ
initial state = คือสถานะเริ่มต้น
goal = เป้าหมา่ยที่อยากให้ตัวเลขมันเรียงกัน
กราฟแสดงถึงปัญหาที่เกิดขึ้น
ไปจาก A ถึง B โดยใช้ขั้นตอนน้อยที่สุดเท่าที่เป็นไปได้
ชั้นของการค้นหา
Breadth-First Search ตามแนวกว้าง
Depth-First Search ตามแนวลึก
ข้อเสียDepth-First Search
-เป็นวิธีที่ไม่ดี
-ไม่รับประกันว่าจะหยุด ถ้าต้นไม้มากมายก็ต้องค้นจากที่ลึกก่อน เพื่อแก้ไขปัญหานี้:Depth-Limited Search
Depth-Limited Search
- DFS ที่มีความลึกคงที่ โหนดที่ระดับความลึกไม่มีการสืบทอด
- อะไรคือสิ่งที่เหมาะสมcut-off depth d?
- ถ้า d มีขนาดเล็กเกินไปไม่อาจหาเป้าหมายได้
- ถ้า d มีขนาดใหญ่เกินไป: การทำงานพิเศษ
- สิ่งที่เกี่ยวกับการเริ่มต้นที่มีขนาดเล็กและให้ d เพิ่มขึ้น?
- ซ้ำลึกการค้นหา
Iterative Deepening Search
- ค้นหาลึกมากขึ้น
- DFS มีความลึกคงค่อยๆที่เพิ่มขึ้น
- มันไม่ซ้ำมากเกินไปในการทำงานหรือไม่
- ในต้นไม้เวลาถูกครอบงำโดยการค้นหาแนวลึกที่สุด(deepest search)
ประสิทธิภาพ
- สมบูรณ์: การประกันเพื่อหาทางแก้ปัญหาเมื่อในทางหนึ่งที่มีอยู่?
- เหมาะสมกับ: ทางออกที่ดีที่สุด?
- ซับซ้อนเวลา
- ซับซ้อนพื้นที่
เกณฑ์ BFS DFS
เสร็จสมบูรณ์? Yes Yes
(ถ้าไม่มีเส้นทางที่ไม่มีที่สิ้นสุด)
การเชื่อมโยงน้อยที่สุด? Yes No
(แต่ไม่จำเป็นต้องเป็นทางออกที่ดีที่สุด)
เวลา O(bd) O(bm)
พื้นที่ O(bd) O(bm)
กรณีเวลาที่เลวร้ายที่สุด
ในการค้นหา
- ปัจจัยที่แตกแขนง
- d: ความลึกของเป้าหมายตื้น
- m: ความลึกสูงสุดของต้นไม้ค้นหา (ดังนั้น d = เมตร BFS, d≤mใน DFS)
ในกรณีที่เลวร้ายที่สุดวิธีการค้นหาอาจจะจบลงมีการขยายตัวของสถานะ
- BFS: O (BD)
- DFS: O (พิพิธภัณฑ์)
BFS
- กรณีที่เลวร้ายที่สุดที่เกิดขึ้นเมื่อโหนดทั้งหมดที่ระดับความลึก d ได้รับการสร้างขึ้น แต่ไม่ขยายตัวเลย
- Q มีขนาด BD, ที่อยู่, ขนาดชี้แจงใน d
 |
DFS
- Q ถือที่ยังไม่ขยาย "พี่น้องsiblings" ของโหนดตามเส้นทางที่ได้รับการพิจารณา
- Q ถือไม่เกิน m(b-1)+1 = O(bm)
BFS Revisited
- การขยายตัว Node: A, B, C, E (เป้าหมาย)
- โซลูชั่นที่พบ: A-B-E (ค่าใช้จ่าย 100) - ไม่ดีที่สุด
- การแก้ไขปัญหานี้: การค้นหาเครื่องแบบค่าใช้จ่าย
Uniform-Cost Search การค้นหาแบบประหยัดต้นทุน
- ขยายโหนดที่มีค่าใช้จ่ายในเส้นทางที่ต่ำที่สุด (ใกล้เคียงกับเป้าหมาย)
- เหมือนกับ BFS หากค่าใช้จ่ายขั้นตอนทั้งหมดเท่ากัน
- การขยายตัว Node: A, C, D, E (เป้าหมาย)
- โซลูชั่นที่พบ: A-C-D-E (ต้นทุน 3) - ที่ดีที่สุด
- ที่ดีสำหรับค่าใช้จ่ายที่ไม่สม่ำเสมอ
Bidirectional Searchการค้นหาสองทิศทาง
- การค้นหาพร้อมกันสองคนคนหนึ่งไปข้างหน้าจากสถานะเริ่มต้นย้อนหลังจากเป้าหมายอื่น ๆ
- ประหยัดพื้นที่
