huynh_bao5
New Member
Download Luận văn Lập trình ràng buộc với bài toán người chơi gôn
MỤC LỤC
LỜI NÓI ĐẦU .4
KÍ HIỆU VÀ Ý NGHĨA CÁC TỪVIẾT TẮT.6
PHẦN I. GIỚI THIỆU VỀLẬP TRÌNH RÀNG BUỘC .8
PHẦN II. NHỮNG CƠSỞVỀBÀI TOÁN THỎA MÃN RÀNG BUỘC.18
CHƯƠNG 1. GIỚI THIỆU NHỮNG KHÁI NIỆM CƠBẢN . 18
1.1. Những định nghĩa quan trọng trong CSP . 18
1.1.1. Định nghĩa miền và nhãn . 18
1.1.2. Định nghĩa ràng buộc . 20
1.1.3. Định nghĩa sựthỏa mãn . 21
1.1.4. Định nghĩa bài toán thỏa mãn ràng buộc (CSP): . 22
1.1.5. Nhiệm vụtrong bài toán CSP. 23
1.2. CSP cho ràng buộc nhịphân . 24
1.3. Một vài ví dụ. 24
1.3.1. Bài toán N-quân hậu. 24
1.3.2. Bài toán SEND+MORE=MONEY . 25
CHƯƠNG 2. GIẢI BÀI TOÁN THỎA MÃN RÀNG BUỘC. 27
2.1. Rút gọn bài toán (Problem redution). 27
2.1.1 Các định nghĩa. 27
2.1.2 Việc rút gọn bài toán: . 28
2.1.3 Bài toán tối thiểu . 29
2.2. Tìm kiếm bộnghiệm . 30
2.2.1 Thuật toán quay lui đơn giản (Simple Backtracking) . 30
2.2.2 Không gian tìm kiếm của CSPs . 32
2.2.3 Đặc tính tổng quát của không gian tìm kiếm trong CSPs . 34
2.2.4 Kết hợp tìm kiếm và rút gọn bài toán . 35
2.2.5 Những điểm chọn trong tìm kiếm . 35
CHƯƠNG 3. THUẬT TOÁN NHẰM RÚT GỌN VÀ TÌM KIẾM LỜI GIẢI
CHO BÀI TOÁN . 40
3.1. Một sốthuật toán nhằm rút gọn thuật toán. . 40
3.2. Một sốthuật toán nhằm tìm kiếm lới giải cho bài toán. 41
PHẦN III. BÀI TOÁN NGƯỜI CHƠI GÔN .43
CHƯƠNG 1. GIỚI THIỆU BÀI TOÁN. 44
1.1. Giới thiệu. 44
1.2. Những vấn đềcần giải quyết trong bài toán. 46
1.3. Sự đối xứng trong bài toán lập trình ràng buộc. 46
1.3.1. Định nghĩa sự đối xứng trong CSPs. 46
1.3.2. Các phương pháp loại bỏ đối xứng . 48
1.4. Sự đối xứng trong SGP . 49
CHƯƠNG 2. LOẠI BỎ ĐỐI XỨNG BẰNG PHƯƠNG PHÁP TĨNH TRONG
BÀI TOÁN SGP . 51
2.1 Loại bỏ đối xứng tĩnh cơbản . 51
2.2 Loại bỏ đối xứng tĩnh bằng kỹthuật hạn chếmiền (ND) . 53
2.3 Loại bỏ đối xứng tĩ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.1 Mô hình dùng biến tập. 56
3.2 Mô hình dùng biến nguyên. 57
3.3 Mô hình kết hợp giữa biến tập và biến nguyên. 58
3.4 Mô hình AMPL . 60
CHƯƠNG 4. LOẠI BỎ ĐỐI XỨNG BẰNG PHƯƠNG PHÁP THÊM RÀNG
BUỘC TRONG THỜI GIAN TÌM KIẾM CHO SGP . 62
4.1 Phương pháp SBDS. 62
4.1.1 Giới thiệu SBDS. 62
4.1.2 SBDS cho SGP. 65
4.2 Phương pháp SBDD . 66
4.2.1 Giới thiệu SBDD . 66
4.2.2 SBDD với DFS. 68
4.2.3 SBDD áp dụng vào SGP . 69
4.2.4 Kết quảkhi áp dụng SBDD cho SGP . 71
4.2.5 So sánh SBDS và SBDD. 73
CHƯƠNG 5. MỘT SỐPHƯƠNG PHÁP LOẠI BỎ ĐỐI XỨNG ĐỘNG
KHÁC CHO SGP . 75
5.1 Loại bỏ đối xứng với Intelligent-Backtracking (IB) . 75
5.1.1 Ý tưởng thuật toán. 75
5.1.2 Thuật toán. 77
5.2 Local Search cho SGP . 79
5.2.1 Mô hình. 79
5.2.2 Lân cận (Neighborhood) và thành phần Tabu . 79
5.2.3 Thuật toán. 80
CHƯƠNG 6. LOẠI BỎ ĐỐI XỨNG BẰNG PHƯƠNG PHÁP TĨNH VÀ
THÊM RÀNG BUỘC DƯTHỪA ĐỂGIẢI SGP . 81
6.1 Loại bỏ đối xứng trong SGP bằng nhiều điểm nhìn. 81
6.1.1 Một sốkhái niệm quan trọng . 81
6.1.2 Loại bỏ đối xứng bằng phương pháp nhiều “điểm nhìn”. 82
6.2 Loại bỏ đối xứng bằng hạn chếmiền và cố định một sốtay gôn . 88
6.3 So sánh với một sốkỹthuật khác. 90
CHƯƠNG 7. GIẢI SGP TRONG MỘT SỐTRƯỜNG HỢP ĐẶC BIỆT VÀ
MỐI LIÊN QUAN VỚI CÁC HÌNH VUÔNG LATIN TRỰC GIAO . 97
7.1 Giới thiệu thuật toán. 97
7.2 Một sốthảo luận cùng kết quảxung quanh thuật toán. 99
7.3 Liên hệSGP với hình vuông Latin trực giao . 101
7.3.1 Giới thiệu hình vuông Latin trực giao. 101
7.3.2 Mối liên hệgiữa MOLS và SGP . 104
7.3.3 Mối liên hệgiữa SGP và MOLR. 106
PHẦN IV. KẾT LUẬN.107
TÀI LIỆU THAM KHẢO.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Players-F)
Kích cỡ của cây tìm kiếm chính là không gian tìm kiếm. Do vậy càng hạn chế
được nhiều nhánh cây (bằng cách thêm các ràng buộc) thì không gian tìm
kiếm sẽ càng nhỏ đi. Điều đặc biệt quan trọng là càng loại bỏ nhánh cây ở
mức càng thấp (gần gốc) thì hiệu quả càng cao (không gian tìm kiếm càng
nhỏ đi). Điều này lý giải tại sao một số lớn các ràng buộc tập trung vào tuần
thứ 2 (phần 2.1).
Trong phần này, cũng đưa ra một ràng buộc nữa cho tuần thứ hai. Do các tay
gôn ở nhóm cuối trong tuần thứ nhất sẽ luôn luôn là phần tử cuối cùng của
các nhóm kể từ tuần thứ hai trở đi (vì các nhóm được sắp theo thứ tự tăng
dần). Chính vì vậy mà ta có đề xuất thêm ràng buộc cho tuần thứ hai như sau:
Các tay gôn trong nhóm cuối cùng ở tuần thứ nhất được gán lần luợt (theo trật
tự tăng dần) vào các nhóm cuối của tuần thứ hai (xem bảng 2.3, các phần tử
10, 11, 12 được cố định trong tuần thứ 2)
1 2 3 4 5 6 7 8 9 10 11 12
1 4 7 2 ? 10 3 ? 11 ? ? 12
Bảng 2.3: Kỹ thuật cố định phần tử cho trường hợp 4-3-w
Hẳn nhiên, nó là kỹ thuật không bảo toàn nghiệm cho trường hợp g < s (Bảo
toàn cho trường hợp g=s). Nhưng cũng thật ngạc nhiên, thực tế nó lại rất hiệu
quả trong nhiều trường hợp. Tất nhiên ở đây có sự thỏa thuận giữa tính bảo
toàn nghiệm và tính hiệu quả.
56
Luận văn thạc sĩ Lập trình ràng buộc và bài toán người chơi gôn
CHƯƠNG 3. CÁC MÔ HÌNH CÙNG PHƯƠNG PHÁP GIẢI SGP
Sở dĩ phần này được giới thiệu sau Chương 2 là vì hầu hết các mô hình đều sử
dụng những kỹ thuật loại bỏ đối xứng tĩnh (phần 2.1). SGP có nhiều mô hình.
Đây cũng là một lý do tại sao SGP tạo được sự thú vị. Trong phần này ta cần
quan tâm đến hai vấn đề, đó là mô hình hóa bài toán và phương pháp giải (kỹ
thuật, thuật toán). Mô hình hóa bài toán liên quan đến hai vấn đề: chọn biến
và chọn ràng buộc. Trong thực tế, thì hai vấn đề này gần như nhau vì việc
chọn biến phụ thuộc rất lớn vào việc chọn ràng buộc. Ta sẽ thấy, SGP có
nhiều cách mô hình khác nhau, điều quan trọng là mô hình nào có ràng buộc
dễ thực thi trong môi trường lập trình ràng buộc.
3.1 Mô hình dùng biến tập
Một ví dụ viết bằng ECLiPSe trong [39] có thể tìm tại [42] dùng biến tập (giá
trị của biến là một tập) để thể hiện cho mỗi nhóm trong mỗi tuần. Thực tế,
đây là một ý tưởng tốt, nhằm loại bỏ đối xứng trong nhóm (φP), các nhóm khi
đó được coi như là một danh sách hay một mảng. Như vậy chúng ta có thể thể
hiện mô hình bài toán:
Biến: Nhóm được thể hiện như một mảng của các mảng các biến tập:
Group[k] là nhóm thứ i của tuần thứ k.
Ràng buộc :
o Số phần tử trong mỗi biến là s: |Group[k]|=s
o Các tập trong mỗi tuần không giao nhau:
Group[k] ∩ Group[k][i’]= ∅ sao cho 1 ≤ i ≤ g với mọi 1 ≤ k ≤ w
o Bất kỳ hai tập nào cũng chỉ giao nhau nhiều nhất 1 phần tử:
Formatted: Font: 14 pt
Formatted: Font: 14 pt, Italic
Formatted: Font: 14 pt, Italic
Formatted: Font: 14 pt, Font color:
Black
Formatted: Font: 14 pt, Not Italic,
Font color: Black
Formatted: Font: 14 pt, Font color:
Black
Formatted: Font color: Black
Formatted: Font color: Black
Formatted: Font: Not Italic, Font
color: Black
Formatted: Font color: Black
Deleted: hương
Deleted: ¶
57
Luận văn thạc sĩ Lập trình ràng buộc và bài toán người chơi gôn
|Group[k] ∩ Group[k’][i’]| ≤ 1 sao cho 1 ≤ i, i’ ≤ g , 1 ≤ k, k’ ≤
w
Với mô hình như vậy, và sử dụng những kỹ thuật loại bỏ đối xứng (phần 2.1),
được thực thi trên ILOG Solver, máy PC Pentium/166MHz. Kết quả như sau:
Trường hợp 8-4-4 có thể giải được
Trường hợp 8-4-5 không tìm thấy lời giải trong nhiều giờ.
Chỉ ra được trường hợp 4-3-5 không có nghiệm trong 5800 giây.
Có thể rút ra nhận xét rằng điểm bất lợi của mô hình này là việc gặp khó khăn
khi thêm các ràng buộc để loại bỏ đối xứng.
3.2 Mô hình dùng biến nguyên
Một mô hình khác là mô hình dùng biến nguyên. Trong mô hình này, chúng
ta cũng cần xác định:
Biến: là mảng số nguyên playInWeek. Nó dùng để chứa tất cả các khả
năng của các cặp khi chơi với nhau, ví dụ, cặp số 1 là giữa tay gôn 1 và
tay gôn 2, cặp số 2 là giữa tay gôn 1 và tay gôn 3, … và cặp cuối cùng
giữa tay gôn n-1 và tay gôn n. Có (n-1)*n/2 biến như vậy. Giá trị được
gán cho biến playInWeek[pair(i,j)], nó trả về số tuần mà pair(i,j) gặp
nhau.
Ràng buộc: chúng ta phải đối mặt với việc biểu diễn ràng buộc trong
mô hình này.
o Chúng ta cần một lượng lớn các ràng buộc để đảm bảo tính bắc
cầu: nếu i, j chơi cùng với nhau trong tuần k và j, l chơi cùng với
nhau trong tuần k, thì khi đó i, l cũng chơi cùng với nhau.
o Chúng ta cũng cần ràng buộc để đảm bảo rằng mỗi tay gôn sẽ
chơi với s-1 tay gôn khác trong mỗi tuần. Chúng ta cần những
Formatted: Font color: Black
Formatted: Font: 14 pt, Not Italic,
Font color: Black
Formatted: Font color: Black
Formatted: Font: Italic
Formatted: Font: Italic
Formatted: Font: Italic
Formatted: Font: Italic
Formatted: Font: Italic
Formatted: Font: Italic
58
Luận văn thạc sĩ Lập trình ràng buộc và bài toán người chơi gôn
ràng buộc như vậy cho mọi tay gôn trong mọi tuần, hơn là cho
các nhóm như mô hình trước. Hay nói một cách khác, mô hình
không cần ràng buộc để đảm bảo mỗi cặp tay gôn được gán
chung một nhóm nhiều nhất một lần.
o Chúng ta cũng có thể dùng ràng buộc để loại bỏ đối xứng giữa
các tuần. Chúng ta gọi j là tay gôn nhỏ nhất chơi với tay gôn 1 ở
tuần thứ k, playInWeek[pair(1,j)]=k, và l là tay gôn nhỏ nhất
chơi với tay gôn 1 ở tuần thứ k+1, playInWeek[pair(1,j)]=k+1,
khi đó j
không có khái nhiệm nhóm thứ nhất, nhóm thứ 2, …
Mô hình này ít tính đối xứng hơn mô hình tập. Chúng không có đối xứng giữa
các thành viên trong nhóm, và cũng mất sự đối xứng giữa các nhóm trong
tuần vì thực tế nhóm không được thể hiện trong mô hình này.
Với mô hình này, kết quả như sau:
Chỉ ra được trường hợp 4-3-5 không có nghiệm trong 570 giây (nhanh
hơn 10 lần so với mô hình trước)
Tuy nhiên số ràng buộc đảm bảo tính bắc cầu sẽ tăng lên rất nhanh và
đòi hỏi nhiều không gian bộ nhớ. Chính điều này mà mô hình không
thể SGP cho trường hợp 8-4-9.
3.3 Mô hình kết hợp giữa biến tập và biến nguyên
Khó khăn chính của mô hình biến nguyên là việc mô tả ràng buộc bắc cầu.
Tuy nhiên nó lại không xuất hiện ở mô hình tập, bởi vì các tay gôn chơi với
nhau trong một nhóm được sắp tự động trong cùng một tập, và trong mô hình
59
Luận văn thạc sĩ Lập trình ràng buộc và bài toán người chơi gôn
biến nguyên thì lại không thể hiện nhóm. Vì vậy chúng ta có thể kết hợp hai
mô hình để giải quyết bài toán.
Biến: PlayWith[k] để chỉ tập các tay gôn chơi cùng tay gôn i trong
tuần thứ k (bao gồm chính tay gôn i). Chú ý rằng biến tập này khác với
mô hình tập ban đầu (một tay gôn cho mỗi tuần thay cho mỗi nhóm cho
mỗi tuần). Do đó, chúng ta tránh được đối xứng trong nhóm.
Ràng buộc:
o Để đảm bảo cỡ của mỗi nhóm là s, chúng ta có thể dùng biến
PlayWith ho
Download miễn phí Luận văn Lập trình ràng buộc với bài toán người chơi gôn
MỤC LỤC
LỜI NÓI ĐẦU .4
KÍ HIỆU VÀ Ý NGHĨA CÁC TỪVIẾT TẮT.6
PHẦN I. GIỚI THIỆU VỀLẬP TRÌNH RÀNG BUỘC .8
PHẦN II. NHỮNG CƠSỞVỀBÀI TOÁN THỎA MÃN RÀNG BUỘC.18
CHƯƠNG 1. GIỚI THIỆU NHỮNG KHÁI NIỆM CƠBẢN . 18
1.1. Những định nghĩa quan trọng trong CSP . 18
1.1.1. Định nghĩa miền và nhãn . 18
1.1.2. Định nghĩa ràng buộc . 20
1.1.3. Định nghĩa sựthỏa mãn . 21
1.1.4. Định nghĩa bài toán thỏa mãn ràng buộc (CSP): . 22
1.1.5. Nhiệm vụtrong bài toán CSP. 23
1.2. CSP cho ràng buộc nhịphân . 24
1.3. Một vài ví dụ. 24
1.3.1. Bài toán N-quân hậu. 24
1.3.2. Bài toán SEND+MORE=MONEY . 25
CHƯƠNG 2. GIẢI BÀI TOÁN THỎA MÃN RÀNG BUỘC. 27
2.1. Rút gọn bài toán (Problem redution). 27
2.1.1 Các định nghĩa. 27
2.1.2 Việc rút gọn bài toán: . 28
2.1.3 Bài toán tối thiểu . 29
2.2. Tìm kiếm bộnghiệm . 30
2.2.1 Thuật toán quay lui đơn giản (Simple Backtracking) . 30
2.2.2 Không gian tìm kiếm của CSPs . 32
2.2.3 Đặc tính tổng quát của không gian tìm kiếm trong CSPs . 34
2.2.4 Kết hợp tìm kiếm và rút gọn bài toán . 35
2.2.5 Những điểm chọn trong tìm kiếm . 35
CHƯƠNG 3. THUẬT TOÁN NHẰM RÚT GỌN VÀ TÌM KIẾM LỜI GIẢI
CHO BÀI TOÁN . 40
3.1. Một sốthuật toán nhằm rút gọn thuật toán. . 40
3.2. Một sốthuật toán nhằm tìm kiếm lới giải cho bài toán. 41
PHẦN III. BÀI TOÁN NGƯỜI CHƠI GÔN .43
CHƯƠNG 1. GIỚI THIỆU BÀI TOÁN. 44
1.1. Giới thiệu. 44
1.2. Những vấn đềcần giải quyết trong bài toán. 46
1.3. Sự đối xứng trong bài toán lập trình ràng buộc. 46
1.3.1. Định nghĩa sự đối xứng trong CSPs. 46
1.3.2. Các phương pháp loại bỏ đối xứng . 48
1.4. Sự đối xứng trong SGP . 49
CHƯƠNG 2. LOẠI BỎ ĐỐI XỨNG BẰNG PHƯƠNG PHÁP TĨNH TRONG
BÀI TOÁN SGP . 51
2.1 Loại bỏ đối xứng tĩnh cơbản . 51
2.2 Loại bỏ đối xứng tĩnh bằng kỹthuật hạn chếmiền (ND) . 53
2.3 Loại bỏ đối xứng tĩ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.1 Mô hình dùng biến tập. 56
3.2 Mô hình dùng biến nguyên. 57
3.3 Mô hình kết hợp giữa biến tập và biến nguyên. 58
3.4 Mô hình AMPL . 60
CHƯƠNG 4. LOẠI BỎ ĐỐI XỨNG BẰNG PHƯƠNG PHÁP THÊM RÀNG
BUỘC TRONG THỜI GIAN TÌM KIẾM CHO SGP . 62
4.1 Phương pháp SBDS. 62
4.1.1 Giới thiệu SBDS. 62
4.1.2 SBDS cho SGP. 65
4.2 Phương pháp SBDD . 66
4.2.1 Giới thiệu SBDD . 66
4.2.2 SBDD với DFS. 68
4.2.3 SBDD áp dụng vào SGP . 69
4.2.4 Kết quảkhi áp dụng SBDD cho SGP . 71
4.2.5 So sánh SBDS và SBDD. 73
CHƯƠNG 5. MỘT SỐPHƯƠNG PHÁP LOẠI BỎ ĐỐI XỨNG ĐỘNG
KHÁC CHO SGP . 75
5.1 Loại bỏ đối xứng với Intelligent-Backtracking (IB) . 75
5.1.1 Ý tưởng thuật toán. 75
5.1.2 Thuật toán. 77
5.2 Local Search cho SGP . 79
5.2.1 Mô hình. 79
5.2.2 Lân cận (Neighborhood) và thành phần Tabu . 79
5.2.3 Thuật toán. 80
CHƯƠNG 6. LOẠI BỎ ĐỐI XỨNG BẰNG PHƯƠNG PHÁP TĨNH VÀ
THÊM RÀNG BUỘC DƯTHỪA ĐỂGIẢI SGP . 81
6.1 Loại bỏ đối xứng trong SGP bằng nhiều điểm nhìn. 81
6.1.1 Một sốkhái niệm quan trọng . 81
6.1.2 Loại bỏ đối xứng bằng phương pháp nhiều “điểm nhìn”. 82
6.2 Loại bỏ đối xứng bằng hạn chếmiền và cố định một sốtay gôn . 88
6.3 So sánh với một sốkỹthuật khác. 90
CHƯƠNG 7. GIẢI SGP TRONG MỘT SỐTRƯỜNG HỢP ĐẶC BIỆT VÀ
MỐI LIÊN QUAN VỚI CÁC HÌNH VUÔNG LATIN TRỰC GIAO . 97
7.1 Giới thiệu thuật toán. 97
7.2 Một sốthảo luận cùng kết quảxung quanh thuật toán. 99
7.3 Liên hệSGP với hình vuông Latin trực giao . 101
7.3.1 Giới thiệu hình vuông Latin trực giao. 101
7.3.2 Mối liên hệgiữa MOLS và SGP . 104
7.3.3 Mối liên hệgiữa SGP và MOLR. 106
PHẦN IV. KẾT LUẬN.107
TÀI LIỆU THAM KHẢO.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ật cố định một số tay gôn (FixingPlayers-F)
Kích cỡ của cây tìm kiếm chính là không gian tìm kiếm. Do vậy càng hạn chế
được nhiều nhánh cây (bằng cách thêm các ràng buộc) thì không gian tìm
kiếm sẽ càng nhỏ đi. Điều đặc biệt quan trọng là càng loại bỏ nhánh cây ở
mức càng thấp (gần gốc) thì hiệu quả càng cao (không gian tìm kiếm càng
nhỏ đi). Điều này lý giải tại sao một số lớn các ràng buộc tập trung vào tuần
thứ 2 (phần 2.1).
Trong phần này, cũng đưa ra một ràng buộc nữa cho tuần thứ hai. Do các tay
gôn ở nhóm cuối trong tuần thứ nhất sẽ luôn luôn là phần tử cuối cùng của
các nhóm kể từ tuần thứ hai trở đi (vì các nhóm được sắp theo thứ tự tăng
dần). Chính vì vậy mà ta có đề xuất thêm ràng buộc cho tuần thứ hai như sau:
Các tay gôn trong nhóm cuối cùng ở tuần thứ nhất được gán lần luợt (theo trật
tự tăng dần) vào các nhóm cuối của tuần thứ hai (xem bảng 2.3, các phần tử
10, 11, 12 được cố định trong tuần thứ 2)
1 2 3 4 5 6 7 8 9 10 11 12
1 4 7 2 ? 10 3 ? 11 ? ? 12
Bảng 2.3: Kỹ thuật cố định phần tử cho trường hợp 4-3-w
Hẳn nhiên, nó là kỹ thuật không bảo toàn nghiệm cho trường hợp g < s (Bảo
toàn cho trường hợp g=s). Nhưng cũng thật ngạc nhiên, thực tế nó lại rất hiệu
quả trong nhiều trường hợp. Tất nhiên ở đây có sự thỏa thuận giữa tính bảo
toàn nghiệm và tính hiệu quả.
56
Luận văn thạc sĩ Lập trình ràng buộc và bài toán người chơi gôn
CHƯƠNG 3. CÁC MÔ HÌNH CÙNG PHƯƠNG PHÁP GIẢI SGP
Sở dĩ phần này được giới thiệu sau Chương 2 là vì hầu hết các mô hình đều sử
dụng những kỹ thuật loại bỏ đối xứng tĩnh (phần 2.1). SGP có nhiều mô hình.
Đây cũng là một lý do tại sao SGP tạo được sự thú vị. Trong phần này ta cần
quan tâm đến hai vấn đề, đó là mô hình hóa bài toán và phương pháp giải (kỹ
thuật, thuật toán). Mô hình hóa bài toán liên quan đến hai vấn đề: chọn biến
và chọn ràng buộc. Trong thực tế, thì hai vấn đề này gần như nhau vì việc
chọn biến phụ thuộc rất lớn vào việc chọn ràng buộc. Ta sẽ thấy, SGP có
nhiều cách mô hình khác nhau, điều quan trọng là mô hình nào có ràng buộc
dễ thực thi trong môi trường lập trình ràng buộc.
3.1 Mô hình dùng biến tập
Một ví dụ viết bằng ECLiPSe trong [39] có thể tìm tại [42] dùng biến tập (giá
trị của biến là một tập) để thể hiện cho mỗi nhóm trong mỗi tuần. Thực tế,
đây là một ý tưởng tốt, nhằm loại bỏ đối xứng trong nhóm (φP), các nhóm khi
đó được coi như là một danh sách hay một mảng. Như vậy chúng ta có thể thể
hiện mô hình bài toán:
Biến: Nhóm được thể hiện như một mảng của các mảng các biến tập:
Group[k] là nhóm thứ i của tuần thứ k.
Ràng buộc :
o Số phần tử trong mỗi biến là s: |Group[k]|=s
o Các tập trong mỗi tuần không giao nhau:
Group[k] ∩ Group[k][i’]= ∅ sao cho 1 ≤ i ≤ g với mọi 1 ≤ k ≤ w
o Bất kỳ hai tập nào cũng chỉ giao nhau nhiều nhất 1 phần tử:
Formatted: Font: 14 pt
Formatted: Font: 14 pt, Italic
Formatted: Font: 14 pt, Italic
Formatted: Font: 14 pt, Font color:
Black
Formatted: Font: 14 pt, Not Italic,
Font color: Black
Formatted: Font: 14 pt, Font color:
Black
Formatted: Font color: Black
Formatted: Font color: Black
Formatted: Font: Not Italic, Font
color: Black
Formatted: Font color: Black
Deleted: hương
Deleted: ¶
57
Luận văn thạc sĩ Lập trình ràng buộc và bài toán người chơi gôn
|Group[k] ∩ Group[k’][i’]| ≤ 1 sao cho 1 ≤ i, i’ ≤ g , 1 ≤ k, k’ ≤
w
Với mô hình như vậy, và sử dụng những kỹ thuật loại bỏ đối xứng (phần 2.1),
được thực thi trên ILOG Solver, máy PC Pentium/166MHz. Kết quả như sau:
Trường hợp 8-4-4 có thể giải được
Trường hợp 8-4-5 không tìm thấy lời giải trong nhiều giờ.
Chỉ ra được trường hợp 4-3-5 không có nghiệm trong 5800 giây.
Có thể rút ra nhận xét rằng điểm bất lợi của mô hình này là việc gặp khó khăn
khi thêm các ràng buộc để loại bỏ đối xứng.
3.2 Mô hình dùng biến nguyên
Một mô hình khác là mô hình dùng biến nguyên. Trong mô hình này, chúng
ta cũng cần xác định:
Biến: là mảng số nguyên playInWeek. Nó dùng để chứa tất cả các khả
năng của các cặp khi chơi với nhau, ví dụ, cặp số 1 là giữa tay gôn 1 và
tay gôn 2, cặp số 2 là giữa tay gôn 1 và tay gôn 3, … và cặp cuối cùng
giữa tay gôn n-1 và tay gôn n. Có (n-1)*n/2 biến như vậy. Giá trị được
gán cho biến playInWeek[pair(i,j)], nó trả về số tuần mà pair(i,j) gặp
nhau.
Ràng buộc: chúng ta phải đối mặt với việc biểu diễn ràng buộc trong
mô hình này.
o Chúng ta cần một lượng lớn các ràng buộc để đảm bảo tính bắc
cầu: nếu i, j chơi cùng với nhau trong tuần k và j, l chơi cùng với
nhau trong tuần k, thì khi đó i, l cũng chơi cùng với nhau.
o Chúng ta cũng cần ràng buộc để đảm bảo rằng mỗi tay gôn sẽ
chơi với s-1 tay gôn khác trong mỗi tuần. Chúng ta cần những
Formatted: Font color: Black
Formatted: Font: 14 pt, Not Italic,
Font color: Black
Formatted: Font color: Black
Formatted: Font: Italic
Formatted: Font: Italic
Formatted: Font: Italic
Formatted: Font: Italic
Formatted: Font: Italic
Formatted: Font: Italic
58
Luận văn thạc sĩ Lập trình ràng buộc và bài toán người chơi gôn
ràng buộc như vậy cho mọi tay gôn trong mọi tuần, hơn là cho
các nhóm như mô hình trước. Hay nói một cách khác, mô hình
không cần ràng buộc để đảm bảo mỗi cặp tay gôn được gán
chung một nhóm nhiều nhất một lần.
o Chúng ta cũng có thể dùng ràng buộc để loại bỏ đối xứng giữa
các tuần. Chúng ta gọi j là tay gôn nhỏ nhất chơi với tay gôn 1 ở
tuần thứ k, playInWeek[pair(1,j)]=k, và l là tay gôn nhỏ nhất
chơi với tay gôn 1 ở tuần thứ k+1, playInWeek[pair(1,j)]=k+1,
khi đó j
không có khái nhiệm nhóm thứ nhất, nhóm thứ 2, …
Mô hình này ít tính đối xứng hơn mô hình tập. Chúng không có đối xứng giữa
các thành viên trong nhóm, và cũng mất sự đối xứng giữa các nhóm trong
tuần vì thực tế nhóm không được thể hiện trong mô hình này.
Với mô hình này, kết quả như sau:
Chỉ ra được trường hợp 4-3-5 không có nghiệm trong 570 giây (nhanh
hơn 10 lần so với mô hình trước)
Tuy nhiên số ràng buộc đảm bảo tính bắc cầu sẽ tăng lên rất nhanh và
đòi hỏi nhiều không gian bộ nhớ. Chính điều này mà mô hình không
thể SGP cho trường hợp 8-4-9.
3.3 Mô hình kết hợp giữa biến tập và biến nguyên
Khó khăn chính của mô hình biến nguyên là việc mô tả ràng buộc bắc cầu.
Tuy nhiên nó lại không xuất hiện ở mô hình tập, bởi vì các tay gôn chơi với
nhau trong một nhóm được sắp tự động trong cùng một tập, và trong mô hình
59
Luận văn thạc sĩ Lập trình ràng buộc và bài toán người chơi gôn
biến nguyên thì lại không thể hiện nhóm. Vì vậy chúng ta có thể kết hợp hai
mô hình để giải quyết bài toán.
Biến: PlayWith[k] để chỉ tập các tay gôn chơi cùng tay gôn i trong
tuần thứ k (bao gồm chính tay gôn i). Chú ý rằng biến tập này khác với
mô hình tập ban đầu (một tay gôn cho mỗi tuần thay cho mỗi nhóm cho
mỗi tuần). Do đó, chúng ta tránh được đối xứng trong nhóm.
Ràng buộc:
o Để đảm bảo cỡ của mỗi nhóm là s, chúng ta có thể dùng biến
PlayWith ho