Thuật toán: Tìm hiểu về Quay lui nhánh cận

Thuật toán: Tìm hiểu về Quay lui nhánh cận
  1. Lý thuyết 

Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy.

Tư tưởng

Dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.

Các bước trong việc liệt kê cấu hình dạng X[1…n]:

  • Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
  • Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]…tiếp tục như vậy cho tới bước:
  • ….
  • Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
  • Thông báo cấu hình tìm được.

Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu

Backtracking Algorithm

Kĩ thuật nhánh cận

Vì thuật toán đệ quy/quay lui thường có độ phức tạp là cấp số mũ nên đa số bài toán sẽ không thể xử lí trong thời gian yêu cầu.

Tuy nhiên khi xét các trường hợp, ta có thể áp dụng kĩ thuật bằng cách loại bỏ sớm các nhánh không thể khả thi từ sớm để giảm bớt rất nhiều độ phức tạp của Code.

VD:

Ta có 10 công việc với thời gian cần làm và lương nhận được khác nhau. Mỗi công việc chỉ làm 1 lần.

Cho một khoảng thời gian có là T, ví dụ khi ta đã tìm được 1 khả năng:

  • Trong 10 tiếng, chọn 4 công việc và kiếm được 600 nghìn

Thì khi xét 1 nhánh khác với 3 công việc, và ta nhận thấy nếu 

  • Thời gian còn lại / (Thời gian dành cho công việc tốt nhất) * Lương công việc cao nhất

Tức là cho dù ta làm công việc tốt nhất cho khoảng thời gian còn lại mà vẫn ít tiền hơn khả năng trên, thì không việc gì cần xét tiếp nhánh đó nữa.

|| Khi bạn đang tắc đường và cố chui vào 1 ngõ rẽ cho nhanh, nhưng bạn nhẩm cho dù đi đường vòng này nhanh nhất vẫn chậm hơn chờ tắc bình thường, thì tốt nhất nên quay đầu lại ngay chứ đừng chui vào ngõ tiếp.

Bài 1:  P135SUMG – SUM5 G – Xâu đặc biệt

https://www.spoj.com/PTIT/problems/P135SUMG/

RiGSu98VtUp07pJVcrBUMkU1Uj47Ht 6UU GqjI8QBq31D 8aSs - quochung.cyou PTIT

Ý tưởng:

  • Tại các vị trí ‘_’ , ta thử tất cả chữ cái có thể thay vào, sau đó tiếp tục di chuyển đến các từ ngữ tiếp theo
  • Cần lưu trữ lại số lượng các phụ âm, nguyên âm, số lượng chữ L hiện tại để dừng lại nếu không thỏa mãn yêu cầu

Độ phức tạp Code: 

  • Do đi qua từng vị trí (n) và tại mỗi vị trí có nhiều nhất 2 nhánh mới tạo ra, nên ~ 2^n
d7UxEWp b1yaW8 P dgr56MMHG8HvFPC2OElB0zyzTjDAAXTYjwfTJQbhQtp Hz0dt8jNSjdLFQYU y1CQoR9THLyI8zoNSAdiO G4t1JYMbGn2QQoBfubnxXgcyNE83nT - quochung.cyou PTIT

Bài 2:  BCQUEEN – N – Queen

https://www.spoj.com/PTIT/problems/BCQUEEN/

MkdmamvxiEI2wZdvuMFEpwcjb9KuLsQGTdflV8Us2OTz4pK 7wyJ - quochung.cyou PTIT

Ý tưởng:

  • Tại các vị trí bất kì, ta thử đặt quân hậu tại đó, sau đó tiếp tục thử
  • Khi đi đến vị trí cuối cùng (cuối phải) thì dừng lại và đếm cấu hình đã thỏa mãn thêm 1
GitHub - andykdy/N-Queens: Solving N-Queens with genetic algorithm

Độ phức tạp:

  • Tại mỗi hàng cần lặp qua tất cả các cột rồi tại mỗi cột tiếp tục thử
  • Độ phức tạp: n^2
30ZkDBRPXWzBw7HXRyJFYAvFw4aal - quochung.cyou PTIT

Bài 3:  P167PROC – ROUND 7C – Ký tự lặp trong 2 xâu liên tiếp

https://www.spoj.com/PTIT/problems/P167PROC/

Ý tưởng:

  • Do N khá nhỏ, ta sinh hoán vị các cách sắp xếp từ
  • Tại mỗi cấu hình hoán vị, ta thử lặp qua dãy sắp xếp hiện tại và đếm số lần lặp, do input đảm bảo các từ được sắp xếp sẵn nên có thể dùng tìm kiếm nhị phân để tối ưu

Độ phức tạp:

  • Gọi độ dài string là L, số lượng xâu là n
  • Sinh toàn bộ hoán vị :  L !
  • Tại mỗi hoán vị, lặp qua dãy 1 lần : n
  • Tại mỗi phần tử, lặp qua tất cả vị trí và tìm kiểm nhị phân : L log(L)
  • Độ phức tạp tổng : L ! n L log(L)
Pi S8JJ9lR7tmY1rcqzGGg8Q MdDsUoLSkGhn2qam fTQbC5rhcBXXW9 AImMp5hP aqsN0yXD kEN8 NYKk0ua2XQ7bwbziNRFTsvk0d0I4fr1PbhNVR4oLr RGQ7f23kPEsR7GoOSajNAWNAkH9A - quochung.cyou PTIT

Comments

No comments yet. Why don’t you start the discussion?

Leave a Reply