chương 1, luận văn trình bày những khái niệm cơ bản về bài toán - thuật toán trong tin học, khái niệm về độ phức tạp của thuật toán và các nguyên tắc đánh giá độ phức tạp. Trên cơ sở đó đưa ra nguyên tắc phân lớp các bài toán để tiến hành lựa chọn giải thuật tốt nhất giải các lớp bài toán trong thực tế. Đưa ra mô hình bài toán Knaspack là một mô hình điển hình của lớp các bài toán NP. Các kiến thức này làm cơ sở để phân tích và thiết kế các thuật toán được trình bày trong các chương tiếp sau.
c 13 CHƯƠNG 2 MỘT SỐ THUẬT TOÁN XẤP XỈ Nội dung chính của chương 2 sẽ nghiên cứu một số thuật toán xấp xỉ đã được nghiên cứu trong các kĩ thuật thiết kế thuật toán như: Thuật toán tham lam, thuật toán quy hoạch động, thuật toán di truyền GA, cùng các bài toán mẫu mực trong thực tế. Các thuật toán đã được tham khảo trong các tài liệu [3, 4, 5, 6, 7, 8]. Việc mô phỏng các thuật toán được thực hiện trên nền ngôn ngữ lập trình C++ hoặc Matlab.1 Khái niệm về thuật toán xấp xỉ Nhiều bài toán có ý nghĩa rất quan trọng trong thực tiễn lại là NP đầy đủ. Nếu là một bài toán NP đầy đủ, ta không thể tìm một thuật toán thời gian đa thức để giải nó chính xác.
Có hai cách tiếp cận để khắc phục tính đầy đủ NP. Thứ nhất: nếu các đầu vào thực tế là nhỏ, một thuật toán có thời gian thực hiện hàm mũ có thể hoàn toàn chấp nhận được Thứ hai: vẫn có thể tìm các giải pháp gần tối ưu trong thời gian đa thức (hoặc trong trường hợp xấu nhất hoặc tính trung bình). Trong thực tế để tính gần tối ưu thường là đủ. Một thuật toán trả về các giải pháp gần tối ưu được gọi là một thuật toán xấp xỉ.
Xét một bài toán tối ưu hóa, ở đó mỗi giải pháp có thể đưa ra có một mức hao phí dương, và ta muốn tìm giải pháp gần tối ưu. Tùy thuộc vào bài toán, một giải pháp gần tối ưu có thể được định nghĩa là một giải pháp có mức hao phí khả dĩ cực đại hoặc một giải pháp có mức hao phí khả dĩ cực tiểu, bài toán có thể là bài toán cực đại hóa hoặc cực tiểu hóa. Một số thuật toán xấp xỉ cho bài toán có một cận tỷ số P(n) nếu với bất kỳ đầu vào có kích cỡ n , mức hao phí C của giải pháp mà thuật toán xấp xỉ tạo sẽ nằm trong một thừa số p(n) của mức hao phí C* của một giải pháp tối ưu: Max C C* * , ≤ p(n) C C c 14 Định nghĩa này áp dụng cả bài toán cực đại hóa lẫn cực tiểu hóa. Với một bài C* toán cực đại hóa, 0 < C ≤ C*, và tỷ số cho ra thừa số qua đó với mức hao phí C của một giải pháp tối ưu lớn hơn mức hao phí của một giải pháp xấp xỉ.
Cũng vậy, C với một bài toán cực tiểu hóa, 0 < C * ≤C, và tỷ số cho ra thừa số qua đó mức C* hao phí của một giải pháp xấp xỉ lớn hơn mức hao phí của một giải pháp tối ưu. Bởi tất cả các giải pháp được mặc nhận có mức hao phí dương, các tỷ số này luôn được định nghĩa rõ ràng. Cận tỷ số của một thuật toán xấp xỉ không bao giờ nhỏ hơn 1, C bởi 1. Một thuật toán xấp xỉ có một cận lỗi tương đối ε(n) nếu C* C C* n C* Một lược đồ xấp xỉ cho một bài toán tối ưu hóa là một thuật toán xấp xỉ chấp nhận không những một bộ dữ liệu vào của bài toán, mà còn một giá trị ε>0 làm đầu vào sao cho với bất kỳ ε, cố định, lược đồ là một thuật toán xấp xỉ có cận lỗi tương đối ε.
Ta nói rằng một lược đồ xấp xỉ có thời gian đa thức nếu với bất kỳ ε > 0 cố định, lược đồ chạy trong thời gian đa thức trong kích cỡ n của bộ dữ liệu đầu vào của nó. Thời gian thực hiện của một lược đồ xấp xỉ thời gian đa thức không tăng quá nhanh khi ε giảm. Về lý tưởng nếu ε giảm theo một thừa số bất biến, thời gian thực hiện để đạt được mức xấp xỉ mong muốn không được gia tăng nhiều hơn một thừa số bất biến. Nói cách khác, ta muốn thời gian thực hiện là đa thức trong 1/ε cũng như trong n.
Ta nói rằng một lược đồ xấp xỉ là một lược đồ xấp xỉ thời gian đa thức đầy đủ nếu thời gian thực hiện của nó là đa thức trong cả 1/ε lẫn trong kích cỡ n của bộ dữ liệu vào đầu vào, ở đó ε là cận lỗi tương đối cho lược đồ. Ví dụ, lược đồ có thể có một thời gian thực hiện (1/ε)2n3. Với một lược đồ như vậy, mọi mức giảm thừa số bất biến trong ε đều có thể đạt được với một mức tăng thừa số bất biến tương ứng trong thời gian thực hiện. c 15 Sau đây chúng ta sẽ nghiên cứu một số phương pháp thiết kế các thuật toán xấp xỉ điển hình trong việc giải quyết các bài toán thuộc lớp NP.2 Phương pháp quy hoạch động Phương pháp quy hoạch động cùng nguyên lí tối ưu được nhà toán học Mỹ Richard Bellman (1920 - 1984) đã đề xuất vào những năm 50 của thế kỷ XX.
Phương pháp này đã được áp dụng để giải nhiều bài toán thực tế đặc biệt là những bài toán tối ưu, ví dụ như: việc xác định các phương án tối ưu trong mô hình kỹ thuật công nghệ, tổ chức sản xuất, kế hoạch hóa kinh tế. Quy hoạch động là kỹ thuật thiết kế bottom-up (từ dưới lên). Nó được bắt đầu với những trường hợp con nhỏ nhất (thường là đơn giản nhất và giải được ngay). Bằng cách tổ hợp các kết quả đã có (không phải tính lại) của các trường hợp con, sẽ đạt tới kết quả của trường hợp có kích thước lớn dần lên và tổng quát hơn, cho đến khi cuối cùng đạt tới lời giải của trường hợp tổng quát nhất.
Để thấy rõ về phương pháp này ta đi tìm hiểu chi tiết ở các nội dung tiếp theo.1 Một số khái niệm Quy hoạch động (Dynamic Programming) là phương pháp giải một bài toán bằng cách tổ hợp lời giải các bài toán con của nó. Phương pháp này dùng để giải bài toán tối ưu có bản chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con. Nếu tìm đúng hệ thức thể hiện bản chất quy hoạch động của bài toán và khéo tổ chức dữ liệu thì ta có thể xử lý được những tập dữ liệu khá lớn. Khi đó, ta có một số khái niệm liên quan như sau: + Bài toán giải theo phương pháp quy hoạch động gọi là bài toán quy hoạch động.
+ Công thức phối hợp nghiệm của các bài toán con để có nghiệm của bài toán lớn gọi là công thức truy hồi của quy hoạch động. + Tập các bài toán nhỏ nhất có ngay lời giải để từ đó giải quyết các bài toán lớn hơn gọi là cơ sở quy hoạch động. c 16 + Không gian lưu trữ lời giải các bài toán con để tìm cách phối hợp chúng gọi là bảng phương án của quy hoạch động. Tư tưởng Phương pháp quy hoạch động dựa trên một nguyên lý quan trọng, đó là Nguyên lý tối ưu của Bellman.
Nguyên lý được phát biểu như sau: “Quy hoạch động là lớp các bài toán mà quyết định ở bước thứ i phụ thuộc vào quyết định ở các bước đã xử lý trước hoặc sau đó”. Quy hoạch động bắt đầu từ việc giải các bài toán nhỏ nhất (bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn cho tới khi giải được bài toán lớn nhất (bài toán ban đầu). Tư tưởng cơ bản của quy hoạch động là : tránh tính toán lại mọi thứ hai lần mà lưu giữ kết quả đã tìm kiếm được vào một bảng làm giả thiết cho việc tìm kiếm những kết quả của trường hợp sau. Chúng ta sẽ làm đầy dần giá trị của bảng này bởi các kết quả của những trường hợp trước đã được giải.
Kết quả cuối cùng chính là kết quả của bài toán cần giải. Nói cách khác phương pháp quy hoạch động đã thể hiện sức mạnh của nguyên lý chia để trị đến cao độ. Tư tưởng của thuật toán quy hoạch động khá đơn giản. Tuy nhiên khi áp dụng thuật toán vào trường hợp cụ thể lại không dễ dàng (điều này cũng tương tự như nguyên tắc Dirichlet trong toán học).2 Các bước thực hiện Bước 1: Lập hệ thức Dựa vào nguyên lý tối ưu tìm cách chia quá trình giải bài toán thành từng giai đoạn, sau đó tìm hệ thức biểu diễn tương quan quyết định của bước đang xử lý với các bước đã xử lý trước đó.
Hoặc tìm cách phân rã bài toán thành các “bài toán con” tương tự có kích thước nhỏ hơn, tìm hệ thức quan hệ giữa kết quả bài toán kích thước đã cho với các kết quả của các bài toán con cùng kiểu có kích thước nhỏ hơn của nó dạng hàm hoặc thủ tục đệ quy. Khi đã có hệ thức tương quan chúng ta có thể xây dựng ngay thuật giải, tuy nhiên hệ thức này thường là các biểu thức đệ quy, do đó dễ gây ra hiện tượng tràn miền nhớ khi ta tổ chức chương trình trực tiếp bằng đệ quy. Bước 2: Tổ chức dữ liệu và chương trình c 17 Tổ chức dữ liệu sao cho đạt các yêu cầu sau: a) Dữ liệu được tính toán dần theo các bước. b) Dữ liệu được lưu trữ để giảm lượng tính toán lặp lại.
c) Kích thước miền nhớ dành cho lưu trữ dữ liệu càng nhỏ càng tốt, kiểu dữ liệu được chọn phù hợp, nên chọn đơn giản dễ truy cập. Bước 3: Làm tốt Làm tốt thuật toán bằng cách thu gọn hệ thức và giảm kích thước miền nhớ. Thường tìm cách dùng mảng một chiều thay cho mảng hai chiều nếu giá trị một dòng (hoặc cột) của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cột) kề trước. Trong một số trường hợp có thể thay mảng hai chiều với các giá trị phần tử chỉ nhận giá trị 0,1 bởi mảng hai chiều mới bằng cách dùng kỹ thuật quản lý bit.
Quy hoạch động là một phương pháp phân tích và thiết kế thuật toán cho phép giảm bớt thời gian thực hiện khi khai thác tốt các đặc điểm của bài toán.