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

: Not Italic Deleted: golfer Deleted: 0¶ 1¶ 2 Deleted: 3¶ 4¶ 5 Deleted: 6¶ 7¶ 8 Deleted: week Deleted: 0¶ 0¶ 0 Deleted: 1¶ 1¶ 1 Deleted: 2¶ 2¶ 2 Deleted: 0¶ 1¶ 2 Deleted: 0¶ 1¶ 2 Deleted: 0¶ 1¶ 2 Deleted: 0¶ 1¶ 2 Deleted: 1¶ 2¶ 0 Deleted: 2¶ 0¶ 1 87 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 xứng giá trị trong V3 . Dùng ràng buộc loại bỏ đối xứng [z0,k,j,..., zn-1,k,j] >lex [z0,k,j+1,..., zn-1,k,j+1] cho mọi 0 ≤ j ≤ g-1 và 0 ≤ k ≤ w-1. Ví dụ trong Bảng 6.1, chúng ta có z0 → [1,0,0, 1,0,0, 1,0,0] và z1 → [1,0,0, 0,1,0, 0,1,0], trong đó z0 → [z0,0,0, z0,0,1, z0,0,2, z0,1,0, z0,1,1, z0,1,2, z0,2,0, z0,2,1, z0,2,2] và z1 → [z1,0,0, z1,0,1, z1,0,2, z1,1,0, z1,1,1, z1,1,2, z1,2,0, z1,2,1, z1,2,2], khi đó z0 >lex z1. Ở đây cần chú ý trật tự giữa zl và pi,k để tránh bị mâu thuẫn. 6.1.2. 3 Kết quả của phương pháp nhiều “điểm nhìn” cho SGP Kết quả trong phần này được thực thi trên ILOG Solver 4.4 với máy Sun Ultra 5/400, 256 MB RAM. Dấu “-” để chỉ nó chạy vượt quá 2 giờ. Bảng 6.3: Kết quả khi dùng phương pháp nhiều “điểm nhìn” cho nghiệm đầu tiên của SGP V1 V3 V1 V2 V1 V3 g s w fails fails choices fails choices fails choices 6 2 11 142 180 0.57 166 425 0.32 142 180 0.2 166 259 0.1 7 2 13 1371 1428 9.63 1525 1966 2.97 1371 1482 1.94 1469 1604 1.4 6 3 5 - - - 47957 47959 332 37590 37591 306 37637 37638 206 7 3 4 687 729 3.33 853 1084 0.81 687 729 0.72 694 760 0.4 8 3 5 - - - 43326 43329 545 17005 17005 206 17067 17068 133 5 4 4 - - - - - - 34727 34727 327 34780 34781 229 6 4 3 - - - - - - 58802 58803 586 59035 59035 370 7 4 3 - - - - - - 20705 20705 272 20947 20947 169 8 4 9 22 142 7.36 27 668 1.52 22 142 0.44 24 207 0.3 7 5 2 4879 4883 112 - - - 48794 48838 127. 50257 50313 78. 8 5 2 7146 7151 261 - - - 71463 71515 213. 74679 74745 127 8 8 9 19 182 41.7 19 821 7.59 19 182 1.75 19 245 0.9 5 4 3 1350 1350 352 49638 49648 435. 13503 13506 134. 15345 15349 80. 5 3 5 1350 1350 215 19643 19654 111. 13503 13506 94.6 16621 16626 64. 5 3 7 1350 1350 46 53824 53954 57.1 13503 13506 19.5 18616 18673 13. Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold Formatted: Font: 14 pt, Bold 88 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 Trong bảng 6.3 ký hiệu V1 V2 là sự kết hợp của hai “điểm nhìn” V1 và V2. Tương tự V1 V3 là sự kết hợp của hai “điểm nhìn” V1 và V3. Lần lượt fails, choices, time chỉ số lần lỗi, số lần chọn khi quay lui và thời gian (giây) cho mỗi “điểm nhìn” tương ứng. Phần được bôi đậm để chỉ mô hình V1 V3 là tốt nhất. Ta sẽ so sánh phương pháp này với phương pháp được đề xuất ở phần sau. 6.2 Loại bỏ đối xứng bằng hạn chế miền (ND) và cố định một số tay gôn (F) Phần lý thuyết đã trình bày chi tiết trong phần 2.2 và 2.3. Ở đây chỉ đưa ra các kết quả cũng như để so sánh với một số phương pháp khác, qua đó để thấy được điểm mạnh cũng như điểm yếu của phương pháp. Kết quả được đưa ra trong Bảng 6.4 sẽ được so sánh với các phương pháp khác ở phần sau: Formatted: Font: 14 pt Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic 89 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 g s w Basic ND ND+ g s w Basi ND ND+ g s w Basi ND ND+ 2 0.02 0.01 0.01 6 0.22 0.18 1.20 11 1.29 1.23 1.11 3 0.02 0.01 0.01 7 0.29 0.25 40.1 12 1.99 1.48 1.33 4 0.06 0.03 0.03 8 0.39 0.32 313 13 2.39 1.79 1.59 5 0.07 0.05 0.05 9 0.52 0.41 0.41 14 2.53 2.17 1.85 6 0.1 0.08 0.08 10 0.63 0.52 0.52 2 15 2.74 2.46 2.12 2 7 0.12 0.11 0.1 2 11 0.77 0.63 0.63 7 42.5 0.99 - 2 0.02 0.01 0.01 6 - - 0.35 8 - 1.30 - 3 0.04 0.03 0.03 7 - 9.16 1.48 3 9 - 3.70 - 3 4 0.08 0.06 0.07 3 8 - - - 4 1.25 0.45 0.40 2 0.02 0.02 0.02 5 47.7 0.57 0.67 5 2.47 0.78 0.69 3 0.07 0.04 0.05 4 6 - - - 6 53.7 1.61 1.06 4 0.14 0.09 0.07 4 39.3 0.39 83.72 7 32.7 61.3 1.48 4 4 5 0.2 0.14 0.12 5 - - - 8 - - 2.16 5 0.1 0.09 0.09 5 6 - - - 4 9 - - 2.49 6 0.14 0.13 0.19 6 6 3 0.38 0.20 0.22 5 6 - 138.7 138.0 7 0.19 0.17 0.63 7 0.36 0.33 0.33 6 5 - 231.2 231.0 8 0.26 0.24 0.64 8 0.49 0.43 0.47 7 4 - 10.04 10.00 2 9 0,29 0.27 0.3 9 0.63 0.56 0.60 8 8 9 - - 6.95 2 0.02 0.01 0.01 10 0.81 0.72 0.79 3 11 - 28.6 - 3 0.03 0.05 0.04 11 1.01 0.89 0.92 4 8 - 18.9 - 4 0.05 0.09 0.09 12 1.20 1.06 1.12 5 6 - 5.13 - 5 0.21 0.16 0.2 2 13 1.27 1.30 7.85 6 5 - 6.06 - 6 9.46 3.51 3.46 8 12.8 6.45 7 4 - 3.58 - 3 7 170.1 180.1 0.95 3 9 - - - 8 3 - 0.84 0.81 2 0.05 0.04 0.03 4 6 11.2 13.2 - 9 9 3 2.63 0.96 0.93 3 0.15 0.1 0.09 5 5 - 1.91 - 2 19 - 7.02 346.0 4 0.66 0.20 1.35 4 - 0.62 - 4 9 - 205.0 - 5 1.22 0.34 1.88 6 5 - - - 9 3 - 1.30 1.24 5 5 6 1.79 0.49 0.78 7 7 8 - - 287.3 10 10 3 - 1.45 1.40 Bảng 6.4: Kết quả cho Basic, F và F+ND Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic 90 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 Trong Bảng 6.4 chỉ ra kết quả được đề xuất (tính bằng giây) khi tìm được nghiệm đầu tiên. Ta dùng SICStus Prolog [29] chạy trên nền Windows XP, máy Laptop Pentium III/850MHz, 256MB. Dấu “-” chỉ thời gian vượt quá 5 phút. Với sự kết hợp khác nhau của 3 kỹ thuật đã mô tả ở trước: Basic (được mô tả trong phần 2.1), ND (được mô tả trong 2.2) và F (được mô tả trong phần 2.3), để có được kết quả khi dùng kỹ thuật Basic, F và F+ND. Trong đó những trường hợp được tô đậm để chỉ đó là trường hợp với số tuần lớn nhất có thể đạt được hoặc nhờ cộng đồng ràng buộc hoặc nhờ những mô hình toán học khác [9,41]. Như vậy dựa vào kết quả thực thi, ta rút ra một số kết luận như sau: ƒ Việc thêm kỹ thuật ND vào Basic cho kết quả hầu như bài toán được giải nhanh hơn trong tất cả các trường hợp. Nó cũng giúp giải được nhiều trường hợp hơn, trong đó có cả những trường hợp được coi là khó của cộng đồng ràng buộc (5-3-7, 7-5-5, 7-6-4, 7-7-8, 8-5-6, 8-5-6, 8-7-4, 9-4-8, 10-4-9, … ). ƒ Khi áp dụng kỹ thuật F nhiều khi chúng ta sẽ mất nghiệm (do nó không bảo toàn tính nghiệm), tuy nhiên nó cho phép chúng ta giải bài toán với nhiều trường hợp nhanh hơn rất nhiều (giải bài toán Kirkman’s School Problem trong vòng 1 giây) và cũng giải được trường hợp khó trong một thời gian nhỏ ( bài toán SGP 8-4-9 trong vòng 2.5 giây, và giải bài toán với nghiệm tối ưu 8-8-9 trong 7 giây). 6.3 So sánh với một số kỹ thuật khác Trong phần này, sẽ so sánh với 3 phương pháp khác thường được sử dụng trong SGP: SBDD (được coi là mạnh nhất cho loại bỏ đối xứng bằng cách thêm ràng buộc trong thời gian tìm kiếm ), Local Search (là phương pháp có Formatted: Font: 14 pt, Font color: Black Formatted: Font: 14 pt, Font color: Black Formatted: Font: 14 pt, Font color: Black Formatted: Font: 14 pt, Font color: Black Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Not Bold Formatted: Font: Not Bold Formatted: Bullets and Numbering Formatted: Font: Bold Formatted: Font: Bold 91 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 thời gian thực thi khá nhanh, đặc biệt là với một số trường hợp khó đối với lập trình ràng buộc trong bài toán SGP ), phương pháp nhiều “điểm nhìn” (một phương pháp rất linh hoạt trong việc loại bỏ đối xứng tĩnh như chúng ta thấy ở phần trên), và phương pháp loại bỏ đối xứng bằng thuật toán quay lui thông minh. 6.3.1 So sánh với phương pháp SBDD Đầu tiên, ta so sánh với phương pháp SBDD (nói chung, SBDD vẫn được đánh giá là tốt hơn SBDS, ít nhất cũng đúng cho SGP [20, 22]) trong [20]. [20] đã sử dụng mô hình biến tập (phần 3.1), thực thi chương trình viết bằng ECLiPSe trên máy Pentium II/450 MHz, môi trường Linux. Trong Bảng 6.5: NDF cho kết quả tốt nhất khi kết hợp giữa ND và F, trong khi đó SBDD mc là kỹ thuật SBDD không cần sự kiểm tra kết hợp (without merged checks). Thông qua Bảng 6.5, ta có thể nhận thấy là hầu hết những trường hợp mà SBDD giải được cũng được giải bằng NDF trong thời gian nhỏ hơn 1 giây! (bao gồm cả bài toán Kirkman’s School). Hơn nữa ở đây cũng giải được nhiều trường hợp hơn (ví dụ, trong dạng g-s=6-2 đạt được 11 tuần trong thời gian 0.63s trong khi đó SBDD cần 1 giờ mà chỉ đạt được 6 tuần). Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: 14 pt, Font color: Black Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold 92 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 g s w SBDD SBDD NDF g s w SBDD SBDD NDF 2 0.0 0.0 0.0 2 0.1 0.1 0.04 3 0.0 0.0 0.0 3 0.2 0.2 0.1 3 3 4 0.1 0.1 0.0 4 2277. 999.9 0.20 2 0.0 0.0 0.0 5 - 3639. 0.34 3 0.1 0.1 0.0 5 5 6 - - 0.49 4 0.1 0.1 0.0 6 6494. 3607. 0.18 5 0.2 0.2 0.0 7 - - 0.25 6 0.3 0.3 0.0 8 - - 0.32 2 7 0.4 0.3 0.1 9 - - 0.41 2 0.0 0.0 0.0 10 - - 0.52 3 0.1 0.1 0.0 2 11 - - 0.63 3 4 9.9 7.6 0.0 2 0.1 0.1 0.02 2 0.0 0.0 0.0 3 0.2 0.2 0.06 3 0.1 0.1 0.0 4 0.4 0.4 0.15 4 0.2 0.2 0.0 5 1683 374.1 0.24 4 4 5 0.3 0.3 0.1 6 - - 0.35 5 0.3 0.3 0.0 7 - - 1.48 6 27.2 16.5 0.1 3 8 - - - 7 504.4 216.1 0.1 2 0.2 0.1 0.04 8 2842.4 1140.8 0.2 3 0.4 0.4 0.12 2 9 5468.5 2410.9 0.2 4 0.5 0.6 0.22 2 0.1 0.1 0.0 5 1461 537.2 0.57 3 0.2 0.1 0.0 4 6 - - - 4 29.9 17.8 0.0 2 0.2 0.2 0.05 5 347.8 109.3 0.2 3 0.4 0.4 0.15 6 - - 3.4 4 1929 602.7 0.39 3 7 - - 0.9 5 - - - 2 0.1 0.1 0.0 5 6 - - - 3 0.2 0.2 0.0 2 0.2 0.1 0.07 4 118.9 11 0.1 6 6 3 0.4 0.3 0.2 5 4 5 1374.6 653.0 0.8 Bảng 6.5: Kết quả SBDD cho SGP với kỹ thuật NDF 93 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 6.3.2 So sánh với phương pháp Local Search Ở đây sẽ so sánh kết quả đạt được với việc giải SGP dùng Local Search (SGLS) [13], được thực thi bằng C, trên 3.06GHz-processor, 512MB RAM (vì vậy cấu hình có thể nhanh hơn cấu hình được thử nghiệm trong Luận văn tốt nghiệp xấp xỉ 50 lần). Cũng cần nói thêm rằng Local Search thường được cho là một phương pháp nhanh trong nhiều trường hợp mà CP rất khó khăn. g s w SGLS NDF g s w SGLS NDF 6 6 3 0.01 0.21 3 11 0.08 28.60 5 5 0.07 1.92 4 8 0.09 18.90 6 4 0.09 0.64 5 6 0.09 5.13 3 0.03 0.25 6 5 0.13 6.06 7 7 8 - 287.21 7 4 0.14 3.58 3 10 0.23 - 8 3 0.09 0.84 8 207.77 1.82 9 9 3 0.19 0.964 9 - 7.36 4 9 0.16 205.05 5 6 0.37 138.23 7 5 0.41 489.30 6 5 1.21 231.41 9 3 0.21 1.34 7 4 0.39 10.06 10 10 3 0.39 1.40 4 360.00 501.46 8 8 9 - 7.36 Bảng 6.6: Kết quả của SGLS với kỹ thuật NDF Trong Bảng 6.6, dấu “-” chỉ những trường hợp thời gian vượt quá 10 phút. Thông qua Bảng 6.6, trong một số trường hợp không tìm được nghiệm tối ưu so với SGLS trong thời gian 10 phút. Tuy nhiên, Luận văn tốt nghiệp cũng tìm ra nghiệm nhiều hơn SGLS 3 trường hợp khó (7-7-8, 8-4-9, 8-8-9). Formatted: Font: 14 pt, Font color: Black Formatted: Font: 14 pt, Italic, Font color: Black Formatted: Font: 14 pt, Italic, Font color: Black Formatted: Font: 14 pt, Font color: Black 94 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 6.3.3 So sánh với phương pháp nhiều “điểm nhìn” Ở đây sẽ lấy kết quả tốt nhất trong Bảng 6.3 (“điểm nhìn” V1V3)và kết quả tốt nhất trong kỹ thuật đã nghiên cứu để so sánh (NDF). Thời gian đều được tính bằng giây. Bảng 6.7: So sánh kết quả trong việc tìm ra nghiệm đầu tiên giữa phương pháp nhiều “điểm nhìn” và NDF. Trong Bảng 6.7 thời gian được tính bằng giây. Tại cột ký hiệu là “+w” để chỉ ra rằng phương pháp được đề xuất (NDF) có thể đạt được hơn “+w” số tuần V1V3 NDF g s w time + w 6 2 11 0.13 0.63 0 7 2 13 1.47 1.30 0 6 3 5 2066.14 0.32 2 7 3 4 0.41 0.20 4 8 3 5 1330.29 0.49 4 5 4 4 2297.76 1.35 1 6 4 3 3703.93 0.13 2 7 4 3 1699.63 0.16 3 8 4 9 0.3 2.94 0 7 5 2 78.34 0.08 3 8 5 2 127.84 0.11 4 8 8 9 0.93 6.95 0 5 4 3 80.83 0.08 2 5 3 5 64.27 0.2 0 5 3 7 13.96 0.95 0 Formatted Formatted: Font: 14 pt, Not Bold Formatted Formatted: Font: 14 pt Formatted: Font: 14 pt Formatted: Font: 14 pt, Italic Formatted Formatted: Font: 14 pt Formatted: Font: 14 pt Formatted Formatted: Font: Not Bold Formatted: Font: 14 pt Formatted Formatted: Font: 14 pt Formatted: Font: Not Bold Formatted: Font: 14 pt Formatted Formatted: Font: 14 pt Formatted: Font: Not Bold Formatted: Font: 14 pt Formatted Formatted: Font: 14 pt Formatted: Font: Not Bold Formatted Formatted Formatted: Font: 14 pt Formatted: Font: Not Bold Formatted Formatted Formatted: Font: Not Bold Formatted Formatted Formatted: Font: Not Bold Formatted Formatted: Font: 14 pt Formatted: Font: 14 pt, Not Bold Formatted Formatted: Font: 14 pt, Not Bold ... [5] ... [3] ... [1] ... [10] ... [9] ... [6] ... [13] ... [4] ... [7] ... [11] ... [14] ... [8] ... [12] ... [2] ... [15] 95 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 của phương pháp nhiều “điểm nhìn” trong vòng nhiều nhất là 5 phút (tham khảo ở Bảng 6.4). Thông qua kết quả so sánh ta có kết luận sau đây: ƒ Hầu hết các trường hợp trong phương pháp nhiều “điểm nhìn” giải được thì đều được giải bằng phương pháp được đề xuất trong thời gian 7 giây! ƒ Có nhiều trường hợp phương pháp nhiều “điểm nhìn” đã cần đến 20, 30 thâm chí 60 phút, trong khi đó ở đây chỉ giải trong vòng xấp xỉ 1 giây! ƒ Có thể giải nhiều trường hợp trong phương pháp nhiều “điểm nhìn” giải trong thời gian lớn (thậm chí một giờ): 6-4-5, 8-3-5, 5-4-4, 6-4-3, 7-4-3, 8-5-2. Trong khi đó, ta có thể giải được với nghiệm tối ưu hơn (đạt được nhiều tuần hơn) trong thời gian 2 phút. 6.3.4 So sánh với phương pháp IB Trong Bảng 6.8 trình bày kết quả so sánh giữa hai phương pháp IB (phần 5.1) và phương pháp NDF. Phương pháp IB [2] được thực thi bằng C++, trên Pentium IV/ 2.4GHz-processor. Thời gian được tính bằng giây. Trong cột w2 có những hàng có ký hiệu a ± b có nghĩa là: a là số tuần phương pháp IB đạt được trong 5 phút, còn b là số tuần mà phương pháp được đề xuất tìm được kém hơn (-) hay nhiều hơn (+) so với phương pháp IB. Như vậy, thông qua Bảng 6.8 có thể đưa ra nhận xét như sau: ƒ Trong 5 phút hầu hết những trường hợp mà phương pháp IB giải được thì phương pháp NDF cũng giải được trong thời gian chấp nhận được. ƒ Có hai trường hợp NDF không tối ưu bằng IB (6-4-6 và 6-4-5) cụ thể hơn là số tuần của NDF đạt được kém 1 trong cả hai trường hợp Formatted: Font: 14 pt, Font color: Black Formatted: Font: 14 pt, Font color: Black 96 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 ƒ Có 5 trường hợp mà NDF giải được với số nghiệm tối ưu hơn (hơn 1,2,3,4 tuần) so với phương pháp IB. Cần chú ý là thời gian cho hai phương pháp đều trong giới hạn 5 phút. IB NDF g s w1 Time w2 Time 3 4 0.01 4 0.064 4 5 0.00 5 0.12 3 7 1.10 7 0.95 4 5 0.10 5 0.865 5 6 0.03 6 0.49 3 7 1.36 7 1.48 4 6 123.01 6-1 0.666 5 5 6.56 5-1 0.39 3 6 0.08 6+2 6.45 4 6 0.05 6 13.217 5 5 0.11 5 1.9 3 8 0.08 8+1 3.70 4 5 0.02 5+4 2.498 5 6 15.63 6 138.77 3 9 4.29 9+2 28.69 4 5 0.51 5+3 18.9 Bảng 6.8: So sánh kết quả trong việc tìm ra nghiệm đầu tiên giữa phương pháp IB và NDF. 97 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 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 Ở đây sẽ giải SGP trong trường hợp đặc biệt p-p-(p+1), khi p là số nguyên tố, ngoài ra cũng đưa ra một vài kết luận với trường hợp s-s-w cho cả trường hợp s chẵn và s lẻ. Phần này cũng nêu ra một quan hệ rất thú vị giữa SGP với hình vuông latin trực giao. 7.1 Giới thiệu thuật toán Thuật toán này dùng để giải SGP cho trường hợp p-p-(p+1), khi p là số nguyên tố. Điều đặc biệt là nó không mất thời gian cho việc tìm kiếm. Ta sẽ minh họa ý tưởng của thuật toán thông qua một ví dụ. Bảng 7.1 là một trường hợp của SGP cho 3-3-4 week group1 group 2 group 3 1 1 2 3 4 5 6 7 8 9 2 1 4 7 2 5 8 3 6 9 3 1 * ** 2 ? ? 3 ? ? 4 1 2 3 Bảng 7.1: Một trường hợp của SGP cho 3-3-4 Như trong phần 2.1 đã nói, các tay gôn 1, 2, 3 được cố định tại các nhóm 1, 2, 3 kể từ tuần thứ hai trở đi. Tuần thứ hai cũng được cố định ở nhóm thứ nhất. Không khó khăn gì để chúng ta có được nghiệm cho tuần thứ 2. Từ đây thuật toán được bắt đầu. Ta sử dụng ý tưởng xuất phát từ kỹ thuật hạn chế miền (ND trong phần 2.2) rằng các phần tử ở vị trí thứ nhất chỉ quan tâm đến nhóm thứ nhất (trong tuần 1), những phần tử ở vị trí thứ hai chỉ quan tâm đến nhóm thứ hai (trong tuần 2), … Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold 98 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 Như vậy phần tử * trong Bảng 7.1 chỉ quan tâm đến những phần tử {4,5,6}, nhưng tay gôn 4 đã gặp tay gôn 1 trong tuần thứ hai, do vậy tay gôn * chỉ có thể gặp tay gôn {5,6}. Một cách rất tự nhiên ta chọn tay gôn 5. Và khi chọn tay gôn 5 cho phần tử * thì phần tử ** chỉ còn một lựa chọn duy nhất là tay gôn 9. Làm tương tự chúng ta sẽ được nhóm thứ hai, và nhóm thứ ba cho tuần thứ ba. Tiếp tục làm như vậy và chúng ta sẽ đạt được tuần thứ 4 nhờ tuần thứ 3. Cuối cùng chúng ta được nghiệm hoàn chỉnh (tối ưu cho số tuần) trong Bảng 7.2 . week group1 group 2 group 3 1 1 2 3 4 5 6 7 8 9 2 1 4 7 2 5 8 3 6 9 3 1 5 9 2 6 7 3 4 8 4 1 6 8 2 4 9 3 5 7 Bảng 7.2: Một nghiệm hoàn chỉnh cho SGP 3-3-4 Và từ đây có thể phát hiện ra một quy luật cho thuật toán. Mô tả dưới dạng mã giả như sau: Procedure SGP_PrimeNumber(In: s, Out: S) n Å s×s W1 Å {, , …} W2 Å {G1, …, Gs}={, …} const Å s+1 for i from 3 to s+1 do {generate ith week} begin WiÅØ for j from 1 to s do {generate jth group} Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic 99 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 Gi Å{Pj} posÅj for k from 2 to s do {generate kth player} posÅ (pos+const) mod n Pk Å W[i-1, pos] Gj ÅGj U{Pk} end for; end for; Wi Å Wi U{ Gj }; end for; end Procedure Chú ý W[i,j]: dùng để chỉ tay gôn ở vị trí thứ j trong tuần W[i].(W[i] được coi là một danh sách với độ dài n). Gi chỉ nhóm thứ i. 7.2 Một số thảo luận cùng kết quả xung quanh thuật toán Dotu và Van Hentenryck [12] cũng có một thuật toán giải trong SGP p-p- (p+1) khi p là nguyên tố (khá tương tự với thuật toán đã được đề xuất). Ở đó các tác giả đã kết luận về thuật toán như sau: ƒ Khi odd chia hết cho 3, thuật toán đạt được nghiệm dạng odd-odd-4. ƒ Khi odd chia hết cho 5, thuật toán đạt được nghiệm dạng odd-odd-6. ƒ Khi odd chia hết cho 7, thuật toán đạt được nghiệm dạng odd-odd-8. Thông qua thuật toán được đề xuất, ta cũng có một số kết luận như sau: ƒ Thuật toán giải SGP cho trường hợp p-p-(p+1), khi p là số nguyên tố (Đã kiểm tra cho mọi số p < 73). ƒ Thuật toán đúng cho mọi trường hợp odd-odd-4, khi odd là số lẻ. Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic 100 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 ƒ Thuật toán đúng cho mọi trường hợp number-number-3. Nó được chứng minh bằng những lập luận sau: o Theo như thuật toán tuần thứ hai được gán với mỗi nhóm đạt được các tay gôn từ các mỗi nhóm khác nhau (do số tay gôn trong mỗi nhóm chính là số nhóm trong tuần), do vậy tuần thứ hai thỏa mãn tuần thứ nhất. o Mỗi nhóm trong tuần thứ ba cũng có được các tay gôn từ các nhóm khác nhau trong tuần thứ hai và tuần thứ nhất. Chuyện gì xảy ra khi tiếp tục áp dụng cho tuần thứ 4 khi s=number là chẵn? Chúng ta hãy cùng xem xét trường hợp này. - Trong tuần thứ hai, tay gôn 1 và tay gôn (s*s/2+1) trong cùng nhóm thứ nhất, bởi vì tay gôn (s*s/2+1) là tay gôn đầu tiên trong trong nhóm (s/2+1). - Nó cũng không khó hình dung ra tay gôn (s*s/2+1) sẽ ở nhóm (s/2+1) trong tuần thứ ba. - Tiếp đến tuần thứ tư, tay gôn (s*s/2+1) sẽ ở nhóm đầu tiên. Và như vậy là nó gặp lại tay gôn 1. Như vậy thuật toán không còn đúng nữa. Chúng ta hãy xem minh họa cho lập luận trên khi number =4 trong Bảng 7.3 Formatted: Font: Not Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font color: Black Formatted: Font color: Black Formatted: Font: Italic 101 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 week group1 group 2 group 3 group 4 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 1 5 9 13 2 6 11 14 3 7 11 15 4 8 12 16 3 1 6 11 16 2 7 12 13 3 8 9 14 4 5 11 15 4 1 7 9 2 3 4 Bảng 7.3: Một minh họa cho thuật toán với trường hợp 4-4-w, khi này tay gôn (s*s/2+1) chính là tay gôn số 9. Như vậy, có thể kết luận thuật toán đúng cho mọi trường hợp number- number-3 với number là bất kỳ (chẵn hay lẻ) mà không mất thời gian tìm kiếm ( trường hợp tối ưu cho SGP 6-6-3 cũng được giải bởi thuật toán ). 7.3 Liên hệ SGP với hình vuông Latin trực giao 7.3.1 Giới thiệu hình vuông Latin trực giao Trước hết, ta muốn giới thiệu về hình vuông (Latin Square) và hình chữ nhật Latin (Latin Rectangle). Định nghĩa 7.1 Một ma trận n×n là hình vuông Latin cấp n, nếu mỗi số 0, 1, …, n-1 xuất hiện đúng một lần trên mỗi hàng và mỗi cột. ■ Ví dụ về một hình vuông Latin như trong Bảng 7.4 là hình vuông Latin cấp 4. Tổng quát hơn, chúng ta có thể thay các số bằng các đối tượng khác nhau. 0 1 2 3 2 3 0 1 3 2 1 0 1 0 3 2 Bảng 7.4: Một ví dụ về hình vuông Latin cấp 4 Formatted: Font: Italic Formatted: Font: Italic 102 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 Định nghĩa 7.2 Một ma trận r×n được gọi là hình chữ nhật Latin, nếu mỗi số 0, 1, …, n-1 xuất hiện nhiều nhất một lần trên mỗi hàng và mỗi cột. ■ Ví dụ về một hình chữ nhật Latin như trong Bảng 7.5. 0 1 2 3 2 3 0 1 3 2 1 0 Bảng 7.5: Một ví dụ về hình chữ nhật Latin 3×4 Như vậy với mỗi hình vuông Latin ta có thể đạt được hình chữ nhật Latin bằng cách loại bỏ một số hàng trong hình vuông Latin. Còn từ hình chữ nhật Latin, liệu chúng ta có đạt được hình vuông Latin không? Câu hỏi đã có trong định lý sau: Định lý 7.3 Nếu r < n, thì với bất kỳ một hình chữ nhật Latin r×n có thể được mở rộng thành hình chữ nhật Latin (r+1)×n. Việc chứng minh có thể tham khảo tại [4]. Bây giờ đã tới lúc chúng ta thảo luận tới các hình vuông Latin trực giao (Mutually orthogonal Latin squares - MOLS). Định nghĩa 7.4 Một tập MOLS là một tập hình vuông Latin cỡ n sao cho bất kỳ một cặp hình vuông Lαvà Lβ nào từ tập đó, thì cặp (Lα(i,j), Lβ(i,j)) phải khác nhau với mọi 1≤ i, j ≤ n. ■ Từ đây suy ra một tính chất sau: Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic 103 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 Tính chất 7.5 Nếu tập MOLS có k hình vuông Latin cỡ n{Li| 1≤ i ≤ k} thì khi đó bộ k - giá trị (Li1(i,j),…, Lik(i,j) ) phải khác nhau với mọi i và j, 1≤ i, j ≤ n. Ví dụ trong Bảng 7.6 là một tập MOLS gồm 3 hình vuông Latin 0 1 2 3 0 1 2 3 0 1 2 3 3 2 1 0 2 3 0 1 1 0 3 2 1 0 3 2 3 2 1 0 2 3 0 1 2 3 0 1 1 0 3 2 3 2 1 0 Bảng 7.6: Hai hình vuông Latin trực giao Từ định nghĩa 7.4 chúng ta cũng suy ra được tập hình chữ nhật trực giao (Mutually orthogonal Latin rectangles - MOLR). Định nghĩa 7.6 Một tập MOLR là một tập hình chữ nhật Latin sao cho bất kỳ một cặp hình chữ nhật Lαvà Lβ nào từ tập đó, thì cặp (Lα(i,j), Lβ(i,j)) phải khác nhau với mọi i và j. ■ Và như vậy thì MOLR cỡ n×n chính là tập MOLS cỡ n. Chú ý rằng tính chất 7.5 cũng đúng cho MOLR. Chúng ta gọi N(n) là số hình vuông lớn nhất có thể từ tập MOLS cấp n; gọi N(m×n) là số hình chữ nhật lớn nhất có thể từ tập MOLR cấp m×n. Khi đó ta có 2 tính chất sau: ƒ N(n) ≤ N(m×n), cho mọi m≤ n ƒ N(m×n) ≤ n-1, cho mọi 1< m ≤ n Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Not Italic Formatted: Font: Italic Formatted: Font: Italic 104 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 7.3.2 Mối liên hệ giữa MOLS và SGP Thực ra cũng không phải tự nhiên mà có sự liên hệ giữa MOLS và SGP. Sự liên hệ này thực chất là cả hai đều liên quan đến các bài toán mang tính tổ hợp. Tại [II.2.3] trong [9], có giới thiệu một thuật toán xây dựng tập MOLS như sau: Nếu n=pe, khi p là số nguyên tố, thì ta có thể xây được dựng tập MOLS như sau: ƒ Đặt GF(n) là một trường hữu hạn cấp n (gồm các số 0,1,…, n-1) ƒ Với mỗi α ∈ GF(n)\{0}, đặt Lα(i,j)= αi+j, với i, j ∈ GF(n), các phép toán thực hiện trong GF(n). Khi đó ta có tập { Lα| α ∈ GF(n)\{0}} chính là tập (n-1) MOLS cấp n. Và từ chính tập MOLS này chúng ta có thể xây dựng được nghiệm cho bài toán SGP (trong trường hợp n là lũy thừa của số nguyên tố, từ đây trở đi ta chỉ xét trường hợp n là lũy thừa của số nguyên tố, nếu xét trường hợp khác chúng tôi sẽ nêu cụ thể). Khi ta đặt cạnh nhau các (n-1) MOLS cấp n ta nhận thấy rằng chính chúng thỏa mãn tính của SGP cho dạng g- g- (g+1): ƒ Có g nhóm và mỗi nhóm có g tay gôn chính được thể hiện bằng (g-1) hình vuông cỡ g (sẽ giải thích sau vì sao chỉ cần g-1 hình vuông) ƒ Trong trường hợp này mọi tay gôn đều gặp nhau đúng một lần. ƒ Các tay gôn không gặp lại nhau chính là tính chất của MOLS được thể hiện thông qua tính chất 7.5 Ta sẽ lấy một ví dụ để làm rõ kết luận trên. Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic 105 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 ta hãy xem bảng sau: week group1 group 2 group 3 1 1 2 3 4 5 6 7 8 9 2 1 4 7 2 5 8 3 6 9 3 1 5 9 2 6 7 3 4 8 4 1 6 8 2 4 9 3 5 7 Bảng 7.7: Một nghiệm cho trường hợp 3-3-4 Khi chúng ta chuyển mô hình sang dạng khác (chính là V1 trong phần 6.1) chúng ta được bảng sau: Golfer week 1 2 3 4 5 6 7 8 9 1 1 1 1 2 2 2 3 3 3 2 1 2 3 1 2 3 1 2 3 3 1 2 3 3 1 2 2 3 1 4 1 2 3 2 3 1 3 1 2 Bảng 7.8: Nghiệm cho trường hợp 3-3-4 ở mô hình lấy nhóm làm giá trị Từ này trở đi ta ký hiệu r hình vuông Latin trong tập MOLS(n) bằng r MOLS(n). Như vậy, với tập 2MOLS(3) được tô đậm ở trên chúng ta xây dựng được nghiệm SGP cho trường hợp 3-3-4. Tóm lại với n là lũy thừa của số nguyên tố n=pe, chúng ta sẽ có được (n-1) MOLS(n) và chúng ta sẽ xây dựng được nghiệm cho SGP với trường hợp n-n- Formatted: Font: Italic Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Bold Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic 106 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 (n+1). Như vậy đây là sự tổng quát so với thuật toán được đề xuất và thuật toán của [13]. Từ đó suy ra trong trường hợp muốn tìm nghiệm SGP cho trường hợp g-g-n chính là tương đương với việc tìm ta (n-2) MOLS(g). Đây quả thực là một sự liên hệ rất thú vị. Hơn nữa, ta cũng có thể khẳng định rằng thuật toán được đề xuất có thể dễ dàng cải tiến (phần 7.1) để có thể tạo ra tập (n-1) MOLS(n) khi n là nguyên tố (tức là e =1, trong [9]). 7.3.3 Mối liên hệ giữa SGP và MOLR Trong [21] cũng tóm tắt 2 phương pháp xây dựng nghiệm cho SGP từ tập các MOLR(m×n). Ở đây xin đưa ra 1 cách tạo dựng thú vị sau: 1. Sharma và Das’s r MOLR(m×n) tương ứng với g- s - w trong SGP và khi đó (g =n)- (s=m)- (w=r+1) (nếu g không chia hết cho s) (w >r+1) (nếu g chia hết cho s) 2. Mathtalk-ga’ r MOLR(m×n) tương ứng với g- s - w trong SGP và khi đó (g =n)- (s=r+1)- (w=m) (nếu g không chia hết cho s) (w >m+1) (nếu g chia hết cho s) Đây quả thực là những sự liên hệ rất thú vị, nó đã tìm ra được nhiều nghiệm cho SGP một cách nhanh chóng (so với lập trình ràng buộc), đồng thời chúng cũng đưa ra được những nghiệm mới, góp phần bổ sung đáng kể vào tập nghiệm cho SGP. Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: 14 pt, Not Bold, Font color: Black Formatted: Font: 14 pt, Not Bold, Font color: Black Formatted: Font: 14 pt, Italic, Font color: Black Formatted: Font: 14 pt, Font color: Black Formatted: Font: 14 pt, Italic, Font color: Black Formatted: Font: 14 pt, Font color: Black Formatted: Font: 14 pt, Italic, Font color: Black Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: Not Italic Formatted: Font: Italic Formatted: Font: 14 pt, Font color: Black Formatted: Font: Italic Formatted: Font: Italic Formatted: Font: 14 pt, Font color: Black Formatted: Font: Italic Formatted: Font: 14 pt, Italic, Font color: Black Formatted: Font: 14 pt, Font color: Black Formatted: Font: 14 pt, Font color: Black Formatted: Font: 14 pt, Not Bold, Font color: Black 107 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 PHẦN IV. KẾT LUẬN Theo cách giải quyết truyền thống với các bài toán tổ hợp khó, có hai cách tiếp cận truyền thống: Hoặc là thực hiện thủ công thuật toán sẽ giải chính xác trong lập trình truyền thống, hoặc là mô hình bài toán dùng thuật toán có sẵn cho lớp các ràng buộc số học cụ thể. Hạn chế của phương pháp thứ nhất là việc thiết kế nó đòi hỏi chi phí lớn và không dễ gì biến đổi khi bài toán thay đổi. Hạn chế của phương pháp thứ hai là không dễ gì diễn tả hiệu quả các ràng buộc trong miền ứng dụng đủ mềm dẻo và hiệu quả cho phép các kinh nghiệm trong các miền được chỉ ra để giải quyết chúng. Ngôn ngữ CP hiện đại có thể khắc phục được những điểm yếu này bằng cách cung cấp một ngôn ngữ lập trình dựa trên việc giải ràng buộc tinh vi nhất. Điều này có nghĩa là người lập trình có thể viết chương trình trong khi kỹ thuật giải chung đã được cung cấp trong việc thực thi ngôn ngữ. Chúng ta đều biết rằng mọi bài toán đều có ràng buộc, công việc của chúng ta là tìm ra giá trị của các biến thỏa mãn các ràng buộc đó. Lập trình ràng buộc càng tỏ rõ hiệu quả trong những bài toán mà việc yêu cầu mô tả ràng buộc mang tính mềm dẻo. Và càng ngày lập trình ràng buộc càng thể hiện rõ vai trò mạnh mẽ của mình trong việc giải những bài toán liên quan đến những thực trong cuộc sống, càng ngày lĩnh vực ứng dụng của nó càng trở nên phong phú (toán học, y học, kinh tế, vật lý, tin học,…). Phần II, Luận văn những kiến thức cô đọng nhất cho CSPs: những định nghĩa cùng với những khái niệm quan trong cho CSPs; Luận văn cũng nêu và thảo luận một cách khái lược khi giải CSPs, các kỹ thuật áp dụng nhằm biến đổi bài toán sao cho bài toán sau khi biến đổi gọn hơn và dễ giải hơn. Luận văn tốt nghiệp cũng nêu tổng quan về các thuật toán tìm kiếm vì nó là một nhân tố quyết định chính trong quá trình tìm nghiệm của bài toán. 108 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 Trong phần III, phần đóng góp chủ yếu của Luận văn, đã giới thiệu và trình bày hệ thống sao cho phù hợp với các tiêu chí cho việc giải SGP: các mô hình khác nhau, các kỹ thuật khác nhau, các phương pháp giải khác nhau, và sự kết hợp giữa chúng. Đồng thời Luận văn cũng so sánh giữa các mô hình, các phương pháp khác nhau. Luận văn tốt nghiệp đã giới thiệu bài toán cùng với những kiến thức cần thiết cho bài toán “Người chơi gôn”. Từ đó chúng được ứng dụng cho những phần sau. Tiếp đến đã giới thiệu một số kỹ thuật, ràng buộc nhằm loại bỏ đối xứng tĩnh trong bài toán, vì hầu như các phương pháp khác đều sử dụng một phần (hoặc hầu hết) các kỹ thuật trong phần này, đồng thời cũng đưa ra 2 kỹ thuật mới để áp dụng cho việc giải SGP. Hai kỹ thuật đó là ƒ Kỹ thuật ND: Đây là một ràng buộc dư thừa, nó không làm mất nghiệm bài toán. Làm bớt khả năng xét trong quá trình tìm kiếm. Nó cũng rất dễ dàng áp dụng cho các phương pháp khác. ƒ Kỹ thuật F: Tuy nó không bảo toàn tính nghiệm cho bài toán, nhưng trong rất nhiều trường hợp nó giúp bài toán giải trong thời gian rất nhanh (Bài toán Kirkman, hay bài toán SGP cho trường hợp 8-4-9). Sau đó, Luận văn cũng giới thiệu bốn mô hình thường được áp dụng cho việc giải SGP (có thể tham khảo thêm mô hình SAT cho SGP[18]). Từ đó nêu ra những đặc trưng của từng mô hình khi áp dụng giải SGP. Vì tính đặc thù của CSPs là tính đối xứng trong bài toán (đối xứng nghiệm, đối xứng ràng buộc) gây tốn thời gian cũng như chi phí cho việc tìm kiếm nghiệm (chúng ta phải tìm kiếm lại những không gian nghiệm mà đáng ra chúng ta có thể suy ra từ những phần khác đã xét). Do vậy việc loại bỏ đối Deleted: PHẦN III: BÀI TOÁN NGƯỜI CHƠI GÔN¶ ¶ Phần này chúng tôi sẽ giới thiệu bài toán đồng thời giới thiệu một số kiến thức nền tảng. Từ đó chúng tôi sẽ tiếp cận bài toán với những mô hình và phương pháp khác nhau để so sánh và thảo luận. Ở phần cuối chúng tôi có giải quyết một trường hợp đăc biệt của bài toán (khi s=g và là số nguyên tố) và có những kết luận xung quanh đó. Phần này chính là phần đóng góp trọng tâm của đồ án. 109 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 xứng là một yêu cầu tự nhiên và thiết yếu. Một kỹ thuật được áp dụng rất phổ biến trong lĩnh vực CSPs đó là kỹ thuật loại bỏ đối xứng động khi giải SGP. Nhưng do tính đặc thù của các phương pháp, ở đây tách ra làm hai phần. ƒ Phần thứ nhất nói về việc áp dụng các kỹ thuật loại bỏ đối xứng trong thời gian tìm kiếm SBDS và SBDD cho SGP và cũng nêu ra một vài điểm nhằm so sánh giữa chúng. ƒ Phần hai giới thiệu hai phương pháp loại bỏ đối xứng động cho SGP đó là Intelligent Backtracking (thực thi bằng quay lui thông minh) và Local Search. Phần tiếp theo, Luận văn tập trung vào việc loại bỏ đối xứng tĩnh khi giải SGP. Chương cuối đưa ra phương pháp được đề xuất cùng với các so sánh kết quả với những phương pháp đã trình bày ở những phần trước. Ta có so sánh kết quả thực nghiệm với các phương pháp: ƒ Phương pháp SBDD (thực thi trên ILOG Solver 5.0 và 400MHz Ultrasparc-II) . Phương pháp này được đánh giá là tốt hơn phương pháp SBDS . Ta có kết luận như sau: o Hầu hết những trường hợp mà SBDD giải được cũng được giải bằng phương pháp được đề xuất trong thời gian nhỏ hơn 1 giây! (bao gồm cả bài toán Kirkman’s School). o Đã tìm được nghiệm tối ưu hơn (số tuần nhiều hơn) trong nhiều trường hợp. ƒ Phương pháp Local Search (thực thi bằng C, trên 3.06GHz-processor, 512MB RAM). Trong [13, 21] đều nhận xét rằng có rất nhiều trường hợp mà giải bằng lập trình ràng buộc rất khó khăn thì Local Search có thể giải nó một cách dễ dàng và ngược lại. Tuy nhiên trong một số Formatted: Font: 14 pt, Italic, Font color: Black 110 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 trường hợp không tìm được nghiệm tối ưu so với SGLS trong thời gian 10 phút. Tuy nhiên ở đây cũng tìm ra nghiệm nhiều hơn SGLS 3 trường hợp khó (7-7-8, 8-4-9, 8-8-9). ƒ Phương pháp nhiều “điểm nhìn” (ILOG Solver 4.4 với máy Sun Ultra 5/400, 256 MB RAM). Sau khi so sánh ta đưa ra được khẳng định như sau: o Hầu hết các trường hợp trong phương pháp nhiều “điểm nhìn” giải được thì đều được giải bằng phương pháp được đề xuất trong thời gian 7 giây. o Có nhiều trường hợp phương pháp nhiều “điểm nhìn” đã cần đến 20, 30 thâm chí 60 phút, trong khi đó chỉ cần giải trong vòng xấp xỉ 1 giây! o Luận văn tốt nghiệp cũng giải nhiều trường hợp trong phương pháp nhiều “điểm nhìn” giải trong thời gian lớn (thậm chí một giờ): 6-4-5, 8-3-5, 5-4-4, 6-4-3, 7-4-3, 8-5-2. Trong khi đó, có thể giải được với nghiệm tối ưu hơn (đạt được nhiều tuần hơn) trong thời gian 2 phút ƒ Phương pháp IB (được thực thi bằng C++, trên Pentium 4/ 2.4GHz- processor). Ta có những kết luận như sau: o Trong 5 phút hầu hết những trường hợp mà phương pháp Intelligent Backtracking giải được thì phương pháp NDF cũng giải được trong thời gian chấp nhận được. o Có hai trường hợp NDF không tối ưu bằng Intelligent Backtracking (6-4-6 và 6-4-5) cụ thể hơn là số tuần của NDF đạt được kém 1 trong cả hai trường hợp Formatted: Font: 14 pt, Italic, Font color: Black Formatted: Font: 14 pt, Italic, Font color: Black 111 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 o Có 5 trường hợp mà NDF giải được với số nghiệm tối ưu hơn (hơn 1,2,3,4 tuần) so với phương pháp Intelligent Backtracking. Trong chương 7, Luận văn có nêu ra một thuật toán để giải SGP cho trường hợp p-p-(p+1), khi p là nguyên tố, mà không tốn thời gian tìm kiếm. Từ thuật toán này, đã cũng rút ra được một kết luận là thuật toán có thể dùng để giải cho trường hợp tổng quát number- number – 3 với number là số bất kỳ. Cũng từ thuật toán này, đã tạo ra được một cách xây dựng tập MOLS. Trên cơ sở đó, Luận văn cũng giải thích được mối liên hệ thú vị SGP và hình vuông Latin trực giao (MOLS). Như vậy là từ bài toán Kirkman’ schoolgirls, tưởng như là một bài toán đố vui, cũng như bài toán “Người chơi gôn” xuất phát từ một câu hỏi thực tế; Luận văn đã tiếp cận và giới thiệu những kỹ thuật trong CSPs để giải quyết cho SGP. Việc giải SGP cũng liên quan rất nhiều đến những bài toán tổ hợp ( Trong SGP khi (s-1)w=gs-1, nó tương đương với bài toán “Balanced Incomplete Block Design” tại I.1 trong [9], “Steiner Triples”, MOLS, …). Chính chúng có những sự tương đồng, sự bổ trợ; giải quyết một vấn đề sẽ tác động đến các vấn đề còn lại, thúc đẩy và tạo ra sự phát triển chung. Có nhiều phương pháp, mô hình để giải SGP. Tuy nhiên tất cả các mô hình đều muốn loại bỏ đối xứng càng nhiều càng tốt (vì SGP cũng như các bài toán trong CSPs có tính đối xứng rất lớn) bằng tĩnh, động hoặc kết hợp cả hai. Việc khó khăn khi giải SGP cũng là những khó khăn chung cho cộng đồng ràng buộc khi phải đối mặt với việc giải CSPs. Mong muốn rằng trong tương lai có thể kết hợp những kỹ thuật được đề xuất với những kỹ thuật khác như SBDD hay SBDS để nâng hiệu quả trong việc tìm kiếm nghiệm cho SGP. 112 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 Ngoài ra cũng có thể thấy rằng có nhiều hướng để phát triển Luận văn như: Phát triển hơn nữa phương pháp (SBDS, SBDD, Intelligent Backtracking, Multiple-viewpoints, Local Search, thêm các ràng buộc dư thừa…). Mỗi phương pháp, mô hình đều đó ưu và nhược trong từng trường hợp riêng. Nếu có thể, sẽ nghiên cứu sự kết hợp giữa các phương pháp (Local Search + Ràng buộc dưa thừa, SBDD + ràng buộc dư thừa, SBDD + IB, …), trong đó có cả sự kết hợp giữa các mô hình, … Việc giải SGP là công việc khó, đòi hỏi phải có sự kết hợp những phương pháp và thậm chí là cần tìm thêm những phương pháp mới, cách tiếp cận mới. Đây cũng tạo tiền đề và mong muốn cho những nghiên cứu trong tương lai. Bất chấp sự nỗ lực của cộng đồng ràng buộc, trường hợp 8-4-10 cũng như một số trường hợp khác trong SGP vẫn còn mở. Nhưng chính thách thức này đã thúc đẩy cộng đồng ngày càng phát triển công nghệ ràng buộc để ngày càng phù hợp với những bài toán khó trong thực tế. 113 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 TÀI LIỆU THAM KHẢO Tiếng Việt 1. Nguyễn Thanh Thủy, (1996), Trí tuệ nhân tạo: Các phương pháp giải quyết vấn đề, NXBGD. Việt Nam. Tiếng Anh 2. Azevedo F. (2006), “An Attempt to Dynamically Break Symmetries in the Social Golfers Problem”, Azevedo et al. (eds): Proceedings of the 11th Annual ERCIM Workshop on Constraint Programming (CSCLP'2006), pp. 101–115. 3. Azevedo F., Van Hau N. (2006), “Extra Constraint for the Social Golfers Problem”, The 13th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Phnom Penh, Cambodia, 13th - 17th November (Short paper) 4. Anderson I., Honkala I. (1997), “A Short Course in Combinatorial Designs”, 5. Association for Constraint Programming, 6. Barnier N., and Brisset P. (2002), “Solving the Kirkman's Schoolgirl Problem in a Few Seconds”, Proceeding of Principles and Practice of Constraint Programming - CP 2002, Springer Verlag,, LNCS 2470, pp. 477–491. 7. Barták R., 8. Cohen D., Jeavons P., Jefferson C., Karen E. P. and Smith B. (2005) “Symmetry Definitions for Constraint Programming”, Proceeding of Principles and Practice of Constraint Programming - CP 2005, Springer Verlag, LNCS 3709, pp. 17-31. 114 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 9. Colbourn C. J., and Dinitz J. H.(1996), “The CRC Handbook of Combinatorial Design”, CRC Press, Boca Raton, FL. 10. Constraint Programming online, 11.Constraints Archive, 12.Crawford J., Luks G., Ginsberg M., and Roy A. (1996), “Symmetry breaking predicates for search problems”, Proceeding of the 5th Int. Conf. on Knowledge Representation and Reasoning, (KR ’96), pp. 148–159. 13.Dotu I., and Van Hentenryck P. (2005), “Scheduling Social Golfers Locally”, Proceedings of the Second International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR’05), Springer Verlag, LNCS 3524, pp. 155–167. 14.Fahle S., Torsten, Stefan, and Sellmann M. “Symmetry breaking”, Proceeding of Principles and Practice of Constraint Programming - CP 2001, Springer Verlag, LNCS 2239, pp. 93–107. 15. Flener P., Frisch A., Hnich B., Kiziltan Z., Miguel I., Walsh T. (2002), “Breaking row and column symmetry in matrix models”, Proceeding of Principles and Practice of Constraint Programming - CP 2002, Springer Verlag, LNCS 2470, pp. 462-476. 16.Focacci F., and Milano M. “Global cut framework for removing symmetries”, Proceeding of Principles and Practice of Constraint Programming - CP 2001, Springer Verlag, LNCS 2239, pp. 77–92. 17.Frisch A., Hnich B., Kiziltan Z., Miguel I., Walsh T. (2002), “Global constraints for lexicographic orderings”, Proceeding of Principles and Practice of Constraint Programming - CP 2002, Springer Verlag, LNCS 2470, pp. 93-108. 115 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 18.Gent I.P. and Lynce I. (2005), “A SAT Encoding for the Social Golfer Problem”, Proceeding of IJCAI'05 workshop on Modelling and Solving Problems with Constraints. 19.Gent I.P., and Smith B. (2000), “Symmetry breaking during search in contraint programming”, W. Horn, editor, EACI’2000, pp. 599–603. 20.Harvey W. (2001), “Symmetry Breaking and the Social Golfer Problem”, Proceedings of SymCon-01: Symmetry in Constraints, pp. 9–16. 21. Harvey W. and Winterer T. (2005) “Solving the MOLR and Social Golfers Problems”, Proceedings of the 11th International Conference on Constraint Programming (CP-2005). 22.Karen E. P. (2003), “Comparison of Symmetry Breaking Method”, Proceeding of Principles and Practice of Constraint Programming - CP 2003, Springer Verlag, LNCS 2833, pp. 990. 23.Kiziltan Z. (2004), “Symmetry Breaking Ordering Constraints”, PhD thesis, Department of Information Science, Uppsala University. 24.Kzrysztof R.Apt (2003), Princeples of Constraint Programming, Cambridge Press. 25.Law Y.C., and Lee J.H.M. (2003), “Expressing symmetry breaking constraints using Multiple Viewpoints and channeling constraints”, Processing of the third International Workshop on Symmetry in Constraint Satisfaction Problem (SymCon’03), pp. 127–141. 26.Law Y.C., and Lee J.H.M. (2005), “Breaking value symmetries in matrix models using channeling constraints”, Processing of the 20th Annual ACM Symposium on Applied Computing (SAC-2005), pp. 375–380. 27.Law Y.C., and Lee J.H.M. (2006), “Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction”. Constraints (2006) to 116 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 appear 17th ECAI, European Conference on Artificial Intelligence, IOS Press. 28.Marriott K., and Stuckey P.J. (1998), Programming with Constraints: An Introduction, MIT Press. 29. Programming Systems Group of the Swedish Institute of Computer Science (2005), SICStus Prolog User’s Manual. 30.Puget J.-F. (1993), “On the Satisfiability of Symmetrical Constraint Satisfaction Problems” Proceedings of ISMIS’93 (1993), pp. 350–361. 31.Puget J.-F. (2002), “Symmetry breaking revisited”, Proceeding of Principles and Practice of Constraint Programming - CP 2002, Springer Verlag, LNCS 2470, pp. 446–461. 32.Puget J.F. (2005), “Breaking symmetries in all different problems”, Proceeding of 19th IJCAI (2005), pp. 272-277. 33.Sellmann M., and Van Hentenryck P. (2005), “Structural symmetry breaking”, Proceeding of IJCAI'05 workshop on Modelling and Solving Problems with Constraints. 34.Sellmann M., and Harvey, W. (2002), “Heuristic constraint propagation – Using local search for incomplete pruning and domain filtering of redundant constraints for the social golfer problem”, Proceedings of the Fourth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP- AI-OR’02), pp. 191–204. 35.Smith B. (2001), “Reducing Symmetry in a Combinatorial Design Problem”. Proceedings of the International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR’01), pp. 351–359. 36.Tsang E. (1993), Foundations of Constraint Satisfaction, Academic Press. 117 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 37.Van Hentenryck P. (1989), Constraint Satisfaction in Logic Programming, MIT Press. 38.Walsh T. (2006) “General Symmetry Breaking Constraints”, Proceeding of Principles and Practice of Constraint Programming - CP 2006, LNCS 4204, pp. 650–664. 39. 40. 41. 42. 43. Page 94: [1] Formatted Hau 9/22/2006 6:34:00 PM Font: Bold Page 94: [1] Formatted Hau 9/22/2006 6:34:00 PM Font: Bold Page 94: [2] Formatted Hau 9/22/2006 6:14:00 PM Font: 14 pt Page 94: [2] Formatted Hau 9/22/2006 6:14:00 PM Font: 14 pt Page 94: [3] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [3] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [3] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [4] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [4] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [4] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [5] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [5] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [5] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [6] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [6] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [6] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [7] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [7] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [7] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [8] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [8] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [8] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [9] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [9] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [9] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [10] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [10] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [10] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [11] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [11] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [11] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [12] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [12] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [12] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [13] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [13] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [13] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt Page 94: [14] Formatted Hau 9/22/2006 6:32:00 PM Font: 14 pt, Not Bold Page 94: [14] Formatted Hau 9/22/2006 6:32:00 PM Font: Not Bold Page 94: [15] Formatted Hau 9/22/2006 6:37:00 PM Font: Italic Page 94: [15] Formatted Hau 9/22/2006 6:37:00 PM Font: Bold