Mở đầu Chương này trình nhắc lại một số kiến thức cơ sở trong lý thuyết tính toán và các khái niệm về bài toán, bài toán NP – đầy đủ, NP – khó, … Một số phương pháp giải các bài toán NP – khó cũng được giới thiệu sơ qua. Tiếp theo là phát biểu bài toán đóng thùng, mô hình toán học của bài toán và một số ứng dụng của bài toán. Chương 2: Một số phương pháp giải bài toán đóng thùng Trong chương này sẽ giới thiệu tổng quan chung về các kết quả nghiên cứu bài toán đóng thùng, đặc biệt là các thuật toán đã đề xuất và đánh giá hiệu quả của chúng. Một số thuật toán quan trọng sẽ được đề cập chi tiết hơn.
Chương 3: Thuật toán di truyền Chương 3 nhắc lại một chút về lịch sử thuật toán di truyền, mô tả sơ đồ hoạt động chung và một số nền tảng lý thuyết khác của thuật toán di truyền. Chương 4: Thuật toán di truyền giải bài toán đóng thùng Chương này sẽ trình bày cụ thể cách tiếp cận theo hướng thuật toán di truyền để giải bài toán đóng thùng, các mô tả chi tiết thiết kế của thuật toán, trình bày các kết quả thực nghiệm và đánh giá kết quả thực nghiệm thu được. Chương 4 là nội dung chính của luận văn. Kết luận và hướng phát triển Phần kết luận chung đánh giá tổng quan lại những kết quả đã thực hiện được trong luận văn, những hạn chế của luận văn và một số vấn đề mở cần tiếp tục giải quyết sau này.
Các khái niệm và thuật ngữ cơ sở Nội dung phần này được trình bày dựa vào các tài liệu tham khảo [1], [9]. Bài toán tính toán, thuật toán và độ phức tạp tính toán của thuật toán Các vấn đề kĩ thuật thường được khái quát dưới dạng bài toán tính toán để tiện cho việc nghiên cứu và xây dựng cách giải quyết. Bài toán tính toán là mối quan hệ giữa đầu vào (những yếu tố cho trước của bài toán) và đầu ra (những kết quả tính toán cần đạt được) của bài toán. Một cách hình thức, ta có thể định nghĩa bài toán tính toán như sau: Định nghĩa 1.
Bài toán tính toán F là ánh xạ từ các xâu nhị phân độ dài hữu hạn vào tập các xâu nhị phân độ dài hữu hạn: F: {0,1} * → {0,1}*. Ở đây, các yếu tố dữ liệu là đầu vào và đầu ra của bài toán được biểu diễn bằng xâu nhị phân. Mọi dạng dữ liệu (số, kí tự, xâu, mảng, tập hợp…) đều có thể mã hóa được bằng xâu nhị phân, hay nói cách khác ta có thể dùng xâu nhị phân để biểu diễn mọi dạng dữ liệu. Ví dụ: Một số nguyên z có biểu diễn dưới dạng xâu nhị phân chính là cách viết trong hệ đếm cơ số 2 của số nguyên đó.
Một kí tự có biểu diễn nhị phân là biểu diễn nhị phân của số nguyên là số thứ tự của kí tự đó trong một bảng mã nào đó (ASCII, Unicode …) Vector có biểu diễn là ghép nối biểu diễn nhị phân (mảng – array) của các thành phần tọa độ của các chiều. Xâu kí tự có biểu diễn là ghép nối biểu diễn của các kí tự thành phần Ma trận được biểu diễn bởi ghép nối các biểu diễn của các vector thành phần hoặc ma trận thành phần cấp thấp hơn nó một đơn vị. Một hệ phương trình tuyến tính dạng A.x = b có thể biểu diễn dưới dạng nhị phân là ghép nối của các xâu biểu diễn nhị phân của các thành phần trong ma trận A và vector b. Đa thức một biến dạng P(x) = a0 + a 1x + …+anxn được đặc trưng bởi dãy các hệ số a 0, a 1,…, a n và số mũ n.
Do đó dùng các xâu nhị phân biểu diễn dãy hệ số a i và xâu nhị phân biểu diễn n là tao có thể tạo thành một biểu diễn hợp lệ cho P(x). Đồ thị thì có biểu diễn bởi ma trận kề Các dữ liệu phức hợp thì được tổ chức dưới dạng tổ hợp cấu trúc của các dữ liệu cơ bản, ví dụ như mảng, bản ghi, cây … Các dữ liệu trong các bài toán tổng quát thì có thể là không hữu hạn (số vô cùng lớn chẳng hạn) nhưng khi đã chuyển sang dạng bài toán tính toán để phục vụ cho việc ứng dụng thực tế thì yếu tố vô hạn cần phải được thay thế bằng yếu tố hữu hạn, vì vậy các xâu nhị phân là hữu hạn. Bài toán chỉ ra mối quan hệ giữa đầu vào và đầu ra, nhưng làm thế nào để đạt được đầu ra từ đầu vào cho trước thì ta cần thuật toán (algorithm – thuật toán). Thuật toán giải bài toán đặt ra là một thủ tục xác định bao gồm một dãy hữu hạn các bước cần thực hiện để thu được đầu ra cho một đầu vào cho trước của bài toán.
Thuật toán có những đặc trưng là: Có đầu vào (Input): là tập các dữ liệu cần cung cấp thuật toán từ lúc đầu để xử lý. Có đầu ra (Output): với mỗi một bộ dữ liệu vào, thuật toán sẽ cho ra một bộ các dữ liệu ra tương ứng với lời giải của bài toán cho bộ dữ liệu vào. Chính xác (Precision): Các bước của thuật toán cần phải được mô tả chính xác và rõ ràng để có thể khi cài đặt trên máy tính có thể thực hiện được. Hữu hạn (Finiteness): với mọi đầu vào thì thuật toán vẫn cần phải đưa được đầu ra sau một số hữu hạn (có thể rất lớn) bước thực hiện.
Đơn trị (Uniqueness): đơn trị có nghĩa là các kết quả trung gian trong quá trình thực hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc vào đầu vào cũng như kết quả ở những bước trước. Tổng quát (Generality): Tức là thuật toán có thể áp dụng để giải mọi bài toán có dạng đã cho. Với mọi thuật toán, bên cạnh tính đúng đắn người ta còn quan tâm đến một yếu tố khác là độ phức tạp tính toán của thuật toán đó. Độ phức tạp tính toán của một thuật toán là lượng tài nguyên tính toán mà thuật toán đó sử dụng để thực hiện công việc.
Có 2 loại tài nguyên cần quan tâm khi đánh giá độ phức tạp tính toán của thuật toán là bộ nhớ và thời gian. Ngày nay, do sự phát triển mạnh của công nghệ chế tạo bộ nhớ và thiết bị lưu trữ, người ta ít phải quan tâm đến vấn đề tài nguyên không gian nhớ thuật toán sử dụng hơn so với trước kia và tập trung quan tâm thiết kế để tiết kiệm thời gian tính toán cần thiết thuật toán đòi hỏi để thực hiện công việc, và ta vẫn thường gọi là thời gian tính. Thời gian tính cụ thể trên máy tính của 1 thuật toán phụ thuộc vào nhiều yếu tố: cấu hình máy, ngôn ngữ cài đặt và cách thức cài đặt thuật toán của lập trình viên, trình biên dịch và dữ liệu vào, trong đó dữ liệu vào là yếu tố quan trọng và đặc trưng nhất. Và để tạo ra sự thống nhất trong cách đánh giá thời gian tính của một thuật toán, ta sẽ không xét đến các yếu tố như cấu hình máy, kỹ thuật lập trình, chương trình dịch … mà chỉ xét đến yếu tố kích thước dữ liệu vào khi đánh giá thời gian tính của thuật toán.
Kích thước dữ liệu vào (hay độ dài dữ liệu vào) được định nghĩa là số bit cần thiết để biểu diễn dữ liệu vào đó (ta đã biết rằng các dữ liệu đều có thể được biểu diễn bằng xâu nhị phân). Nhưng từ đó thì làm thế nào để đo được thời gian tính? Để đo thời gian tính của một thuật toán, người ta tiến hành đếm số phép toán cơ bản mà nó phải thực hiện. Phép toán cơ bản được định nghĩa là những phép toán có thể được thực hiện với thời gian bị chặn bởi một hằng số không phụ thuộc vào kích thước dữ liệu. Các phép tính toán học thông thường không là các phép tính cơ bản, ví dụ nhân hay cộng hai số nguyên thì thời gian tính toán kết quả rõ ràng phụ thuộc vào độ lớn (cũng như độ dài biểu diễn) của 2 số nguyên đó.
Nhưng với những phép toán thực hiện trên một ngôn ngữ lập trình nào đó thì do kích thước của các kiểu dữ liệu do ngôn ngữ đó cung cấp là bị chặn cho nên thời gian thực hiện các thao tác với các dữ liệu này là bị chặn. Các phép toán số học, logic. trên một ngôn ngữ lập trình cụ thể là các phép toán cơ bản. Đánh giá thời gian tính của thuật toán theo kích thước dữ liệu vào thường được thể hiện dưới dạng các hàm số quan hệ giữa chúng.
Mục tiếp theo sẽ trình bày về các ký hiệu tiệm cận (asymptotic notation) dùng để biểu diễn những mối quan hệ hàm này. Các kí hiệu tiệm cận Các kí hiệu tiệm cận thường hay sử dụng khi đánh giá độ phức tạp tính toán của thuật toán gồm có: Θ, Ο, Ω và ο, ω. Các kí hiệu này được định nghĩa sử dụng như sau: Định nghĩa 1. Cho các hàm f(n) và g(n) là các hàm số của n nguyên dương.
Kí hiệu Θ(g(n)) biểu diễn tập các hàm Θ(g(n)) = {f(n) : tồn tại các hằng số dương c 1, c2 và n0 sao cho 0 ≤ c1g(n) ≤ f(n) ≤ c2 g(n), với mọi n ≥ n0.} Ta nói g(n) là đánh giá tiệm cận đúng của f(n) hay f(n) có bậc là g(n) Kí hiệu Ο(g(n)) biểu diễn tập các hàm Ο(g(n)) = {f(n) : tồn tại các hằng số dương c và n 0 sao cho f(n) ≤ cg(n), với mọi n ≥ n0.} Ta nói g(n) là cận trên tiệm cận của f(n) hay f(n) có bậc không quá g(n) Kí hiệu Ω(g(n)) biểu diễn tập các hàm Ω(g(n)) = {f(n) : tồn tại các hằng số dương c và n 0 sao cho cg(n) ≤ f(n), với mọi n ≥ n0. Kí hiệu ο(g(n)) biểu diễn tập các hàm ο(g(n)) = {f(n) : với mọi hằng số c > 0, ta luôn tìm được một hằng số n0 sao cho 0 ≤ f(n) < cg(n), với mọi n ≥ n0.} Ta nói f(n) có bậc thấp hơn g(n) Kí hiệu ω(g(n)) biểu diễn tập các hàm ω(g(n)) = {f(n) : với mọi hằng số c > 0, ta luôn tìm được một hằng số n0 sao cho f(n) > cg(n) ≥ 0, với mọi n ≥ n0.1 minh hoạ cho các kí hiệu O, Ω, Θ. 1 Giải thích các kí hiệu tiệm cận O, Ω, Θ. Ta cũng thấy rằng f(n) = Θ(g(n)) khi và chỉ khi đồng thời f(n) = Ω(g(n)) và f(n) = Ο(g(n)).