CƠ SỞ LÝ THUYẾT VÀ LỚP BÀI TOÁN NP-KHÓ
Các khái niệm cơ bản về đồ thị
Đồ thị là công cụ mạnh mẽ để biểu diễn nhiều cấu trúc và giải quyết các bài toán thực tế Lý thuyết đồ thị, một lĩnh vực toán học lâu đời, đã được phát triển từ những năm đầu thế kỷ 18 bởi nhà toán học Thụy Sĩ, và hiện nay có rất nhiều ứng dụng trong đời sống.
Sỹ Leonhard Euler là một trong những nhà toán học nổi bật, và trong vài thập kỷ qua, lý thuyết đồ thị đã thu hút sự chú ý đáng kể nhờ vào sự phát triển nhanh chóng của công nghệ thông tin và sự ra đời của máy tính điện tử.
Trong bài viết này, chúng ta sẽ khám phá những khái niệm cơ bản về đồ thị, tạo nền tảng vững chắc cho việc áp dụng các thuật toán trong các lĩnh vực liên quan đến đồ thị.
1.1 Định nghĩa đồ thị Đồ thị là một cấu trúc rời rạc gồm các đỉnh và cách cạnh nối các đỉnh này Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lƣợng cạnh nối các đỉnh này Ta định nghĩa các loại đồ thị nhƣ sau Định nghĩa 1.1 Đơn đồ thị vô hướng G = (V, E) bao gồm V là tập không rỗng chứa các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là cạnh [Hình 2.a] Định nghĩa 1.2 Đơn đồ thị có hướng G = (V, E) bao gồm tập các đỉnh V và tập các cạnh E là các cặp có thứ tự gồm hai phần tử khác nhau của V Các cạnh của đồ thị có hướng còn được gọi là các cung [Hình 2.b]
Đồ thị có thể chia thành hai loại: đồ thị vô hướng và đồ thị có hướng Trong bài viết này, chúng ta sẽ sử dụng thuật ngữ "đồ thị" để chỉ đồ thị vô hướng mà không cần chú thích thêm.
1.2 Đường đi và tính liên thông Định nghĩa 1.3 Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương trên đồ thị vô hướng G= (V,E) là dãy x 0 , x 1 , x 2 ,… x n-1 , x n trong đó u = x 0 , v = x n , (x i , x i+1 ) Є E, i = 1 n Đỉnh u được gọi là đỉnh đầu, còn đỉnh v được gọi là đỉnh cuối của đường đi Đường đi mà có đỉnh đầu trùng với đỉnh cuối được gọi là chu trình Chu trình được gọi là đơn nếu như không có cạnh nào lặp lại Để xác định xem có luôn tồn tại đường đi giữa 2 cặp đỉnh trong đồ thị, chúng ta đưa ra khái niệm tính liên thông của đồ thị Định nghĩa 1.4 Đồ thị vô hướng G= (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó Định nghĩa 1.5 Đồ thị có hướng G = (V, E) được gọi liên thông mạnh nếu luôn được đường đi giữa hai đỉnh bất kỳ của nó Đồ thị có hướng G = (V, E) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là liên thông
1.3 Cây và cây Steiner Định nghĩa 1.6 Cây là đồ thị vô hướng, liên thông và không chứa chu trình Định nghĩa 1.7 Cho đồ thị vô hướng G = (V, E) và tập các đỉnh W ⊂ V Cây T = (W’, F) được gọi là cây Steiner của W nếu nó là cây trong G bao trùm tất cả các đỉnh của của W Quy ước:
Terminal node: là các đỉnh trong W
Steiner node: là các đỉnh trong W’-W
Dễ thấy rằng một đồ thị vô hướng liên thông bất kỳ có thể có nhiều hơn một cây Steiner
Trọng số của cây Steiner được xác định bằng cách gán một trọng số thực w(e) cho mỗi cạnh e thuộc tập E của đồ thị G Trọng số của cây Steiner T được tính theo công thức W(T) = Σ w(e), trong đó tổng hợp tất cả trọng số của các cạnh trong cây.
Cây Steiner nhỏ nhất: cây Steiner nhỏ nhất của G là cây Steiner T có W(T) nhỏ nhất
(a) là đồ thị ban đầu đã cho
(b) Cây Steiner T = (W’,F )tương ứng của đồ thị (a) với W= {1,2,3,4}
Các thông số của cây T:
F = {(2,3), (3,4), (4,1) (2,5)} có tổng trọng số là 11
Độ phức tạp tính toán
Các vấn đề kỹ thuật thường được mô tả dưới dạng bài toán tính toán, giúp nghiên cứu và giải quyết hiệu quả hơn Bài toán tính toán bao gồm mối quan hệ giữa đầu vào, tức là các yếu tố đã cho, và đầu ra, là những kết quả cần đạt được Độ phức tạp tính toán được coi là tiêu chí quan trọng để đánh giá hiệu quả của bài toán này.
2.1 Một số khái niệm cơ bản Định nghĩa 2.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ố đầ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
Bài toán thể hiện mối quan hệ giữa đầu vào và đầu ra, và để đạt được đầu ra từ đầu vào đã cho, cần sử dụng các thuật toán Thuật toán giải bài toán được định nghĩa là một quy trình xác định, bao gồm một số bước hữu hạn cần thực hiện để thu được đầu ra tương ứng với đầu vào đã cho.
Độ phức tạp tính toán của một thuật toán là yếu tố quan trọng bên cạnh tính đúng đắn, phản ánh lượng tài nguyên mà thuật toán sử dụng để thực hiện công việc Để đánh giá độ phức tạp này, cần chú ý đến hai loại tài nguyên chính: bộ nhớ và thời gian.
Ngày nay, sự phát triển công nghệ bộ nhớ đã khiến vấn đề tài nguyên bộ nhớ trong thuật toán ít được chú trọng hơn so với thời gian tính toán Thời gian chạy thực tế của thuật toán phụ thuộc vào nhiều yếu tố như cấu hình máy, ngôn ngữ lập trình, phương pháp cài đặt, trình biên dịch và đặc biệt là dữ liệu đầu vào Dữ liệu đầu vào không chỉ là yếu tố quan trọng mà còn là tiêu chí chính để so sánh hiệu quả của các thuật toán Để đảm bảo tính nhất quán trong việc đánh giá thời gian tính toán, chỉ nên xem xét kích thước dữ liệu đầu vào.
2.2 Các ký hiệu tiệm cận:
Khi đánh giá độ phức tạp tính toán của thuật toán, các ký hiệu tiệm cận quan trọng bao gồm Θ, Ο và Ω Trong phần này, chúng ta sẽ nhắc lại định nghĩa và một số tính chất của các tiệm cận, đồng thời bỏ qua hai ký hiệu ο và ω Định nghĩa 2.4 đề cập đến các hàm f(n) và g(n), là những hàm số của số nguyên dương n.
Θ(g(n)) = {f(n) : tồn tại các hằng số dương c1, c 2 và n 0 sao cho 0 ≤ c 1 ≤ f(n) ≤ c2g(n), với mọi n ≥ n0} g(n) đƣợc gọi là đánh giá tiệm cận đúng của f(n) hay f(n) có bậc là g(n)
Ο(g(n)) = {f(n) : tồn tại các hằng số dương c và n0 sao cho f(n) ≤ cg(n), với mọi n ≥ n0} g(n) gọi là tiệm cận trên tiêm cận của f(n) hay f(n) có bậc không quá g(n)
Ω(g(n)) = {f(n) : tồn tại các hằng số dương c và n0 sao cho cg(n) ≤ f(n), với mọi n ≥ n0} Gọi g(n) là tiệm cận dưới của f(n), tức là f(n) có bậc ít nhất là g(n) Để đánh giá thời gian tính toán của các thuật toán, cần tuân thủ các quy ước liên quan đến các ký hiệu tiệm cận.
Nếu một thuật toán có thời gian tính tốt nhất t(n) trong trường hợp tối ưu với kích thước dữ liệu đầu vào n, và t(n) = Ω(g(n)), thì thời gian tính tốt nhất của thuật toán không thể nhỏ hơn g(n) Điều này có nghĩa là thời gian tính tốt nhất của thuật toán được xác định là Ω(g(n)).
Nếu thuật toán có thời gian tính t(n) trong trường hợp tồi tệ nhất là t(n) = Ο(g(n)) với kích thước dữ liệu đầu vào n, thì thời gian tính tốt nhất của thuật toán sẽ không nhỏ hơn g(n) Điều này có nghĩa là thời gian tính tốt nhất cũng có thể được biểu diễn là Ο(g(n)).
Nếu một thuật toán yêu cầu thời gian tính trung bình t(n) với kích thước dữ liệu đầu vào n và t(n) = Θ(g(n)), thì thời gian tính tốt nhất của thuật toán không thể nhỏ hơn g(n) Do đó, thời gian tính tốt nhất của thuật toán sẽ được biểu diễn là Θ(g(n)).
Thông thường khi nói thuật toán có thời gian tính là Ο(f(n)) thì hiểu là thời gian tính của thuật toán đánh giá trong tình huống tồi nhất là Ο(f(n))
Còn khi nói thuật toán có thời gian tính là Ω(f(n)) thì hiểu đánh giá thời gian tính của thuật toán trong tình huống tốt nhất là Ω(f(n))
2.3 Độ phức tạp tính toán của bài toán Định nghĩa 2.5 Độ phức tạp tính toán của một bài toán là thời gian tính (ở đây chỉ quan tâm đến đánh giá thời gian thực hiện, bỏ qua đánh giá về yêu cầu bộ nhớ) của thuật toán tốt nhất trong số tất cả các thuật toán giải bài toán đó
Để xác định thời gian tính toán của thuật toán tốt nhất trong bài toán có những thuật toán chưa biết, có hai phương pháp giải quyết vấn đề này.
Cách thứ nhất: Sử dụng các kỹ thuật đưa ra cận dưới cho độ phức tạp tính toán của bài toán
Cách thứ hai là chỉ ra rằng bài toán đang được xem xét có độ khó tương đương với những bài toán khó nhất hiện nay, tức là có mức độ phức tạp tính toán không hề kém cạnh.
Lớp bài toán NP-khó
3.1 Một số khái niệm cơ bản Định nghĩa 3.1 Thuật toán có thời gian tính đa thức là thuật toán mà độ phứa tạp thời gian của nó trong trường hợp xấu nhất được giới hạn trên bởi một hàm đa thức của kích thước dữ liệu đầu vào (kích thước dữ liệu đầu vào được tính bằng số bít cần thiết để biểu diễn nó) Tức là nếu n là kích thước dữ liệu đầu vào, thì luôn tồn tại một đa thức p(n) sao cho
Các thuật toán có độ phức tạp thời gian trong trường hợp xấu nhất sau đều có thời gian tính đa thức: Ο(p(n)) = 2n ; 3n 3 + 4 ; 5n + n 10 ; nlgn
Các thuật toán có độ phức tạp thời gian trong trường hợp xấu nhất không thuộc dạng đa thức bao gồm: Ο(f(n)) = 2^n, 2^(0.01n), 2^(√n) và n! Bài toán quyết định là loại bài toán mà đầu ra chỉ có thể là hai giá trị: đúng hoặc sai.
Bài toán tối ưu hóa (P) được định nghĩa là tối đa hóa hàm f(x) với điều kiện x thuộc tập D Bài toán quyết định tương ứng với bài toán tối ưu này có dạng "có" hoặc "không", tức là xác định xem có tồn tại giá trị x trong D sao cho f(x) đạt giá trị tối đa hay không.
(PD) “Cho giá trị K Hỏi có tìm được u Є D sao cho f(u) ≥ K hay không?”
Bài toán tối ưu và bài toán quyết định có mối liên hệ chặt chẽ, được thể hiện qua Định lý 3.1: nếu bài toán quyết định tương ứng với một bài toán tối ưu có thể giải hiệu quả bằng thuật toán thời gian đa thức, thì bài toán tối ưu đó cũng sẽ được giải hiệu quả bằng thuật toán tương tự Ngoài ra, Định nghĩa 3.4 nêu rõ rằng bằng chứng ngắn gọn dễ kiểm tra sẽ xác nhận tính chính xác của câu trả lời.
Trong bài toán, câu trả lời "yes" cho bộ dữ liệu tương ứng là một bằng chứng có độ dài bị giới hạn bởi một đa thức bậc cố định liên quan đến độ dài của dữ liệu đầu vào Việc kiểm tra bằng chứng này cho phép xác nhận câu trả lời "yes" đối với đầu vào đã cho trong thời gian đa thức.
3.2 Lớp bài toán P, NP, và co-NP
Dưới đây là phân loại các lớp của bài toán Định nghĩa 3.5 P là lớp bài toán quyết định có thể được giải quyết trong thời gian đa thức
P là tập hợp các bài toán có thể giải quyết nhanh chóng, trong khi NP là lớp bài toán quyết định mà để xác nhận câu trả lời "có", cần có chứng cứ ngắn gọn và dễ kiểm tra.
Có thể khẳng định rằng NP là một lớp bài toán cho phép kiểm tra nhanh chóng câu trả lời "có" trong thời gian đa thức, nếu đã có sẵn lời giải.
Rõ ràng rằng P là tập con của NP, nhưng việc xác định liệu NP có phải là tập con của P hay không vẫn chưa có lời giải Theo định nghĩa 3.7, co-NP là lớp bài toán mà việc xác nhận câu trả lời "không" có thể thực hiện bằng cách cung cấp một bằng chứng ngắn gọn và dễ dàng kiểm tra.
Co-NP là lớp bài toán hoàn toàn ngược lại với lớp NP Mối quan hệ giữa ba lớp bài toán này có thể được mô tả một cách trực quan qua hình ảnh minh họa dưới đây.
3.3 Khái niệm quy dẫn Định nghĩa 3.8 Giả sử A và B là hai bài toán quyết định Ta nói bài toán A có thể quy dẫn sau thời gian đa thức về bài toán B nếu tồn tại thuật toán thời gian đa thức
R cho phép chuyển đổi dữ liệu đầu vào x của A thành dữ liệu đầu vào R(x) của B, đảm bảo rằng x là dữ liệu "yes" của A chỉ khi R(x) là dữ liệu "yes" của B.
Ký hiệu A < B biểu thị rằng bài toán A có thể được quy dẫn về bài toán B, thường được sử dụng để so sánh độ khó của hai bài toán Nếu A có thể quy dẫn được về B, điều này cho thấy mối quan hệ giữa độ phức tạp của chúng.
Yes/no Đầu vào cho A x R(x) Đầu ra cho B Đầu ra cho A Đầu vào cho B
Hình 4: Các lớp bài toán P, NP và co-NP
Hình 5:Sơ đồ quá trình quy dẫn
Nếu A khó hơn B, tức là chưa tìm ra thuật toán thời gian đa thức để giải A, thì B cũng sẽ khó Ngược lại, nếu B dễ, nghĩa là đã có thuật toán thời gian đa thức cho B, thì A cũng sẽ dễ.
3.4 Lớp bài toán NP-đầy đủ và NP-khó Định nghĩa 3.9 Một bài toán quyết định A được gọi là NP-đầy đủ nếu như A là bài toán trong NP và mọi bài toán trong NP đều có thể quy dẫn về A Định nghĩa 3.10 Một bài toán A được gọi là NP-khó 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ọi bài toán trong
Nếu một bài toán NP-khó có thể được giải quyết nhanh chóng, điều đó đồng nghĩa với việc mọi bài toán khác trong NP cũng có thể được giải quyết nhanh chóng Các bài toán NP-khó ít nhất có độ khó tương đương với bất kỳ bài toán nào trong NP, trong khi NP-đầy đủ là nhóm các bài toán khó nhất trong NP Hình dưới đây minh họa cách phân loại tạm thời các bài toán này.
Các giải thuật tìm đường đi ngắn nhất
Trong phần này, chúng ta sẽ khám phá bài toán tìm đường đi ngắn nhất từ một đỉnh hoặc giữa tất cả các cặp đỉnh trong đồ thị, một vấn đề quan trọng sẽ được áp dụng cụ thể trong chương 4.
Bài toán tìm đường đi ngắn nhất trong đồ thị G = (V, E) yêu cầu xác định đường đi ngắn nhất từ đỉnh nguồn s thuộc V đến mỗi đỉnh v cũng thuộc V Nhiều thuật toán đã được phát triển để giải quyết vấn đề này Bài viết sẽ điểm qua một số thuật toán nổi tiếng và phân tích độ phức tạp tính toán của chúng.
Hình 6: Phân lớp tạm thời các bài toán
Thuật toán Dijkstra cho phép tìm đường đi ngắn nhất từ một đỉnh s đến các đỉnh còn lại của đồ thị có trọng số
Phương pháp của thuật toán là xác định tuần tự đỉnh có chiều dài đến s theo thứ tự tăng dần
Thuật toán này sử dụng nhãn tạm thời cho mỗi đỉnh để xác định cận trên của chiều dài đường đi ngắn nhất từ đỉnh s đến đỉnh đó Trong quá trình lặp, các nhãn tạm thời sẽ được cập nhật, và một nhãn tạm thời sẽ được chính thức hóa Khi nhãn của một đỉnh trở thành chính thức, điều đó đồng nghĩa với việc xác định được chiều dài ngắn nhất của đường đi từ đỉnh s đến đỉnh đó.
10 for all v là đỉnh kề của u do
18 end while Độ phức tạp tính toán:
Thời gian chạy của thuật toán Dijkstra phụ thuộc vào cách cài đặt hàng đợi ưu tiên nhỏ nhất Nếu sử dụng các đỉnh được đánh số từ 1 đến |V| và lưu trữ d[v] dưới dạng mảng, thì thao tác chèn và xóa sẽ mất O(1) thời gian Tuy nhiên, để tìm đỉnh có d[u] nhỏ nhất, cần O(V) thời gian do phải tìm kiếm trên toàn bộ mảng Do đó, tổng thời gian cần thiết cho thuật toán sẽ là O(V² + E) = O(V²).
Thuật toán Kruskal xây dựng cây khung bằng cách sử dụng phương pháp hợp nhất, trong đó các cạnh được xét theo thứ tự trọng số từ nhỏ đến lớn Bắt đầu với cây T không có cạnh nào, thuật toán kiểm tra từng cạnh của đồ thị vô hướng G = (V, E) và chỉ thêm cạnh vào T nếu nó không tạo ra chu trình Quá trình này được lặp lại cho đến khi cây khung hoàn chỉnh.
Đã kết nạp đƣợc n-1 cạnh vào trong T
Trong một đồ thị không liên thông G, nếu chưa đủ cạnh được kết nạp nhưng thêm một cạnh bất kỳ từ số cạnh còn lại sẽ hình thành chu trình đơn Điều này dẫn đến việc tìm kiếm cây khung không thành công.
Mô hình thuật toán Kruskal
2 Lab[k] := -1 // lab lưu số đỉnh của gốc cây k
3 For all (edge(u,v) Є E theo thứ tự từ cạnh trọng số nhỏ tới cạnh trọng số lớn) do
4 R1:=getRoot(u) // r1 là gốc của cây chứa đỉnh u
6 If r1 ≠ r2 then // cạnh(u,v) nối hai cây khác nhau
7 Kết nạp (u,v) vào cây, nếu đã đủ n-1 cạnh thì thuật toán dừng
8 Union (r1,r2) // hợp nhất hai cây thành một cây
Về độ phức tạp tính toán, thao tác GetRoot có độ phức tạp là O(lgn) và thao tác Union là O(1) Khi đã có danh sách cạnh đã sắp xếp, vòng lặp dựng cây khung sẽ duyệt qua danh sách này và gọi 2 lần thao tác GetRoot cho mỗi cạnh, dẫn đến độ phức tạp O(mlgn) Nếu đồ thị có cây khung (m ≥ n-1), chi phí thời gian chủ yếu nằm ở thao tác sắp xếp danh sách cạnh, với độ phức tạp của HeapSort là O(mlgm) Do đó, độ phức tạp tính toán của thuật toán trong trường hợp xấu nhất là O(mlgm), nhưng thực tế, thuật toán thường chỉ duyệt một phần danh sách cạnh để xây dựng cây khung.
Thuật toán Floyd-Warshall giải quyết bài toán tìm đường đi ngắn nhất giữa các cặp đỉnh trong đồ thị bằng phương pháp quy hoạch động Nguyên lý tối ưu của thuật toán này khẳng định rằng nếu k là đỉnh nằm trên đường đi ngắn nhất từ đỉnh i đến đỉnh j, thì đoạn đường từ i đến k và từ k đến j cũng phải là ngắn nhất.
Thuật toán Floyd-Warshall có thời gian tính toán được xác định bởi ba vòng lặp for lồng nhau Mỗi lần thực hiện dòng lệnh cần thời gian O(1), do đó, thuật toán này hoạt động với độ phức tạp thời gian O(n^3).
Chương này đã trình bày các lý thuyết cơ bản về đồ thị và bài toán đường đi ngắn nhất Tiếp theo, chương 2 sẽ khám phá bài toán thiết kế mạng chịu lỗi cùng với các ứng dụng thực tiễn của nó.
BÀI TOÁN THIẾT KẾ MẠNG CHỊU LỖI
Phát biểu bài toán
1.1 Bài toán thiết kế mạng chịu lỗi
Bài toán thiết kế mạng chịu lỗi (SNDP - Survivable Network Design Problem) đƣợc phát biểu nhƣ sau:
Trong đồ thị vô hướng kết nối G = (V, E), với tập đỉnh V và tập cạnh E, mỗi cạnh e được gán trọng số không âm w(e) Tập đỉnh V bao gồm bốn loại nút: nút gốc (J), nút khách hàng loại 1 (C1), nút khách hàng loại 2 (C2) và nút trong không gian (S) Mục tiêu là tìm cách kết nối các khách hàng C = C1 ∪ C2 đến cơ sở hạ tầng hiện có (J) với tổng chi phí kết nối nhỏ nhất, đồng thời đảm bảo đáp ứng yêu cầu kết nối của từng loại khách hàng.
Hình 7: Mô hình mạng chịu lỗi Để tiện cho việc trình bày, đồ án xin đƣa ra một số khái niệm liên quan
Các nghiên cứu trước đây đã chỉ ra rằng bài toán SNDP (Stochastic Network Design Problem) thuộc lớp bài toán NP-khó Dưới đây là sơ đồ quy dẫn cho bài toán này.
SAT → Chu kỳ Hamilton → TSP
Bài toán SNDP thuộc lớp NP-khó, khiến việc tìm kiếm lời giải chính xác trở nên khó khăn khi kích thước dữ liệu đầu vào lớn Đồ án này không tập trung vào việc tìm kiếm lời giải chính xác tốt nhất, mà thay vào đó sẽ tìm kiếm lời giải xấp xỉ Trong điều kiện lý tưởng, lời giải xấp xỉ này sẽ gần với lời giải tốt nhất và có chi phí thời gian chấp nhận được.
Một trong những phương pháp phổ biến để tìm lời giải xấp xỉ cho các bài toán NP-khó là áp dụng các giải thuật heuristic và meta-heuristic Chương 3 sẽ cung cấp cái nhìn tổng quan chi tiết về các giải thuật này.
Các ứng dụng của bài toán
SNDP có nhiều ứng dụng thực tiễn, bao gồm thiết kế mạng truyền thông và mạng phân tán với trọng tâm là độ tin cậy Đồ án này tập trung vào bài toán thiết kế mạng truy cập (last mile) và mô hình hóa các bài toán ứng dụng thành đồ thị Các bài toán liên quan đến khái niệm sống sót (“Survivable”) như thiết kế mạng lưới giao thông chống tắc nghẽn, hệ thống lưới điện, đường ống, đường nước và mạng truyền thông kiểm soát cơ sở hạ tầng rất được quan tâm, nhằm giảm thiểu chi phí sửa chữa khi gặp sự cố Bài viết sẽ giới thiệu hai ứng dụng cụ thể của SNDP trong thiết kế mạng truyền thông và mạng lưới giao thông.
2.1 Thiết kế mạng truyền thông
Mạng truyền thông là tập hợp các máy tính độc lập cùng với các phương tiện giao tiếp giữa chúng Mạng này thường được sử dụng bởi nhiều người, cho phép họ truy cập và chia sẻ thông tin một cách hiệu quả.
Bài toán SNDP (Shortest Network Design Problem) là một vấn đề quan trọng trong thiết kế mạng truyền thông, đặc biệt là về mặt bảo mật Mạng truyền thông có thể được mô hình hóa dưới dạng đồ thị, trong đó trọng số thể hiện chất lượng dịch vụ (QoS), như tốc độ dữ liệu tối đa Mục tiêu chính là đảm bảo tốc độ dữ liệu mong muốn ngay cả khi một số liên kết gặp sự cố Để duy trì tính tin cậy và an toàn của mạng, cần xem xét các đường đi giữa các máy tính trong mạng Bài toán SNDP giúp đáp ứng các yêu cầu về độ tin cậy và khả năng chịu lỗi trong thiết kế mạng truyền thông cơ bản.
Trong một mạng máy tính, khi chỉ có một máy tính hoạt động như máy chủ và các máy tính khác kết nối đến máy chủ này, hệ thống có thể được mô hình hóa như một cây khung Cây khung này có gốc là máy tính đảm nhận vai trò server, trong khi các đỉnh đại diện cho các máy tính khách hoặc các thiết bị mạng như router và switch Các cạnh thể hiện kết nối giữa các máy tính Để đảm bảo tính tin cậy của mạng, cần xác định số lượng đường đi cần thiết đến máy chủ, nhằm đảm bảo rằng khi gặp sự cố hỏng hóc hoặc tấn công, toàn bộ mạng vẫn hoạt động ổn định.
Khi một cơ sở hạ tầng mạng truy cập đã có sẵn và nhiều máy tính đã được kết nối, việc bổ sung các máy tính mới vào mạng truyền thông cần được thực hiện thông qua bước tiền xử lý.
Thu gọn cơ sở hạ tầng đã tồn tại ban đầu xem nhƣ nó chỉ đƣợc nhìn thấy trên mạng là một máy tính duy nhất
Việc kết nối thêm máy tính vào mạng tương tự như trường hợp ban đầu
Kết thúc chúng ta lại phải xử lý đƣa nó về tối ƣu kết nối với một trong tập hợp các máy đã có
Việc sử dụng một cây Steiner kết hợp với việc bổ sung các đường kết nối theo nhu cầu sẽ giúp tiết kiệm chi phí và đáp ứng tốt hơn các yêu cầu chịu lỗi của mạng truyền thông.
2.2 Thiết kế mạng lưới giao thông
Mạng lưới giao thông là yếu tố thiết yếu trong mỗi thành phố, đặc biệt khi dân số tăng cao, dẫn đến sự phức tạp và tắc nghẽn giao thông, như tại Hà Nội Mặc dù đã có nhiều giải pháp như phân luồng và chắn ngã ba, nhưng hiệu quả chỉ tạm thời Việc tối ưu hóa cơ sở hạ tầng giao thông để giảm tắc nghẽn là nhiệm vụ quan trọng của cơ sở hạ tầng quan trọng (CIP) và mạng lưới truyền thông Báo cáo năm 1997 của Ủy ban Tổng thống về bảo vệ cơ sở hạ tầng quan trọng đã xác định các yếu tố cần thiết cho quốc phòng và an ninh Để xây dựng mô hình cơ sở hạ tầng giao thông hiệu quả, cần xác định các tình trạng nguy cơ tắc nghẽn và thiết kế một cấu trúc đồ thị có trọng số dựa trên khoảng cách Euclide Điều này bao gồm việc nhóm và kết nối các nút giao thông, từ đó xác định số lượng con đường phân chia cần thiết Kết quả là một đồ thị con hỗ trợ thiết kế tối ưu cho mạng lưới giao thông.
Ngoài ra, các ứng dụng như hệ thống lưới điện, đường ống, đường nước cũng được xem xét nhƣ là vấn đề chịu lỗi của bài toán
Bài toán SNDP đóng vai trò quan trọng trong ứng dụng tin học và nhiều lĩnh vực khác trong đời sống Với tính hữu dụng cao, nhiều nghiên cứu đã được thực hiện nhằm tìm ra các giải pháp tối ưu cho bài toán này Phần tiếp theo sẽ trình bày lại bài toán SNDP cùng với một số giải thuật heuristic để giải quyết vấn đề này.
GIẢI THUẬT HEURISTIC VÀ META-HEURISTIC
Lịch sử phát triển
Bài toán tối ưu tổ hợp nhằm tìm kiếm lời giải tốt nhất trong một không gian giải pháp rời rạc Nhiều bài toán trong lĩnh vực này có độ phức tạp cao và thuộc lớp NP-khó, khiến việc tìm kiếm lời giải tối ưu trong thời gian đa thức trở nên không khả thi Do đó, các thuật toán heuristic và meta-heuristic đã được phát triển để giải quyết các bài toán tổ hợp, nhằm tìm ra lời giải gần tối ưu trong thời gian chấp nhận được.
Meta-heuristic là thuật ngữ chỉ các giải thuật heuristic dùng để giải quyết các bài toán tổ hợp phức tạp Nó bao gồm nhiều chiến lược khác nhau nhằm khám phá không gian tìm kiếm, cần đạt được sự cân bằng giữa tính đa dạng và chuyên sâu Để cài đặt thành công một giải thuật heuristic, cần khai thác kinh nghiệm từ quá trình tìm kiếm để xác định những vùng có giải pháp chất lượng cao gần tối ưu Một số giải thuật heuristic và meta-heuristic nổi tiếng bao gồm giải thuật luyện thép (SA - Simulated Annealing), giải thuật di truyền (GA - Genetic Algorithm) và giải thuật tối ưu hóa đàn kiến (ACO - Ant Colony Optimization).
Giải thuật tối ƣu hóa đàn kiến (ACO) đƣợc đề xuất bởi Marco Dorigo năm
1992, là meta-heuristic dùng chiến lƣợc của đàn kiến trong thế giới thực để giải bài toán tối ƣu
Giải thuật di truyền (GA) được phát minh bởi John Holland và phát triển cùng với các đồng nghiệp và sinh viên của ông Giải thuật này dựa trên các phương thức xác suất, lấy cảm hứng từ cơ chế di truyền trong sinh học và quá trình tiến hóa của các cá thể trong một loài.
Giải thuật luyện thép (SA) là phương pháp xác suất được đề xuất bởi
Kirkpatrick, Gelett và Vecchi (1983) cùng Cerny (1985) đã áp dụng nguyên lý thu được trạng thái năng lượng nhỏ nhất thông qua quá trình nóng chảy và ngưng tụ của kim loại tự nhiên để phát triển các giải pháp tối ưu cho nhiều bài toán khác nhau.
Hình sau đây cho ta thấy mối liên hệ giữa các kỹ thuật tìm kiếm
Các giải thuật heuristic cơ bản
Mô hình giải thuật heuristic tổng quát nhƣ sau:
Các kỹ thuật tìm kiếm
Dựa trên tính toán Ngẫu nhiên Đếm
Trực tiếp Gián tiếp Giải thuật luyện thép Giải thuật tiến hóa Quy hoạch động
Newton Tham lam Chiến lƣợc tiến hóa Giải thuật di truyền
Hình 9: Các kỹ thuật tìm kiếm
Have local transformations been exhausted?
No Is this solution feasible
Initialize counters to enumerate local transformations
No Examine next local transformation
2.1 Giải thuật tìm kiếm cục bộ và luyện thép
2.1.1 Giải thuật tìm kiếm cục bộ
Tìm kiếm cục bộ là một phương pháp hiệu quả để giải quyết các bài toán tính toán phức tạp, với ý tưởng di chuyển từ lời giải gần đúng ban đầu đến các lời giải láng giềng nhằm tìm kiếm lời giải tối ưu hơn Trong bài viết này, lời giải được xây dựng trên đồ thị G = (V, E, c) thông qua cách tiếp cận heuristic, sử dụng một trong ba phép toán di chuyển được đề cập chi tiết trong chương 4 Một trong ba phép toán này sẽ được chọn ngẫu nhiên để áp dụng vào lời giải hiện tại, và nếu lời giải mới tìm được tốt hơn, nó sẽ trở thành lời giải hiện tại mới.
Giải thuật tìm kiếm cục bộ
4 while chưa đạt tới số lần thực hiện giải thuật (hoặc điều kiện kết thúc khác) do
5 new_solution:= di_chuyển_với_phép_toán_ngẫu nhiên(candidate_solution)
6 if (cost(new_solution)
