- Định lý Ford-Fulkerson 241 7.3 Thuật toán tìm luồng cực đại trong m ạng 244 7.4 M ột số bài toán luồng tổng quát 249 7.5 M ột sô' ứng dụng trong tổ hợp 252 Phần 3. - Các bài toán tổng quát Tổ hợp đụng chạm đến nhiều vấn đề khác nhau của toán học, do đó khó có thể định nghĩa nó một cách hình thức. - Bài toán đếm được áp dụng một Phân J . - h) Bải toán liệt kê: bài toán này quan tâm đến tất cả cấu hình có thể có được, vì thế lời giải của nó cần được biểu diễn dưới dạng thuật toán "vét cạn" tất cả các cấu hình. - Bài toán liệt kê được làm "nền" cho nhiều bài toán khác. - Đ ây là bài toán có nhiều ứng dụng irong thực tién và lý thuyết tổ hợp đã đóng góp m ột phần đáng kể trong việc xây dựng được những thuật toán hữu hiệu. - N hiều bài toán nổi tiếng đã được giải trên máy tính bàng nhữrm thuật toán của toán hữu hạn. - Bài toán dem 2 BÀI TOÁN ĐẾM 2.1. - T a sẽ xét m ột số thí dụ m inh hoạ cho việc sử dụng nguyên lý bù Irừ để giải các bài toán đếm. - Bài toán dếm = N{A^ n /Ì. - Số N trong bài toán trên được gọi là sốmcĩt íhứ ĩựvìì được ký hiệu là D. - T h í dụ dưới đây trình bày m ột bài toán nổi tiếng củ a Lucas (1891). - Đ ể tính i>{2n, k) ta giải 2 bài toán con sau đây: B ài to á n 1. - T heo bài toán 1, số cách thuộc lớp này là Cf,rl. - Theo bài toán 1, sô’ c á c li thuộc lớp này là Ờ n-k . - n -k Từ kết quả của bài toán 2, ta nhận được 2n . - G iải: Gọi lĩ„ là sô' lần di chuyển đĩa ít nhất cần thực hiện để giải xong bài toán tháp Hà nội. - Hàm sinh và bài toán đếm G iả sử {/ỉ„ I. - M ột lời giải bài toán của bài toán với . - Dưới đây là m ột số bài toán m à việc giải quyết nó được đưa về việc xây dựng TRAN. - Xét bài toán m ở đầu. - Bài toán đưa ra danh sách tất cá càu hình tổ hợp có thể có, được gọi là hài toán liệt kê tổ hợp. - Có thể nói rằng phương pháp liệt kê là cách cuối cùng để có thể giải được m ột số bài toán tổ hợp hiện nay. - Để xây dựng chừng 1 tỷ cấu hình (con số này không phải là lớn đối với các bài toán tổ hợp - xem lại các số m ất thứ tự D,„ số phân bố í. - Thuật toán và độ phức tạp tính toán N hư đã giới thiệu ở trên, ta hiểu việc giải bài toán liệt kê là xây dựng m ột thuật toán để theo đó có thể lần lượt xây dựng được tất cả các cấu hình cần quan tâm. - Ta hiểu thuật toán giải bài toán đặt ra là một thủ tục xác định hao gồm mộ! dãy hữu hạn các hước cán thực hiện đ ể thu được lời giải của bài toán. - Thuật toán có các đặc trưng sau đây. - Đ ầu ra (Output): Với mỗi tập các dữ liệu đầu vào, thuật toán đưa ra các dữ liệu tương ứng với lời giải của bài toán. - Chính xá c (Precision): C ác bước của thuật toán được m ô tả chính xác. - T ổng quát (Generality): T huật toán có thể áp dụng để giải m ọi bài toán có dạng đã cho. - M ô tả thuật toán tìm số lớn nhất trong ba sô' đã cho. - Tuy rang bài toán đặt ra là rất đơn giản nhưrm mục đích của chúng ta là dùng nó để giải thích khái niệm thuật toán. - Thuật toán gổm các bước sau: Bước 1. - Tất nhiên có thể m ô tả thuật toán sử dụng m ột ngôn ngữ lập trình nào đó. - Dưới đây ta liệt kê m ột sô' câu lệnh chính được sử dụng để mô tả thuật toán. - Bài toán liệt ké T h í dụ 3. - Thuật toán tìm sô' lớn nhất trong dãy hữu hạn số. - Sử dụng thủ tục này ta xây dựng thuật toán giải bài toán đặt ra. - Rõ ràng, thời gian tính của m ột thuật toán là hàm của dữ liệu đầu vào. - Thời gian như vậy sẽ được gọi là thời gian tính tốt nhất của thuật toán với đầu vào kích thước n. - Thời gian nhiều nhất cần thiết để thực hiện thuật toán với m ọi bộ dữ liệu đầu vào kích thước n. - Thời gian như vậy sẽ được gọi là thời gian tinh tồi nliãt của thuật toán với đầu vào kích thước n. - Thời gian trung bình cần thiết để thực hiện thuật toán trên tập hữu hạn các đầu vào kích thước n. - Thời gian như vậy sẽ được gọi là thời gian tính trung hình của thuật toán. - m à thuật toán đòi hỏi thực hiện. - Rõ ràng vòng lặp trong thuật toán luôn thực hiện đúng n. - Thí dụ., giả sử thời gian tính tồi nhất của m ột thuật toán là t{n. - 0.15 sẽ cho ta thời gian tính đo bằng phút của thuật toán. - Bây giờ ta có thể định nghĩa bậc của thời gian tính tốt nhất, tồi nhất, và trung bình của thuật toán như sau Đ ịn h n g h ĩa. - N ếu thuật toán đòi hỏi (hời gian íính tồi nhấì là t(n) VỚI độ dài đcìu vào n và ì{n. - N ếu thuật toán đòi hỏi thời gian tính trung bình là. - Nếu thời gian tính tốt nhất của thuật toán vừa là 0{g(n)) vừa là Q.{g{n. - ta sẽ nói thời gian tính tốt nhất của thuật toán là Q{g(n. - Đ ể giải bài toán. - Rõ ràng thời gian tính củà thuật toán có thể đánh giá bởi số lần thực hiện câu lệnh. - Do đó thời gian tính tốt nhất của thuật toán là. - Vì th ế thời gian tính tồi nhất của thuật toán là Q(n). - Cuối cùng, ta tính thời gian tính trung bình của thuật toán. - Vậy thời gian tính trung bình của thuật toán là 0{n). - nlA, nên thời gian tính trung bình của thuật toán ià Q.{n). - Đối với thuật toán trong thí dụ này. - Sử dụng m ệnh đề vừa chứng m inh ta có thể đánh giá được số phép chia nhiểu nhất cần phải thực hiện trong thuật toán Euclide. - Khi đó với m ột sô' kích thước đầu vào nhất định thuật toán B có thể vẫn là tốt hơn. - B à i to á n liệ t kâ Nếu như đối với m ột bài toán ta có thể xây dựng thuật loán vơi thời gian tính tồi nhất là đa thức, 'áù bài toán đặt ra gọi là dược giải toí. - Nếu bài toán không có thuật toán với thời gian tồi nhất đa thức để giải thì nó được gọi là khc) (Ịiái (intractable). - N ếu như có thuật toán giải bài toán như vậy, thì chắc chắn nó sẽ đòi hỏi rất nhiều thời gian. - Những bài toán như vậy được gọi ià không giải được (unsolvable problem. - Phương pháp sinh Phương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp đặt ra nếu như hai điều kiện sau được thực hiện: ỉ ) C ó t h ể xá c định được m ột thứ tự trên tập các cẩu hình tổ hợp cấn liệí kê. - Bài toán đặt ra là: Cho x. - Bài toán dặt ra là. - Vì vậy, thông thường thuật toán sinh chỉ có thể xây dựng được đối với những bài toán liệt kê tổ hơp đơn giản. - Đ ể giải những bài toán liệt kê phức tạp, người ta thường dùng thuật toán được trình bày trong m ục tiếp theo, có tính phổ dụng cao hơn. - Đ ó là thuật toán quay lui. - Các phần còn lại giống như bài toán trước. - Việc xây dựng hàm g phụ thuộc vào từng bài toán tối ưu tổ hợp cụ thể. - V iệc tính giá trị của g phải đoíi giản hơn việc giải bài toán tối ưu tổ hợp ở vế phải của. - Dưới đây chúng ta sẽ xét m ột số thí dụ m inh hoạ cho thuật toán vừa trình bày. - B ù i Ĩ(XUÌ t o i ưu ì ổ hợp M ô hình toán học của bài toán có dạng sau. - Ký hiệu D là tập các phương án của bài toán ( 1): D ¿ a X í \ l a 2. - (2 ) Để xây dựng hàm tính y ận dưới, cùng với bài toán cái túi (1) ta xét bài toán cái tiíi biến liên tục sau: Tim g = max. - ,v„) là m ột phương án luỳ ý của bài toán (3). - G iải bài toán cái túi sau theo thuật toán nhánh cận vừa trình bày f{ x. - Quá trình giải bài toán được m ô tả trong cây tìm kiếm trong hình 1. - Giải bài toán cái túi bàng thuật toán nhánh cận Dưới đây là chương trình trên PASCAL giải bài toán cái túi theo thuật toán nhánh cận vừa trình bày. - Mô hình của bài toán đã trình bày trong inục trước. - Để có được thuật toán nhánh cận giải bài toán người du lịch, trước hết cần đưa ra cách đánh giá cận dưới cho phương án bộ phận. - Sử dụng cách tính cận dưới vừa nêu ta có thể áp dụng thuật toán nhánh cận để giải bài toán người du lịch. - Giải bài toán người du lịch với m a trận chi phí sau c Cliươní’ 5. - Giải bài toán người du lịch Chương trình trên PA SCA L thực hiện thuật toán có thể viết như sau: 121 Phan 1. - M ột Irong những phương pháp xây dựng Irên tư tưởng của thuật toán nhánh cận cho phép giải bài toán người du lịch với kích ihước lớn hơn sẽ được trình bày trong m ục tiếp theo. - Thuật toán nhánh cận giải bài toán người du lịch Thuật toán nhánh cận là m ột trong những phương pháp giải chủ yếu của tối ưu tổ hợp. - M ục này sẽ trình bày m ột cách thể hiện khác những tư tưởng của thuật toán nhánh cận vào việc xây dựng thuật toán giải bài toán người du lịch. - X ét bài toán gia công n chi tiết trên 3 máy theo thứ tự A, B, c với bảng thời gian a-, bị, c. - Áp dụng thuật toán nhánh cận giải bài toán người du lịch với m a trận chi phí sau a) A B CD E A B 4 0 Q 1 1 27 C '1 ^ 11 C 12 35 D E b) A B C D E A B C D E c) A B C D E A B C D E n Thành phố xuất phát là A. - Giải các bài toán cái túi sau đây bằng thuật toán nhánh cận a) 17 X. - Q uá trình thực hiện thuật toán mô tả trên cây tìm kiếm lời giải. - M ô tả thuật toán quay lui để giải bài toán sau. - N hư là ví dụ ứng dụng, xét bài toán lập lịch sau đây. - Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thành phố K önigsberg. - Lý thuyết đồ thị T h í d ụ 3