Propagation redundancy in finite domain constraint satisfaction
Luận án · Tiến sĩ · năm 2006 · đề tài tham khảo
| Loại tài liệu | Luận án |
|---|---|
| Bậc học | Tiến sĩ |
| Tác giả | Chiu Wo Choi |
| Cơ sở đào tạo | Đại học Quốc gia TP. Hồ Chí Minh |
| Năm | 2006 |
| Nguồn | Thư viện số Đại học Quốc gia TP. Hồ Chí Minh · trang gốc |
Tóm tắt
A widely adopted approach to solving constraint satisfaction problems combines backtracking tree search with various degrees of constraint propagation for pruning the search space. One common technique to improve the execution efficiency is to add redundant constraints, which are constraints logically implied by others in the problem model and may offer extra information to enhance constraint propagation. However, some redundant constraints are propagation redundant and hence do not contribute additional propagation information to the constraint solver. In this thesis, we propose propagation rules as a tool to compare the propagation strength of constraints, and establish results relating logical and propagation redundancy. Redundant constraints arise naturally in the process of redundant modeling, where two models of the same problem are connected and combined through channeling constraints. We characterize channeling constraints in terms of restrictive and unrestrictive channel function and give general theorems for proving propagation redundancy of constraints in the combined model. We illustrate, on problems from CSPLib, how detecting and re-moving propagation redundant constraints can often significantly speed up constraint-solving.
Bản toàn văn lưu tại thư viện Đại học Quốc gia TP. Hồ Chí Minh
Thông tin và tóm tắt ở trên lấy từ kho số mở của thư viện trường. Bản toàn văn do thư viện trường quản lý — có nơi cho đọc trực tuyến, có nơi cần tài khoản bạn đọc của trường.
Mở tại thư viện trường ↗
Dùng tài liệu tham khảo cho đúng
- Đọc để hiểu cách người trước đặt câu hỏi, chọn phương pháp, trình bày số liệu — rồi tự làm với dữ liệu và bối cảnh của bạn.
- Ý, số liệu, bảng biểu lấy từ tài liệu này phải trích dẫn (tác giả, năm, tên đề tài, cơ sở đào tạo).
- Đề tài trùng tên vẫn làm được nếu khác đơn vị khảo sát, thời gian hoặc cách tiếp cận — nêu rõ điểm khác trong phần mở đầu.
Đề tài cùng ngành
- Nghiên cứu phản ứng điện hóa của ion Arsenic (III) trên điện cực vàng và ứng dụng phân tích As(III) trong nước
- Nghiên cứu sử dụng cellulose vi khuẩn sinh tổng hợp bởi Acetobacter xylinum từ nước dừa để làm phụ gia sản xuất giấy
- Study of nuclear structure effects from alpha-cluster transfer in nucleus-nucleus scattering and from the nucleon knockout reactions
- Ideal nguyên thuỷ trong Đại số đường đi Leavitt của đa đồ thị
- Nhân tố Việt Nam trong quan hệ Liên Xô - Trung Quốc
- Nuôi cấy mô phân sinh ngọn chồi và tìm hiểu khả năng tái sinh thực vật ở cúc (Chrysanthemum sp.)
- Dòng hóa biểu hiện và tinh sạch beta - galactosidase trong escherichia coli
- Nghiên cứu hệ Protease trùn quế (Perionyx excavatus) trong quá trình tự phân và khả năng ứng dụng
Tác giả muốn gỡ, sửa thông tin hoặc bổ sung bản toàn văn: gửi yêu cầu qua trang Liên hệ, kèm đường dẫn trang này.