5. อัลกอริทึมการค้นหา

DFS เป็นการค้นหาแบบลงลึกไปตามกิ่งใดกิ่งหนึ่งจนสุดทางก่อน หากยังไม่พบคำตอบจึงย้อนกลับ (Backtrack) มาสำรวจกิ่งอื่นที่เหลือ

เริ่มจำลอง DFS

ลักษณะเด่น

• ● ใช้หน่วยความจำน้อยกว่า BFS ในหลายๆ กรณี
• ● เหมาะกับปัญหาที่ต้องการสำรวจเชิงลึก หรือการเล่นเกมหมากกระดาน
• ● อาจไม่พบคำตอบที่สั้นที่สุด หรืออาจติดลูปในกราฟที่มีความลึกอนันต์

A* เป็นอัลกอริทึมค้นหาเส้นทางที่ฉลาดขึ้น โดยพิจารณาทั้งต้นทุนที่ใช้ไปแล้วและต้นทุนประมาณการที่เหลือ เพื่อมุ่งหน้าไปสู่เป้าหมายอย่างมีทิศทาง

เริ่มจำลอง A*

ฟังก์ชันประเมิน (Heuristic)

ลักษณะเด่น

• ● รับประกันการหาเส้นทางที่สั้นที่สุดเสมอ เมื่อ h(n) เป็นค่าที่ยอมรับได้ (Admissible)
• ● มีประสิทธิภาพการค้นหาสูงกว่า BFS และ DFS เพราะมีตัวนำทาง
• ● นิยมใช้มากที่สุดในระบบนำทาง GPS และ AI ในวิดีโอเกม