Tài liệu Tổ chức dữ liệu cho các thuật toán quay lui

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN QUANG TRÌNH TỔ CHỨC DỮ LIỆU CHO LỚP CÁC THUẬT TOÁN QUAY LUI LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2013 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN QUANG TRÌNH TỔ CHỨC DỮ LIỆU CHO LỚP CÁC THUẬT TOÁN QUAY LUI Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: PGS.TSKH Nguyễn Xuân Huy THÁI NGUYÊN - 2013 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ i LỜI CAM ĐOAN Học viên xin cam đoan, kết quả của luận văn hoàn toàn là kết quả của tự bản thân học viên tìm hiểu, nghiên cứu và thực hiện theo sự hƣớng dẫn khoa học của PGS.TSKH. Nguyễn Xuân Huy. Các tài liệu tham khảo đƣợc trích dẫn và chú thích đầy đủ. Thái Nguyên, ngày 10 tháng 10 năm 2013 Học viên Nguyễn Quang Trình Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ ii LỜI CẢM ƠN Học viên xin đƣợc bày tỏ lòng biết ơn chân thành và sâu sắc nhất đến thầy giáo PGS.TSKH. Nguyễn Xuân Huy, ngƣời đã tận tình hƣớng dẫn và tạo mọi điều kiện tốt nhất để học viên có thể hoàn thành luận văn này. Xin chân thành cảm ơn các thầy giáo, cô giáo Trƣờng Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên, Viện Công nghệ Thông tin - Viện Khoa học và Công nghệ Việt Nam đã trực tiếp giảng dạy, giúp đỡ và tạo mọi điều kiện thuận lợi trong quá trình học tập và nghiên cứu. Cảm ơn các thầy cô giáo, các bạn học viên lớp cao học Khoa học máy tính CK10C, gia đình và các đồng nghiệp đã luôn quan tâm, hỗ trợ, khuyến khích trong suốt thời gian học tập và thực hiện đề tài. Xin chân thành cám ơn! Học viên Nguyễn Quang Trình Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ iii MỤC LỤC TRANG BÌA LỜI CAM ĐOAN .............................................................................................. i LỜI CẢM ƠN ................................................................................................... ii MỤC LỤC ........................................................................................................ iii DANH MỤC CÁC HÌNH ................................................................................. v MỞ ĐẦU .......................................................................................................... 1 1. Lí do chọn đề tài ............................................................................................ 1 2. Đối tƣợng và phạm vi nghiên cứu ................................................................. 1 3. Hƣớng nghiên cứu của đề tài ........................................................................ 1 4. Những nội dung nghiên cứu chính ................................................................ 1 5. Phƣơng pháp nghiên cứu ................................................................................. 2 6. Ý nghĩa khoa học của đề tài .......................................................................... 2 Chƣơng 1. TỔNG QUAN THUẬT TOÁN QUAY LUI .............................. 3 1.1. Giới thiệu chung ......................................................................................... 3 1.2. Ý tƣởng của thuật toán [1], [2], [3], [5] ..................................................... 3 1.3. Kết luận ...................................................................................................... 7 Chƣơng 2. XÂY DỰNG THUẬT TOÁN QUAY LUI VÀ TỔ CHỨC DỮ LIỆU CHO MỘT SỐ BÀI TOÁN KINH ĐIỂN................. 8 2.1. Bài toán từ chuẩn [2] .................................................................................. 8 2.1.1. Giới thiệu bài toán ............................................................................... 8 2.1.2. Tổ chức dữ liệu và chƣơng trình ......................................................... 8 2.1.3. Nhận xét ............................................................................................ 11 2.2. Bài toán xếp hậu [1], [2] .......................................................................... 12 2.2.1. Giới thiệu bài toán ............................................................................. 12 2.2.2. Tổ chức dữ liệu và chƣơng trình ....................................................... 13 2.2.3. Nhận xét ............................................................................................ 20 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ iv 2.3. Bài toán đa giác ........................................................................................ 21 2.3.1. Giới thiệu bài toán ............................................................................. 21 2.3.2. Tổ chức dữ liệu và chƣơng trình ....................................................... 23 2.3.3. Nhận xét ............................................................................................ 29 2.4. Bài toán ô số Sudoku................................................................................ 30 2.4.1. Giới thiệu bài toán ............................................................................. 30 2.4.2. Tổ chức dữ liệu và chƣơng trình ....................................................... 32 2.4.3. Nhận xét ............................................................................................ 36 2.5. Kết luận .................................................................................................... 36 Chƣơng 3. CÀI ĐẶT CHƢƠNG TRÌNH ................................................... 37 3.1. Cài đặt cho bài toán từ chuẩn ................................................................... 37 3.1.1. Giới thiệu chƣơng trình ..................................................................... 37 3.1.2. Thử nghiệm chƣơng trình ................................................................. 41 3.2. Cài đặt cho bài toán xếp hậu .................................................................... 42 3.2.1. Giới thiệu chƣơng trình ..................................................................... 42 3.2.2. Thử nghiệm chƣơng trình ................................................................. 43 3.3. Cài đặt cho bài toán đa giác .................................................................... 45 3.3.1. Giới thiệu chƣơng trình ..................................................................... 45 3.3.2. Thử nghiệm chƣơng trình ................................................................. 47 3.4. Cài đặt cho bài toán ô số Sudoku ............................................................. 48 3.4.1. Giới thiệu chƣơng trình ..................................................................... 48 3.4.2. Thử nghiệm chƣơng trình ................................................................. 49 KẾT LUẬN .................................................................................................... 53 TÀI LIỆU THAM KHẢO ............................................................................ 54 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ v DANH MỤC CÁC HÌNH Hình 1.1 Cây tìm kiếm lời giải theo thuật toán quay lui ............................. 7 Hình 2.1 Cây tìm kiếm lời giải cho bài toán từ chuẩn ............................... 11 Hình 2.2 Lời giải 1 với N = 4 .................................................................... 15 Hình 2.3 Lời giải 2 với N = 4 .................................................................... 16 Hình 2.4 Cây lời giải bài toán xếp hậu với N = 4 ...................................... 17 Hình 2.5 Các đƣờng chéo chính................................................................. 18 Hình 2.6 Các đƣờng chéo phụ ................................................................... 18 Hình 2.7 Nghiệm v1 = (2, 4, 1, 3) .............................................................. 20 Hình 2.8 Trò chơi Instant Insanity ............................................................. 21 Hình 2.9 Đáp án đạt đƣợc sau khi xoay mỗi khối sang trái 1 góc 90o....... 21 Hình 2.10 Bài toán đa giác với m = 4, n = 6 ................................................ 22 Hình 2.11 Đáp án của bài toán đa giác với m = 4, n = 6 ............................. 23 Hình 2.12 Cách tìm nghiệm id = {1,5,6,3} .................................................. 29 Hình 2.13 Đề bài 1 ....................................................................................... 31 Hình 2.14 Đáp án đề bài 1 ........................................................................... 31 Hình 2.15 Đề bài 2 ....................................................................................... 32 Hình 2.16 Đáp án đề bài 2 ........................................................................... 32 Hình 3.1 Giao diện chƣơng trình TUCHUAN........................................... 41 Hình 3.2 Tìm 1 nghiệm với n = 7 .............................................................. 41 Hình 3.3 Tìm 1 nghiệm với n = 100 .......................................................... 41 Hình 3.4 Tìm 1 nghiệm với n = 1000 ........................................................ 42 Hình 3.5 Giao diện chƣơng trình XEPHAU .............................................. 42 Hình 3.6 20 nghiệm đầu tiên ...................................................................... 43 Hình 3.7 Các nghiệm 68 → 92 .................................................................. 43 Hình 3.8 20 nghiệm đầu tiên ...................................................................... 44 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ vi Hình 3.9 Các nghiệm 699 → 724 .............................................................. 44 Hình 3.10 Chƣơng trình XEPHAU cải tiến ................................................. 45 Hình 3.11 Giao diện chƣơng trình DAGIAC............................................... 46 Hình 3.12 Thử nghiệm chƣơng trình với M = 4, N = 6 ............................... 47 Hình 3.13 Thử nghiệm chƣơng trình với M = 10, N = 20 ........................... 47 Hình 3.14 Thử nghiệm chƣơng trình với M = 40, N = 40 ........................... 48 Hình 3.15 Giao diện chƣơng trình SUDOKU ............................................. 49 Hình 3.16 Đọc đề bài từ tệp input de1 ......................................................... 50 Hình 3.17 Đáp án de1 bằng phƣơng án 1 .................................................... 50 Hình 3.18 Đáp án de1 bằng phƣơng án 2 .................................................... 51 Hình 3.19 Đọc đề bài từ tệp input de2 ......................................................... 52 Hình 3.20 Đáp án de2 bằng phƣơng án 1 .................................................... 52 Hình 3.21 Đáp án de2 bằng phƣơng án 2 .................................................... 52 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 1 MỞ ĐẦU 1. Lí do chọn đề tài Để giải một bài toán thông thƣờng có nhiều cách tiếp cận. Mỗi cách tiếp cận khác nhau cho kết quả với độ tối ƣu khác nhau. Với nhiều bài toán việc tìm ra giải thuật tối ƣu không phải việc đơn giản, do đó một kĩ năng cần thiết để giải đƣợc một bài toán hoàn chỉnh là phải giải đƣợc bài toán ở kích thƣớc dữ liệu vừa phải. Đây sẽ là những bộ dữ liệu thử mang tính định hƣớng chiến lƣợc cho việc giải bài toán. Với phƣơng pháp này có thể giải ngay bằng cách duyệt toàn bộ hoặc có thể giải đƣợc một phần lớn của bài toán. Một thuật toán giúp duyệt toàn bộ hiệu quả, nhanh chóng là thuật toán quay lui. Việc áp dụng và cài đặt thuật toán quay lui cho các bài toán thƣờng khá trừu tƣợng và khó hiểu. Và khó hơn là việc kết hợp thuật toán quay lui với nhánh cận để giúp quá trình duyệt đƣợc hiệu quả hơn. Do đó học viên thấy việc phân tích, đánh giá và định hƣớng cách tiếp cận một bài toán bằng thuật toán quay lui là rất cần thiết. Trong khuôn khổ luận văn thạc sỹ, học viên chọn đề tài nghiên cứu: “Tổ chức dữ liệu cho lớp các thuật toán quay lui” 2. Đối tƣợng và phạm vi nghiên cứu Tìm hiểu một số đặc trƣng của lớp các bài toán đòi hỏi duyệt các khả năng. Ứng dụng để giải một số bài toán liệt kê và tìm phƣơng án tối ƣu. 3. Hƣớng nghiên cứu của đề tài Tìm hiểu các kỹ thuật và quy trình duyệt dữ liệu. Cài đặt chƣơng trình cho một số bài toán. 4. Những nội dung nghiên cứu chính Chƣơng 1. Tổng quan thuật toán quay lui Chƣơng này giới thiệu một số vấn đề liên quan đến đặc điểm, ý tƣởng và nội dung của thuật toán quay lui. Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 2 Chƣơng 2. Xây dựng thuật toán quay lui và tổ chức dữ liệu cho một số lớp bài toán kinh điển.  Bài toán từ chuẩn  Bài toán xếp hậu  Bài toán đa giác  Bài toán ô số Sudoku Chƣơng 3. Cài đặt chƣơng trình cho các bài toán ở Chƣơng 2 và thử nghiệm. 5. Phƣơng pháp nghiên cứu Phân tích, liệt kê, đối sánh, nghiên cứu tài liệu, tổng hợp các kết quả của các nhà nghiên cứu liên quan đến lĩnh vực nghiên cứu. 6. Ý nghĩa khoa học của đề tài Vận dụng tốt thuật toán quay lui, giúp chúng ta có thể dễ dàng giải đƣợc các bài toán liệt kê, tối ƣu. Xây dựng cơ sở khoa học cho các bài toán tìm kiếm. Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 3 Chƣơng 1 TỔNG QUAN THUẬT TOÁN QUAY LUI Chƣơng này giới thiệu một số vấn đề liên quan đến đặc điểm, ý tƣởng và nội dung của thuật toán quay lui. 1.1. Giới thiệu chung Thuật toán duyệt toàn bộ bằng cách sử dụng các vòng lặp lồng nhau có thể áp dụng cho các bài toán có kích thƣớc của các tập nghiệm cố định. Với những bài toán mà kích thƣớc của nghiệm phụ thuộc vào dữ liệu đầu vào hoặc một số điều kiện nào khác thì việc sử dụng các vòng lặp lồng nhau là bất khả thi. Lúc này, chỉ có thuật toán quay lui là có thể thực hiện duyệt qua đƣợc tất cả các bộ nghiệm của bài toán. Thuật toán quay lui là chiến lƣợc tìm nghiệm bài toán bằng cách xét tất cả các phƣơng án có thể. Đây là một thuật toán có thể áp dụng để giải rất nhiều bài toán với kích thƣớc dữ liệu thích hợp. Ƣu điểm của thuật toán là đảm bảo tìm ra nghiệm đúng chính xác. Tuy nhiên, hạn chế là độ phức tạp thƣờng lớn. Những bài toán tìm một nghiệm, liệt kê hoặc bài toán tối ƣu là những lớp bài toán có thể giải bằng thuật toán quay lui. 1.2. Ý tƣởng của thuật toán [1], [2], [3], [5] Giả sử ta phải tìm trong một tập dữ liệu D cho trƣớc một dãy dữ liệu: v = (v[1], v[2],..., v[n]) thoả đồng thời hai tính chất P và Q. Trƣớc hết ta chọn một trong hai tính chất đã cho để làm nền, tính chất thứ hai tạm gác bỏ, giả sử ta chọn tính chất P. Sau đó ta thực hiện các bƣớc sau đây: Bƣớc 1. (Khởi trị) Xuất phát từ một dãy ban đầu v = (v[1],..., v[i]) nào đó của các phần tử trong D sao cho v thoả P. Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 4 Bƣớc 2. Nếu v thoả Q ta dừng thuật toán và thông báo kết quả là dãy v, ngƣợc lại ta thực hiện Bƣớc 3. Bƣớc 3. Tìm tiếp một phần tử v[i + 1] để bổ sung cho v sao cho v = (v[1],..., v[i], v[i + 1]) thoả P. Có thể xảy ra các trƣờng hợp sau đây: 3.1. Tìm đƣợc phần tử v[i + 1]: quay lại bƣớc 2. 3.2. Không tìm đƣợc v[i + 1] nhƣ vậy, tức là với mọi v[i + 1] có thể lấy trong D, dãy v = (v[1],..., v[i], v[i + 1]) không thoả P. Điều này có nghĩa là đi theo đƣờng v = (v[1],..., v[i]) sẽ không dẫn tới kết quả. Ta phải đổi hƣớng tại một vị trí nào đó. Để thoát khỏi ngõ cụt này, ta tìm cách thay v[i] bằng một giá trị khác trong D. Nói cách khác, ta loại v[i] khỏi dãy v, giảm i đi một đơn vị rồi quay lại bƣớc 3. Cách làm nhƣ trên đƣợc gọi là quay lui: lùi lại một bƣớc. Dĩ nhiên ta phải đánh dấu v[i] là phần tử đã loại tại vị trí i để sau đó không đặt lại phần tử đó vào vị trí i trong dãy v. Khi nào thì có thể trả lời là không tồn tại dãy v thoả đồng thời hai tính chất P và Q? Nói cách khác, khi nào thì ta có thể trả lời là bài toán vô nghiệm? Dễ thấy, bài toán vô nghiệm khi ta đã duyệt hết mọi khả năng. Ta nói là đã vét cạn mọi khả năng. Chú ý rằng có thể đến một lúc nào đó ta phải lùi liên tiếp nhiều lần. Từ đó suy ra rằng, thông thƣờng bài toán vô nghiệm khi ta không còn có thể lùi đƣợc nữa. Có nhiều sơ đồ giải các bài toán quay lui, dƣới đây là hai sơ đồ khá đơn giản, không đệ quy. Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 5 Sơ đồ 1: Giải bài toán quay lui Sơ đồ 2: Giải bài toán quay lui (tìm 1 nghiệm) (tìm 1 nghiệm) Khởi trị v: v thoả P; Khởi trị v: v thoả P; repeat repeat if (v thoả Q) then if (v thoả Q) then begin begin Ghi nhận nghiệm; Ghi nhận nghiệm; exit; exit; end; end; if (Tìm được 1 nước đi) if (Hết khả năng duyệt) then Tiến then else begin if (có thể lùi được) Ghi nhận vô nghiệm; then Lùi exit; else end; begin if (Tìm được 1 nước đi) Ghi nhận: vô nghiệm; then Tiến exit; else Lùi; end; until false; until false; Thông thƣờng ta khởi trị cho v là dãy rỗng (không chứa phần tử nào) hoặc dãy có một phần tử. Ta chỉ yêu cầu dãy v đƣợc khởi trị sao cho v thoả P. Lƣu ý là cả dãy v thoả P chứ không phải từng phần tử trong v thoả P. Có bài toán yêu cầu tìm toàn bộ (mọi nghiệm) các dãy v thoả đồng thời hai tính chất P và Q. Nếu biết cách tìm một nghiệm ta dễ dàng suy ra cách tìm mọi nghiệm nhƣ sau: mỗi khi tìm đƣợc một nghiệm, ta thông báo nghiệm đó trên màn hình hoặc ghi vào một tệp rồi thực hiện thao tác Lùi, tức là giả vờ nhƣ không công nhận nghiệm đó, do đó phải loại v[i] cuối cùng trong dãy v để tiếp tục tìm hƣớng khác. Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 6 Phƣơng pháp này có tên là phƣơng pháp giả sai. Hai sơ đồ trên sẽ đƣợc sửa một chút nhƣ sau để tìm mọi nghiệm. Sơ đồ 3: Giải bài toán quay lui Sơ đồ 4: Giải bài toán quay lui (tìm mọi nghiệm) (tìm mọi nghiệm) Khởi trị: v thoả P; Khởi trị: v thoả P; d := 0; {đếm số nghiệm} d := 0; {đếm số nghiệm} repeat repeat if (v thoả Q) then if (v thoả Q) then begin begin d := d + 1; d := d + 1; Ghi nhận nghiệm thứ d; Ghi nhận nghiệm thứ d; Lùi; { giả sai } Lùi; { giả sai } end; end; if (Tìm được 1 nước đi) if (Hết khả năng duyệt) then Tiến then else if (có thể lùi được) begin then Lùi if d = 0 then else { hết khả năng } Ghi nhận: vô nghiệm; begin else if d = 0 then Ghi nhận: d nghiệm; Ghi nhận: vô nghiệm; exit; else end; Ghi nhận: d nghiệm; if (Tìm được 1 nước đi) exit; then Tiến end; until false; Soá hoùa bôûi Trung taâm Hoïc lieäu else Lùi; until false; http://lrc.tnu.edu.vn/ 7 Quá trình tìm kiếm lời giải theo thuật toán quay lui có thể mô tả bởi cây tìm kiếm lời giải sau đây: Start 1 2 3 Quay lui từ Bƣớc 4 về Bƣớc 3 4 … Xét tiếp các khả năng của Bƣớc 3 8 … 5 6 7 Hình 1.1 Cây tìm kiếm lời giải theo thuật toán quay lui 1.3. Kết luận Thuật toán quay lui, cũng nhƣ nhiều thuật toán khác nó chỉ mang tính định hƣớng chiến lƣợc để giải bài toán. Đây là không phải là một công cụ siêu việt để có thể giải tất cả các bài toán tìm nghiệm, liệt kê hay tối ƣu. Do đó, khi áp dụng thuật toán, đôi khi ta phải kết hợp thêm nhiều kĩ thuật, thuật toán khác thì mới có thể đem lại kết quả tốt nhất. Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 8 Chƣơng 2 XÂY DỰNG THUẬT TOÁN QUAY LUI VÀ TỔ CHỨC DỮ LIỆU CHO MỘT SỐ BÀI TOÁN KINH ĐIỂN Chƣơng 2 sẽ trình bày cách tổ chức dữ liệu để có thế áp dụng thuật toán quay lui cho một số bài toán kinh điển. 2.1. Bài toán từ chuẩn [2] 2.1.1. Giới thiệu bài toán Một từ chuẩn loại M là một dãy các chữ số, mỗi chữ số nằm trong khoảng từ 1 đến M. Số lƣợng các chữ số có mặt trong một từ đƣợc gọi là chiều dài của từ đó. Từ loại M đƣợc gọi là từ chuẩn nếu nó không chứa hai khúc (từ con) liền nhau mà giống nhau. Với giá trị n cho trƣớc, hiển thị trên màn hình một từ chuẩn loại 3 có chiều dài n. Thí dụ: 12131 là từ chuẩn loại 3, chiều dài 5. 1213123 là từ chuẩn loại 3, chiều dài 7. 1213213 không phải là từ chuẩn vì nó chứa liên tiếp hai từ con giống nhau là 213. Tƣơng tự, 12332 không phải là từ chuẩn vì chứa liên tiếp hai từ con giống nhau là 3. 2.1.2. Tổ chức dữ liệu và chương trình Ta dùng mảng v[1..n] để lƣu từ cần tìm. Tại mỗi vị trí k ta xác định giá trị v[k] trong khoảng 1..M sao cho v[1..k] là từ chuẩn. Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 9 Mảng v: 1 2 3 4 5 … n 1 2 1 3 1 … … Với k = 5, tại vị trí v[5], từ v[1..5] = “12131” là từ chuẩn. Điều kiện P: v[1..k] là từ chuẩn. Điều kiện Q: Dừng thuật toán theo một trong hai tình huống sau đây: nếu i = n thì bài toán có nghiệm v[1..n]. nếu i = 0 thì bài toán vô nghiệm. Duyệt các giá trị tại vị trí v[k] của từ v[1..k] bắt đầu từ v[k] + 1 đến M (M = 3) sao cho v[1..k] là từ chuẩn. CoNuocDi = true nếu tồn tại 1 giá trị v[k] nhƣ vậy. Ngƣợc lại, nếu với mọi v[k] = v[k] + 1 đến M, từ v[1..k] đều không chuẩn thì CoNuocDi = false. // Tai vi tri k xac dinh duoc 1 gia tri // thoa v[1..k] la tu chuan bool CoNuocDi(int k) { for (int i = v[k]+1; i <= 3; ++i) { v[k] = i; if (Chuan(k)) return true; } return false; } Để kiểm tra tính chuẩn của từ v[1..k], ta lƣu ý rằng từ v[1..k-1] đã chuẩn (tính chất P), do đó chỉ cần kiếm tra các cặp từ có chứa v[k], cụ thể là khảo sát các cặp từ có chiều dài k đứng cuối từ v. // Xac dinh v[1..k] la tu chuan bool Chuan(int k) { Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 10 int k2 = k/2; for (int j = 1; j <= k2; ++j) if (Bang(k,j)) return false; return true; } Đó là các cặp từ v[(k-d-d+1)..(k-d)] và v[k-d+1..k] với d = 1..(k/2). Nếu với mọi d nhƣ vậy hai từ đều khác nhau thì v[1..k] là từ chuẩn. Ngƣợc lại, v[1..k] không phải từ chuẩn. Hàm Bang(k,d) kiểm tra xem hai từ kề nhau chiều dài d tính từ k trở về trƣớc có bằng nhau hay không. Hai từ đƣợc xem là khác nhau nếu chúng khác nhau tại một vị trí nào đó. // ? v[k-d-d+1..k-d] = v[k-d+1..k] bool Bang(int k, int d) { int i; for (i = 0; i < d; ++i) if (v[k-i] != v[k-d-i]) return false; return true; } Thí dụ, tại vị trí k = 5, kiểm tra tính chuẩn của từ v[1..5] với d = 1..k/2 Mảng v: 1 2 3 … 1 2 1 3 n 1 … … so sánh các cặp từ: v[4] và v[5] (với d = 1), có v[4] = “3” khác v[5] = “1” v[2..3] và v[4..5] (với d = 2), có v[2..3] = “21” khác v[4..5] = “31” Kết luận: v[1..5] = “12131” là từ chuẩn. Quá trình tìm kiếm lời giải của bài toán từ chuẩn theo thuật toán quay lui có thể mô tả bởi cây tìm kiếm lời giải sau: Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 11 Start t 1 1 3 2 1 1 3 2 2 2 … 3 3 2 1 3 … Hình 2.1. Cây tìm kiếm lời giải cho bài toán từ chuẩn 2.1.3. Nhận xét Độ phức tạp của bài toán là hàm mũ MN , tuy nhiên với bài toán tìm 1 nghiệm thì có thể giải trong thời gian tƣơng đối nhanh. Với việc tổ chức dữ liệu sử dụng kiểu dữ liệu mảng có: Ƣu điểm: Truy nhập vào phần tử của mảng đƣợc thực hiện trực tiếp dựa vào địa chỉ tính đƣợc nên tốc độ nhanh, đồng đều đối với mọi phần tử. Nhƣợc điểm: Kiểu dữ liệu mảng bị hạn chế về việc khai báo kích thƣớc. Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 12 2.2. Bài toán xếp hậu [1], [2] 2.2.1. Giới thiệu bài toán Phát biểu bài toán: Quân Hậu trên bàn cờ Vua có thể “ăn” quân khác theo hàng, theo cột chứa nó hoặc theo đƣờng chéo của hình vuông nhận nó làm đỉnh. a) Tìm một cách xếp N quân Hậu trên bàn cờ Vua kích thƣớc N N ô sao cho không quân nào “ăn” đƣợc quân nào. b) Tìm mọi cách xếp N quân Hậu theo điều kiện trên. Lịch sử bài toán: Bài toán đƣợc đƣa ra vào năm 1848 bởi kỳ thủ Max Bezzel, và sau đó nhiều nhà toán học, trong đó có Gauss và Georg Cantor, có các công trình về bài toán này và tổng quát nó thành bài toán xếp hậu. Các lời giải đầu tiên đƣợc đƣa ra bởi Franz Nauck năm 1850. Nauck cũng đã tổng quát bài toán thành bài toán n quân hậu. Năm 1874, S. Gunther đƣa ra phƣơng pháp tìm lời giải bằng cách sử dụng định thức, và J.W.L. Glaisher hoàn chỉnh phƣơng pháp này. Edsger Dijkstra đã sử dụng vấn đề này năm 1972 để minh họa sức mạnh của những gì ông gọi là cấu trúc chƣơng trình. Ông cũng mô tả chi tiết về thuật toán quay lui - theo chiều sâu. Định lý: Với N > 3, có ít nhất một nghiệm cho bài toán N quân hậu. Định lý này đƣợc chứng minh lần đầu bới Ahrens năm 1910. Sau đó Hoffman, Loessi, và Moore năm 1969. Gần đây có một số lời giải mới đƣợc công bố, thậm chí có phƣơng án xếp đƣợc ngay 1 nghiệm của bài toán tại trang web: http://vi.wikipedia.org/wiki/Bài_toán_tám_quân_hậu Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/