Backtracking: การแก้ปัญหาที่ซับซ้อนด้วย Objective-C

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

การทำงานของ Backtracking

Backtracking จะเริ่มต้นด้วยการสร้างทางเลือกที่เป็นไปได้ จากนั้นมันจะตรวจสอบแต่ละทางเลือกเรื่อย ๆ จนกระทั่งพบทางเลือกที่ถูกต้อง ในกรณีที่พบว่าทางเลือกที่เลือกไปนั้นไม่เป็นทางออกที่ถูกต้อง (backtrack) ระบบจะเดินทางกลับเพื่อสำรวจทางเลือกอื่น ๆ อีกครั้ง และกระบวนการนี้จะนำไปสู่การตอบข้อคำถามที่ถูกต้องในท้ายที่สุด

Use Case ในโลกจริง

Backtracking มีการนำไปใช้ในหลาย ๆ ด้าน เช่น

ตัวอย่าง Code ใน Objective-C

เราจะลองมาสร้างตัวอย่างการทำ Sudoku ด้วย Backtracking กัน โดยเราจะมีตาราง Sudoku เป็นฟังก์ชันในการแก้ปัญหา ดังนี้:

 #import <Foundation/Foundation.h>

#define UNASSIGNED 0
#define N 9

BOOL isSafe(int grid[N][N], int row, int col, int num) {
    for (int x = 0; x < N; x++) {
        if (grid[row][x] == num || grid[x][col] == num) {
            return NO;
        }
    }

    int startRow = row - row % 3, startCol = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (grid[i + startRow][j + startCol] == num) {
                return NO;
            }
        }
    }

    return YES;
}

BOOL solveSudoku(int grid[N][N]) {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            if (grid[row][col] == UNASSIGNED) {
                for (int num = 1; num <= 9; num++) {
                    if (isSafe(grid, row, col, num)) {
                        grid[row][col] = num;

                        if (solveSudoku(grid)) {
                            return YES;
                        }
                        grid[row][col] = UNASSIGNED; // backtrack
                    }
                }
                return NO; // trigger backtracking
            }
        }
    }
    return YES;
}

void printGrid(int grid[N][N]) {
    for (int r = 0; r < N; r++) {
        for (int d = 0; d < N; d++) {
            printf("%d ", grid[r][d]);
        }
        printf("\n");
    }
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int grid[N][N] = {
            {5, 3, UNASSIGNED, UNASSIGNED, 7, UNASSIGNED, UNASSIGNED, UNASSIGNED, UNASSIGNED},
            {6, UNASSIGNED, UNASSIGNED, 1, 9, 5, UNASSIGNED, UNASSIGNED, UNASSIGNED},
            {UNASSIGNED, 9, 8, UNASSIGNED, UNASSIGNED, UNASSIGNED, UNASSIGNED, 6, UNASSIGNED},
            {8, UNASSIGNED, UNASSIGNED, UNASSIGNED, 6, UNASSIGNED, UNASSIGNED, UNASSIGNED, 3},
            {4, UNASSIGNED, UNASSIGNED, 8, UNASSIGNED, 3, UNASSIGNED, UNASSIGNED, 1},
            {7, UNASSIGNED, UNASSIGNED, UNASSIGNED, 2, UNASSIGNED, UNASSIGNED, UNASSIGNED, 6},
            {UNASSIGNED, 6, UNASSIGNED, UNASSIGNED, UNASSIGNED, UNASSIGNED, 2, 8, UNASSIGNED},
            {UNASSIGNED, UNASSIGNED, UNASSIGNED, 4, 1, 9, UNASSIGNED, UNASSIGNED, 5},
            {UNASSIGNED, UNASSIGNED, UNASSIGNED, UNASSIGNED, 8, UNASSIGNED, UNASSIGNED, 7, 9}
        };

        if (solveSudoku(grid)) {
            printGrid(grid);
        } else {
            printf("No solution exists");
        }
    }
    return 0;
}

ในโค้ดตัวอย่างข้างต้น เราได้สร้างฟังก์ชัน `solveSudoku` ที่ทำการตรวจสอบและกรอกค่าลงในช่องที่ว่างในตาราง Sudoku หากพบว่าไม่มีการจัดเรียงที่ถูกต้อง (backtrack) จะทำการย้อนกลับไปเลือกหมายเลขอื่น

วิเคราะห์ Complexity

การใช้ Backtracking จะมีการประเมิน Complexity ในเชิงเวลาว่า Worst case อาจจะมีตั้งแต่ O(n!) ในปัญหาที่ซับซ้อน เช่น Sudoku แต่ในกรณีที่มีการใช้เทคนิคอื่น ๆ ร่วมด้วยเช่น Heuristic เรียบร้อยแล้ว Complexity จะลดลงได้

ข้อดี

- การออกแบบ Backtracking ง่ายต่อการเข้าใจและใช้งาน

- เหมาะสำหรับปัญหาที่ต้องการการค้นหาค่าที่หนาแน่น

ข้อเสีย

- หากไม่มีการปรับปรุง Complexity อาจทำให้การคำนวณใช้เวลานาน

- บางครั้งการใช้ Backtracking อาจไม่เหมาะสมกับปัญหาที่มีโครงสร้างที่ซับซ้อน

เรียนรู้เพิ่มเติมและเชิญชวนที่ EPT

หากคุณต้องการเพิ่มพูนความรู้และเข้าใจ Algorithm ยอดนิยมอย่าง Backtracking รวมทั้งการพัฒนาโปรแกรมในหลายภาษารวมทั้ง Objective-C ขอเชิญคุณเข้าศึกษาที่ EPT (Expert-Programming-Tutor) สถานที่ที่เต็มไปด้วยผู้เชี่ยวชาญที่จะช่วยให้คุณสามารถเข้าใจและทำโปรแกรมได้อย่างมั่นใจ

ร่วมกันเปิดโลกแห่งการเขียนโปรแกรมและเรียนรู้สิ่งใหม่ ๆ ไปด้วยกันที่ EPT!

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