Luận văn Thạc sĩ: Lập trình ràng buộc với bài toán người chơi gôn

Luận văn Thạc sĩ phân tích Lập trình ràng buộc và ứng dụng giải bài toán người chơi gôn. Trình bày các khái niệm, mô hình và giải thuật tối ưu.

• Tác giả: Nguyễn Văn Hậu
• Người hướng dẫn: PGS. Nguyễn Tinh Thuý
• Trường học: Trường Đại Học Bách Khoa Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Lập Trình Ràng Buộc Với Bài Toán Người Chơi Gôn
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2006
• Địa điểm: Hà Nội

Tóm tắt

I. Giới thiệu về Lập trình Ràng buộc

Lập trình ràng buộc (Constraint Programming - CP) là một paradigm lập trình mạnh mẽ được phát triển từ cuối những năm 1960. Nó cho phép các lập trình viên mô tả và duy trì các quan hệ phức tạp giữa các đối tượng một cách dễ dàng. Thay vì chỉ định từng bước thực hiện, lập trình ràng buộc cho phép khai báo những ràng buộc (constraints) mà dữ liệu phải thỏa mãn. Phương pháp này giúp giải quyết các bài toán tối ưu hóa, lập lịch, và phân công một cách hiệu quả. Các ngôn ngữ CP hiện đại sử dụng lan truyền cục bộ để tự động suy diễn và loại bỏ các giá trị không khả thi, giúp giảm không gian tìm kiếm đáng kể.

1.1. Định nghĩa vấn đề thỏa mãn Ràng buộc

Bài toán thỏa mãn ràng buộc (CSP - Constraint Satisfaction Problem) bao gồm ba thành phần chính: tập hợp các biến, miền giá trị của từng biến, và tập hợp các ràng buộc. Mục tiêu là tìm một phép gán giá trị cho tất cả các biến sao cho tất cả các ràng buộc được thỏa mãn. CSP được ứng dụng rộng rãi trong các lĩnh vực như lên kế hoạch, lập lịch biểu, và thiết kế cơ khí.

1.2. Những khái niệm cơ bản trong CSP

Các khái niệm quan trọng bao gồm miền giá trị, ràng buộc nhị phân, và tính nhất quán. Miền giá trị là tập hợp tất cả các giá trị có thể gán cho một biến. Ràng buộc xác định những tổ hợp giá trị nào được phép. Lan truyền ràng buộc là kỹ thuật giảm không gian tìm kiếm bằng cách loại bỏ các giá trị không khả thi từ các miền biến.

II. Các Thuật toán Tìm kiếm và Rút gọn

Để giải quyết bài toán CSP, cần kết hợp giữa rút gọn bài toán và tìm kiếm có lập luận. Rút gọn bài toán nhằm loại bỏ các giá trị không khả thi từ miền của các biến trước khi bắt đầu tìm kiếm. Tìm kiếm được thực hiện trên không gian bao gồm tất cả các gán giá trị có thể. Kỹ thuật lan truyền cục bộ (local propagation) là nền tảng của nhiều thuật toán hiệu quả. Các phương pháp như AC-3 (Arc Consistency) giúp duy trì tính nhất quán giữa các biến. Việc kết hợp tìm kiếm và rút gọn tạo thành một chiến lược giải quyết mạnh mẽ, cho phép xử lý các bài toán phức tạp với hiệu suất cao.

2.1. Phương pháp Rút gọn Bài toán

Rút gọn bài toán là quá trình loại bỏ các giá trị từ miền của các biến dựa trên ràng buộc hiện tại. Các định nghĩa như nhất quán cung cấp (Arc Consistency) và nhất quán nút (Node Consistency) là cơ sở. Kỹ thuật hạn chế miền (Domain Reduction) được áp dụng để giảm kích thước miền giá trị, từ đó giảm không gian tìm kiếm đáng kể.

2.2. Chiến lược Tìm kiếm Hiệu quả

Tìm kiếm có lập luận sử dụng các ràng buộc để hướng dẫn quá trình khám phá. Các kỹ thuật như tìm kiếm sâu trước kết hợp với lan truyền ràng buộc giúp phát hiện mâu thuẫn sớm. Heuristic lựa chọn biến và heuristic lựa chọn giá trị tối ưu hóa thứ tự gán giá trị, giảm số nút trong cây tìm kiếm.

III. Bài toán Người chơi Gôn và Ứng dụng CSP

Bài toán người chơi gôn (Social Golfer Problem - SGP) là một bài toán lập trình ràng buộc cổ điển và có tính thách thức cao. Bài toán yêu cầu sắp xếp một số tay gôn thành các nhóm trong nhiều tuần, với điều kiện rằng không có hai tay gôn nào được chơi cùng nhóm quá một lần. Bài toán này có đối xứng cao, khiến việc tìm kiếm trở nên khó khăn. Ứng dụng lập trình ràng buộc vào SGP cho phép mô hình hóa các ràng buộc phức tạp một cách tự nhiên. Bài toán người chơi gôn có nhiều ứng dụng thực tiễn trong lập lịch biểu, phân công công việc, và thiết kế thực nghiệm thống kê.

3.1. Định nghĩa Bài toán Người chơi Gôn

SGP được định nghĩa: sắp xếp g tay gôn thành s nhóm có p người mỗi nhóm, trong w tuần. Ràng buộc chính là không có hai tay gôn nào xuất hiện trong cùng một nhóm quá một lần. Bài toán có thể được biểu diễn bằng các biến, miền giá trị, và ràng buộc trong khung CSP. Ký hiệu: g = số tay gôn, s = số nhóm, p = người trong nhóm, w = số tuần.

3.2. Thử thách của Đối xứng

Đối xứng trong bài toán người chơi gôn bao gồm ba loại: đối xứng trong nhóm (các tay gôn hoán vị), đối xứng trong tuần (các nhóm hoán vị), và đối xứng giữa các tuần. Những đối xứng này làm tăng đáng kể không gian tìm kiếm, khiến nhiều thuật toán tìm kiếm trở nên không hiệu quả. Việc loại bỏ đối xứng là chìa khóa để giải quyết bài toán một cách nhanh chóng.

IV. Các Phương pháp Loại bỏ Đối xứng

Loại bỏ đối xứng là một kỹ thuật quan trọng để cải thiện hiệu suất giải bài toán người chơi gôn. Hai phương pháp chính là SBDS (Symmetry Breaking During Search) và SBDD (Symmetry Breaking By Domain Restrictions). SBDS thêm ràng buộc khi phát hiện mâu thuẫn trong quá trình tìm kiếm. SBDD thu hẹp miền giá trị từ đầu bằng cách cố định một số biến hoặc thêm ràng buộc khác biệt. Các phương pháp này giúp giảm số lượng giải pháp đối xứng, tập trung vào tìm kiếm giải pháp thực sự khác nhau. Kỹ thuật intelligent backtracking kết hợp với loại bỏ đối xứng tạo ra những thuật toán hiệu quả, cho phép giải quyết các bài toán lớn hơn.

4.1. Phương pháp SBDS Loại bỏ Đối xứng Trong Tìm kiếm

SBDS (Symmetry Breaking During Search) hoạt động bằng cách thêm ràng buộc động khi phát hiện đối xứng trong quá trình tìm kiếm. Mỗi khi một nhánh tìm kiếm được khám phá, ràng buộc mới được tạo để ngăn chặn các giải pháp đối xứng tương tự. Phương pháp này thích ứng tốt với bài toán người chơi gôn vì có thể xác định đối xứng cụ thể dựa trên cấu trúc của giải pháp hiện tại.

4.2. Phương pháp SBDD Loại bỏ Đối xứng Qua Hạn chế Miền

SBDD (Symmetry Breaking By Domain Restrictions) loại bỏ đối xứng trước khi bắt đầu tìm kiếm bằng cách thêm ràng buộc tĩnh. Kỹ thuật cố định một số tay gôn trong các tuần hoặc nhóm cụ thể giúp phá vỡ đối xứng. SBDD hiệu quả nhưng có thể mạnh mẽ hơn SBDS vì có thể tìm được tất cả giải pháp cơ bản mà không cần quay lui.

Trích đoạn nội dung tài liệu

BỘ GIÁO DỤC VÀ ĐẢO TẠO TRUONG DAI HOC BACH KHOA HA NOI LUAN VAN THAC SỸ KHOA HOC LẬP TRÌNH RÀNG BUỘC VỚI BÀI TOÁN NGƯỜI CHƠI GÔN NGHÀNH: CÔNG NGHỆ THÔNG TTN MÃ SỐ NGUYÊN VĂN HẬU Người hướng đẫn khoa học: PGS. NGUYỄN TIIANH THUÝ ‘TS. FRANCISCO AZEVEDO HA NOL 2006 MUC LUC LOI NOI DAU 4 KÍ HIỆU VÀ Ý NGHĨA CÁC TU VIET TAT. GIGI THIEU VE LAP TRINH RANG BUOC.

NHUING CO 8G VA BAI TOAN THOA MAN RANG BU 18 CHUONG 1. GIGI THIEU NHUNG KHAI NIÊM CƠ BẢN. Những định nghĩa quan trọng trong CSP 18 1. Định ngiữa miền vànhãn I.

- Dinh nghĩa ràng buộc. Đinh nghĩa sựthóa mãn. Dinh nghĩa bài toán thôa mãn rằng buộcc(CSP) 22 1. Nhiễm vụ trong bai toán CSP.

CSP cho ràng buộc nhị phẩn 24 13. Bài toán N-guân hậu 24 1. Bài toán SEND+MOREEMONEY.- GIẢI BÀITOÁN THÔA MÃN RẰNG BUỘC. Rut gon bat toan (Problem redntion} 27 211 Cácdinhnghũa.

Việc nit gon bài taàn 28 2. Tim kiểm bỏ nghiệm 30 2.3 Không gian lim kiếm cia CSPs 32 2.3 Đặc Lính tổng quát của không gian tìm kiểm trong CSTs. Kếthợp tim kiếm và rút gọn bài toán.5 Những điểm chọn trong lim kiểm. THUAT TOAN NIIAM RUT GON VA TIM KIEM LOI GIẢI GHO BÀI TOÁN 40 3.

Một số thuật tuản nhằm rút gọn thuật toản. Một số thuật toán nhằm tìm kiếm lới giải cho bài toán. 41 PHAN IIL BẢITOÁN NGƯỜICHƠIGÔN.43 +uận văn thạc vĩ Lap trình rằng buộc và bài toán người chơi gôn CHƯƠNG l. GIỚI THIỆU BÀI TOÁN 44 1.

Những vấn đề cần iti quyết trong ‘hai toán. Sự đổi xứng trong bài loan lập trình rằng buộc. Dịnh nghĩa sự đổi xứng trang CSPs 46 1. Các phương pháp loại bỏ đối xửng,.

Sự đối xứng trong SGP 48 CHƯƠNG2. LOAI BO BOI XUNG BANG PHUONG PHAP TINH TRONG BAITOAN SGP. - 51 21 Loại bỏ đối xứng ảnh cợ bản sesee ST 22 Loại bỏ đối xứng tính bằng kỹ thuật hạn chế miễn @D).aại bỏ đổi xứng nh bằng kỹ thuật cố định một số tay gôn 55 CHƯƠNG 3. CÁC MÔ HÌNH CỨNG PHƯƠNG PHÁP GIẢI SGP 56 3.

Mô hình dùng biến lập.2 Mö hinh đùng biển nguyên. Mô hình kết hợp giữa biển tập và biển nguyên 58 34 MôhìnhAMPL. LOẠI BÖ ĐỐI XỨNG RẰNG PHƯƠNG PHÁP THÊM RANG BUQC TRONG THOI GIAN TIM KIEM CHO SGP.1 Phiang phap SBDS 62 411 Giớithiệu§BDS.12 SBMS cho SGP - 65 42 Phương pháp SBDD. SBDD ap dung vio SGP - 69 Két qua khi ap dung SBDD cho SGP.

7E So sanh SBDS va SBDD. MỘT SỐ PHƯƠNG PHÁP LOẠI BỘ ĐÔI XỨNG DONG KHAC.1 Loại bỏ đối xứng với Inveligent acktacking a 75 SAL Ý tưởng thuậttoán. 78 +uận văn thạc vĩ Lập trình ràng buộc và bài loán người chơi gôn 9 lệnh mà từ đỏ việc tính toán giá trị của một thành phần dựa trên 2 thành tổ còn lại. Vì vậy, I có thổ được suy xa từ U và R bằng công thức sau: I=U, Nhưng nếu guá trị của được tính tử hai thành phần cỏn lại, một công thức khác ei pha sink: R UA Việc đỏi hỏi người lập trình mồ tả và duy tì các quan hệ giữa các đổi tượng trong lập trình là hợp lý ch các ứng dụng có sử dụng.

Tuy shiên trơng ;ủdễu ng dụng, vẫn đề quan trọng là mô hình các quan hệ và tim ra các đổi tượng. théa man, Vi ly do đó mà Lừ cuối những uănn 60, đã có nhiễu chuyên gia quan tâm đến các ngôn ngữ lập trinh cho phép người lập trinh đơn gián háa các quan hệ giữa các trạng thải của đối trợng, Nó là vai trỏ thực tlú cơ bản nhằm dim báo rằng những quan hệ đó lay những rằng buộc được duy tr. Những ngôn ngữ như vậy được coi là ngôn ngữ CP (Constraint Programming). lan đâu những ngôn ngữ CP chỉ thành công với một số phần.

(?hủng bố trợ cho một ngôn ngữ truyền thống với việc giải quyết các ràng buộc bằng các kỹ thuật không định hước đơn giản. Những ngôn ngữ nảy phần lớn phụ thuộc vào phương pháp lan truyén cuc bd (local propagation). Phương pháp “lan truyền cục bộ” dùng mội răng buộc để gán ruột giá trị vào một biến clưưa biết từ các giả trị đã biết cho các biến khác trong rằng buộc. trong định hiật ÂÔm có thể tỉnh toàn một giá trị R„ I hoặc V từ hai giá trị đã biết, Bài toán với.

lan truyền ene bộ là phương pháp giái quyết ràng bnộc giữa cäc quan hệ vến. Ví ản, nó không thể dùng để giải cóc phương trình xảy ra đồng thời như X=— Y-Z và X— 2Y+Z. Như vậy việc dựa trêu lan tuyển cục bộ của những ngôn ngữ thời kỳ đân cỏ hai điểm yêu: Những thuận lợi giải quyết những ràng buộc. +uận văn thạc vĩ Lập trình ràng buộc và bài loán người chơi gôn Ky hiện * nghĩa P Chỉ mmột bài toám thóa mãn ràng buộc.

Zhoặc X Chỉ lập cac bién trong CSP D Chỉ mriều cho toàn bộ các biểu trong CSP c Lap trinh Logic Rang bude ” Số tay gồu trong bài toán “Người chơi gôn” 8 Sẻ nhóm trong một tuần s Số phần lữ trong xuỗi nhôm. w Số tuần đạt được Gy Chỉ tay gồu trơng tuâu thứ ï ở nhóm thử ÿ tứ) Chí tay gõn trong tuần thí ? ở nhàm Thứ j Tại vị trí n Is Số phân từ của lập S Or Đối xứng trang nhóm (các tay gồn thay đổi) 5 Đổi xứng trong tuần (cá nhóm thay đổi) Ow Đổi ximg giữa các tuần (các tuần thay đổi) x Đổi xứng giữa các tay gôn (cúc tay gôn hoán vị) Na) Số hình vuéng lớn nhất có thể từ tập MOLS cấp ø Ngon Số hình chữ nhật lớn nhất cỏ thể từ tập MOLR cấp m7 rMOLSớ) C6 z hình vuông Lan trực giao cấp m rMOLR(nxn) Có r hình chữ nhật Latn trực giao cắp mi +uận văn thạc vĩ Lập trình ràng buộc và bài loán người chơi gôn 9 lệnh mà từ đỏ việc tính toán giá trị của một thành phần dựa trên 2 thành tổ còn lại. Vì vậy, I có thổ được suy xa từ U và R bằng công thức sau: I=U, Nhưng nếu guá trị của được tính tử hai thành phần cỏn lại, một công thức khác ei pha sink: R UA Việc đỏi hỏi người lập trình mồ tả và duy tì các quan hệ giữa các đổi tượng trong lập trình là hợp lý ch các ứng dụng có sử dụng. Tuy shiên trơng ;ủdễu ng dụng, vẫn đề quan trọng là mô hình các quan hệ và tim ra các đổi tượng.

théa man, Vi ly do đó mà Lừ cuối những uănn 60, đã có nhiễu chuyên gia quan tâm đến các ngôn ngữ lập trinh cho phép người lập trinh đơn gián háa các quan hệ giữa các trạng thải của đối trợng, Nó là vai trỏ thực tlú cơ bản nhằm dim báo rằng những quan hệ đó lay những rằng buộc được duy tr. Những ngôn ngữ như vậy được coi là ngôn ngữ CP (Constraint Programming). lan đâu những ngôn ngữ CP chỉ thành công với một số phần. (?hủng bố trợ cho một ngôn ngữ truyền thống với việc giải quyết các ràng buộc bằng các kỹ thuật không định hước đơn giản.

Những ngôn ngữ nảy phần lớn phụ thuộc vào phương pháp lan truyén cuc bd (local propagation). Phương pháp “lan truyền cục bộ” dùng mội răng buộc để gán ruột giá trị vào một biến clưưa biết từ các giả trị đã biết cho các biến khác trong rằng buộc. trong định hiật ÂÔm có thể tỉnh toàn một giá trị R„ I hoặc V từ hai giá trị đã biết, Bài toán với. lan truyền ene bộ là phương pháp giái quyết ràng bnộc giữa cäc quan hệ vến.

Ví ản, nó không thể dùng để giải cóc phương trình xảy ra đồng thời như X=— Y-Z và X— 2Y+Z. Như vậy việc dựa trêu lan tuyển cục bộ của những ngôn ngữ thời kỳ đân cỏ hai điểm yêu: Những thuận lợi giải quyết những ràng buộc. +uận văn thạc vĩ Lập trình ràng buộc và bài loán người chơi gôn 5.2 Loœal§eareheho8QP. Làn cận (Neighborhood) và thanh phân Tgbn.

LOAI BO DOI XUNG BANG PHUONG PHAP TINH VA “THÊM RÀNG BUỘC DƯ THỪA DÊ GIẢI SGŒP.1 Loại bỏ đối xứng trong SGP bằng nhiều điểm nhìn. BL 611 Một số khải niêm quan trọng 1 6.3 Loại bỏ đối xứng bằng phương pháp nhiều “điểm nhìn”. #2 62 Loại bỏ đối xứng bàng hạn chế miễn và cố định một số tay gỏn. 88 63 So sánh với một số kỹ thuật khác.

GIAI SGP TRONG MOT 86 TRUONG HOP BAC BIRT VA. MỐI LIÊN QUAN VỚI CÁC HĨNH VUÔNG LATTN TRỰC GIAO.2 ___ Một số thảo luận cùng kết quả xung quanh thuật toán.4 __ Liên hệ SGP với hình vuông Latin trục giao.1 Giải thiêu hình vuâng Latin trực giao lôi 7. Môi ênhộ giữa MOLS va SGP Seo. Mắt liên hệ giữa SGPvà MOI.

sceesenieririeririsreasoae TỦ TÀI T,IỆU THAM KHẢO - 118 +uận văn thạc vĩ Lập trình ràng buộc và bài loán người chơi gôn 4 LOI NOI DAU Người đầu tiên mà tôi xin dành sự cảm ơn và kinh trong dic biét 1a PGS. Nghyễn Thanh Thủy. Không những cuốn sách đần tiên đã làm tôi say mê với “Trí tuệ Nhân tạo” là của Thầy mà Thầy còn là người trực tiếp hưởng dẫn của. Chỉnh Thấy là người đã tin tưởng và lạo điều kiệu tốt nhất cho tôi hoàn thành Luận văn tết nghiệp này.

Chắc chắn sẽ không thế nói hết được những tình cảm mà tồi muốn nói, muản vin on Wi TS. Thay là người cùng tôi ngồi viết những chương tinh đầu trên và sửa lỗi cho tôi. Mọi thắc mắc của tôi đồn được Thay giải đáp và còn hơn thể nữa. Thầy coi lôi là một người bạn, với tôi, Thấy là một người bạn lớn.

Tỏi cũng rất muốn đảnh lới cảm ơn tới 7S. Trấn Đình Khang, người đã có những giúp đỡ tôi, động viên lôi rất nhưều về mật tính thần. Téi xin cảm ơm tới tất cả những đồng nghiệp trong khoa CNTT, trưởng ĐHSPKT Hưng Yên, đặc biệt là 7h.S Ned Hite Tinh, Th.S Nguyén Minh Quy va TRS Nguyễn Đình Hắn, họ là nguồn động viên rết lớn cho tôi. Xin cảm ơn những người bạn tốt của tôi: Vi, ý, Chuẩn, Hiến, Thổ, 2lưng.

Đong, Äanoela, họ đã cỗ vũ và chia sẻ với tôi mọi điền trong cuộc sống, Những người cuỗi cùng mà tôi xii dành lời cảm ơi, là gia đình tôi. Họ luôn lá điểm tựa đâu tiên và mãi mãi của tôi. Mọi điều tôi làm, tôi đều nghĩ tới họ. Lishon, Neay 26 thang 10 wan 2006 +uận văn thạc vĩ Lập trình ràng buộc và bài loán người chơi gôn ACKNOWLEDGEMENTS The first person I would like to thank and respect specially is Prof Nguyen Thanh Thuy.

Not only the first book that I read made me intorested in ‘Artificial Intelligence”, but also he is my excellent supervisor. He believed in me, gave me a good change to do my thosis.