การค้นในปริภูมิสถานะ

ปัญหาต่างๆ ที่เราได้ศึกษาและออกแบบอัลกอริทึมกันมา เป็นปัญหาที่มีอัลกอรึมที่หาคำตอบได้รวดเร็ว แต่ก็มีมากมายหลากหลายปัญหาในทางปฏิบัติที่คำตอบของปัญหาได้มาจากวิธีแจกแจงและตรวจสอบผลเฉลย แต่การแจกแจงและตรวจสอบเช่นนี้ใช้เวลานานมาก (แม้กับข้อมูลขาเข้าที่มีปริมาณไม่มาก) ดังนั้นจึงไม่ควรอย่างยิ่งที่จะแจกแจงและตรวจสอบทุก ๆ กรณี การแจกแจงและตรวจสอบนั้น เปรียบได้กับ การค้นคำตอบในปริภูมิสถานะผลเฉลยที่มีขนาดใหญ่ จะค้นไปทางไหน อย่างไร หากกระทำอย่าง "ฉลาด" ย่อมพบคำตอบได้เร็วขึ้น บทนี้นำเสนอกลวิธีการค้นคำตอบในปริภูมิสถานะ ได้แก่ การค้นตามแนวลึกและแนวกว้าง ซึ่งสามารถเพิ่มกลวิธีการย้อนรอย (backtracking) ที่มีฟังก์ชันการตรวจสอบความมีแววของปมสถานะ ถ้าไม่มีแววว่าจะนำไปสู่คำตอบ ก็อย่าค้นต่อจากปมนั้น ผนวกกับการค้นตามต้นทุนต่ำสุด ที่จะนำการค้นไปสู่คำตอบได้ถูกทิศถูกทาง นอกจากนี้ยังมีกลวิธีขยายและจำกัดเขต (branch and bound) ที่ใช้กับปัญหาการหาคำตอบดีสุดที่เรียกว่า optimization problems