ย้อนรอยอัลกอริทึม

Backtracking Algorithm คืออะไร?

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

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

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

อัลกอริทึมการย้อนกลับทำงานอย่างไร?

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

ย้อนรอยอัลกอริทึม

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

โดยทั่วไปอัลกอริทึมการย้อนกลับมีขั้นตอนต่อไปนี้ในการแก้ปัญหา:

ขั้นตอนที่ 1) การเริ่มต้น: เริ่มด้วยสารละลายเปล่าหรือบางส่วนเบื้องต้น

ขั้นตอนที่ 2) การเลือก:โดยพิจารณาจากเกณฑ์และข้อจำกัดที่เฉพาะเจาะจง เลือกตัวเลือกหนึ่งเพื่อขยายโซลูชันปัจจุบัน

ขั้นตอนที่ 3) การสำรวจ:แก้ปัญหาแบบย้อนกลับโดยพิจารณาผู้สมัครที่เลือกและดำเนินการแก้ไขปัญหาต่อไป

ขั้นตอนที่ 4) การตรวจสอบข้อจำกัด: ตรวจสอบว่าโซลูชันบางส่วนในปัจจุบันละเมิดข้อจำกัดใดๆ ในทุกขั้นตอนหรือไม่ หากเป็นเช่นนั้น ให้ย้อนกลับไปยังขั้นตอนก่อนหน้าและลองใช้ตัวเลือกอื่น

ขั้นตอนที่ 5) การยุติ:กระบวนการย้อนกลับจะหยุดเมื่อพบวิธีแก้ปัญหาที่ถูกต้องหรือใช้การรวมกันทั้งหมดจนหมด

ขั้นตอนที่ 6) การย้อนกลับ:หากตัวเลือกปัจจุบันไม่สามารถแก้ไขปัญหาที่กำหนดได้ ตัวเลือกจะกลับไปยังสถานะก่อนหน้า จากนั้นจะพิจารณาตัวเลือกใหม่เพื่อแก้ไขปัญหาที่กำหนด

ขั้นตอนที่ 7) ทำซ้ำ: ดำเนินการต่อด้วยขั้นตอนเหล่านี้จนกว่าจะสามารถแก้ไขปัญหาได้หรือพิจารณาตัวเลือกทั้งหมดแล้ว

ลักษณะการวนซ้ำของอัลกอริทึมการย้อนกลับ

อัลกอริทึมการย้อนกลับมีลักษณะการเรียกซ้ำ ซึ่งหมายความว่าอัลกอริทึมจะเรียกตัวเองด้วยพารามิเตอร์ที่แตกต่างกันจนกว่าจะพบวิธีแก้ปัญหาหรือทดสอบความเป็นไปได้ทั้งหมดแล้ว:

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

คำศัพท์ทั่วไปที่เกี่ยวข้องกับปัญหาการย้อนกลับ

เหล่านี้เป็นคำศัพท์พื้นฐานบางส่วนที่เกี่ยวข้องกับเทคนิคการย้อนกลับ:

  • เวกเตอร์โซลูชัน: แสดงถึงโซลูชันเป็น n-tuples เช่น (X1, X2, …, Xn)
  • ข้อ จำกัด:กฎการจำกัดค่า X ทั้งโดยชัดแจ้งและโดยนัย
  • พื้นที่โซลูชั่น:ค่า X ที่ถูกต้องทั้งหมดที่ตอบสนองข้อจำกัดที่ชัดเจน
  • ต้นไม้ประจำรัฐ: แสดงพื้นที่โซลูชันเป็นต้นไม้
  • พื้นที่ของรัฐ:อธิบายเส้นทางในแผนผังสถานะ
  • สถานะปัญหา:โหนดในต้นไม้การค้นหาที่แสดงโซลูชันบางส่วน
  • สถานะโซลูชัน:สถานะที่สร้างทูเพิลโซลูชันที่ถูกต้องใน S
  • ตอบ รัฐ: ตอบสนองข้อจำกัดที่ซ่อนเร้นและให้ผลลัพธ์ตามที่ต้องการ
  • โหนดที่มีแนวโน้ม: นำไปสู่โซลูชันที่ต้องการและยังคงเป็นไปได้
  • โหนดที่ไม่มีแนวโน้ม:นำไปสู่สภาวะที่ไม่สามารถทำได้และไม่ได้รับการสำรวจเพิ่มเติม
  • โหนดสด:สร้างขึ้นโดยเด็กที่ยังไม่ถูกสำรวจ
  • อี-โหนด:โหนดสดพร้อมการสร้างเด็กอย่างต่อเนื่อง
  • โหนดที่ตายแล้ว:ไม่มีการขยายผลสร้างลูกหลานเพิ่มเติมอีก
  • การสร้างโหนดเชิงลึก:ใช้โหนดสดล่าสุดเป็น E-node ถัดไป
  • ฟังก์ชันการกำหนดขอบเขต:เพิ่มหรือลดค่า B(x1, x2, …, Xa) เพื่อการเพิ่มประสิทธิภาพ
  • ต้นไม้สถิตย์:การกำหนดสูตรต้นไม้อย่างอิสระจากกรณีปัญหา
  • ต้นไม้ไดนามิก:การกำหนดสูตรต้นไม้จะแตกต่างกันไปตามกรณีปัญหา

เมื่อใดจึงควรใช้อัลกอริทึมการย้อนกลับ?

เราสามารถเลือกเทคนิคการย้อนกลับเพื่อแก้ไขปัญหาที่ซับซ้อนได้เมื่อ:

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

ประเภทของปัญหาการย้อนกลับ

มีปัญหาสามประเภทในอัลกอริทึมการย้อนกลับ: ปัญหาการตัดสินใจ ปัญหาการเพิ่มประสิทธิภาพ และปัญหาการแจงนับ มาเรียนรู้เกี่ยวกับปัญหาเหล่านี้ด้านล่างกัน

  1. ปัญหาการตัดสินใจ: ในปัญหาประเภทนี้ เป้าหมายคือการพิจารณาว่ามีวิธีแก้ปัญหาที่เป็นไปได้หรือไม่ เราจะตรวจสอบคำตอบ "ใช่" และ "ไม่ใช่" ตัวอย่างเช่น ปัญหาราชินี n ตัว ซึ่งเป็นปัญหาการตัดสินใจที่ตรวจสอบความน่าจะเป็นในการวางราชินี n ตัวบนกระดานหมากรุกขนาด n × n โดยไม่โจมตีกันเอง
  2. ปัญหาการเพิ่มประสิทธิภาพ:ในปัญหาการเพิ่มประสิทธิภาพ เป้าหมายคือการค้นหาวิธีแก้ปัญหาที่ดีที่สุดจากตัวเลือกมากมาย ซึ่งอาจรวมถึงการกำหนดค่าสูงสุดและต่ำสุดของฟังก์ชันหรือตัวแปรบางตัว ตัวอย่างเช่น พิจารณาปัญหาเป้สะพายหลัง โดยมีเป้าหมายเพื่อเพิ่มมูลค่ารวมของสิ่งของในกระเป๋าให้สูงสุดในขณะที่ต้องปฏิบัติตามขีดจำกัดน้ำหนัก
  3. ปัญหาการนับ:วัตถุประสงค์คือค้นหาวิธีแก้ปัญหาที่เป็นไปได้ทั้งหมดสำหรับปัญหาที่กำหนด เราแสดงรายการตัวเลือกที่ถูกต้องทั้งหมดโดยไม่มีการละเว้น ตัวอย่างเช่น การสร้างชุดตัวอักษรที่เป็นไปได้ทั้งหมดจากชุดอักขระที่กำหนดให้

การประยุกต์ใช้การ Backtracking และตัวอย่าง

มีแอปพลิเคชัน Backtracking มากมาย แอปพลิเคชันบางส่วนจะอธิบายด้านล่างพร้อมรหัสหลอก

  1. Sudoku Solver: ปัญหานี้มีซับกริด 3×3 ที่มีตัวเลขซ้ำกัน เทคนิคการย้อนกลับจะแสดงให้เห็นว่าผลลัพธ์ที่ได้เป็นเท็จ ซึ่งบ่งชี้ว่าจำเป็นต้องมีการจัดวางตัวเลขที่แตกต่างกัน
  2. function solveSudoku(board):
        if no empty cells:
            return true  # Sudoku is solved
        for each empty cell (row, col):
            for num from 1 to 9:
                if num is valid in (row, col):
                    place num in (row, col)
                    if solveSudoku(board):
                        return true
                    remove num from (row, col)
        return false  # No valid solution
    
  3. ปัญหา N-Queen:แนวทางการย้อนกลับจะกำหนดวิธีการนำเสนอราชินีบนกระดานหมากรุก N × N เพื่อไม่ให้ราชินีตัวใดตัวหนึ่งคุกคามซึ่งกันและกัน
  4. function solveNQueens(board, col):
        if col >= N:
            return true  # All queens are placed
        for each row in the column col:
            if isSafe(board, row, col):
                place queen at (row, col)
                if solveNQueens(board, col + 1):
                    return true
                remove queen from (row, col)
        return false  # No valid solution in this branch
    
  5. ปัญหาผลรวมย่อย:ใช้เพื่อค้นหาเซ็ตย่อยของตัวเลขจากเซ็ตที่กำหนดซึ่งรวมกันได้ผลรวมเป้าหมายที่ต้องการ
  6. function subsetSum(nums, target, index, currentSubset):
        if target == 0:
            print(currentSubset)  # Subset with the target sum found
            return
        if index >= len(nums) or target < 0:
            return
       currentSubset.add(nums[index])
       subsetSum(nums, target - nums[index], index + 1, currentSubset)
       currentSubset.remove(nums[index])
       subsetSum(nums, target, index + 1, currentSubset)
    
  7. ปัญหาวัฏจักรแฮมิลตัน:สามารถใช้การย้อนกลับเพื่อค้นหาทัวร์ที่ปิดในกราฟที่เยี่ยมชมแต่ละจุดยอดเพียงครั้งเดียวเท่านั้น
  8. ปัญหาหนูในเขาวงกต:เทคนิคการย้อนกลับใช้เพื่อค้นหาเส้นทางของหนูจากจุดเริ่มต้นของเขาวงกตไปยังทางออก

ข้อดีและข้อเสียของอัลกอริธึมการแบ็คแทร็กกิ้ง

ข้อดีของอัลกอริธึมการย้อนกลับ

เทคนิคการย้อนกลับใช้เพื่อแก้ไขปัญหาที่ซับซ้อน มีข้อดีหลายประการ เช่น:

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

ข้อเสียของอัลกอริธึมการย้อนกลับ

เทคนิคการย้อนกลับยังมีข้อจำกัดบางประการ เช่น ความซับซ้อนของเวลา เทคนิคนี้มีข้อเสียดังต่อไปนี้:

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

ความแตกต่างระหว่างการย้อนกลับและการเรียกซ้ำ

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

สรุป

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

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

นวัตกรรมทางเทคโนโลยีทั้งหมดเหล่านี้จะปฏิวัติอัลกอริทึมการย้อนกลับ ทำให้กลายเป็นเครื่องมือที่ทรงพลังและอเนกประสงค์ในการแก้ไขปัญหาที่ซับซ้อนในโดเมนต่างๆ