แนะนำหัวข้อ
สามารถดู video ของหัวข้อนี้ก่อนได้ ดู video
แนะนำหัวข้อ และ Algorithm ชุดแรก Backtracking
Backtracking คืออะไร ?
Backtracking เป็นเทคนิคที่ใช้วิธีการแบบ Brute Force ในการค้นหาคำตอบทั้งหมดของปัญหา (Brute Force เป็นวิธีการแก้ปัญหาแบบตรงไปตรงมา โดยการสร้างและทดสอบทุกคำตอบที่เป็นไปได้จนกว่าจะพบคำตอบที่ถูกต้อง เป็นวิธีการที่ง่ายต่อการเขียนโปรแกรม แต่อาจใช้เวลาและ Resource คอมพิวเตอร์ค่อนข้างมากในการแก้ปัญหา เมื่อปัญหาเริ่มมีขนาดใหญ่เพิ่มขึ้นเรื่อยๆ) โดยจะสร้างผลเฉลยทีละส่วนๆ และจะย้อนกลับไปเมื่อพบว่าผลเฉลยส่วนนั้นไม่สามารถนำไปสู่คำตอบที่ถูกต้องได้
กระบวนการทำงานจะเริ่มจากจุดเริ่มต้น และค่อยๆ สร้างผลเฉลยโดยการเพิ่มองค์ประกอบใหม่ๆ เข้าไปเรื่อยๆ ถ้าผลเฉลยส่วนนั้นไม่สามารถนำไปสู่คำตอบที่ถูกต้องได้ ก็จะย้อนกลับไปที่จุดก่อนหน้า และลองเพิ่มองค์ประกอบอื่นแทน จนกว่าจะพบคำตอบที่ถูกต้อง
ประเภทของปัญหาที่ใช้ Backtracking
Backtracking มักถูกนำมาใช้กับปัญหาประเภทต่อไปนี้
- ปัญหาการตัดสินใจ (Decision Problem) เช่น การหาว่ามีวิธีจัดเรียงตัวเลขให้ได้ผลรวมเป็นค่าหนึ่งหรือไม่
- ปัญหาการหาค่าที่ดีที่สุด (Optimization Problem) เช่น การหาเส้นทางสั ้นที่สุดระหว่างสองจุด
- ปัญหาการนับจำนวน (Enumeration Problem) เช่น การหาจำนวนวิธีจัดเรียงตัวเลขทั้งหมด
ตัวอย่างปัญหาที่ใช้ Backtracking
- ปัญหา N-Queen ซึ่งต้องวาง Queen ไปบนกระดานขนาด N*N โดยไม่ให้ Queen ตัวใดโจมตี Queen ตัวอื่นได้
- ปัญหาการเดินของม้า (Knight's Tour) ซึ่งต้องเดินม้าให้ผ่านทุกช่องบนกระดาน 8*8 โดยไม่ผ่านช่องเดียวกันสองครั้ง
- ปัญหาการแก้เกม Sudoku
- ปัญหาการหาเส้นทางในเขาวงกต (Maze)