วันจันทร์ที่ 24 สิงหาคม พ.ศ. 2558
Classes of Search
| Class | Name | Operation |
| ไม่รู้เส้นทางใด | Depth-First Breadth-First |
ระบบการตรวจสอบข้อเท็จจริงของต้นไม้ ทั้งค้นหาจนกว่าจะพบเป้าหมาย |
| รู้เส้นทางเส้นทาง | Greedy Best- First | ใช้มาตรการแก้ปัญหาของความดีของสถานะ เช่น ระยะทางประมาณเป้าหมาย |
| ไม่รู้ความเหมาะสม | UniformCost | ใช้เส้นทาง "ความยาว" วัดพบ "สั้น" เส้นทาง |
| รู้ความเหมาะสม | A* | ใช้เส้นทาง"ความยาว"
มาตรการและ การแก้ปัญหาพบเส้นทาง"สั้น" |
Uninformed (ไม่รู้) VS. Informed (รู้)
- Uninformed search :(หรือการค้นหาแบบตาบอด): ไม่มีเพิ่มเติมข้อมูลเกี่ยวกับสถานะเกินกว่าที่ระบุไว้ในคำนิยามปัญหา
- Informed search :(หรือการค้นหาที่ Heuristicการค้นหาที่เลือกคำตอบที่เหมาะสมกับการค้นหาเท่านั้นแต่อาจจะไม่ใช่คำตอบที่ดีที่สุด): ใช้ problem- 7? ค้นหาแจ้ง (เทียบกับการแก้ปัญหาการค้นหา): ใช้ความรู้เฉพาะปัญหาที่นอกเหนือจากความหมายของปัญหาของตัวเอง
Informed (Heuristic) Search
- บางขั้นตอนวิธีการค้นหาที่ใช้heuristic functions.
- heuristic functionsอาจจะช่วยเป็นแนวทางในการค้นหาและเพิ่มความเร็วอย่างน้อยโดยเฉลี่ยกระบวนการในการหาที่เป้าหมาย
- การประเมินผลการใช้ฟังก์ชัน f (s) ซึ่งประมาณการระยะทางไปยังเป้าหมาย
- ขยายโหนดที่มีลักษณะที่ดีที่สุด (มีแนวโน้มมากที่สุด)ในขณะที่คนที่มีต่ำสุด f (s)
- เราจะหารือสองวิธี:
- Greedy best-first search
- A* search
Greedy Best-First Search
- ขยายโหนดที่ปรากฏขึ้นใกล้เคียงกับเป้าหมาย
- เลือกเส้นทางที่ดีที่สุดที่ดูจากโหนดปัจจุบัน S เพื่อเป้าหมาย
- f (s) = h (s) h (s): ประเมินค่าใช้จ่ายของเส้นทางถูกที่สุดจากโหนดเพื่อเป้าหมาย
- h (เป้าหมาย) = 0
- วิธีการแก้ปัญหา:A-C-O-N-E-X เสียค่าใช้จ่าย 86
- ทางออกที่ดีที่สุด: A-S-P-X เสียค่าใช้จ่าย 80
- วิธีการแก้ปัญหาที่พบโดยโลภค้นหาที่ดีที่สุดอาจจะเป็นครั้งแรกไม่เหมาะสม
A* Search
- ขยายโหนดที่ปรากฏอยู่บนเส้นทางที่ดีที่สุดจากจุดเริ่มต้นไปสู่เป้าหมาย
- เลือกเส้นทางที่ดีที่สุดที่ดูจากจุดเริ่มต้นไปสู่เป้าหมาย
- f (s) = g (s) + h (s)
g (s): ค่าใช้จ่ายของเส้นทางที่ถูกที่สุดตั้งแต่ต้นจน s
h (s): ประเมินค่าใช้จ่ายของเส้นทางถูกที่สุดจาก s ไปโหนดเป้าหมาย
- h (เป้าหมาย) = 0
- ในตัวอย่างของเรา A * พบทางออกที่ดีที่สุด:A-S-P-X (เสียค่าใช้จ่าย 80)
- นี้ไม่ได้เกิดอุบัติเหตุ ในความเป็นจริง A * จะเสมอหาทางออกที่ดีที่สุดทุกครั้งที่เขา) ตอบสนองเงื่อนไขบางอย่าง
Admissibility
ฟังก์ชั่นการแก้ปัญหา h (s) เป็นที่ยอมรับ (หรือในแง่ดี) ถ้ามันไม่เคย overestimates ค่าใช้จ่ายไปที่เป้าหมายA* Search
- A* = สมบูรณ์ที่สุด,ดีที่สุด
- A * จะเสร็จสมบูรณ์และที่ดีที่สุดที่ได้รับ h (s) ตอบสนองเงื่อนไขบางประการ
- เงื่อนไขอะไร?--> h (s) เป็นที่ยอมรับ
- ดังนั้น เป็นปัญหาหรือไม่? -->หน่วยความจำ
หน่วยความจำขอบเขตในการค้นหาแบบHeuristic
- A * ความต้องการในปริมาณที่ชี้แจงของหน่วยความจำ
- การแก้ไข: การใช้หน่วยความจำขอบเขตการค้นหาแก้ปัญหา
ซ้ำที่ดีที่สุดครั้งแรกที่การค้นหา (BFS)
ซ้ำ-ลึก * A (IDA *)
หน่วยความจำแบบย่อขอบเขต A * (SMA *)
ซ้ำที่ดีที่สุดครั้งแรกที่การค้นหา (RBFS)
- หนึ่งที่ไม่สามารถให้ขึ้นใจของพวกเขา
- คล้ายกับ DFS แต่แทนที่จะดำเนินการต่อไปอย่างไม่มีกำหนดลงเส้นทางปัจจุบัน RBFS ติดตามมูลค่าของเส้นทางเลือกที่ดีที่สุดที่มีอยู่จากบรรพบุรุษใด ๆ ของโหนดปัจจุบัน ถ้าโหนดปัจจุบันเกินกว่านี้วงเงินที่เรียกซ้ำคลายกลับไปที่ทางเลือกเส้นทาง ในฐานะที่เป็นเรียกซ้ำคลาย, RBFS แทนที่ค่าของแต่ละโหนดไปตามเส้นทางที่ดีที่สุดมูลค่าของโหนดลูก
- ที่ดีที่สุดถ้า h เป็นที่ยอมรับ
- การเปลี่ยนแปลงและยังคงมีหน่วยความจำน้อยจึงลำบากในการฟื้นฟูโหนดที่มากเกินไป
- ประหยัดมากเกินไปเกี่ยวกับหน่วยความจำที่มันไม่มีประสิทธิภาพ
IDA*
- ซ้ำ-ลึก * A (IDA *)
- คล้ายกับการค้นหาลึกซ้ำมาตรฐาน แต่ใช้f ค่าใช้จ่าย (g + h) เป็นทางลัด (แทนของความลึก); ที่ซ้ำกัน, ตัดเป็นค่าใช้จ่าย f เล็กที่สุดของโหนดใด ๆ ที่เกินตัดทวนก่อนหน้านี้
Simplified Memory-Bounded A* (SMA*)
- ขยายที่ดีที่สุด (ต่ำสุด f) โหนดจนกว่าหน่วยความจำเต็ม
- เพิ่มโหนดใหม่ในการค้นหาต้นไม้โดยวางโหนดเก่า มักจะลดลงที่เลวร้ายที่สุด (f สูงสุด) อย่างใดอย่างหนึ่ง
- เมื่อวางโหนดสำรองค่า F ไปยังparent ด้วยวิธีนี้ancestor ของทรีย่อย(subtree) ไม่รู้ที่มีคุณภาพของเส้นทางที่ดีที่สุดในทรีย่อยว่า
- เพิ่มทรีย่อย(subtree)ใหม่ลืมเฉพาะเมื่อเส้นทางอื่น ๆ ได้รับการแสดงที่จะดูแย่ลง
