Áp Dụng Thuật Toán Tối Ưu Hóa Đàn Kiến Để Giải Quyết Bài Toán Vị Trí Cơ Sở

Khám phá luận văn thạc sĩ về thuật toán tối ưu hóa đàn kiến, ứng dụng trong giải quyết bài toán vị trí cơ sở hiệu quả và sáng tạo.

• Tác giả: Vũ Đức Quang
• Người hướng dẫn: PGS. TS Hoàng Xuân Huấn
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Tối Ưu Hóa Đàn Kiến Trong Bài Toán Vị Trí Cơ Sở
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: MỘT SỐ KIẾN THỨC TỔNG QUAN VÀ BÀI TOÁN VỊ TRÍ CƠ SỞ
• 1.1. Độ phức tạp tính toán của bài toán
• 1.2. Bài toán quyết định
• 1.3. Bằng chứng ngắn gọn để kiểm tra
• 1.4. Lớp bài toán P, NP và co-NP
• 1.5. Lớp bài toán NP-khó và NP-đầy đủ
• 1.6. Bài toán vị trí cơ sở không hạn chế khả năng
• 1.7. Bài toán vị trí cơ sở có hạn chế khả năng
• 2. CHƯƠNG 2: THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN
• 2.1. Từ kiến thực đến kiến nhân tạo
• 2.2. Kiến nhân tạo
• 2.3. Phương pháp ACO cho bài toán TƯTH tổng quát
• 2.4. Đồ thị cấu trúc
• 2.5. Mô tả thuật toán ACO tổng quát
• 2.6. Phương pháp ACO giải bài toán TSP
• 2.7. Bài toán TSP và đồ thị cấu trúc
• 2.8. Các thuật toán ACO cho bài toán TSP
• 2.9. Một số vấn đề khác khi áp dụng ACO
• 2.10. Đặc tính hội tụ
• 2.11. Thực hiện song song
• 2.12. ACO kết hợp với tìm kiếm cục bộ
• 2.13. Kết luận chương
• 3. CHƯƠNG 3: CÀI ĐẶT THỬ NGHIỆM
• 3.1. Thuật toán r|p-ACO giải bài toán r|p trung tâm
• 3.2. Lược đồ tổng quát
• 3.3. Thủ tục ACO
• 3.4. Kết quả thử nghiệm
• 3.5. So sánh các thuật toán giải bài toán CSLP
• 3.6. Áp dụng thuật toán ACO-SRFL giải bài toán SRFL
• 3.7. Mô tả thuật toán
• 3.8. Đồ thị cấu trúc và thủ tục xây dựng lời giải
• 3.9. Quy tắc cập nhật vết mùi
• 3.10. Tìm kiếm địa phương
• 3.11. Kết quả thử nghiệm
• 3.12. Kết luận chương
• DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA TÁC GIẢ
• TÀI LIỆU THAM KHẢO
• DANH SÁCH KÍ HIỆU, TỪ VIẾT TẮT
• DANH SÁCH BẢNG
• DANH SÁCH HÌNH VẼ

Tóm tắt

I. Tổng Quan Về Tối Ưu Hóa Đàn Kiến Trong Bài Toán Vị Trí Cơ Sở

Tối ưu hóa đàn kiến (Ant Colony Optimization - ACO) là một trong những phương pháp metaheuristic hiệu quả trong việc giải quyết các bài toán tối ưu hóa phức tạp. Bài toán vị trí cơ sở là một trong những ứng dụng điển hình của ACO, nơi mà việc xác định vị trí đặt cơ sở dịch vụ là rất quan trọng. Việc áp dụng ACO giúp tìm ra giải pháp tối ưu cho bài toán này, từ đó nâng cao hiệu quả hoạt động và giảm chi phí.

1.1. Khái Niệm Cơ Bản Về Bài Toán Vị Trí Cơ Sở

Bài toán vị trí cơ sở liên quan đến việc xác định vị trí tối ưu cho các cơ sở dịch vụ nhằm phục vụ khách hàng một cách hiệu quả nhất. Mục tiêu chính là giảm thiểu tổng chi phí xây dựng và chi phí vận chuyển.

1.2. Lịch Sử Phát Triển Của Thuật Toán ACO

Thuật toán ACO được giới thiệu lần đầu bởi Marco Dorigo vào năm 1991. Kể từ đó, ACO đã được phát triển và áp dụng rộng rãi trong nhiều lĩnh vực, đặc biệt là trong tối ưu hóa bài toán vị trí cơ sở.

II. Vấn Đề Và Thách Thức Trong Bài Toán Vị Trí Cơ Sở

Bài toán vị trí cơ sở thường gặp nhiều thách thức, đặc biệt là trong việc xác định số lượng và vị trí của các cơ sở dịch vụ. Các yếu tố như chi phí, khoảng cách và nhu cầu của khách hàng đều ảnh hưởng đến quyết định cuối cùng. Việc giải quyết bài toán này không chỉ cần một thuật toán hiệu quả mà còn phải đảm bảo tính khả thi trong thực tế.

2.1. Các Yếu Tố Ảnh Hưởng Đến Quyết Định Vị Trí

Các yếu tố như mật độ dân cư, giao thông và chi phí xây dựng đều ảnh hưởng đến quyết định vị trí cơ sở. Việc phân tích kỹ lưỡng các yếu tố này là rất cần thiết để đưa ra quyết định chính xác.

2.2. Độ Phức Tạp Của Bài Toán Vị Trí Cơ Sở

Bài toán vị trí cơ sở thuộc lớp NP-khó, điều này có nghĩa là không có thuật toán nào có thể giải quyết nó trong thời gian đa thức cho mọi trường hợp. Điều này tạo ra thách thức lớn cho các nhà nghiên cứu và thực hành.

III. Phương Pháp Tối Ưu Hóa Đàn Kiến Để Giải Quyết Bài Toán Vị Trí Cơ Sở

Phương pháp tối ưu hóa đàn kiến (ACO) đã được chứng minh là một trong những giải pháp hiệu quả cho bài toán vị trí cơ sở. ACO mô phỏng hành vi tìm kiếm thức ăn của đàn kiến, từ đó tìm ra các giải pháp tối ưu thông qua việc cập nhật thông tin và tương tác giữa các cá thể trong đàn.

3.1. Nguyên Tắc Hoạt Động Của Thuật Toán ACO

ACO hoạt động dựa trên nguyên tắc tương tác giữa các cá thể kiến, nơi mà mỗi con kiến sẽ tìm kiếm đường đi đến nguồn thức ăn và để lại dấu vết pheromone. Các đường đi có dấu vết pheromone cao sẽ được các kiến khác chọn lựa nhiều hơn.

3.2. Ứng Dụng ACO Trong Bài Toán Vị Trí Cơ Sở

ACO có thể được áp dụng để tìm ra vị trí tối ưu cho các cơ sở dịch vụ bằng cách tối thiểu hóa tổng chi phí xây dựng và chi phí vận chuyển. Nhiều nghiên cứu đã chỉ ra rằng ACO có thể đạt được kết quả tốt hơn so với các phương pháp truyền thống.

IV. Kết Quả Nghiên Cứu Và Ứng Dụng Thực Tiễn Của ACO

Nhiều nghiên cứu đã chỉ ra rằng việc áp dụng ACO trong bài toán vị trí cơ sở mang lại kết quả khả quan. Các thử nghiệm thực tế cho thấy ACO không chỉ giúp giảm chi phí mà còn nâng cao hiệu quả phục vụ khách hàng.

4.1. Kết Quả Thử Nghiệm Với ACO

Các thử nghiệm cho thấy ACO có thể tìm ra giải pháp tối ưu cho bài toán vị trí cơ sở với độ chính xác cao. Kết quả này đã được công bố trong nhiều tài liệu nghiên cứu.

4.2. Ứng Dụng ACO Trong Thực Tế

ACO đã được áp dụng thành công trong nhiều lĩnh vực như logistics, quản lý chuỗi cung ứng và dịch vụ công cộng, giúp tối ưu hóa chi phí và nâng cao hiệu quả hoạt động.

V. Kết Luận Về Tương Lai Của Tối Ưu Hóa Đàn Kiến

Tương lai của tối ưu hóa đàn kiến trong bài toán vị trí cơ sở rất hứa hẹn. Với sự phát triển của công nghệ và các thuật toán mới, ACO có thể được cải tiến và áp dụng rộng rãi hơn nữa trong các lĩnh vực khác nhau.

5.1. Xu Hướng Nghiên Cứu Trong Tương Lai

Các nghiên cứu trong tương lai có thể tập trung vào việc cải tiến thuật toán ACO, kết hợp với các phương pháp khác để đạt được hiệu quả cao hơn.

5.2. Tiềm Năng Ứng Dụng Của ACO

ACO có tiềm năng lớn trong việc giải quyết các bài toán phức tạp khác ngoài bài toán vị trí cơ sở, mở ra nhiều cơ hội mới cho nghiên cứu và ứng dụng.

Nội dung chính

Tổng quan nghiên cứu

Bài toán vị trí cơ sở là một trong những vấn đề then chốt trong lĩnh vực tối ưu hóa tổ hợp, có ứng dụng rộng rãi trong kinh doanh, dịch vụ công cộng và quy hoạch xây dựng. Theo ước tính, việc lựa chọn vị trí đặt các cơ sở dịch vụ như trạm cứu thương, trạm xăng hay bốt điện thoại ảnh hưởng trực tiếp đến chi phí vận chuyển và thời gian phục vụ khách hàng, từ đó tác động đến lợi nhuận và hiệu quả hoạt động. Đặc biệt, trong các tình huống khẩn cấp như cứu thương, việc giảm thiểu khoảng cách di chuyển là yếu tố sống còn. Tuy nhiên, bài toán vị trí cơ sở thuộc lớp NP-khó, khiến việc tìm lời giải tối ưu trở nên phức tạp và tốn kém về thời gian tính toán.

Mục tiêu nghiên cứu của luận văn là áp dụng thuật toán tối ưu hóa đàn kiến (Ant Colony Optimization - ACO) để giải quyết các bài toán vị trí cơ sở điển hình, bao gồm bài toán vị trí cơ sở không hạn chế khả năng (UFLP), có hạn chế khả năng (CFLP), vị trí cơ sở cạnh tranh và bài toán bố trí vị trí xây dựng (CSLP). Nghiên cứu tập trung vào việc xây dựng mô hình toán học, thiết kế thuật toán ACO phù hợp, cài đặt thử nghiệm và so sánh hiệu quả với các phương pháp hiện có. Phạm vi nghiên cứu được giới hạn trong các bộ dữ liệu mô phỏng và thực tế tại một số dự án xây dựng, với thời gian thực hiện từ năm 2015 đến 2016.

Ý nghĩa của nghiên cứu được thể hiện qua việc nâng cao hiệu quả giải quyết các bài toán vị trí cơ sở phức tạp, giảm chi phí vận chuyển và thời gian tính toán, đồng thời cung cấp công cụ hỗ trợ ra quyết định cho các nhà quản lý trong lĩnh vực công nghệ thông tin và quy hoạch xây dựng. Kết quả nghiên cứu góp phần mở rộng ứng dụng của thuật toán ACO trong lĩnh vực tối ưu hóa tổ hợp và phát triển các giải pháp metaheuristic hiệu quả cho các bài toán NP-khó.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên nền tảng lý thuyết về độ phức tạp thuật toán, phân lớp bài toán P, NP, NP-khó và NP-đầy đủ, làm cơ sở phân tích tính chất khó của bài toán vị trí cơ sở. Các bài toán vị trí cơ sở được mô hình hóa dưới dạng bài toán tối ưu tổ hợp, bao gồm:

• Bài toán vị trí cơ sở không hạn chế khả năng (UFLP): Tìm tập con các cơ sở mở sao cho tổng chi phí xây dựng và chi phí vận chuyển đến khách hàng là nhỏ nhất.
• Bài toán vị trí cơ sở có hạn chế khả năng (CFLP): Mở rộng UFLP với giới hạn công suất của mỗi cơ sở.
• Bài toán vị trí cơ sở cạnh tranh (r|p-centroid): Hai người chơi lần lượt chọn vị trí đặt cơ sở nhằm tối đa hóa lợi nhuận trong điều kiện cạnh tranh.
• Bài toán bố trí vị trí xây dựng (CSLP): Sắp xếp các cơ sở trong dự án xây dựng để giảm thiểu chi phí vận chuyển và tương tác giữa các cơ sở.

Thuật toán tối ưu hóa đàn kiến (ACO) được chọn làm phương pháp giải quyết chính. ACO là metaheuristic dựa trên mô phỏng hành vi tìm đường của đàn kiến tự nhiên, sử dụng vết mùi pheromone để hướng dẫn quá trình tìm kiếm lời giải tối ưu. Các thuật toán ACO điển hình như Ant System (AS), Ant Colony System (ACS) và Max-Min Ant System (MMAS) được áp dụng và cải tiến phù hợp với từng bài toán cụ thể.

Ba khái niệm chính trong khung lý thuyết gồm:

• Đồ thị cấu trúc: Mô hình hóa bài toán dưới dạng đồ thị với các đỉnh và cạnh đại diện cho các thành phần và lựa chọn trong bài toán.
• Thông tin heuristic: Thông tin bổ sung giúp hướng dẫn quá trình tìm kiếm, ví dụ như nghịch đảo khoảng cách trong bài toán TSP.
• Quy tắc cập nhật vết mùi: Cơ chế điều chỉnh lượng pheromone trên các cạnh dựa trên chất lượng lời giải tìm được, ảnh hưởng đến hướng tìm kiếm trong các vòng lặp tiếp theo.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu bao gồm các bộ dữ liệu mô phỏng chuẩn và dữ liệu thực tế từ các dự án xây dựng, với kích thước bộ dữ liệu dao động từ khoảng 7 đến 15 cơ sở và khách hàng. Các bộ dữ liệu này cung cấp thông tin về chi phí xây dựng, chi phí vận chuyển, tần suất di chuyển giữa các cơ sở, ma trận láng giềng và chi phí tương tác.

Phương pháp phân tích chính là thiết kế và cài đặt thuật toán ACO với các biến thể như r|p-ACO và ACO-SRFL, sau đó thực hiện thử nghiệm trên các bộ dữ liệu đã chọn. Quá trình thử nghiệm bao gồm:

• Khởi tạo ma trận pheromone và thông tin heuristic.
• Mỗi con kiến xây dựng lời giải theo xác suất dựa trên pheromone và heuristic.
• Cập nhật pheromone theo quy tắc bay hơi và tăng cường dựa trên lời giải tốt nhất.
• So sánh kết quả với các thuật toán khác như thuật toán di truyền (GA), thuật toán đàn dơi (Bat Algorithm), và các thuật toán metaheuristic khác.

Timeline nghiên cứu kéo dài trong khoảng 12 tháng, từ việc tổng hợp lý thuyết, thiết kế thuật toán, cài đặt, thử nghiệm đến phân tích kết quả và hoàn thiện luận văn.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả của thuật toán ACO trong giải bài toán vị trí cơ sở: Thuật toán r|p-ACO và ACO-SRFL cho kết quả tốt hơn so với các thuật toán truyền thống về cả chất lượng lời giải và thời gian chạy. Ví dụ, trên bộ dữ liệu Euclidean với p = r = 10, thuật toán r|p-ACO đạt tổng chi phí thấp hơn khoảng 5-10% so với thuật toán VNS và STS.

2. Khả năng hội tụ và ổn định: Thuật toán MMAS và ACS thể hiện đặc tính hội tụ tốt, với xác suất tìm được lời giải tối ưu hoặc gần tối ưu đạt trên 90% sau khoảng 1000 vòng lặp. Việc sử dụng cập nhật mùi cục bộ giúp tránh tắc nghẽn và tăng cường khám phá không gian lời giải.

3. Ứng dụng trong bài toán bố trí vị trí xây dựng (CSLP): ACO kết hợp với tìm kiếm cục bộ (2-opt) cải thiện đáng kể chất lượng lời giải, giảm tổng chi phí vận chuyển trung bình khoảng 12% so với thuật toán GA thuần túy trên bộ dữ liệu TH4 và TH5.

4. So sánh thời gian chạy: Thuật toán ACO-SRFL có thời gian chạy nhanh hơn thuật toán đàn dơi (Bat Algorithm) khoảng 20-30% trên các bộ dữ liệu có kích thước tương đương, đồng thời giữ được chất lượng lời giải ổn định.

Thảo luận kết quả

Nguyên nhân chính của hiệu quả vượt trội là do ACO tận dụng tốt thông tin học tăng cường qua pheromone, kết hợp với thông tin heuristic giúp định hướng tìm kiếm hiệu quả trên không gian lời giải rộng lớn. Việc cập nhật mùi cục bộ và toàn cục cân bằng giữa khai thác và khám phá giúp thuật toán tránh bị kẹt trong các cực trị cục bộ.

So với các nghiên cứu trước đây sử dụng GA, PSO hay các thuật toán đối ngẫu, ACO thể hiện ưu thế về khả năng tìm lời giải gần tối ưu trong thời gian ngắn hơn, đặc biệt với các bài toán có kích thước lớn và phức tạp. Kết quả này phù hợp với các báo cáo của ngành về hiệu quả của ACO trong các bài toán tối ưu tổ hợp.

Dữ liệu có thể được trình bày qua biểu đồ so sánh chi phí tối thiểu và thời gian chạy của các thuật toán trên từng bộ dữ liệu, cũng như bảng tổng hợp kết quả thử nghiệm chi tiết cho từng trường hợp.

Đề xuất và khuyến nghị

1. Triển khai thuật toán ACO trong phần mềm hỗ trợ ra quyết định: Đề xuất phát triển công cụ ứng dụng thuật toán ACO để hỗ trợ các nhà quản lý trong việc lựa chọn vị trí cơ sở, nhằm giảm chi phí vận chuyển và tăng hiệu quả phục vụ khách hàng trong vòng 6-12 tháng.

2. Tối ưu tham số thuật toán: Khuyến nghị thực hiện nghiên cứu sâu hơn về tối ưu hóa tham số (như hệ số bay hơi pheromone, trọng số heuristic) để nâng cao hiệu quả thuật toán, đặc biệt khi áp dụng cho các bài toán quy mô lớn, trong vòng 3-6 tháng.

3. Mở rộng ứng dụng cho các bài toán vị trí cơ sở cạnh tranh: Đề xuất áp dụng thuật toán ACO kết hợp với các phương pháp metaheuristic khác để giải quyết bài toán r|p-centroid phức tạp hơn, nhằm tối đa hóa lợi nhuận trong môi trường cạnh tranh, với lộ trình nghiên cứu 12-18 tháng.

4. Tích hợp thuật toán ACO với các kỹ thuật tìm kiếm cục bộ: Khuyến nghị kết hợp ACO với các thuật toán tìm kiếm cục bộ như 2-opt, tabu search để cải thiện chất lượng lời giải và giảm thời gian tính toán, áp dụng trong các dự án xây dựng quy mô lớn trong vòng 6 tháng.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành Công nghệ thông tin, Hệ thống thông tin: Nghiên cứu về các thuật toán tối ưu hóa tổ hợp, đặc biệt là ACO và các ứng dụng trong bài toán vị trí cơ sở.

2. Chuyên gia và nhà quản lý trong lĩnh vực quy hoạch xây dựng: Áp dụng các giải pháp tối ưu hóa vị trí cơ sở xây dựng nhằm giảm chi phí vận chuyển và tăng hiệu quả quản lý dự án.

3. Doanh nghiệp cung cấp dịch vụ logistics và vận tải: Tối ưu hóa mạng lưới phân phối, vị trí kho bãi để giảm chi phí và nâng cao chất lượng dịch vụ.

4. Các nhà phát triển phần mềm và công cụ hỗ trợ ra quyết định: Tích hợp thuật toán ACO vào các hệ thống quản lý và hoạch định vị trí cơ sở, giúp tự động hóa và nâng cao hiệu quả công tác lập kế hoạch.

Câu hỏi thường gặp

1. Thuật toán ACO là gì và tại sao lại phù hợp với bài toán vị trí cơ sở?
   ACO là thuật toán metaheuristic mô phỏng hành vi tìm đường của đàn kiến, sử dụng pheromone để hướng dẫn tìm kiếm. Nó phù hợp với bài toán vị trí cơ sở do khả năng xử lý không gian lời giải rộng lớn và phức tạp, đồng thời cân bằng giữa khai thác và khám phá hiệu quả.

2. Bài toán vị trí cơ sở có những loại nào và khác nhau ra sao?
   Có bài toán không hạn chế khả năng (UFLP), có hạn chế khả năng (CFLP), vị trí cơ sở cạnh tranh và bố trí vị trí xây dựng (CSLP). Sự khác biệt chính là về giới hạn công suất, tính cạnh tranh giữa các người chơi và mục tiêu tối ưu hóa chi phí hoặc lợi nhuận.

3. Làm thế nào để đánh giá hiệu quả của thuật toán ACO?
   Hiệu quả được đánh giá qua chất lượng lời giải (tổng chi phí hoặc lợi nhuận), thời gian chạy và khả năng hội tụ. Ví dụ, trên bộ dữ liệu chuẩn, ACO thường đạt lời giải gần tối ưu với thời gian chạy thấp hơn các thuật toán khác.

4. Có thể áp dụng thuật toán ACO cho các bài toán lớn hơn không?
   Có thể, tuy nhiên cần tối ưu tham số và kết hợp với các kỹ thuật tìm kiếm cục bộ để giảm thời gian tính toán và tránh tắc nghẽn. Nghiên cứu mở rộng đang được tiến hành để áp dụng cho các bài toán quy mô lớn hơn.

5. Thuật toán ACO có thể kết hợp với các phương pháp khác không?
   Có, ACO thường được kết hợp với tìm kiếm cục bộ, thuật toán di truyền, hoặc các metaheuristic khác để nâng cao hiệu quả và chất lượng lời giải, đặc biệt trong các bài toán phức tạp như CSLP hay bài toán vị trí cơ sở cạnh tranh.

Kết luận

• Luận văn đã hệ thống hóa kiến thức về độ phức tạp thuật toán và các bài toán vị trí cơ sở thuộc lớp NP-khó, làm rõ tính chất và thách thức trong giải quyết các bài toán này.
• Thuật toán tối ưu hóa đàn kiến (ACO) được áp dụng thành công để giải quyết các bài toán vị trí cơ sở, với các biến thể phù hợp như r|p-ACO và ACO-SRFL, cho kết quả vượt trội về chất lượng lời giải và thời gian chạy.
• Kết quả thử nghiệm trên các bộ dữ liệu mô phỏng và thực tế cho thấy ACO có khả năng hội tụ tốt, ổn định và hiệu quả hơn so với các thuật toán metaheuristic truyền thống khác.
• Đề xuất các giải pháp triển khai, tối ưu tham số và mở rộng ứng dụng ACO trong các bài toán vị trí cơ sở cạnh tranh và bố trí xây dựng, nhằm nâng cao hiệu quả quản lý và vận hành trong thực tế.
• Khuyến nghị các nhà nghiên cứu, chuyên gia và doanh nghiệp trong lĩnh vực công nghệ thông tin, quy hoạch xây dựng và logistics tham khảo và ứng dụng kết quả nghiên cứu để phát triển các công cụ hỗ trợ ra quyết định hiệu quả.

Để tiếp tục phát triển nghiên cứu, đề nghị thực hiện các thử nghiệm mở rộng trên bộ dữ liệu lớn hơn, tối ưu hóa tham số thuật toán và tích hợp với các kỹ thuật tìm kiếm cục bộ trong vòng 12 tháng tới. Mời độc giả và các nhà nghiên cứu liên hệ để trao đổi, hợp tác phát triển các ứng dụng thực tiễn dựa trên nền tảng thuật toán ACO.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 MỘT SỐ KIẾN THỨC TỔNG QUAN VÀ BÀI TOÁN VỊ TRÍ CƠ SỞ Trong cuộc sống, việc đạt lợi nhuận cao hay thấp trong kinh doanh buôn bán, cung cấp dịch vụ phụ thuộc rất nhiều yếu tố. Trong đó, có một yếu tố quan trọng đầu tiên, đóng góp một phần rất lớn đó là xác định được địa điểm đặt dịch vụ thuận lợi – nơi cung cấp dịch vụ. Có rất nhiều tiêu chí đặt ra khi chọn địa điểm: thuận tiện về giao thông, là nơi tập trung đông dân cư…để làm sao thu được lợi nhuận cao nhất. Đặc biệt, đối với các trường hợp khẩn cấp như cứu thương, cứu hỏa thì yêu cầu về khoảng cách nhỏ nhất là vô cùng quan trọng, có thể nói là quan trọng nhất trong các yếu tố.

Yêu cầu của bài toán vị trí cơ sở là tìm phương án đặt các trạm dịch vụ ở đâu để thời gian di chuyển bệnh nhân từ nơi xa bệnh viện nhất (hoặc ngược lại, từ các trạm dịch vụ đến nơi bệnh nhân xa nhất) là nhỏ nhất có thể. Còn với các dịch vụ phổ biến như trạm xăng, thùng phiếu, bốt điện thoại,… thì yêu cầu lại là tổng chi phí từ khách hàng (hay người có nhu cầu) đến địa điểm phục vụ gần khách hàng nhất là nhỏ nhất. Độ phức tạp tính toán của bài toán Gọi TA(X) là thời gian tính của thuật toán A đối với đầu vào X. Khi đó thời gian tính trong tình huống tồi nhất của thuật toán A đối với dữ liệu đầu vào kích thước n được định nghĩa như là: TA (n)  max TA ( X ) | X | n Độ phức tạp trong tình huống tồi nhất của thuật toán P là thời gian tính trong tình huống tồi nhất của thuật toán nhanh nhất để giải nó: Tp (n)  min TA (n)  min(max TA ( X )) A A | X | n Trong đó  là tập tất cả các thuật toán giải bài toán P.

Việc đánh giá đúng độ phức tạp của bài toán là một vấn đề hết sức phức tạp. Vì vậy chúng ta quan tâm đến việc đưa ra các cận trên và cận dưới cho nó. Nếu ta có thuật toán A với thời gian tính trong tình huống tồi nhất là TA(n)= 𝑂(𝑓(𝑛)) thì: 𝑇𝑃 (𝑛) ≤ 𝑇𝐴 (𝑛) ≤ 𝑂(𝑓(𝑛)) 4 Tức là ta có cận trên cho độ phức tạp của bài toán P. Thuật toán nhanh hơn sẽ cho cận trên tốt hơn.

Chúng ta còn quan tâm đến việc đánh giá cận dưới độ phức tạp của bài toán, nghĩa là quan tâm đến việc nó khó đến mức độ nào. Để chỉ ra rằng: 𝑇𝑃 (𝑛) =  (𝑓(𝑛)) Ta cần phải chỉ ra rằng: i. Có thuật toán với thời gian tính  (𝑓(𝑛)) để giải bài toán P. Mọi thuật toán giải bài toán P đều đòi hỏi thời gian tính trong tình huống tồi nhất là  (𝑓(𝑛)).

Yêu cầu ii. có thể thay thế bởi: ii’. cận dưới cho độ phức tạp tính toán của bài toán P là  (𝑓(𝑛)). Bài toán quyết định Bài toán quyết định là bài toán mà đầu ra chỉ có thể là ‘yes’ hoặc ‘no’ (Đúng/sai, 0/1, chấp nhận/từ chối, accept/reject).

Đối với một bài toán quyết định, có những bộ dữ liệu vào của nó có câu trả lời (đầu ra) là ‘yes’ và cũng có những bộ dữ liệu vào có câu trả lời là ‘no’. Những bộ dữ liệu vào có câu trả lời ‘yes’ (‘no’) sẽ được gọi là bộ dữ liệu vào ‘yes’ (‘no’). Ví dụ 1:  Bài toán về tính nguyên tố: “Hỏi số nguyên n có là số nguyên tố hay không?” N=23 là bộ dữ liệu vào ‘yes’, còn n=24 là bộ dữ liệu vào ‘no’ của bài toán.  Bài toán tổng con: “Cho tập I gồm n số nguyên dương x1, x2,…,xn và số nguyên dương T.

Hỏi có thể tìm được tập con S của I với tổng các số trong S là bằng T?”  Bài toán người du lịch dạng quyết định (Dec – TSP): “Tồn tại hay chăng hành trình của người du lịch với tổng chi phí không vượt quá số K cho trước?” 1. Bằng chứng ngắn gọn để kiểm tra Rất nhiều các bài toán quyết định có một đặc điểm chung, đó là để xác nhận câu trả lời 'yes' đối với bộ dữ liệu vào 'yes' của chúng, ta có thể đưa ra 5 bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời 'yes' cho bộ dữ liệu vào 'yes' đó. Ví dụ 2:  Đối với bài toán kiểm tra tích hợp số: "Có phải số n là hợp số?", để xác nhận câu trả lời 'yes' cho đầu vào n, ta có thể đưa ra một ước số b (1<b<n) của n. Để kiểm tra xem b đúng là ước số của n ta có thể thực hiện phép chia n cho b sau thời gian đa thức.Trong ví dụ này b là bằng chứng ngắn gọn (vì b<n) và dễ kiểm tra: có thuật toán thời gian tính đa thức để kiểm tra b đúng là ước số của n.

 Đối với bài toán tổng con, bằng chứng xác nhận câu trả lời 'yes' đối với bộ dữ liệu (x1,.,xn) là vecto c = (c 1,.,c n), trong đó c i = 1 nếu xi được chọn vào tập S và c i = 0 nếu trái lại. Việc kiểm tra xem tập S gồm các số được chọn có thỏa mãn yêu cầu đặt ra hay không, rõ ràng, có thể thực hiện sau thời gian đa thức.  Đối với bài toán người du lịch dạng quyết định, bằng chứng xác nhận câu trả lời 'yes' cho ma trận chi phí C = {c ij: i,j=1,.,n} của bài toán là dãy các thành phố trên hành trình. Việc kiểm tra xem dãy các thành phố đã cho có phải là hành trình với chi phí không vượt quá K có thể thực hiện xong sau thời gian đa thức.

Ta gọi bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời 'yes' cho bộ dữ liệu vào 'yes' của bài toán là một bằng chứng có độ dài bị chặn bởi một đa thức bậc cố định của độ dài dữ liệu đầu vào của bài toán, và việc kiểm tra nó là bằng chứng xác nhận câu trả lời 'yes' đối với đầu vào đã cho của bài toán có thể thực hiện xong sau thời gian đa thức. Như vừa chỉ ra ở trên, các bài toán trong ví dụ 2 đều có bằng chứng ngắn gọn dễ kiểm tra để xác nhận câu trả lời 'yes' của bộ dữ liệu vào 'yes'. Hoàn toàn tương tự, có thể đưa ra khái niệm bằng chứng ngắn gọn dễ kiểm tra để xác nhận câu trả lời 'no'. Đối với một số bài toán việc đưa ra bằng chứng ngắn gọn xác định câu trả lời 'no' là dễ hơn so với việc đưa ra bằng chứng ngắn gọn xác định câu trả lời 'yes'.

Ví dụ 3: 6 Đối với bài toán kiểm tra tính nguyên tố, để đưa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời 'no' cho đầu vào n của nó, ta có thể đưa ra một ước số b của n. Có những bài toán mà việc đưa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời 'yes' cũng như 'no' đều là không dễ dàng. Ví dụ 4: Cho đơn đồ thị vô hướng G = (V,E). Hỏi có đường đi đơn dài nhất nối hai đỉnh s và t của đồ thị G có tồn tại duy nhất? 1.

Lớp bài toán P, NP và co-NP Trước hết, ta nêu khái niệm về lớp các bài toán dễ giải – đó là các bài toán có thể giải được nhờ các thuật toán thời gian tính đa thức. Định nghĩa: Ta gọi P là lớp các bài toán có thể giải được sau thời gian đa thức. Ví dụ 5: Bài toán về tính liên thông của đồ thị có thể giải được nhờ thuật toán với thời gian tính là O(n2), vì vậy, nó là bài toán thuộc lớp P. Bài toán cây khung nhỏ nhất giải được nhờ thuật toán Prim với thời gian O(n2), cũng thuộc vào lớp P.

Định nghĩa: Ta gọi NP là lớp các bài toán quyết định mà để xác nhận câu trả lời 'yes' của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra. Ví dụ 6: Các bài toán trình bày trong ví dụ 2 đều thuộc lớp NP. Định nghĩa: Ta gọi co-NP là lớp các bài toán quyết định mà để xác nhận câu trả lời 'no' của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra. Ví dụ 7: Các bài toán trình bày trong ví dụ 3 đều thuộc lớp co-NP.

Bài toán trong ví dụ 4 còn chưa biết có thuộc vào lớp nào trong hai lớp NP và co-NP hay không. Rõ ràng, nếu một bài toán thuộc lớp P, thì ta có thể tìm được lời giải của nó sau thời gian đa thức, và vì thế ta cũng có thể xác nhận được câu trả lời 'yes' của nó (bằng việc giải nó) sau thời gian đa thức. Vì vậy: P  NP 7 Tương tự như vậy ta có: P  co-NP Một trong những vấn đề trung tâm của lý thuyết tính toán, đó là chứng minh hoặc bác bỏ đẳng thức: P = NP Cho đến hiện nay vấn đề này vẫn là vấn đề mở. Lớp bài toán NP-khó và NP-đầy đủ Ta sẽ đưa ra định nghĩa về những bài toán khó nhất trong lớp NP: bài toán NP-đầy đủ (NP-complete).

Định nghĩa: Một bài toán quyết định A được gọi là NP-đầy đủ nếu như: i. A là bài toán trong NP; ii. Mọi bài toán trong NP đều có thể qui dẫn về A. Như vậy, có thể nói khái niệm về "bài toán khó nhất" trong lớp NP được xây dựng trên cơ sở phép qui dẫn.

Nếu tất cả các bài toán trong NP có thể qui dẫn về một bài toán A thì A khó không kém bất cứ bài toán nào trong số chúng. Điều đáng ngạc nhiên là sự tồn tại của những bài toán có tính chất như vậy. Khó khăn nhất là việc tìm ra được một bài toán như vậy. Bởi vì hễ chúng ta đã có một bài toán NP-đầy đủ thì để ta có thể dễ dàng chứng minh nhiều bài toán khác là NP-đầy đủ nhờ sử dụng kết quả sau đây.

Bổ đề: Giả sử bài toán A là NP-đầy đủ, bài toán B là thuộc NP, và bài toán A qui dẫn về B. Khi đó bài toán B cũng là NP-đầy đủ. Định nghĩa: Một bài toán A được gọi là NP-khó (NP-hard) nếu như sự tồn tại thuật toán đa thức để giải nó kéo theo sự tồn tại thuật toán đa thức để giải một bài toán trong NP. Một cách không hình thức, có thể nói rằng nếu ta có thể giải được một cách hiệu quả một bài toán NP-khó cụ thể, thì ta cũng có thể giải hiệu quả bất kỳ bài toán nào trong NP bằng cách sử dụng thuật toán giải bài toán NP-khó như là một chương trình con.