ตัวอย่าง Backtracking

ปัญหา N Queen (ปัญหา classic)

https://leetcode.com/problems/n-queens/description/

เรามาเริ่มต้นรู้จัก Backtrack กับปัญหาสุด classic ที่ทุกคนที่เรียนรู้ Backtracking ต้องเรียนนั่นก็คือ N Queen

ปัญหา N-Queen เป็นปัญหา classic ในการจัดวาง Queen บนกระดานหมากรุกขนาด N*N โดยที่ Queen แต่ละตัวต้องไม่โจมตี Queen ตัวอื่น ซึ่งหมายความว่า Queen เหล่านั้นต้องไม่อยู่ในแนวเดียวกันทั้งแนวนอน แนวตั้ง และแนวทแยงมุม

เราจะใช้เทคนิค Backtracking ในการแก้ปัญหานี้ โดยจะค้นหาตำแหน่งที่เหมาะสมในการวาง Queen แต่ละตัว ถ้าไม่สามารถวาง Queen ได้ที่ตำแหน่งนั้น ก็จะย้อนกลับไปลองวาง Queen ที่ตำแหน่งก่อนหน้า และเราจะทำแบบนี้ไปเรื่อยๆจนกว่าจะเจอคำตอบสักคำตอบออกมาได้

class Solution {
public:
  vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<string> board(n, string(n, '.'));
    solveNQueensUtil(result, board, 0, n);
    return result;
  }

private:
  void solveNQueensUtil(vector<vector<string>> &result, vector<string> &board,
                        int row, int n) {
    if (row == n) { // ถ้าวาง Queen ครบทุกแถวแล้ว เพิ่มผลลัพธ์เข้าไปใน vector result
      result.push_back(board);
      return;
    }

    for (int col = 0; col < n; col++) {
      if (isSafe(board, row, col, n)) { // ตรวจสอบว่าสามารถวาง Queen ได้ที่ตำแหน่งนี้หรือไม่
        board[row][col] = 'Q'; // วาง Queen ลงบนกระดาน
        solveNQueensUtil(result, board, row + 1, n); // ค้นหาตำแหน่งสำหรับ Queen ตัวถัดไป
        board[row][col] = '.'; // ถอด Queen ออกจากกระดาน (backtrack)
      }
    }
  }

  bool isSafe(vector<string> &board, int row, int col, int n) {
    // ตรวจสอบแนวนอน
    for (int i = 0; i < col; i++) {
      if (board[row][i] == 'Q') {
        return false;
      }
    }

    // ตรวจสอบแนวตั้ง
    for (int i = 0; i < row; i++) {
      if (board[i][col] == 'Q') {
        return false;
      }
    }

    // ตรวจสอบแนวทแยงมุมซ้ายบน
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] == 'Q') {
        return false;
      }
    }

    // ตรวจสอบแนวทแยงมุมขวาบน
    for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
      if (board[i][j] == 'Q') {
        return false;
      }
    }

    return true; // ถ้าไม่มีรากตัวใดโจมตีตำแหน่งนี้
  }
};

อธิบายการทำงานของโปรแกรม

1. function solveNQueens จะเริ่มทำงานโดยสร้าง vector board ขนาด n*n และเรียก function solveNQueensUtil เพื่อค้นหาคำตอบออกมา
2. function solveNQueensUtil จะทำงานแบบ Backtracking โดย
   • ถ้าวาง Queen ครบทุกแถวแล้ว (row == n) ให้เพิ่มผลลัพธ์เข้าไปใน vector result (แปลว่าได้คำตอบแล้วเรียบร้อย)
   • ถ้ายังไม่ครบ ให้ลองวาง Queen ในแต่ละ column ของแถวปัจจุบัน (row)
     • ถ้าสามารถวาง Queen ได้ที่ตำแหน่งนั้น (ที่ isSafe() == true) ให้วาง Queen ลงบนกระดาน แล้วเรียก function ตัวเองอีกครั้ง (recursive function) เพื่อค้นหาตำแหน่งสำหรับ Queen ตัวถัดไป (row+1)
     • หลังจากค้นหาตำแหน่งสำหรับ Queen ตัวถัดไปเสร็จแล้ว ให้ถอด Queen ออกจากกระดาน (backtrack)
3. function isSafe จะตรวจสอบว่าสามารถวาง Queen ได้ที่ตำแหน่ง (row, col) หรือไม่ โดยดูว่ามี Queen ตัวอื่นโจมตีตำแหน่งนี้หรือไม่ ทั้งในแนวนอน แนวตั้ง และแนวทแยงมุม ถ้าไม่มี Queen ตัวใดโจมตี = ก็จะส่งค่ากลับเป็น true ออกมา แปลว่าสามารถวาง Queen ตรงตำแหน่งนั้นได้

สุดท้าย โปรแกรมนี้จะค้นหาคำตอบทั้งหมดของปัญหา N-Queen และเก็บผลลัพธ์ไว้ใน Vector ตอบออกมาได้

result:
["..Q.","Q...","...Q",".Q.."]

เปรียบเทียบได้กับกระดานตามภาพตัวอย่างใน leet code
..Q.
Q...
...Q
.Q..

ทำไมต้องใช้ Recursion ในการ Backtrack

อย่างที่ทุกคนเห็นจากตัวอย่างนี้ Backtracking นั้นมักจะต้องใช้ Recursive Function เพื่อแก้ปัญหา

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

1. การแบ่งปัญหาออกเป็นส่วนย่อย Backtracking จำเป็นต้องแบ่งปัญหาออกเป็นส่วนย่อยๆ เพื่อค้นหาผลเฉลย ซึ่งเป็นหลักการพื้นฐานของ Recursion
2. การย้อนกลับ เมื่อผลเฉลยส่วนนึงไม่สามารถนำไปสู่คำตอบได้ จำเป็นต้องย้อนกลับไปยังจุดตัดสินใจก่อนหน้า ซึ่งเป็นการทำงานแบบถอยหลังที่สามารถทำได้ด้วยหลักการของ Recursion
3. การจัดการ state ในการ Backtrack ต้องมีการจัดการ state ของผลเฉลยที่สร้างขึ้นในแต่ละขั้นตอน ซึ่ง Recursion สามารถทำได้ง่ายด้วยการส่งค่าผ่าน parameter เข้า Recursive function ไปในฐานะ state ต่อไปได้

ดังนั้น จึง สรุปได้ว่า การใช้ Recursion ในการ Backtrack ช่วยให้การเขียน code สามารถจัดการกับปัญหาที่ซับซ้อนได้ จากการพยายามย่อยปัญหาลงมา และสามารถย้อนกลับไปมาระหว่าง state ด้วยความสามารถของ Recursion ได้ (ส่งผลทำให้ code สั้นด้วยคล้ายๆกับเคสของ DFS ที่เลือกใช้ระหว่าง Recursion กับ Stack ที่ code ของ Recursion สั้นกว่า)

มาลองดู Complexity กันบ้าง

Time Complexity ของ Backtracking algorithm สำหรับปัญหา N-Queen คือ O(N!)

เหตุผลที่เป็นเช่นนี้เนื่องจาก

• ในการวาง Queen ตัวแรก เรามี N ตำแหน่งให้เลือก
• สำหรับ Queen ตัวที่สอง เราต้องไม่วางใน column เดียวกันกับ Queen ตัวแรก และต้องไม่อยู่ในเส้นทแยงมุมเดียวกัน ดังนั้นจึงมีประมาณ N-1 ตำแหน่งให้เลือก
• สำหรับ Queen ตัวที่สาม เราต้องไม่วางใน column เดียวกันกับ Queen สองตัวแรก และต้องไม่อยู่ในเส้นทแยงมุมเดียวกัน ดังนั้นจึงมีประมาณ N-2 ตำแหน่งให้เลือก
• กระบวนการนี้จะดำเนินต่อไปจนกระทั่งวาง Queen ตัวสุดท้าย ซึ่งจะมีเพียงตำแหน่งเดียวให้เลือก ดังนั้นจำนวนตำแหน่งที่ต้องพิจารณาทั้งหมดคือ N * (N-1) * (N-2) * ... * 1 = N!

โดย ในแต่ละตำแหน่งที่พิจารณาอยู่ เราต้องใช้เวลา O(N) ในการตรวจสอบว่าสามารถวาง Queen ได้หรือไม่ โดยต้องดูว่ามี Queen ตัวอื่นอยู่ในแนวเดียวกันหรือไม่ ทั้งในแนวนอน แนวตั้ง และแนวทแยงมุม

ดังนั้น Time Complexity โดยรวมของ Backtracking algorithm สำหรับปัญหา N-Queen จึงเป็น O(N! * N) = O(N!)

จุดอ่อนของ Backtracking

เรามาพูดถึงจุดอ่อนของ Backtracking algorithm กันบ้าง การใช้ Backtracking Algorithm นั้นจะเริ่มมีปัญหา โดยมีตั้งแต่

1. เมื่อปัญหาเริ่มมีขนาดใหญ่ Backtracking เป็นวิธีการแบบ Brute Force ซึ่งต้องค้นหาคำตอบโดยการ “ลองทุกทาง” เลือกที่เป็นไปได้ ดังนั้นสำหรับปัญหาขนาดใหญ่ที่มีพื้นที่ค้นหาขนาดมหาศาล algorithm นี้จะใช้เวลาและ Resource คอมพิวเตอร์มาก ทำให้มีประสิทธิภาพต่ำ (ดูจาก Big O ก็คงตอบได้ไม่ยาก)
2. เมื่อการทำงานซ้ำซ้อนกัน (Thrashing) Backtracking มักจะทำงานซ้ำๆ กันบ่อยครั้ง เนื่องจากไม่สามารถระบุสาเหตุที่แท้จริงของ fail case ได้ ทำให้ต้องย้อนกลับไปลองวิธีการอื่นๆ แม้ว่าจะเคยพบ fail case นั้นมาก่อนแล้วก็ตาม ส่งผลให้เสียเวลาและ Resource โดยไม่จำเป็นไป
3. เมื่อมีตัวแปรต่อเนื่อง (Continuous) Backtracking เหมาะสำหรับปัญหาที่มีตัวแปรแบบ Discrete เท่านั้น (พูดง่ายๆเช่น จำนวนเต็ม) สำหรับปัญหาที่มีตัวแปรต่อเนื่อง (Continuous) (พูดง่ายๆเช่น ทศนิยม) อาจต้องใช้เทคนิคอื่นร่วมด้วย

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

เทคนิคที่สามารถลด Big O ของ Backtracking

ใน Algorithm เอง มีหลายเทคนิคที่สามารถช่วยลด Time Complexity ของ Backtracking ได้ ดังนี้

1. Pruning เป็นเทคนิคที่สำคัญที่สุดในการลดเวลาการทำงานของ Backtracking โดยการตัดทอนหรือกำจัดส่วนของพื้นที่ค้นหาที่ “ไม่น่าจะนำไปสู่คำตอบที่ถูกต้อง” ออกไป ทำให้ไม่ต้องสิ้นเปลืองเวลาในการค้นหาในส่วนนั้น

ตัวอย่างเช่น

• ปัญหาการหาเส้นทางสั้นที่สุดในเขาวงกต โดย algorithm จะค้นหาทุกเส้นทางที่เป็นไปได้จนถึงจุดหมายปลายทาง
• เมื่อใช้ Pruning พื้นที่ค้นหา algorithm จะตรวจสอบว่าเส้นทางนั้นนำไปสู่ทางตันหรือไม่ ถ้าใช่ก็จะข้ามการค้นหาในเส้นทางนั้นไปเลย จะช่วยลดเวลาในการค้นหาลงได้

2. Memoization เป็นการจดจำและเก็บผลลัพธ์ของปัญหาย่อยที่ได้คำนวณไปแล้ว เพื่อไม่ต้องคำนวณซ้ำในกรณีที่ต้องใช้ผลลัพธ์เดิมนั้นอีก ช่วยลดการคำนวณซ้ำซึ่งเป็นจุดอ่อนของ Backtracking

ตัวอย่างเช่น

• ปัญหาการแก้สมการ fibonacci โดย algorithm จะคำนวณ fibonacci ตั้งแต่เริ่มต้นทุกครั้ง
• เมื่อใช้การ Memoization algorithm จะเก็บค่า fibonacci ที่คำนวณไปแล้วไว้ในตัวแปร ถ้าต้องการค่าเดิมก็จะดึงมาใช้ได้เลยโดยไม่ต้องคำนวณซ้ำได้

** เทคนิคนี้จะเป็นส่วนหนึ่งของ Dynamic Programming เราจะกลับมาพูดคุยกันอีกทีในหัวข้อนั้นกัน

3. Heuristics เป็นการประมาณค่าหรือใช้กฎเบื้องต้นในการคัดกรองทางเลือกบางส่วนออกไป เพื่อให้ algorithm สามารถเลือกทางเลือกที่ดีที่สุดก่อน ช่วยลดพื้นที่ค้นหาและเวลาในการค้นหาลงได้

ตัวอย่างเช่น

• ปัญหาการเล่นเกม N-Puzzle โดย algorithm จะลองย้ายชิ้นส่วนไปทุกตำแหน่งที่เป็นไปได้
• เมื่อใช้ค่า Heuristics algorithm จะประเมินว่าการย้ายชิ้นส่วนไปยังตำแหน่งใดจะนำไปสู่จุดหมายปลายทางได้เร็วที่สุด แล้วจะลองย้ายไปยังตำแหน่งนั้นก่อน

4. Constraints การนำข้อจำกัดหรือเงื่อนไขเพิ่มเติมของปัญหามาใช้ในการตัดสินว่าจะดำเนินการค้นหาในทางเลือกนั้นต่อไปหรือไม่ ช่วยกำจัดทางเลือกที่ไม่เป็นไปตามข้อจำกัดออกไปได้เร็วขึ้น

ตัวอย่างเช่น

• ปัญหาการแก้เกม sudoku โดย algorithm จะลองวางตัวเลขทุกค่าที่เป็นไปได้ในทุกช่องว่าง
• เมื่อใช้ Constraints เช่น ตัวเลขในแถวเดียวกันต้องไม่ซ้ำกัน algorithm จะตรวจสอบข้อจำกัดนี้ก่อน ถ้าไม่เป็นไปตามก็จะข้ามการลองวางตัวเลขในช่องนั้นไป

5. Ordering การจัดลำดับการค้นหาทางเลือกต่างๆ อย่างเหมาะสม เช่น เริ่มจากทางเลือกที่มีโอกาสนำไปสู่คำตอบมากที่สุดก่อน อาจช่วยให้พบคำตอบได้เร็วขึ้น

ตัวอย่างเช่น

• ปัญหาการหาคำตอบของวงเล็บเปิด-ปิดที่ถูกต้อง โดย algorithm จะลองเรียงวงเล็บทุกรูปแบบ
• เมื่อใช้การ Ordering algorithm จะเริ่มลองเรียงวงเล็บจากรูปแบบที่มีโอกาสถูกต้องมากที่สุดก่อน เช่น เริ่มจากวงเล็บเปิดทั้งหมดแล้วตามด้วยวงเล็บปิด

6. Precomputation การคำนวณค่าหรือข้อมูลบางอย่างที่จำเป็นสำหรับการค้นหาไว้ล่วงหน้า เพื่อไม่ต้องคำนวณซ้ำในระหว่างการค้นหา จะสามารถช่วยประหยัดเวลาได้

ตัวอย่างเช่น

• ปัญหาการหาเส้นทางสั้นที่สุดของพนักงานขาย โดย algorithm จะคำนวณระยะทางระหว่างเมืองทุกคู่ในระหว่างการค้นหา
• เมื่อใช้ Precomputation algorithm จะคำนวณระยะทางระหว่างเมืองทุกคู่ไว้ก่อนล่วงหน้า แล้วจึงนำค่าเหล่านั้นมาใช้ในการค้นหาเส้นทาง ก็จะช่วยประหยัดเวลาจากอต่เดิมที่ต้องคำนวนทุกคู่เมืองได้

และนี่คือเทคนิคโดยประมาณที่ช่วยทำให้การคำนวน Backtracking สามารถลดการคำนวนให้น้อยลงได้ การนำเทคนิคเหล่านี้มาประยุกต์ใช้อย่างเหมาะสมจะช่วยลดความซับซ้อนทางเวลาและเพิ่มประสิทธิภาพของ Backtracking algorithm ได้อย่างมาก