Luận văn Thạc sĩ Khoa học: Tìm hiểu độ phức tạp một số thuật toán

Chia sẻ: Caphesuadathemhanh | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

34
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung của bản luận văn bao gồm ba chương, trình bày cụ thể như sau: Trình bày tóm tắt những kiến thức cơ bản và trọng tâm về lý thuyết thuật toán như máy Turing đơn định, máy Turing không đơn định, thuật toán, độ phức tạp thuật toán; Gồm có ba phần chính trình bày về khái niệm bài toán, danh sách các bài toán quan trọng và khái niệm độ phức tạp của bài toán; Gồm có hai phần chính trình bày lớp các bài toán P, NP và lớp bài toán NP-đầy đủ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Tìm hiểu độ phức tạp một số thuật toán

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN --------------------- Nguyễn Thế Quyền TÌM HIỂU ĐỘ PHỨC TẠP MỘT SỐ THUẬT TOÁN LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – Năm 2013
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN --------------------- Nguyễn Thế Quyền TÌM HIỂU ĐỘ PHỨC TẠP MỘT SỐ THUẬT TOÁN Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán Mã số: 60.46.35 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Nguyễn Hữu Ngự Hà Nội – Năm 2013
MỤC LỤC MỞ ĐẦU ................................................................................................................... 3 CHƢƠNG 1. KIẾN THỨC CHUẨN BỊ .................................................................. 4 1.1. Máy Turing.......................................................................................................... 4 1.1.1. Máy Turing............................................................................................... 4 1.1.2. Máy Turing tất định .................................................................................. 5 1.1.3. Máy Turing không tất định ....................................................................... 7 1.2. Khái niệm thuật toán ............................................................................................ 8 1.2.1. Khái niệm thuật toán ................................................................................. 8 1.2.2. Ví dụ về thuật toán.................................................................................... 9 1.2.3. Luận đề Church-Turing .......................................................................... 10 1.3. Độ phức tạp của thuật toán ................................................................................ 11 1.3.1. Độ phức tạp về thời gian ......................................................................... 11 1.3.2. Ví dụ cách tính độ phức tạp .................................................................... 12 CHƢƠNG 2. BÀI TOÁN VÀ ĐỘ PHỨC TẠP CỦA BÀI TOÁN ........................ 14 2.1. Bài toán là gì? .................................................................................................... 14 2.2. Một số bài toán quan trọng ................................................................................ 15 2.3. Độ phức tạp của bài toán ................................................................................... 20 CHƢƠNG 3. PHÂN LỚP CÁC BÀI TOÁN THEO ĐỘ PHỨC TẠP ................. 21 3.1. Lớp các bài toán P, NP và mối quan hệ giữa lớp P và lớp NP ............................ 21 3.1.1. Lớp P ...................................................................................................... 21 3.1.2. Lớp NP ................................................................................................... 21 3.1.3. Mối quan hệ giữa lớp P và NP ................................................................ 21 3.2. Lớp các bài toán NPC. ....................................................................................... 21 3.2.1. Phép dẫn với thời gian đa thức ................................................................ 21 3.2.2. Lớp các bài toán NPC ............................................................................. 22 3.2.3. Mối quan hệ giữa các lớp bài toán P, NP và NPC ................................... 22
3.2.4. Một số bài toán lớp NPC......................................................................... 23 1) Bài toán SAT. Định lý Cook .............................................................. 23 2) Bài toán 3SATIFIABILITY (3SAT) .................................................. 30 3) Bài toán 3-DIMENSIONAL MATCHING (3DM) ............................ 33 4) Bài toán VERTEX COVER (VC) ...................................................... 37 5) Bài toán CLIQUE .............................................................................. 39 6) Bài toán HAMILTON CIRCUIL (HC) .............................................. 39 7) Bài toán PARTITION ........................................................................ 39 8) Bài toán TRAVELING SALEMAN (TSP) ........................................ 39 KẾT LUẬN ............................................................................................................. 41 TÀI LIỆU THAM KHẢO ...................................................................................... 42
MỞ ĐẦU Lý thuyết độ phức tạp là một lĩnh vực trung tâm của khoa học máy tính với các kết quả liên quan chặt chẽ với sự phát triển và sử dụng các thuật toán. Nghiên cứu về lý thuyết độ phức tạp sẽ giúp chúng ta hiểu biết sâu sắc và khám phá ra ranh giới của những vấn để “có thể” tính toán với các nguồn tài nguyên hợp lý. Trong bản luận văn này, trước hết chúng tôi tìm hiểu một số khái niệm quan trọng của lý thuyết thuật toán như thuật toán và độ phức tạp của thuật toán. Trên cơ sở đó, chúng tôi bước đầu tìm hiểu một số khái niệm quan trọng của lý thuyết độ phức tạp như khái niệm bài toán, độ phức tạp của bài toán. Cuối cùng là chúng tôi tìm hiểu về các lớp phức tạp của bài toán và mối quan hệ giữa các lớp phức tạp đó. Trong đó đặc biệt quan tâm đến lớp phức tạp NP-đầy đủ. Nội dung của bản luận văn bao gồm ba chương: Chƣơng 1: Trình bày tóm tắt những kiến thức cơ bản và trọng tâm về lý thuyết thuật toán như máy Turing đơn định, máy Turing không đơn định, thuật toán, độ phức tạp thuật toán. Chƣơng 2: Gồm có ba phần chính trình bày về khái niệm bài toán, danh sách các bài toán quan trọng và khái niệm độ phức tạp của bài toán. Chƣơng 3: Gồm có hai phần chính trình bày lớp các bài toán P, NP và lớp bài toán NP-đầy đủ. Để hoàn thành bản luận văn này, chúng tôi đã nhận được sự giúp đỡ tận tình của thầy hướng dẫn – PGS.TS. Nguyễn Hữu Ngự và sự chỉ bảo góp ý của các thầy cô trong Bộ môn Tin học, Khoa Toán – Cơ – Tin học và các bạn đồng nghiệp. Nhân đây, chúng tôi cũng xin cảm ơn các thầy cô và các bạn đồng nghiệp đã giúp đỡ chúng tôi trong quá trình làm luận văn.
CHƢƠNG 1. KIẾN THỨC CHUẨN BỊ Trước khi nói về thuật toán, chúng ta hãy xem xét một mô hình tính toán thể hiện khá tốt về các thuật toán. 1.1. Máy Turing (Turing machine) 1.1.1. Máy Turing Gồm có: 1) Tập trạng thái trong hữu hạn 2) Băng vô hạn hai phía (về lý thuyết có thể kéo dài tuỳ ý cả hai phía) 3) Bảng tín hiệu vào, bảng tín hiệu trên băng và một đầu đọc-ghi 4) Bảng chuyển trạng thái q  ... B B B B a1 a2 ... ... ai ... ... an B B B ... Một bước làm việc của máy gồm: - Đầu đọc-ghi đọc tín hiệu trên băng - Căn cứ vào trạng thái trong và tín hiệu đọc trên băng, đầu đọc-ghi sẽ ghi một tín hiệu trên băng, dịch chuyển sang phải hoặc sang trái một ô và chuyển sang một trạng thái trong nào đó. Quy ước khi máy bắt đầu làm việc thì trạng thái là trạng thái đầu của máy, với input hữu hạn trên băng, đầu đọc-ghi nằm ở ký tự bên trái nhất của input. Các kết quả trung gian trong khi tính toán có thể lưu trên băng hoặc có thể tổ chức lưu vào trạng thái trong (nhưng chú ý là số trạng thái trong của một máy phải hữu hạn).
1.1.2. Máy Turing tất định (DTM) Có thể định nghĩa một cách hình thức một máy Turing tất định như sau: là một bộ: M = trong đó: - : là bảng tín hiệu trên băng (hữu hạn) - : là bảng tín hiệu vào (hữu hạn),    - Q: là tập trạng thái (trong) (hữu hạn) - F: là hàm chuyển F: Q x   Q x  x {L,R} - q0: trạng thái ban đầu (q0  Q) - t1: trạng thái kết thúc (t1  Q) - B: ký tự trắng, B  , B   Ý nghĩa: -  là các tín hiệu vào để ghi input -  là các tín hiệu đọc và ghi trên băng Hàm chuyển F(q, a) = (q', a', D) có thể cho bằng bảng như sau: a ... ... q (q', a', D) ... - Ban đầu các tín hiệu trên băng là B, băng có thể kéo dài vô hạn ở cả hai chiều: trái và phải. Xâu a1a2...qai...ak được gọi là một hình trạng của máy, trong đó các ak , qQ, có nghĩa là đầu đọc-ghi đang đọc ô thứ i, tín hiệu đang được đọc là ai. Tại mỗi bước, máy ở trạng thái q, đầu đọc-ghi đọc tín hiệu ai tại ô trên băng, hình trạng của máy có dạng a1a2...ai-1qai...ak. Theo hàm chuyển F(q, ai) = (q', c, D), máy
sẽ chuyển sang trạng thái q', ghi c lên băng (thay cho a i), đầu đọc-ghi chuyển sang phải hay sang trái một ô tùy theo D là R hoặc L. Ta nói rằng máy M chuyển từ hình trạng: H = a1a2...ai-1qai...ak sang hình trạng: H' = a1a2...q'ai-1cai+1...ak nếu D = L hoặc H' = a1a2...ai-1cq'ai+1...ak nếu D = R Ký hiệu H  H'. Máy sẽ làm việc từng bước cho đến khi gặp hình trạng mà hàm chuyển F(s,a) không xác định hoặc gặp trạng thái kết thúc t1. Xâu x (input) trên bảng tín hiệu  (tức là x  *) gọi là được đoán nhận bởi máy M nếu tồn tại dãy hình trạng H0, H1, ..., Hm sao cho: H0  H1  ... Hm. H0 là hình trạng ban đầu, input x được ghi trên băng, đầu đọc-ghi nhìn vào ký tự đầu tiên của input, trạng thái của máy là q0, tức là: H0 = q0a1a2...ai-1ai...an với x = a1a2...ai-1ai...an. Hm có trạng thái là t1. Tập N các xâu (ngôn ngữ trên ) thuộc * gọi là được đoán nhận bởi máy M nếu N = {x | x*, x được đoán nhận bởi máy M}. Các bài toán có thể có nhiều loại: - Đoán nhận một tính chất của input - Tính toán một giá trị - ... Chú ý: Hàm chuyển F có thể không xác định khắp nơi. Máy sẽ dừng khi gặp trạng thái t1 kết thúc (cho trả lời "yes") hoặc dừng ở trạng thái khác t 1 (cho trả lời "no") hoặc gặp bộ (s, a) tại đó F(s, a) không xác định (cũng cho trả lời "no"). Tuy nhiên có thể làm cho hàm chuyển F trở thành xác định khắp nơi nếu thêm một trạng thái kết
thúc phủ định qp, và với mọi bộ (s, a) tại đó F(s, a) không xác định cho máy chuyển sang trạng thái qp F(s, a) = (qp, , ). Nếu không có gì khác thì ngầm định bảng tín hiệu vào là  = {0,1}, và chủ yếu ta chỉ xét ví dụ trên các bài toán đoán nhận. Ký hiệu q0 là trạng thái đầu, t1 là trạng thái kết thúc khẳng định. Ví dụ: Máy Turing đoán nhận ngôn ngữ {x | x có độ dài chẵn} 0 1 B q0 (q1, 0, R) (q1, 0, R) (t1, B, ' ') q1 (q0, 0, R) (q0, 0, R) - Với input 010110 ta có dãy hình trạng: (q0)010110  0(q1)10110  01(q0)0110  010(q1)110  0101(q0)10  01011(q1)0  010110(q0)  010110(t1) trạng thái cuối cùng là trạng thái kết thúc đoán nhận t1. 1.1.3. Máy Turing không tất định (NTDM) Định nghĩa như máy Turing tất định, trong đó hàm chuyển F là hàm đa trị nghĩa là F: Q x   2Q x  x {L,R}. Tại mỗi bước, có thể chuyển sang bước sau bằng một trong các khả năng tùy theo hàm chuyển F. Nếu có một nhánh đoán nhận input x thì xem như máy đoán nhận input đó. Giả sử F(s, a) = {(si1, ai1, Di1), (si2, ai2, Di2), ..., (sim, aim, Dim)} là một tập (có thể rỗng). Với hình trạng H với trạng thái s và tín hiệu a được đọc máy có thể chuyển đến một trong các hình trạng: H  Hi1, H  Hi2, ..., H  Him trong đó Hik có trạng thái sik và tín hiệu được ghi là aik. Có thể biểu diễn các bước làm việc của máy bằng hàng đợi hoặc bằng cây.
Ví dụ: 0 1 B (q0,1,R) q0 (q1,1,R) q1 (q2,0,L) (t1,' ',' ') q2 (q0,1,R) Với w = 010 (q0)010 1(q0)10 1(q1)10 (q2)100 1(q0)00 11(q0)0 11(q1)0 111(q0) 111(q1)B (t1) 1.2. Khái niệm thuật toán (algorithm) Bài toán xử lý thông tin: Input  Công cụ  Output Với dữ liệu vào (input) công cụ sẽ tính toán và cho kết quả theo yêu cầu của bài toán. Nói chung ta phân biệt một số loại bài toán: - Những bài toán đoán nhận một tính chất (xét số nguyên n có phải nguyên tố hay không,...) - Những bài toán tính giá trị một hàm - Những bài toán tìm một lời giải (tìm đường đi trên đồ thị, tìm chu trình Hamilton, ...). Để giải quyết bài toán cần thuật toán. Thuật toán là công cụ xử lý thông tin. 1.2.1. Khái niệm Một cách không hình thức thì thuật toán là việc mô tả một cách chính xác quá trình thực hiện trên các đối tượng để nhằm đạt được một kết quả nào đó theo một yêu cầu cho trước.
Cần chú ý đặc trưng hữu hạn trong thuật toán: - Đối tượng hữu hạn, thao tác hữu hạn - Cho kết quả qua một số hữu hạn bước. Ta phân biệt hai loại thuật toán: tất định và không tất định. Đối với thuật toán tất định tại mỗi thời điểm chỉ có không quá một bước tiếp theo. Đối với thuật toán không tất định tại mỗi thời điểm có thể có một số khả năng để lựa chọn bước tiếp theo. Thông thường để mô tả thuật toán (tức là chỉ dẫn ở mỗi bước cần thực hiện những công việc gì) ta dùng một văn bản hướng dẫn các bước, một sơ đồ khối, một ngôn ngữ lập trình nào đó, hoặc một ngôn ngữ tựa Pascal, ... 1.2.2. Ví dụ về thuật toán Ví dụ: Thuật toán sắp dãy số tăng bằng đổi chỗ trực tiếp Input: n và dãy số n phần tử a1, a2, ..., an . Output: Dãy số a1, a2, ..., an được sắp xếp tăng. Mô tả cụ thể các bước: 1. i = 1 2. k = i + 1 3. Nếu ai > ak thì hoán vị ai với ak 4. k = k + 1 5. Nếu k ak then hoán vị giá trị ai với ak cho nhau.
Sơ đồ khối: Nhập n, dãy số a1, ..., an i=1 k = i+1 Đ ai>ak hoán vị ai với ak S k = k+1 Đ k
1.3. Độ phức tạp của thuật toán Để đánh giá hiệu quả của một thuật toán, ta có thể đánh giá độ phức tạp của thuật toán về mặt thời gian, tức là thời gian máy tính làm việc và về không gian, tức là dung lượng bộ nhớ của máy tính cần thiết để thực hiện thuật toán. Trong luận văn này, khi nói đến độ phức tạp của thuật toán ta luôn hiểu là độ phức tạp về thời gian. 1.3.1. Độ phức tạp về thời gian Thời gian làm việc của máy tính khi chạy một thuật toán nào đó không chỉ phụ thuộc vào thuật toán, mà còn phụ thuộc vào máy tính được sử dụng. Vì thế, để có một tiêu chuẩn chung, ta sẽ đo độ phức tạp của một thuật toán bằng số các phép tính phải thực hiện. Khi thực hiện cùng một thuật toán, số các phép tính phải thực hiện còn phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế, độ phức tạp của thuật toán sẽ là một hàm số phụ thuộc độ lớn của đầu vào. Trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này, mà chỉ cần biết “cỡ” của chúng, tức là cần có một ước lượng đủ tốt của chúng. Giả sử A là một thuật toán. Ký hiệu T(X) là thời gian tính toán với đầu vào X. Độ phức tạp của thuật tính trong trường hợp xấu nhất: T(n) = max {T(X), X có độ dài bằng n} Nếu A là thuật toán không tất định, thì T(n) là độ dài dài nhất trong các nhánh làm việc với đầu vào X. Trên thực tế còn xét đến độ phức tạp trong trường hợp trung bình: T(X), X có độ dài bằng n Ttb(n) = số các dữ liệu có thể với độ dài n Để ước lượng độ phức tạp của thuật toán, ta dùng khái niệm bậc O-lớn và bậc (bậc Theta). Giả sử f(n) và g(n) là hai hàm xác định trên tập hợp các số nguyên dương. Ta nói f(n) có bậc O-lớn của g(n), và viết f(n) = O(g(n)) hoặc f = O(g), nếu tồn tại n0 và hằng số dương C sao cho với mọi n  n0 luôn có f(n)  C.g(n).
Nếu tồn tại n0 và các hằng số dương C1 và C2 sao cho với mọi n  n0 luôn có C1g(n)  f(n)  C2g(n), thì ta ký hiệu f(n) = (g(n)). Ký hiệu O nói rằng hàm f(n) bị chặn trên bởi g(n) (sai khác một hằng số dương), còn ký hiệu  nói rằng hàm f(n) tương đương với g(n) (sai khác các hằng số dương). Nếu thuật toán A có T(n) = O(g(n)) thì g(n) mới chỉ là chặn trên của T(n), còn nếu T(n) =(g(n)) thì g(n) mới là tượng trưng chính xác cho độ phức tạp của thuật toán. Tuy nhiên việc tính O dễ hơn việc tính . Nếu T(n) = O(g(n)) (hoặc tốt hơn là (g(n))) trong đó g(n) là một đa thức theo n thì ta nói rằng thuật toán làm việc với thời gian đa thức, gọi tắt là thuật toán đa thức. Thuật toán đa thức thường được xem là tốt. 1.3.2. Ví dụ cách tính độ phức tạp Ví dụ 1: Thuật toán tìm kiếm nhị phân Input: dãy số tăng a1, ..., an; số x. Output: trả lời x có thuộc dãy hay không Dùng thuật toán đệ quy DQ(a, b) (tìm trên đoạn con [d, c]) 1. Nếu d = c và a(c) = x return "yes" 2. c = (a + b)/2 3. Nếu a(c) = x return "yes" 4. Nếu x < a(c) thì gọi DQ(a, c-1) else gọi DQ(c+1, b) Để tìm nghiệm, gọi DQ(1, n) Đánh giá độ phức tạp: T(2*k) = T(k) + 2. T(1) = 1 T(2) = T(1) + 2 ... T(2k) = T(2k-1) + 2 Lấy 2k xấp xỉ n, T(n) = T(2k) (cộng từng vế và khử) = 2*k – 1 = 2*log2n - 1 = O(logn).
Ví dụ 2: (tính độ phức tạp trung bình) Máy Turing đoán nhận ngôn ngữ {X | X  {0,1}* có ít nhất một chữ số 1} Số dữ liệu có thể với độ dài n là s = 2n Số các X không có chữ số 1 (không được đoán nhận) là 1 (duy nhất "00...0"), thời gian T(X) = n, tỷ lệ không đoán nhận là T0(n) = n/s. Với i  n thì số các X (được đoán nhận) có X(i) = '1', và X(k) = '0' với k < i, là 2n-i, với thời gian T(X) = i. Tổng thời gian tính với các X này là: h = 1*2n-1 + 2*2n-2 + ... + n*2n-n Tỷ lệ đoán nhận là T1(n) = h/s = t t = 1*2-1 + 2*2-2 + ... + (n-1)*2-(n-1) + n*2-n Đặt c = 1/2 (khi đó T0(n) = n/s = n*cn) t = c + 2*c2 + ... + (n-1)*cn-1 + n*cn c*t = c2 + 2*c3 + ... + (n-1)*cn + n*cn+1 t - c*t = c + c2 + ... + cn + n*cn+1 = c*[(1- cn)/(1- c) - n*cn] T1(n) = t = c*[(1- cn)/(1- c) - n*cn ]/(1-c) (vì c/(1-c) = 1) Vậy Ttb(n) = T1(n) + T0(n) = (1- cn)/(1- c) - n*cn + n*cn = 2 - 1/2n-1. Trong khi đó độ phức tạp T(n) = n.
CHƢƠNG 2. BÀI TOÁN VÀ ĐỘ PHỨC TẠP CỦA BÀI TOÁN 2.1. Bài toán là gì? Trong giới hạn của chúng ta, sẽ chỉ xem xét các bài toán là một vấn đề phù hợp với tính toán của máy tính và một tập hợp các kết quả chính xác. Vấn đề về tìm kiếm một bản án thích đáng dành cho bị cáo không phải là bài toán vì nó phụ thuộc vào tư pháp và do đó nó không thích hợp cho việc xử lý của máy tính. Mặt khác, vấn đề về việc dịch một văn bản tiếng Đức sang một ngôn ngữ khác thì phù hợp với việc xử lý của phép tính, nhưng trong trường hợp này không rõ các kết quả có chính xác hay không. Vì vậy vấn đề dịch thuật cũng không phải là một bài toán. Một ví dụ rõ ràng về một bài toán là việc tính toán con đường ngắn nhất từ đỉnh s đến đỉnh t trong một đồ thị mà trong đó mỗi cạnh được gắn với một chi phí dương (chúng ta có thể diễn giải như khoảng cách hay thời gian di chuyển). Một bài toán được xác định bởi:  Một mô tả tập hợp đầu vào được phép, mỗi một đầu vào có thể được thể hiện như là một chuỗi hữu hạn trên một bảng chữ cái hữu hạn (tập hợp ký hiệu của máy tính)  Một phát biểu về các tính chất mà câu trả lời (hoặc giải pháp) cần phải thoả mãn. Thông thường bài toán được mô tả như trong ví dụ sau: Đầu vào: Một số nguyên dương n Câu hỏi: n có nguyên tố không? Trong mỗi trường hợp, khi chúng ta tìm kiếm một trong nhiều câu trả lời chính xác tiềm năng, chúng ta coi bài toán như là một bài toán tìm kiếm. Nếu chúng ta tìm kiếm một giải pháp tối ưu về mặt nào đó, chúng ta coi bài toán đó như là một bài toán tối ưu (ví dụ như trường hợp tìm kiếm một đường đi ngắn nhất). Thông thường, tính toán giá trị của một giải pháp tối ưu là đủ (ví dụ, độ dài của một con đường ngắn nhất). Những biến thể này được gọi là các bài toán đánh giá. Bài toán đánh giá luôn luôn có
giải pháp duy nhất. Trong trường hợp đặc biệt, khi câu trả lời có thể chỉ là 0 (không) và 1 (có) và chúng ta phải quyết định khả năng nào trong hai khả năng này là chính xác, thì lúc đó chúng ta nói về một bài toán quyết định. Các bài toán quyết định phát sinh tự nhiên trong nhiều tình huống: Từ một cấu hình cho trước của một bàn cờ, liệu quân cờ màu trắng có một chiến lược giành chiến thắng không? Có phải con số đưa ra là một số nguyên tố không? Có thể thoả mãn các điều kiện đã quy định không? Các bài toán bao gồm tất cả các vấn đề có thể xử lý được bởi máy tính và chúng ta có thể phân biệt một cách rõ ràng giữa các giải pháp chính xác và không chính xác. Trong số này có các bài toán tối ưu và các bài toán với các giải pháp duy nhất như các bài toán đánh giá và các bài toán quyết định. Các định dạng đầu vào khác nhau cho cùng một “bài toán” sẽ đưa đến các bài toán khác nhau, nhưng thông thường những bài toán này về mặt thuật toán rất giống nhau. 2.2. Một số bài toán quan trọng 1) Các bài toán về ngƣời bán hàng Bài toán người bán hàng (TSP): là bài toán tìm kiếm một chu trình ngắn nhất qua n thành phố, mỗi thành phố đúng một lần và quay trở lại điểm xuất phát của nó. Các thành phố được ký hiệu bằng các nhãn là 1, ..., n và các khoảng cách giữa các thành phố là di,j (1 ≤ i, j ≤ n). Các khoảng cách được chọn từ tập  {∞}, và giá trị ∞ có nghĩa là không có sự kết nối trực tiếp giữa hai thành phố cụ thể. Mỗi chu trình là một phép hoán vị π của {1, …, n}, do đó các thành phố đã đến được sắp xếp theo thứ tự là π(1), π(2), …, π(n), π(1). Giá trị của một chu trình π được tính bởi: dπ(1), π(2) + dπ(2), π(3) + … + dπ(n-1), π(n) + dπ(n), π(1) và một chu trình có giá trị cực tiểu cần được tính toán. Có nhiều biến thể đối với bài toán này. TSP (hoặc TSPOPT) là ký hiệu cho bài toán tối ưu nói chung. TSPEVAL và TSPDEC ký hiệu cho các bài toán ước lượng và bài toán quyết định có liên quan. Đối với bài toán quyết định, đầu vào bao gồm một giới hạn D và phải xác định có hay
không một chu trình có giá trị không vượt quá D. Chúng ta cũng sẽ xem xét các biến thể bị giới hạn sau đây:  TSPSYM: các khoảng cách là đối xứng (di,j = dj,i)  TSP∆: các khoảng cách thoả mãn bất đẳng thức tam giác, có nghĩa là di,j≤di,k+dk,j  TSPd-Euclid: các thành phố là các điểm trong không gian Euclide d chiều Rd và khoảng cách tương ứng với khoảng cách Euclide (chuẩn L2)  TSPN: các khoảng cách thuộc {1, …, N} (N là một số tự nhiên xác định)  DHC (Chu trình Hamilton định hướng): khoảng cách thuộc {1, ∞}, và các định dạng đầu vào thông thường là một đồ thị định hướng chỉ chứa những cạnh có giá trị bằng 1.  HC = DHCSYM: biến thể đối xứng của DHC, mà định dạng đầu vào thông thường là một đồ thị vô hướng chỉ chứa những cạnh có giá trị bằng 1. 2) Các bài toán về xếp ba lô Làm thế nào để một hành khách thu xếp hành lý của mình trong giới hạn W từ n đồ vật muốn mang theo với giả thiết rằng đồ vật thứ i (i = 1, n ) có trọng lượng wi  và có giá trị ui  được gọi là bài toán xếp ba lô (KNAPSACK). Hành khách không được phép mang các đồ vật có tổng trọng lượng vượt quá W. Do hạn chế này, mục tiêu là tối đa hoá tổng giá trị của tất cả các đồ vật được chọn. Ở đây, cũng có các biến thể mà trong đó các giá trị ui và/hoặc các trọng lượng wi đều bị chặn. Trong trường hợp tổng quát, các đồ vật có những giá trị khác nhau trên mỗi đơn vị trọng lượng. KNAPSACK* biểu thị trường hợp đặc biệt với ui = wi cho tất cả các đồ vật. Mục tiêu chỉ là để đạt tới càng gần càng tốt giới hạn trọng lượng mà không bị vượt quá mức quy định. Hơn nữa, nếu W = (w1 + w2 + … + wn)/2, và chúng ta xem xét bài toán quyết định là liệu chúng ta có thể đạt được trọng lượng tối đa cho phép hay không, thì bài toán sẽ tương đương với câu hỏi liệu tất cả các đồ vật có thể được chia thành hai nhóm
có tổng trọng lượng giống nhau không. Trường hợp đặc biệt này được gọi là bài toán phân hoạch (PARTITION). 3) Các bài toán về phân hoạch Bài toán phân hoạch (PARTITION) cũng là một trường hợp đặc biệt của bài toán đóng thùng (BINPACKING), trong đó các thùng có kích thước b có sẵn, chúng ta phải đóng thùng n đồ vật với các kích cỡ u1, u2, ..., un vào càng ít thùng càng tốt. Nhưng chúng ta cũng có thể xem BINPACKING như là một trường hợp rất đặc biệt của bài toán lập lịch. Lớp của các bài toán lập lịch là gần như không thể đạt được về mặt tổng quát. Trong mỗi trường hợp, các nhiệm vụ phải được phân chia giữa con người hoặc máy móc với những hạn chế ở các mặt khác nhau. Không phải tất cả mọi người đều thích hợp cho mọi nhiệm vụ, những người khác nhau có thể cần những khoảng thời gian khác nhau để hoàn thành cùng một nhiệm vụ, những nhiệm vụ nhất định có thể cần được hoàn thành theo một trình tự cụ thể, có thể xác định những thời điểm bắt đầu sớm nhất hoặc những thời điểm hoàn thành chậm nhất (các thời hạn chót), và có thể sử dụng các điều kiện tối ưu khác nhau. 4) Các bài toán giám sát (hoặc phủ) Một bài toán giám sát điển hình là bài toán triển lãm nghệ thuật. Yêu cầu đưa ra là giám sát tất cả các bức tường của một phòng triển lãm với càng ít máy quay càng tốt. Chúng ta sẽ hạn chế trong các bài toán giám sát trên các đồ thị vô hướng, trong trường hợp đó chúng thường được gọi là các bài toán phủ. Trong bài toán phủ đỉnh (VERTEXCOVER), mỗi đỉnh sẽ theo dõi tất cả các cạnh liên quan tới nó, và tất cả các cạnh được theo dõi với càng ít đỉnh càng tốt. Trong bài toán phủ cạnh (EDGECOVER), các vai trò đảo ngược lại: mỗi cạnh theo dõi hai đỉnh liên quan đến nó, các đỉnh sẽ được giám sát với càng ít cạnh càng tốt. 5) Các bài toán clique Các đỉnh của đồ thị có thể được sử dụng để biểu diễn con người, các cạnh sẽ biểu diễn mối quan hệ giữa mọi người. Một clique được định nghĩa là một nhóm trong
đó mỗi người thích những người khác trong nhóm. Trong bài toán phủ clique (CLIQUECOVER), các đỉnh của một đồ thị phải được phân chia thành càng ít tập hợp càng tốt, theo cách như vậy mỗi tập hợp tạo thành một clique. Trong bài toán clique (ký hiệu là CLIQUE), một clique lớn nhất có thể sẽ được tính toán. Một anti-clique (“không ai thích ai cả”, giữa hai đỉnh bất kỳ không có một cạnh nào) được gọi là một tập hợp độc lập, và bài toán tính toán một tập hợp độc lập lớn nhất được gọi là INDEPENTSET. 6) Các bài toán xây dựng nhóm Xây dựng nhóm có nghĩa là phân chia những người với khả năng khác nhau vào các nhóm hợp tác, trong đó các thành viên của mỗi nhóm phải làm việc cùng nhau. Đối với bài toán k-DM (đối sánh k chiều, nghĩa là xây dựng các nhóm có kích thước k), chúng ta có sẵn k nhóm người (mỗi nhóm đại diện cho một trong k khả năng), và danh sách các nhóm k thành viên tiềm năng, trong đó mỗi người đến từ các nhóm khả năng. Mục đích là để hình thành nên càng nhiều nhóm càng tốt với hạn chế là mỗi người chỉ có thể được tham gia vào một nhóm. 2-DM cũng được biết đến như là bài toán hôn nhân: hai “khả năng” được hiểu như là hai giới tính, một nhóm có tiềm năng được xem như là một cuộc “hôn nhân bền vững”, và mục tiêu là tối đa hoá số lượng các cuộc hôn nhân bền vững. 7) Các bài toán luồng tối ƣu trong các mạng Trong bài toán luồng qua mạng (NETWORKFLOW), người ta tìm kiếm các luồng tối đa trong các mạng. Chúng ta chỉ quan tâm đến bài toán cơ bản mà trong đó chúng ta tìm kiếm để tối đa hoá luồng từ s đến t trong một đồ thị có hướng. Luồng f(e) chạy theo một cạnh e phải là số nguyên không âm bị chặn trên bởi khả năng c(e) của cạnh đó. Luồng tổng đạt đến một đỉnh v  {s, t}, nghĩa là tổng số f(e) với e = (., v) phải bằng luồng tổng rời khỏi v, tức là tổng số f(e) với e = {v, .}. Đỉnh nguồn s không có bất kỳ cạnh nào đi vào và đỉnh đích t không có bất kỳ cạnh nào đi qua.