Backtracking: ปลดล็อคปัญหาด้วยการค้นหาที่มีประสิทธิภาพใน Ruby

 

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

 

Backtracking คืออะไร?

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

Backtracking นิยมใช้ในการแก้ปัญหาเชิงคอมพิวเตอร์ เช่น การจัดเรียง การหาค่าที่ดีที่สุดในปัญหาที่มีหลายตัวแปร หรือแม้กระทั่งการแก้ปัญหาในเกมเช่น Sudoku, N-Queens เป็นต้น

 

ตัวอย่าง Code ด้วย Ruby

เราจะมาดูตัวอย่างการใช้ Backtracking ในการแก้ปัญหา N-Queens Problem ซึ่งเป็นปัญหาที่มีอยู่ในเกมหมากรุก โดยต้องใช้วิธี placement ภายใน board ให้น้อยที่สุดในความสอดคล้องกัน:

 class NQueens
  def initialize(n)
    @board = Array.new(n) { Array.new(n, 0) }
    @solutions = []
  end

  def solve(n = 0)
    if n == @board.size
      add_solution
      return
    end

    @board.size.times do |col|
      if valid_move?(n, col)
        @board[n][col] = 1
        solve(n + 1)
        @board[n][col] = 0  # backtrack
      end
    end
  end

  def valid_move?(row, col)
    # ตรวจสอบความถูกต้อง
    (0...row).each do |i|
      return false if @board[i][col] == 1 || @board[i][col - (row - i)].to_i == 1 || @board[i][col + (row - i)].to_i == 1
    end
    true
  end

  def add_solution
    solution = @board.map { |row| row.map { |cell| cell == 1 ? 'Q' : '.' }.join }
    @solutions << solution
  end

  def print_solutions
    @solutions.each_with_index do |solution, i|
      puts "Solution ##{i + 1}:"
      solution.each { |row| puts row }
      puts "\n"
    end
  end
end

n_queens = NQueens.new(4)
n_queens.solve
n_queens.print_solutions

ในตัวอย่างข้างต้น เราได้ประกาศคลาส `NQueens` ที่ทำหน้าที่ในการหาคำตอบของปัญหา N-Queens โดยใช้ Backtracking ในการตรวจสอบความถูกต้องเมื่อวาง Queen ลงในแต่ละแถว:

1. `initialize` ทำการสร้าง board ที่มีขนาด n x n

2. `solve` คือฟังก์ชันหลักในการทำงาน ซึ่งถ้าถึงแถวสุดท้าย จะทำการเพิ่ม solution ไปยัง array ของ solutions

3. `valid_move?` ใช้ในการตรวจสอบว่าการวาง Queen ในตำแหน่งนั้นๆ จะไม่ถูก Queen อื่นทำร้าย

4. `add_solution` จะทำการเก็บผลลัพธ์ที่ได้

5. `print_solutions` จะแสดงผลลัพธ์ทั้งหมดที่ทำการหาได้

 

Usecase ในโลกจริง

Backtracking มีการใช้ในหลาย ๆ สาขา เช่น:

- เกม: การแก้ปัญหาในเกมต่าง ๆ เช่น Sudoku, Crossword, และ Maze Solving - วิทยาศาสตร์: การค้นหาโมเลกุลในเคมีที่มีโครงสร้างซับซ้อน - โลจิสติกส์: การวางแผนเส้นทางที่มีประสิทธิภาพในการขนส่งสินค้า

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

 

การวิเคราะห์ Complexity

- Time Complexity: ความซับซ้อนทางเวลาในการใช้ Backtracking มักจะมีรูปแบบเป็น O(N!), เนื่องจากสำหรับ N queens จะมีวิธีการวาง queen ในแต่ละแถวที่มากมาย (O(N^N) ในบางกรณี) - Space Complexity: ความซับซ้อนทางพื้นที่จะอยู่ที่ O(N), เนื่องจากเราต้องใช้พื้นที่ในการจัดเก็บค่าที่ถูกวางในบอร์ด

 

ข้อดีและข้อเสียของ Algorithm นี้

ข้อดี:

- สามารถแก้ปัญหาที่ซับซ้อนได้อย่างเป็นระบบ

- ช่วยลดการทำงานที่ไม่จำเป็นผ่านการ backtrack

- สามารถใช้ได้ง่ายในการเขียนโปรแกรม เช่น ในภาษา Ruby

ข้อเสีย:

- อาจใช้เวลานานหากละเลยการเพิ่มประสิทธิภาพ

- เวลาในการค้นหาอาจมากในกรณีที่มีการแก้ไขที่ลึกเกินไป

 

สรุป

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

หากคุณสนใจในการเรียนรู้การเขียนโปรแกรมไม่ว่าจะเป็น Backtracking หรือเทคนิคอื่น ๆ อย่าลืมมาที่ EPT (Expert-Programming-Tutor) โรงเรียนสอนเขียนโปรแกรมที่คุณจะได้สัมผัสประสบการณ์จริงและเข้าใจพื้นฐานของการเขียนโปรแกรมอย่างลึกซึ้ง!

 

 

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