Please enable JavaScript.

Coggle requires JavaScript to display documents.

Cách giải bài toán thỏa mãn ràng buộc (Có thể chưa biết: bài toàn…

- - - - Gán giá trị cho từng biến
      - Chỉ xem xét các giá trị không vi phạm ràng buộc
    - - 4.1 chọn biến chưa có giá trị
      - 4.2 thứ tự giá trị gán
      - 4.3 hàm suy diễn
      - 4.4 hàm quay lui
      - Tăng hiệu suất
        
        (*) Phát hiện trường hợp vô nghiệm sớm?
        
        Được gọi là: PP lan truyền ràng buộc (hoặc pp suy diễn)
        
        gồm 2 pp:
        
        P.P kiểm tra tiến (Forward Checking FC)
        (hay còn gọi là 1-nhất quán: 1 - Consistency)
        
        Nhược điểm:
        nhược điểm của pp này là ko phát hiện lỗi sớm, nó chỉ đảm bảo tính nhất quán cục bộ (local consistency)
        
        P.P cạnh hợp lệ
        (arc-consistency/ AC3/ 2-consistency)
        
        mấu chốt: pp "cạnh hợp lệ" hoàn toàn dựa trên pp "kiểm tra tiến" hay nói cách khác
        nó kế thừa và mở rộng từ pp "kiểm tra tiến"
        
        pp cạnh hợp lệ đơn giản là 1 nút giảm thì các nút LÂN CẬN GIẢM có thể giảm và nếu nút LÂN CẬN GIẢM thì các nút kế (lân cận) với các NÚT LÂN CẬN lại giảm (đệ quy).
        Tóm: pp cạnh hợp lệ là: cứ giảm đi một giá trị => thì ta lại kiểm tra lân cận của nó!
        
        k-consistency (k-hợp lệ):
        
        với mỗi k nút, kiểm tra các phép gán từ k-1
        nút đến nút thứ k
        k càng lớn, chi phí tính toán càng cao
        
        n-hợp lệ ⇒ tìm kiếm không cần quay lại
        
        PP. Khai thác kiến trúc bài toán? - khó
        
        P.P Thứ tự (với 3 Heuristic)
        (Đây là 3 heuristic cho giải pháp quay lui back tracking)
        
        P.P Lựa chọn giá trị - Thứ tự giá trị gán thử (lựa chọn các giá trị)
        => ưu tiên tìm đến lời giải cao
        
        P.p Least-constraining value Heuristic (LCV)
        "tưởng tượng bạn giàu bạn có rồi - hãy nhường người khác"
        
        mục đích tìm kiếm lời giải => Lựa chọn giá trị có ảnh hưởng tối thiểu đến các giá trị khác
        
        P.P Lựa chọn biến - Thứ tự gán các biến (hay còn gọi là lựa chọn biến)
        => ưu tiên tìm đến lời giải ko cao
        
        P.p Minimum Remaining Values
        MRV (còn được gọi là "fail-first"heuristic)
        (Lựa chọn các biến có tập giá trị hợp lệ nhỏ nhất => nghĩa là chọn lại những màu đã tô)
        
        Ý nghĩa + cách giải của pp này là:
        
        Lựa chọn các biến có khả năng tạo lỗi sớm để tỉa nhánh cây tìm kiếm.
        
        fail-first nghĩa là - gặp lỗi
        sớm - sai lầm sớm => thì mục đích là quay lui sớm (đỡ mất tg)
        
        P.p Degree Heuristic (D)
        (ước tính mức độ ảnh hưởng)
        
        Lựa chọn biến bị ràng buộc nhiều nhất với các biến còn lại (Cứ nào có bậc cao nhất là chọn cái đó trước)
        
        Mục đích PP này giúp Giảm số lượng nhánh con