CHƯƠNG 5 – CÁC PHƯƠNG PHÁP TÌM KIẾM LỜI GIẢI THỎA MÃN CÁC RÀNG BUỘC

3. Các cải tiến của giải thuật quay lui

Trong giải thuật RescusiveBacktracking ở trên, thứ tự các biến có thể ảnh hưởng đến thời gian và không gian bộ nhớ của giải thuật. Chúng ta có thể thay đổi thứ tự các biến để gán giá trị, và khi biến được chọn, chúng ta có thể chọn giá trị nào trước các giá trị khác trong các giá trị hợp lệ để gán cho biến đó. Đôi khi thứ tự các biến và thứ tự các giá trị gán cho các biến làm tăng đáng kể hiệu quả của giải thuật. a) Nguyên tắc chọn biến tiếp theo Vì lời giải của bài toán chỉ xuất hiện ở mức độ sâu n trong giải thuật đệ qui, vì vậy ResicusiveBacktracking ưu tiên phát triển theo chiều sâu để tìm ra phép gán đầy đủ (tức là lời giải) của bài toán trong thời gian nhanh nhất. Khi một số biến được gán giá trị, miền giá trị của các biến còn lại cũng sẽ bị co hẹp lại do tập các ràng buộc chi phối. Vì thế, để có thể tìm kiếm được phép gán có độ sâu n nhanh nhất mà không bị hủy bỏ để gán lại giá trị cho biến thì có 2 nguyên tắc sau: - Nguyên tắc 1: Lựa chọn biến mà miền giá trị hợp lệ còn lại là ít nhất (biến có ít lựa chọn nhất nên được chọn trước để làm giảm độ phức tạp của cây tìm kiếm) - Nguyên tắc 2: Lựa chọn biến tham gia vào nhiều ràng buộc nhất (gán cho biến khó thỏa mãn nhất) Trong hai nguyên tắc trên, nguyên tắc thứ nhất được ưu tiên cao hơn và được áp dụng trong suốt quá trình thực hiện của giải thuật. Đối với phép chọn biếu đầu tiên hoặc trong trường hợp có nhiều biến có cùng số giá trị ít nhất thì nguyên tắc thứ hai sẽ được sử dụng để lựa chọn biến tiếp theo. Ví dụ, đối với bài toán tô màu đồ thị, ban đầu chúng ta chọn biến SA để gán giá trị vì SA tham gia vào nhiều mối ràng buộc hơn (nguyên tắc 2). Khi chọn màu biến cho SA thì các biến WA, NT, Q, NSW,V sẽ được chọn ở bước gán tiếp theo do chỉ còn 2 lựa chọn là hai màu còn lại (nguyên tắc 1), trong 5 biến này ta lại lấy biến NT, Q hoặc NSW vì nó tham gia vào nhiều ràng buộc hơn (có thể chọn 1 trong ba biến này ngẫu nhiên). Cứ như vậy chúng ta sẽ chọn thứ tự các biến còn lại dựa trên Nguyên tắc 1, nếu có nhiểu biến cùng thỏa mãn nguyên tắc 1 thì chọn trong chúng biến thỏa mãn Nguyên tắc 2. b) Nguyên tắc chọn thứ tự giá trị gán cho biến Một khi một biến được lựa chọn để gán giá trị thì sẽ có nhiều giá trị có thể gán cho biến đó. Việc lựa chọn thứ tự giá trị gán cho biến có tác động không nhỏ trong việc tìm ra lời giải đầu tiên. Trong trường hợp bài toán cần tìm tất cả lời giải hoặc bài toán không có lời giải thì thứ tự các giá trị gán cho biến không có tác dụng. Trong trường hợp bài toán yêu cầu tìm ra một lời giải và chúng ta mong muốn tìm ra lời giải trong thời gian nhanh nhất thì chúng ta sẽ lựa chọn giá trị cho biến đang xét sao cho nó ít ràng buộc đến các biến còn lại nhất. Ví dụ: nếu ta đã chọn WA=đỏ, NT=xanh da trời và chúng ta đang xem xét gán giá trị cho biến Q. Có 2 giá trị có thể gán cho Q mà không bị xung đột với hai phép gán trước: đỏ và xanh da trời. Trong 2 cách này thì nếu gán xanh da trời thì làm cho biến SA không còn giá trị để gán, còn nếu gán màu đỏ thì sẽ có 1 giá trị có thể gán cho biến SA. Vậy trong trường hợp này ta sẽ gán màu đỏ cho biến Q để tăng khả năng tìm được lời giải đầu tiên. c) Kiểm tra tiến (kiểm tra trước – forward checking) Trong nguyên tắc chọn thứ tự giá trị gán cho một biến, chúng ta cần phải kiểm tra xem giá trị định gán sẽ tác động thế nào đối với các biến chưa gán thông qua các ràng buộc. Việc hạn xác định tác động trước như vậy gọi là forward checking. Forward checking còn có tác dụng hạn chế không gian tìm kiếm (hạn chế miền giá trị cho các biến còn lại khi biến hiện tại được gán một giá trị cụ thể). Ví dụ, nếu ban đầu chúng ta gán WA màu đỏ thì miền giá trị của các bang lân cận (NT và SA) sẽ không thể là màu đỏ được nữa. Nếu gán tiếp Q là màu xanh lá cây thì NT và SA chỉ còn nhận giá trị là xanh da trời và NSW chỉ còn miền giá trị là màu đỏ (xem diễn biến miền giá trị các biến thu hẹp dần trong quá trình gán giá trị cho biến WA và Q) d) Lan truyền ràng buộc (constraint propagation) Trong quá trình gán giá trị cho biến, nếu một biến có mà miền giá trị của nó không còn giá trị nào hợp lệ để gán thì chúng ta phải hủy bỏ việc gán giá trị cho biến ngay trước đó và gán bằng giá trị khác. Nếu một trong các biến còn lại mà miền giá trị chỉ 1 giá trị hợp lý thì chúng ta có thể áp dụng tập các ràng buộc liên quan đến biến đó để giảm miền giá trị cho biến còn lại khác. Chẳng hạn, bằng forward checking chúng ta đã xác định được biến SA chỉ có giá trị màu xanh da trời thì chúng ta áp dụng các ràng buộc liên quan đến SA để suy ra rằng biến NSW không thể nhận giá trí màu xanh da trời. Khi đó NSW chỉ còn màu đỏ và áp dụng các ràng buộc liên quan đến NSW suy ra V không thể nhận màu đỏ, v.v. Quả trình loại bỏ miền giá trị cho các biên còn lại dựa trên các ràng buộc gọi là lan truyền ràng buộc nhằm giảm bớt không gian tìm kiếm phép gán hợp lệ.