Skip to main content

แนะนำหัวข้อ

c++-basic-backtracking สามารถดู video ของหัวข้อนี้ก่อนได้ ดู video

แนะนำหัวข้อ และ Algorithm ชุดแรก Backtracking

Backtracking คืออะไร ?

Backtracking เป็นเทคนิคที่ใช้วิธีการแบบ Brute Force ในการค้นหาคำตอบทั้งหมดของปัญหา (Brute Force เป็นวิธีการแก้ปัญหาแบบตรงไปตรงมา โดยการสร้างและทดสอบทุกคำตอบที่เป็นไปได้จนกว่าจะพบคำตอบที่ถูกต้อง เป็นวิธีการที่ง่ายต่อการเขียนโปรแกรม แต่อาจใช้เวลาและ Resource คอมพิวเตอร์ค่อนข้างมากในการแก้ปัญหา เมื่อปัญหาเริ่มมีขนาดใหญ่เพิ่มขึ้นเรื่อยๆ) โดยจะสร้างผลเฉลยทีละส่วนๆ และจะย้อนกลับไปเมื่อพบว่าผลเฉลยส่วนนั้นไม่สามารถนำไปสู่คำตอบที่ถูกต้องได้

กระบวนการทำงานจะเริ่มจากจุดเริ่มต้น และค่อยๆ สร้างผลเฉลยโดยการเพิ่มองค์ประกอบใหม่ๆ เข้าไปเรื่อยๆ ถ้าผลเฉลยส่วนนั้นไม่สามารถนำไปสู่คำตอบที่ถูกต้องได้ ก็จะย้อนกลับไปที่จุดก่อนหน้า และลองเพิ่มองค์ประกอบอื่นแทน จนกว่าจะพบคำตอบที่ถูกต้อง

ประเภทของปัญหาที่ใช้ Backtracking

Backtracking มักถูกนำมาใช้กับปัญหาประเภทต่อไปนี้

  1. ปัญหาการตัดสินใจ (Decision Problem) เช่น การหาว่ามีวิธีจัดเรียงตัวเลขให้ได้ผลรวมเป็นค่าหนึ่งหรือไม่
  2. ปัญหาการหาค่าที่ดีที่สุด (Optimization Problem) เช่น การหาเส้นทางสั้นที่สุดระหว่างสองจุด
  3. ปัญหาการนับจำนวน (Enumeration Problem) เช่น การหาจำนวนวิธีจัดเรียงตัวเลขทั้งหมด

ตัวอย่างปัญหาที่ใช้ Backtracking

  • ปัญหา N-Queen ซึ่งต้องวาง Queen ไปบนกระดานขนาด N*N โดยไม่ให้ Queen ตัวใดโจมตี Queen ตัวอื่นได้
  • ปัญหาการเดินของม้า (Knight's Tour) ซึ่งต้องเดินม้าให้ผ่านทุกช่องบนกระดาน 8*8 โดยไม่ผ่านช่องเดียวกันสองครั้ง
  • ปัญหาการแก้เกม Sudoku
  • ปัญหาการหาเส้นทางในเขาวงกต (Maze)