อัลกอริทึม A*
บน
- จะรู้ได้อย่างไรว่าความเป็นไปได้มีแนวโน้มหรือไม่?
- ผ่านฟังก์ชั่น f (x) = g (x) + h (x)
- ซึ่งเป็นฟังก์ชันฮิวริสติก
- g (x) คือค่าใช้จ่ายจากต้นกำเนิดถึงโหนด x
- H (x) เป็นฟังก์ชั่นฮิวริสติกสำหรับการประเมินค่าใช้จ่ายของโหนดถัดไป
- เรามักจะดูความเป็นไปได้ของการขยายต้นไม้และคำนวณค่าของ F (x)
- เราเพิ่มโหนดที่มี F (x) ที่เล็กที่สุดในหมู่ที่เราพบ
- OA* เป็นอัลกอริทึมที่มีประสิทธิภาพที่สุดสำหรับวิธีการขั้นต่ำในกราฟ
- อย่างไรก็ตามมันเป็นข้อ จำกัด ที่รุนแรง
- จำเป็นต้องกำหนด H (x) ที่ยอมรับได้: มันจะไม่คืนค่ามากกว่าระยะทางจริงจาก x ถึง y
- ถ้า H (x) ยอมรับได้ แต่ประเมินระยะทางที่แท้จริงต่ำเกินไปอัลกอริทึมจะไม่มีประสิทธิภาพมาก หาก H (x) ไม่สามารถยอมรับได้อัลกอริทึมอาจไม่พบวิธีขั้นต่ำ
- ความซับซ้อน
- ความซับซ้อนขึ้นอยู่กับฟังก์ชั่น H (x) โดยตรง
- ในกรณีที่เลวร้ายที่สุดปริมาณของโหนดที่สำรวจนั้นเป็นแบบทวีคูณในขนาดของเส้นทางที่เล็กที่สุด แต่มีความซับซ้อนพหุนามถ้า H ∗ (x) −H (x) ≤O (logh ∗ (x))
- ใช้งานได้ดีเมื่อไหร่?
- กราฟที่หนึ่งสามารถประมาทระยะห่างระหว่างสองจุดยอดเช่นเดียวกับในแผนที่
- ระยะทางที่สั้นที่สุดระหว่างสองจุดคือเส้น แต่อาจเป็นระยะทางที่แท้จริงจะมากกว่านั้น
- วิธีขั้นต่ำในกรณีนี้คืออะไร?
ดำเนินโครงการ
ผลลัพธ์
ผู้เขียน
ใบอนุญาต
โครงการนี้อยู่ภายใต้ MIT ดูที่นี่สำหรับข้อมูลเพิ่มเติม
