บทที่ 21 brute force และ backtracking
จบบทนี้ น้องจะดูขอบเขตของโจทย์แล้วรู้ว่าลองทุกแบบได้ไหม และเขียนตัวลองทุกแบบได้ครบโดยไม่ซ้ำ ทั้งลูปซ้อน ทุกเซตย่อยด้วย bitmask ทุกลำดับด้วย next_permutation และ backtracking ที่สร้างคำตอบทีละช่องแล้วถอยกลับเมื่อผิดกฎ เช่น N-Queens และซูโดกุ จากนั้นจะตัดกิ่งที่ไม่มีหวังทิ้ง จนโจทย์ที่ลองครบต้องใช้เวลาหลายนาทีเหลือไม่ถึงวินาที ซึ่งเป็นหัวข้อ exhaustive search และ backtracking ของค่าย 2 และใช้ได้กับโจทย์ TOI ที่ขอบเขตเล็กผิดปกติ ปิดท้ายด้วยการแทนสถานะของปริศนา ซึ่งต่อไปใช้กับ BFS ในบทที่ 27 และ meet in the middle สำหรับโจทย์ N ≤ 40
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 21.1 นับก่อนลอง | สามขั้นก่อนลองทุกแบบ ลูปซ้อนที่ไม่หยิบซ้ำ ตัดลูปชั้นในที่คำนวณได้ และดูขอบเขตแล้วเดาวิธี |
| 21.2 ทุกเซตย่อยและทุกลำดับ | bitmask แทนเซตย่อย __builtin_popcount next_permutation และเวลาจริงของ 2n กับ n! |
| 21.3 backtracking | ต้นไม้การค้นหา N-Queens ผลรวมเซตย่อย ซูโดกุ 4 × 4 และโครงเลือก ลอง คืนสภาพ |
| 21.4 ตัดกิ่งและ branch and bound | ตัดกิ่งที่ไม่มีทางถูก ตัดกิ่งที่ไม่มีทางดีกว่า ค่าประมาณที่มองโลกในแง่ดี และจำนวน nodes ก่อนและหลังตัดที่วัดจริง |
| 21.5 state space และ meet in the middle | แทนสถานะด้วย bitmask ค้นด้วย DFS ที่จำ visited และแบ่งครึ่งให้ N = 40 ทันเวลา |