Bài toán tối ưu hóa

Trong khoa học máy tính và toán học, bài toán tối ưu hóa là bài toán tìm kiếm "lời giải tốt nhất "trong tất cả các lời giải khả thi. Bài toán tối ưu hóa có thể được chia thành hai loại tùy thuộc vào việc các biến là liên tục hay rời rạc. Bài toán tối ưu hóa với các biến rời rạc còn được gọi là một bài toán tối ưu hóa tổ hợp. Trong một bài toán tối ưu hóa tổ hợp, chúng ta tìm kiếm một đối tượng như là một số nguyên, hoán vị hay đồ thị từ một tập hợp hữu hạn (hoặc có thể là vô hạn đếm được). Bài toán với các biến liên tục bao gồm bài toán hạn chế và bài toán đa phương thức.
Bài toán tối ưu hóa liên tục.
Dạng tiêu chuẩn của một bài toán tối ưu hóa (liên tục) là
trong đó
Theo quy ước, dạng tiêu chuẩn xác định một bài toán cực tiểu hóa. Bài toán cực đại hóa có thể được giải bằng cách phủ định hàm mục tiêu.
Bài toán tối ưu hóa tổ hợp.
Chính thức, là một bài toán tối ưu hóa tổ hợp formula_6 là một bộ tứ formula_7, trong đó
Mục tiêu là sau đó tìm ra một số trường hợp formula_3 một lời giải tối ưu, có nghĩa là, là một lời giải khả thi formula_12
Đối với mỗi bài toán tối ưu hóa tổ hợp, có một bài toán quyết định tương ứng yêu cầu cho dù đó có là một lời giải khả thi đối với một số biện pháp cụ thể formula_21. Ví dụ, nếu có một đồ thị formula_22 chứa các đỉnh formula_23 và formula_24, một bài toán tối ưu hóa có thể là "tìm một đường đi từ formula_23 tới formula_24 sử dụng các cạnh ít nhất". Bài toán này có thể có một câu trả lời, đó là, 4. Một bài toán quyết định tương ứng sẽ là "một đường đi từ formula_23 tới formula_24 mà sử dụng 10 cạnh hoặc ít hơn?" Bài toán này có thể có được câu trả lời đơn giản hoặc là 'có' hoặc là 'không'.
Trong lĩnh vực thuật toán xấp xỉ, các thuật toán được thiết kế để tìm các lời giải gần tối ưu cho các bài toán khó. Phiên bản quyết định bình thường sau đó là một định nghĩa không đầy đủ về bài toán này kể từ khi nó chỉ xác định các lời giải chấp nhận được. Mặc dù chúng ta có thể giới thiệu các bài toán quyết định phù hợp, bài toán này được mô tả đặc điểm tự nhiên hơn như là một bài toán tối ưu hóa.
Bài toán tối ưu hóa NP.
Bài toán tối ưu hóa NP (NPO-"NP optimization") là bài toán tối ưu hóa tổ hợp với các điều kiện bổ sung sau. Lưu ý rằng các đa thức dưới đây là các hàm kích thước của đầu vào của các hàm tương ứng, không phải là kích thước của một số tập hợp ẩn của các trường hợp đầu vào.
Điều này ngụ ý rằng bài toán quyết định tương ứng thì nằm trong NP. Trong khoa học máy tính, các bài toán tối ưu hóa thú vị thường có những đặc tính trên và cho nên đó là những bài toán NPO. Một bài toán ngoài ra còn được gọi là một bài toán tối ưu hóa-P (PO), nếu có tồn tại một thuật toán mà tìm các lời giải tối ưu trong thời gian đa thức. Thông thường, khi đối phó với lớp NPO, thứ được quan tâm trong các bài toán tối ưu hóa mà các phiên bản quyết định là NP-đầy đủ. Lưu ý rằng các quan hệ độ cứng luôn đối với một số phép suy giảm nào đó. Do sự kết hợp giữa các thuật toán xấp xỉ và các bài toán tối ưu hóa máy tính, các suy giảm duy trì xấp xỉ trong một số khía cạnh là dành cho đối tượng này được ưu tiên hơn so với mức giảm Turing và Karp thông thường. Một ví dụ về việc giảm như vậy sẽ giảm L. Vì lý do này,vấn đề tối ưu hóa với các phiên bản quyết định hoàn chỉnh NP không được gọi là hoàn chỉnh NPO.
NPO được chia thành các phân lớp sau tùy theo tính xấp xỉ được của chúng:
Một lớp quan tâm khác là NPOPB, NPO với các hàm chi phí đa thức bị chặn. Các bài toán với điều kiện này có nhiều tính chất mong muốn.
Xem thêm.
Mục tiêu là sau đó tìm ra một số trường hợp formula_3 một lời giải tối ưu, có nghĩa là, là một lời giải khả thi formula_12