แผนการเรียน
/

Complete Search & Backtracking
การค้นหาทุกความเป็นไปได้และการย้อนรอย

Day 04 Afternoon: เทคนิคการสร้างคำตอบและการใช้ Pruning เพื่อเพิ่มความเร็ว

หัวข้อที่จะเรียนรู้

1
Complete Search: แนวคิดการลองทุกวิธีเพื่อหาคำตอบ
2
Generating Subsets & Permutations: การสร้างสับเซตและวิธีเรียงสับเปลี่ยน
3
Pruning Techniques: การตัดกิ่งที่ไม่จำเป็นเพื่อลดเวลาทำงาน

แนวคิด Complete Search

"เป็นวิธีการแก้ปัญหาโดยการ สร้างความเป็นไปได้ทั้งหมด ของคำตอบ แล้วตรวจสอบว่าแต่ละวิธีถูกต้องหรือไม่"

  • ใช้ได้กับเกือบทุกปัญหา แต่ต้องระวังเรื่อง Time Complexity
  • มักใช้เมื่อขนาดของข้อมูล (N) มีค่าไม่มากนัก
  • หากเขียนแบบ Recursive จะเรียกว่า Backtracking

Method 1: Recursion

ใช้หลักการ "เลือก" หรือ "ไม่เลือก" สมาชิกแต่ละตัว

void search(int k) {
  if (k == n) { process(subset); return; }
  // ไม่เลือกสมาชิกตัวที่ k
  search(k + 1);
  // เลือกสมาชิกตัวที่ k
  subset.push_back(k);
  search(k + 1);
  subset.pop_back(); // Backtrack!
}

Complexity: $O(2^n)$

Method 2: Bit Representation

ใช้บิต 0 และ 1 แทนสถานะการเลือกสมาชิก

for (int b = 0; b < (1 << n); b++) {
  for (int i = 0; i < n; i++) {
    if (b & (1 << i)) { // สมาชิกตัวที่ i อยู่ในเซต }
  }
}
ข้อดี: เขียนโค้ดสั้นกว่าแบบ Recursion และทำงานได้รวดเร็วในเชิง Iterative

Recursive Permutations

void search() {
  if (permutation.size() == n) { process(); return; }
  for (int i = 0; i < n; i++) {
    if (chosen[i]) continue;
    chosen[i] = true;
    permutation.push_back(i);
    search();
    chosen[i] = false; // คืนค่าสถานะ
    permutation.pop_back();
  }
}
STL Alternative: ใช้ std::next_permutation เพื่อสร้างวิธีถัดไปใน $O(N)$

Backtracking Framework

"Try - Recurse - Undo"

1. Try: วางชิ้นส่วนคำตอบลงในตำแหน่งปัจจุบัน

2. Recurse: เรียกฟังก์ชันเดิมเพื่อวางชิ้นส่วนถัดไป

3. Undo: ดึงชิ้นส่วนออกเพื่อลองความเป็นไปได้อื่น

"หัวใจสำคัญคือการล้างค่าสถานะ (Reset state) หลังจากการเรียกเสร็จสิ้น"

ตัวอย่าง: ปัญหาการวางควีน N ตัว

วางควีน $N$ ตัวในกระดาน $N \times N$ โดยไม่ให้ควีนตัวใดกินกันได้เลย

กฎการตรวจสอบ:

• แถวเดียวกัน (Row)
• คอลัมน์เดียวกัน (Col)
• แนวทแยง (Diagonals)

"ใช้ Backtracking เพื่อวางควีนทีละแถว และเช็คเงื่อนไขก่อนวางตัวถัดไป"

Pruning: เพิ่มความฉลาดให้ตัวค้นหา

Symmetry Pruning

หากปัญหาเหมือนกันในมุมกลับ ให้คำนวณด้านเดียวแล้วคูณสอง

Early Termination

หากรู้แน่ๆ ว่าเส้นทางนี้ไม่มีทางได้คำตอบ ให้หยุดและย้อนกลับทันที

การตัดกิ่งที่ดีสามารถลดเวลาทำงานจากนาทีให้เหลือเพียงวินาทีได้

Contest Strategy: Subtasks

"ในโจทย์ระดับ IOI Style อัลกอริทึม Backtracking แบบพื้นฐานอาจจะได้เพียง 20-30 แต้ม
แต่ถ้าเราเพิ่ม Pruning ที่ฉลาดเข้าไป เราอาจจะเก็บคะแนนได้ถึง 60-100 แต้ม!"

"First make it work, then make it fast"

Ready to Code?

15.00 - 17.00 น.

Practice: N-Queens, Subsets, Permutations

"โค้ดที่ดีที่สุดคือโค้ดที่คุณเขียนด้วยตัวเอง" เจอกันในแล็บครับ!