ย้อนรอยอัลกอริทึม
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 ได้
- การตัดสินใจนำไปสู่ทางเลือกเพิ่มเติม: คุณสามารถเลือก เทคนิคการย้อนกลับเพื่อทบทวนทางเลือกอย่างเป็นระบบ
- จำเป็นต้องสำรวจวิธีแก้ปัญหาที่เป็นไปได้ทั้งหมด:การย้อนกลับจะสำรวจโซลูชันทั้งหมดอย่างเป็นระบบด้วยการทำชุดการตัดสินใจที่สร้างขึ้นจากกันและกัน
ประเภทของปัญหาการย้อนกลับ
มีปัญหาสามประเภทในอัลกอริทึมการย้อนกลับ: ปัญหาการตัดสินใจ ปัญหาการเพิ่มประสิทธิภาพ และปัญหาการแจงนับ มาเรียนรู้เกี่ยวกับปัญหาเหล่านี้ด้านล่างกัน
- ปัญหาการตัดสินใจ: ในปัญหาประเภทนี้ เป้าหมายคือการพิจารณาว่ามีวิธีแก้ปัญหาที่เป็นไปได้หรือไม่ เราจะตรวจสอบคำตอบ "ใช่" และ "ไม่ใช่" ตัวอย่างเช่น ปัญหาราชินี n ตัว ซึ่งเป็นปัญหาการตัดสินใจที่ตรวจสอบความน่าจะเป็นในการวางราชินี n ตัวบนกระดานหมากรุกขนาด n × n โดยไม่โจมตีกันเอง
- ปัญหาการเพิ่มประสิทธิภาพ:ในปัญหาการเพิ่มประสิทธิภาพ เป้าหมายคือการค้นหาวิธีแก้ปัญหาที่ดีที่สุดจากตัวเลือกมากมาย ซึ่งอาจรวมถึงการกำหนดค่าสูงสุดและต่ำสุดของฟังก์ชันหรือตัวแปรบางตัว ตัวอย่างเช่น พิจารณาปัญหาเป้สะพายหลัง โดยมีเป้าหมายเพื่อเพิ่มมูลค่ารวมของสิ่งของในกระเป๋าให้สูงสุดในขณะที่ต้องปฏิบัติตามขีดจำกัดน้ำหนัก
- ปัญหาการนับ:วัตถุประสงค์คือค้นหาวิธีแก้ปัญหาที่เป็นไปได้ทั้งหมดสำหรับปัญหาที่กำหนด เราแสดงรายการตัวเลือกที่ถูกต้องทั้งหมดโดยไม่มีการละเว้น ตัวอย่างเช่น การสร้างชุดตัวอักษรที่เป็นไปได้ทั้งหมดจากชุดอักขระที่กำหนดให้
การประยุกต์ใช้การ Backtracking และตัวอย่าง
มีแอปพลิเคชัน Backtracking มากมาย แอปพลิเคชันบางส่วนจะอธิบายด้านล่างพร้อมรหัสหลอก
- Sudoku Solver: ปัญหานี้มีซับกริด 3×3 ที่มีตัวเลขซ้ำกัน เทคนิคการย้อนกลับจะแสดงให้เห็นว่าผลลัพธ์ที่ได้เป็นเท็จ ซึ่งบ่งชี้ว่าจำเป็นต้องมีการจัดวางตัวเลขที่แตกต่างกัน
- ปัญหา N-Queen:แนวทางการย้อนกลับจะกำหนดวิธีการนำเสนอราชินีบนกระดานหมากรุก N × N เพื่อไม่ให้ราชินีตัวใดตัวหนึ่งคุกคามซึ่งกันและกัน
- ปัญหาผลรวมย่อย:ใช้เพื่อค้นหาเซ็ตย่อยของตัวเลขจากเซ็ตที่กำหนดซึ่งรวมกันได้ผลรวมเป้าหมายที่ต้องการ
- ปัญหาวัฏจักรแฮมิลตัน:สามารถใช้การย้อนกลับเพื่อค้นหาทัวร์ที่ปิดในกราฟที่เยี่ยมชมแต่ละจุดยอดเพียงครั้งเดียวเท่านั้น
- ปัญหาหนูในเขาวงกต:เทคนิคการย้อนกลับใช้เพื่อค้นหาเส้นทางของหนูจากจุดเริ่มต้นของเขาวงกตไปยังทางออก
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
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
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)
ข้อดีและข้อเสียของอัลกอริธึมการแบ็คแทร็กกิ้ง
ข้อดีของอัลกอริธึมการย้อนกลับ
เทคนิคการย้อนกลับใช้เพื่อแก้ไขปัญหาที่ซับซ้อน มีข้อดีหลายประการ เช่น:
- เทคนิคการย้อนกลับมีประสิทธิภาพในการจัดการกับข้อจำกัด
- วิธีนี้เหมาะสำหรับการแก้ไขปัญหาการเพิ่มประสิทธิภาพ
- เทคนิคนี้ใช้ได้กับปัญหาหลายประเภท
- ขั้นตอนนี้สามารถช่วยตรวจสอบวิธีแก้ปัญหาที่เป็นไปได้ทั้งหมด
- เนื่องจากมีการย้อนกลับ จึงช่วยประหยัดหน่วยความจำได้มากกว่าเทคนิค Bruteforce
ข้อเสียของอัลกอริธึมการย้อนกลับ
เทคนิคการย้อนกลับยังมีข้อจำกัดบางประการ เช่น ความซับซ้อนของเวลา เทคนิคนี้มีข้อเสียดังต่อไปนี้:
- ไม่มีการรับประกันว่าจะแก้ปัญหาได้
- มันช้าลงเนื่องจากมีหลายการผสมผสานกัน
- มีความซับซ้อนของเวลาสูงเนื่องจากมีความเป็นไปได้หลายประการ
- ไม่เหมาะกับข้อจำกัดแบบเรียลไทม์ เนื่องจากการค้นหาวิธีแก้ปัญหาที่ดีที่สุดอาจใช้เวลานาน
- ประสิทธิภาพขึ้นอยู่กับระดับความซับซ้อนของปัญหา
ความแตกต่างระหว่างการย้อนกลับและการเรียกซ้ำ
Recursion | ย้อนรอย |
---|---|
เรียกตัวเองจนกว่าจะถึงกรณีฐาน | ใช้การเรียกซ้ำเพื่อตรวจสอบความเป็นไปได้ทั้งหมดจนกระทั่งพบผลลัพธ์ที่ดีที่สุดเท่าที่จะเป็นไปได้ |
แนวทางจากล่างขึ้นบน | แนวทางจากบนลงล่าง |
ไม่มีค่าใดที่ถูกทิ้งไป | โซลูชันที่ไม่สามารถดำเนินการได้จะถูกปฏิเสธ |
สรุป
การย้อนกลับเป็นกลยุทธ์อัลกอริทึมที่มีประโยชน์สำหรับการแก้ปัญหาที่ซับซ้อนโดยการสำรวจวิธีแก้ปัญหาที่เป็นไปได้อย่างเป็นระบบและย้อนกลับเมื่อจำเป็น เราคาดหวังว่าเทคนิคการย้อนกลับจะได้รับการปรับปรุงด้วยการปรับปรุงพลังการประมวลผลและประสิทธิภาพของอัลกอริทึม ความก้าวหน้าเหล่านี้จะช่วยให้สามารถแก้ไขปัญหาที่ใหญ่และซับซ้อนมากขึ้นได้อย่างมีประสิทธิภาพ
นอกจากนี้ โมเดลการเรียนรู้ของเครื่องยังสามารถช่วยแนะนำการตัดสินใจย้อนกลับโดยอิงจากรูปแบบที่เรียนรู้ก่อนหน้านี้ได้
นวัตกรรมทางเทคโนโลยีทั้งหมดเหล่านี้จะปฏิวัติอัลกอริทึมการย้อนกลับ ทำให้กลายเป็นเครื่องมือที่ทรงพลังและอเนกประสงค์ในการแก้ไขปัญหาที่ซับซ้อนในโดเมนต่างๆ