Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng

ủa thành phần liên thông tương ứng trong H, ... Quá trình sẽ kết thúc khi ta trở về đỉnh xuất phát, tức là thu được chu trình đi qua mỗi cạnh của đồ thị đúng một lần. * Hệ quả: Đồ thị liên thông G là nửa Euler (mà không là Euler) khi và chỉ khi có đúng hai đỉnh bậc lẻ trong G. * Chú ý: Ta có thể vạch được một chu trình Euler trong đồ thị liên thông G có bậc của mọi đỉnh là chẵn theo thuật toán Fleury sau đây. Xuất phát từ một đỉnh bất kỳ của G và tuân theo hai quy tắc sau: - Mỗi khi đi qua một cạnh nào thì xoá nó đi; sau đó xoá đỉnh cô lập (nếu có); - Không bao giờ đi qua một cầu, trừ phi không còn cách đi nào khác. u s v w t x y z Hình 1.16. Xây dựng đường đi Xuất phát từ u, ta có thể đi theo cạnh (u,v) hoặc (u,x), giả sử là (u,v) (xoá (u,v)). Từ v có thể đi qua một trong các cạnh (v,w), (v,x), (v,t), giả sử (v,w) (xoá (v,w)). Tiếp tục, có thể đi theo một trong các cạnh (w,s), (w,y), (w,z), giả sử (w,s) (xoá (w,s)). Đi theo cạnh (s,y) (xoá (s,y) và s). Vì (y,x) là cầu nên có thể đi theo một trong hai cạnh (y,w), (y,z), giả sử (y,w) (xoá (y,w)). Đi theo (w,z) (xoá (w,z) và w) và theo (z,y) (xoá (z,y) và z). Tiếp tục đi theo cạnh (y,x) (xoá (y,x) và y). Vì (x,u) là cầu nên đi theo cạnh (x,v) hoặc (x,t), giả sử (x,v) (xoá (x,v)). Tiếp tục đi theo cạnh (v,t) (xoá (v,t) và v), theo cạnh (t,x) (xoá cạnh (t,x) và t), cuối cung đi theo cạnh (x,u) (xoá (x,u), x và u). 1.1.6. Bài toán người phát thư Trung Hoa: Một nhân viên đi từ Sở Bưu Điện, qua một số đường phố để phát thư, rồi quay về Sở. Người ấy phải đi qua các đường theo trình tự nào để đường đi là ngắn nhất? Bài toán được nhà toán học Trung Hoa Guan nêu lên đầu tiên (1960), vì vậy thường được gọi là “bài toán người phát thư Trung Hoa”. Ta xét bài toán ở một dạng đơn giản như sau. Cho đồ thị liên thông G. Một chu trình qua mọi cạnh của G gọi là một hành trình trong G. Trong các hành trình đó, hãy tìm hành trình ngắn nhất, tức là qua ít cạnh nhất. Rõ ràng rằng nếu G là đồ thị Euler (mọi đỉnh đều có bậc chẵn) thì chu trình Euler trong G (qua mỗi cạnh của G đúng một lần) là hành trình ngắn nhất cần tìm. Chỉ còn phải xét trường hợp G có một số đỉnh bậc lẻ (số đỉnh bậc lẻ là một số chẵn). Khi đó, mọi hành trình trong G phải đi qua ít nhất hai lần một số cạnh nào đó. Dễ thấy rằng một hành trình qua một cạnh (u,v) nào đó quá hai lần thì không phải là hành trình ngắn nhất trong G. Vì vậy, ta chỉ cần xét những hành trình T đi qua hai lần một số cạnh nào đó của G. Ta quy ước xem mỗi hành trình T trong G là một hành trình trong đồ thị Euler GT, có được từ G bằng cách vẽ thêm một cạnh song song đối với những cạnh mà T đi qua hai lần. Bài toán đặt ra được đưa về bài toán sau: Trong các đồ thị Euler GT, tìm đồ thị có số cạnh ít nhất (khi đó chu trình Euler trong đồ thị này là hành trình ngắn nhất). Định lý (Gooodman và Hedetniemi, 1973). Nếu G là một đồ thị liên thông có q cạnh thì hành trình ngắn nhất trong G có chiều dài q + m(G), trong đó m(G) là số cạnh mà hành trình đi qua hai lần và được xác định như sau: Gọi V0(G) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của G. Ta phân 2k phần tử của G thành k cặp, mỗi tập hợp k cặp gọi là một phân hoạch cặp của V0(G). Ta gọi độ dài đường đi ngắn nhất từ u đến v là khoảng cách d(u,v). Đối với mọi phân hoạch cặp Pi, ta tính khoảng cách giữa hai đỉnh trong từng cặp, rồi tính tổng d(Pi). Số m(G) bằng cực tiểu của các d(Pi): m(G)=min d(Pi). Ví dụ 2: Giải bài toán người phát thư Trung Hoa cho trong đồ thị sau: D C E F B K J A I H G G GT Hình 1.17. Xây dựng đường đi GT và G Tập hợp các đỉnh bậc lẻ VO(G)={B, G, H, K} và tập hợp các phân hoạch cặp là P={P1, P2, P3}, trong đó P1 = {(B, G), (H, K)} ® d(P1) = d(B, G)+d(H, K) = 4+1 = 5, P2 = {(B, H), (G, K)} ® d(P2) = d(B, H)+d(G, K) = 2+1 = 3, P3 = {(B, K), (G, H)} ® d(P3) = d(B, K)+d(G, H) = 3+2 = 5. m(G) = min(d(P1), d(P2), d(P3)) = 3. Do đó GT có được từ G bằng cách thêm vào 3 cạnh: (B, I), (I, H), (G, K) và GT là đồ thị Euler. Vậy hành trình ngắn nhất cần tìm là đi theo chu trình Euler trong GT: A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A. * Định lý: Đồ thị có hướng liên thông yếu G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc vào bằng bậc ra. Chứng minh: Chứng minh tương tự như chứng minh của Định lý 4.1.2 và điều kiện đủ cũng cần có bổ đề dưới đây tương tự như ở Bổ đề 4.1.3. * Bổ đề: Nếu bậc vào và bậc ra của mỗi đỉnh của đồ thị có hướng G không nhỏ hơn 1 thì G chứa chu trình đơn. * Hệ quả: Đồ thị có hướng liên thông yếu G là nửa Euler (mà không là Euler) khi và chỉ khi tồn tại hai đỉnh x và y sao cho: dego(x) = degt(x)+1, degt(y) = dego(y)+1, degt(v) = dego(v), "vÎV, v ¹ x, v ¹ y. Chứng minh: Chứng minh tương tự như ở Hệ quả 4.1.4. 1.1.7. Đường đi Hamilton và đồ thị Hamilton Năm 1857, nhà toán học người Ailen là Hamilton(1805-1865) đưa ra trò chơi “đi vòng quanh thế giới” như sau. Cho một hình thập nhị diện đều (đa diện đều có 12 mặt, 20 đỉnh và 30 cạnh), mỗi đỉnh của hình mang tên một thành phố nổi tiếng, mỗi cạnh của hình (nối hai đỉnh) là đường đi lại giữa hai thành phố tương ứng. Xuất phát từ một thành phố, hãy tìm đường đi thăm tất cả các thành phố khác, mỗi thành phố chỉ một lần, rồi trở về chỗ cũ. Trước Hamilton, có thể là từ thời Euler, người ta đã biết đến một câu đố hóc búa về “đường đi của con mã trên bàn cờ”. Trên bàn cờ, con mã chỉ có thể đi theo đường chéo của hình chữ nhật 2 x 3 hoặc 3 x 2 ô vuông. Giả sử bàn cờ có 8 x 8 ô vuông. Hãy tìm đường đi của con mã qua được tất cả các ô của bàn cờ, mỗi ô chỉ một lần rồi trở lại ô xuất phát. Bài toán này được nhiều nhà toán học chú ý, đặc biệt là Euler, De Moivre, Vandermonde, ... Hiện nay đã có nhiều lời giải và phương pháp giải cũng có rất nhiều, trong đó có quy tắc: mỗi lần bố trí con mã ta chọn vị trí mà tại vị trí này số ô chưa dùng tới do nó khống chế là ít nhất. Một phương pháp khác dựa trên tính đối xứng của hai nửa bàn cờ. Ta tìm hành trình của con mã trên một nửa bàn cờ, rồi lấy đối xứng cho nửa bàn cờ còn lại, sau đó nối hành trình của hai nửa đã tìm lại với nhau. Trò chơi và câu đố trên dẫn tới việc khảo sát một lớp đồ thị đặc biệt, đó là đồ thị Hamilton. C B D A E J L H T K I O P F M G S R N Q * Định nghĩa: Chu trình (t.ư. đường đi) sơ cấp chứa tất cả các đỉnh của đồ thị (vô hướng hoặc có hướng) G được gọi là chu trình (t.ư. đường đi) Hamilton. Một đồ thị có chứa một chu trình (t.ư. đường đi) Hamilton được gọi là đồ thị Hamilton (t.ư. nửa Hamilton). Hình 1.18. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị Đồ thị Hamilton (hình thập nhị diện đều biểu diẽn trong mặt phẳng) với chu trình Hamilton A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A (đường tô đậm). Xét đồ thị có hướng G gồm n đỉnh sao cho mỗi đỉnh ứng với một đấu thủ và có một cung nối từ đỉnh u đến đỉnh v nếu đấu thủ ứng với u thắng đấu thủ ứng với v. Như vậy, đồ thị G có tính chất là với hai đỉnh phân biệt bất kỳ u và v, có một và chỉ một trong hai cung (u,v) hoặc (v,u), đồ thị như thế được gọi là đồ thị có hướng đầy đủ. Từ Mệnh đề 4.2.2 dưới đây, G là một đồ thị nửa Hamilton. Khi đó đường đi Hamilton trong G cho ta sự sắp xếp cần tìm. Đường đi Hamilton tương tự đường đi Euler trong cách phát biểu: Đường đi Euler qua mọi cạnh (cung) của đồ thị đúng một lần, đường đi Hamilton qua mọi đỉnh của đồ thị đúng một lần. Tuy nhiên, nếu như bài toán tìm đường đi Euler trong một đồ thị đã được giải quyết trọn vẹn, dấu hiệu nhận biết một đồ thị Euler là khá đơn giản và dễ sử dụng, thì các bài toán về tìm đường đi Hamilton và xác định đồ thị Hamilton lại khó hơn rất nhiều. Đường đi Hamilton và đồ thị Hamilton có nhiều ý nghĩa thực tiễn và đã được nghiên cứu nhiều, nhưng vẫn còn những khó khăn lớn chưa ai vượt qua được. Người ta chỉ mới tìm được một vài điều kiện đủ để nhận biết một lớp rất nhỏ các đồ thị Hamilton và đồ thị nửa Hamilton. Sau đây là một vài kết quả. * Định lý (Rédei): Nếu G là một đồ thị có hướng đầy đủ thì G là đồ thị nửa Hamilton. Chứng minh: Giả sử G=(V,E) là đồ thị có hướng đầy đủ và a=(v1,v2, ..., vk-1, vk) là đường đi sơ cấp bất kỳ trong đồ thị G. -- Nếu a đã đi qua tất cả các đỉnh của G thì nó là một đường đi Hamilton của G. -- Nếu trong G còn có đỉnh nằm ngoài a, thì ta có thể bổ sung dần các đỉnh này vào a và cuối cùng nhận được đường đi Hamilton. Thật vậy, giả sử v là đỉnh tuỳ ý không nằm trên a. a) Nếu có cung nối v với v1 thì bổ sung v vào đầu của đường đi a để được a1=(v, v1, v2, ..., vk-1, vk). b) Nếu tồn tại chỉ số i (1 £ i £ k-1) mà từ vi có cung nối tới v và từ v có cung nối tới vi+1 thì ta chen v vào giữa vi và vi+1 để được đường đi sơ cấp a2=(v1, v2, ..., vi, v, vi+1, ..., vk). c) Nếu cả hai khả năng trên đều không xảy ra nghĩa là với mọi i (1 £ i £ k) vi đều có cung đi tới v. Khi đó bổ sung v vào cuối của đường đi a và được đường đi a3=(v1, v2, ..., vk-1, vk, v). Nếu đồ thị G có n đỉnh thì sau n-k bổ sung ta sẽ nhận được đường đi Hamilton. * Định lý (Dirac, 1952): Nếu G là một đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ hơn thì G là một đồ thị Hamilton. a b’ a' b y Chứng minh: Định lý được chứng minh bằng phản chứng. Giả sử G không có chu trình Hamilton. Ta thêm vào G một số đỉnh mới và nối mỗi đỉnh mới này với mọi đỉnh của G, ta được đồ thị G’. Giả sử k (>0) là số tối thiểu các đỉnh cần thiết để G’ chứa một chu trình Hamilton. Như vậy, G’ có n+k đỉnh. Hình 1.19. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị là chu trình Hamilton ayb ...a trong G’, trong đó a và b là các đỉnh của G, còn y là một trong các đỉnh mới. Khi đó b không kề với a, vì nếu trái lại thì ta có thể bỏ đỉnh y và được chu trình ab ...a, mâu thuẩn với giả thiết về tính chất nhỏ nhất của k. Ngoài ra, nếu a’ là một đỉnh kề nào đó của a (khác với y) và b’ là đỉnh nối tiếp ngay a’ trong chu trình P thì b’ không thể là đỉnh kề với b, vì nếu trái lại thì ta có thể thay P bởi chu trình aa’ ...bb’ ... a, trong đó không có y, mâu thuẩn với giả thiết về tính chất nhỏ nhất của k. Như vậy, với mỗi đỉnh kề với a, ta có một đỉnh không kề với b, tức là số đỉnh không kề với b không thể ít hơn số đỉnh kề với a (số đỉnh kề với a không nhỏ hơn +k). Mặt khác, theo giả thiết số đỉnh kề với b cũng không nhỏ hơn +k. Vì không có đỉnh nào vừa kề với b lại vừa không kề với b, nên số đỉnh của G’ không ít hơn 2(+k)=n+2k, mâu thuẩn với giả thiết là số đỉnh của G’ bằng n+k (k>0). Định lý được chứng minh. * Hệ quả: Nếu G là đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ hơn thì G là đồ thị nửa Hamilton. Chứng minh: Thêm vào G một đỉnh x và nối x với mọi đỉnh của G thì ta nhận được đơn đồ thị G’ có n+1 đỉnh và mỗi đỉnh có bậc không nhỏ hơn . Do đó theo Định lý 4.2.3, trong G’ có một chu trình Hamilton. Bỏ x ra khỏi chu trình này, ta nhận được đường đi Hamilton trong G. * Định lý (Ore, 1960): Nếu G là một đơn đồ thị có n đỉnh và bất kỳ hai đỉnh nào không kề nhau cũng có tổng số bậc không nhỏ hơn n thì G là một đồ thị Hamilton. * Định lý: Nếu G là đồ thị phân đôi với hai tập đỉnh là V1, V2 có số đỉnh cùng bằng n (n ³ 2) và bậc của mỗi đỉnh lớn hơn thì G là một đồ thị Hamilton. e f g h b a c d a e f g b c d a Hình 1.20. Đồ thị Hamilton Đồ thị G này có 8 đỉnh, đỉnh nào cũng Đồ thị G’ này có 5 đỉnh bậc 4 và 2 đỉnh có bậc 4, nên theo Định lý 4.2.3, G là bậc 2 kề nhau nên tổng số bậc a b b d e c của hai đỉnh đồ thị Hamilton. không kề nhau bất kỳ bằng 7 hoặc 8, nên theo Định lý 4.2.5, G’ là đồ thị Hamilton. Đồ thị phân đôi này có bậc của mỗi đỉnh bằng 2 hoặc 3 (> 3/2), nên theo Định lý 4.2.6, nó là đồ thị Hamilton. Hình 1. 21. Đồ thị phân đôi 1.2. Đồ thị có trọng số và bài toán tìm đường đi ngắn nhất Trong đời sống, chúng ta thường gặp những tình huống như sau: để đi từ địa điểm A đến địa điểm B trong thành phố, có nhiều đường đi, nhiều cách đi; có lúc ta chọn đường đi ngắn nhất (theo nghĩa cự ly), có lúc lại cần chọn đường đi nhanh nhất (theo nghĩa thời gian) và có lúc phải cân nhắc để chọn đường đi rẻ tiền nhất (theo nghĩa chi phí), v.v... Có thể coi sơ đồ của đường đi từ A đến B trong thành phố là một đồ thị, với đỉnh là các giao lộ (A và B coi như giao lộ), cạnh là đoạn đường nối hai giao lộ. Trên mỗi cạnh của đồ thị này, ta gán một số dương, ứng với chiều dài của đoạn đường, thời gian đi đoạn đường hoặc cước phí vận chuyển trên đoạn đường đó, ... Đồ thị có trọng số là đồ thị G=(V,E) mà mỗi cạnh (hoặc cung) eÎE được gán bởi một số thực m(e), gọi là trọng số của cạnh (hoặc cung) e. Trong phần này, trọng số của mỗi cạnh được xét là một số dương và còn gọi là chiều dài của cạnh đó. Mỗi đường đi từ đỉnh u đến đỉnh v, có chiều dài là m(u,v), bằng tổng chiều dài các cạnh mà nó đi qua. Khoảng cách d(u,v) giữa hai đỉnh u và v là chiều dài đường đi ngắn nhất (theo nghĩa m(u,v) nhỏ nhất) trong các đường đi từ u đến v. Có thể xem một đồ thị G bất kỳ là một đồ thị có trọng số mà mọi cạnh đều có chiều dài 1. Khi đó, khoảng cách d(u,v) giữa hai đỉnh u và v là chiều dài của đường đi từ u đến v ngắn nhất, tức là đường đi qua ít cạnh nhất. 1.2.1. Bài toán tìm đường đi ngắn nhất: Cho đơn đồ thị liên thông, có trọng số G=(V,E). Tìm khoảng cách d(u0,v) từ một đỉnh u0 cho trước đến một đỉnh v bất kỳ của G và tìm đường đi ngắn nhất từ u0 đến v. Có một số thuật toán tìm đường đi ngắn nhất; ở đây, ta có thuật toán do E. Dijkstra, nhà toán học người Hà Lan, đề xuất năm 1959. Trong phiên bản mà ta sẽ trình bày, người ta giả sử đồ thị là vô hướng, các trọng số là dương. Chỉ cần thay đổi đôi chút là có thể giải được bài toán tìm đường đi ngắn nhất trong đồ thị có hướng. Phương pháp của thuật toán Dijkstra là: xác định tuần tự đỉnh có khoảng cách đến u0 từ nhỏ đến lớn. Trước tiên, đỉnh có khoảng cách đến a nhỏ nhất chính là a, với d(u0,u0)=0. Trong các đỉnh v ¹ u0, tìm đỉnh có khoảng cách k1 đến u0 là nhỏ nhất. Đỉnh này phải là một trong các đỉnh kề với u0. Giả sử đó là u1. Ta có: d(u0,u1) = k1. Trong các đỉnh v ¹ u0 và v ¹ u1, tìm đỉnh có khoảng cách k2 đến u0 là nhỏ nhất. Đỉnh này phải là một trong các đỉnh kề với u0 hoặc với u1. Giả sử đó là u2. Ta có: d(u0,u2) = k2. Tiếp tục như trên, cho đến bao giờ tìm được khoảng cách từ u0 đến mọi đỉnh v của G. Nếu V={u0, u1, ..., un} thì: 0 = d(u0,u0) < d(u0,u1) < d(u0,u2) < ... < d(u0,un). 1.2.2. Thuật toán Dijkstra: procedure Dijkstra (G=(V,E) là đơn đồ thị liên thông, có trọng số với trọng số dương) {G có các đỉnh a=u0, u1, ..., un=z và trọng số m(ui,uj), với m(ui,uj) = ¥ nếu (ui,uj) không là một cạnh trong G} for i := 1 to n L(ui) := ¥ L(a) := 0 S := V \ {a} u := a while S ¹ Æ begin for tất cả các đỉnh v thuộc S if L(u) +m(u,v) < L(v) then L(v) := L(u)+m(u,v) u := đỉnh thuộc S có nhãn L(u) nhỏ nhất {L(u): độ dài đường đi ngắn nhất từ a đến u} S := S \ {u} end 1.2.3. Bài toán áp dụng: a n b e d g m h k 1 3 33 2 1 4 2 4 2 6 2 3 5 5 6 3 1 2 3 Tìm khoảng cách d(a,v) từ a đến mọi đỉnh v và tìm đường đi ngắn nhất từ a đến v cho trong đồ thị G sau. Hình 1.22. Tìm đường đi ngắn nhất d(a,v) của đồ thị Bảng1.22. Tìm đường đi ngắn nhất d(a,v) của đồ thị L(a) L(b) L(c) L(d) L(e) L(g) L(h) L(k) L(m) L(n) 0 ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ - 3 3 2 1 ¥ ¥ ¥ ¥ ¥ - - 5 2 2 ¥ ¥ ¥ ¥ 3 - - - 3 2 5 ¥ ¥ ¥ ¥ - - - - 4 6 3 ¥ ¥ ¥ - - - - - 6 6 4 ¥ ¥ - - - - - - 10 6 6 ¥ - - - - - - - 9 6 8 - - - - - - - 7 8 - - - - - - - - - - 8 * Định lý: Thuật toán Dijkstra tìm được đường đi ngắn nhất từ một đỉnh cho trước đến một đỉnh tuỳ ý trong đơn đồ thị vô hướng liên thông có trọng số. Chứng minh: Định lý được chứng minh bằng quy nạp. Tại bước k ta có giả thiết quy nạp là: (i) Nhãn của đỉnh v không thuộc S là độ dài của đường đi ngắn nhất từ đỉnh a tới đỉnh này; (ii) Nhãn của đỉnh v trong S là độ dài của đường đi ngắn nhất từ đỉnh a tới đỉnh này và đường đi này chỉ chứa các đỉnh (ngoài chính đỉnh này) không thuộc S. Khi k=0, tức là khi chưa có bước lặp nào được thực hiện, S=V \ {a}, vì thế độ dài của đường đi ngắn nhất từ a tới các đỉnh khác a là ¥ và độ dài của đường đi ngắn nhất từ a tới chính nó bằng 0 (ở đây, chúng ta cho phép đường đi không có cạnh). Do đó bước cơ sở là đúng. Giả sử giả thiết quy nạp là đúng với bước k. Gọi v là đỉnh lấy ra khỏi S ở bước lặp k+1, vì vậy v là đỉnh thuộc S ở cuối bước k có nhãn nhỏ nhất (nếu có nhiều đỉnh có nhãn nhỏ nhất thì có thể chọn một đỉnh nào đó làm v). Từ giả thiết quy nạp ta thấy rằng trước khi vào vòng lặp thứ k+1, các đỉnh không thuộc S đã được gán nhãn bằng độ dài của đường đi ngắn nhất từ a. Đỉnh v cũng vậy phải được gán nhãn bằng độ dài của đường đi ngắn nhất từ a. Nếu điều này không xảy ra thì ở cuối bước lặp thứ k sẽ có đường đi với độ dài nhỏ hơn Lk(v) chứa cả đỉnh thuộc S (vì Lk(v) là độ dài của đường đi ngắn nhất từ a tới v chứa chỉ các đỉnh không thuộc S sau bước lặp thứ k). Gọi u là đỉnh đầu tiên của đường đi này thuộc S. Đó là đường đi với độ dài nhỏ hơn Lk(v) từ a tới u chứa chỉ các đỉnh không thuộc S. Điều này trái với cách chọn v. Do đó (i) vẫn còn đúng ở cuối bước lặp k+1. Gọi u là đỉnh thuộc S sau bước k+1. Đường đi ngắn nhất từ a tới u chứa chỉ các đỉnh không thuộc S sẽ hoặc là chứa v hoặc là không. Nếu nó không chứa v thì theo giả thiết quy nạp độ dài của nó là Lk(v). Nếu nó chứa v thì nó sẽ tạo thành đường đi từ a tới v với độ dài có thể ngắn nhất và chứa chỉ các đỉnh không thuộc S khác v, kết thúc bằng cạnh từ v tới u. Khi đó độ dài của nó sẽ là Lk(v)+m(v,u). Điều đó chứng tỏ (ii) là đúng vì Lk+1(u)=min(Lk(u), Lk(v)+m(v,u)). * Mệnh đề: Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh cho trước đến một đỉnh tuỳ ý trong đơn đồ thị vô hướng liên thông có trọng số có độ phức tạp là O(n2). Chứng minh: Thuật toán dùng không quá n-1 bước lặp. Trong mỗi bước lặp, dùng không hơn 2(n-1) phép cộng và phép so sánh để sửa đổi nhãn của các đỉnh. Ngoài ra, một đỉnh thuộc Sk có nhãn nhỏ nhất nhờ không quá n-1 phép so sánh. Do đó thuật toán có độ phức tạp O(n2). 1.2.3. Thuật toán Floyd: Cho G=(V,E) là một đồ thị có hướng, có trọng số. Để tìm đường đi ngắn nhất giữa mọi cặp đỉnh của G, ta có thể áp dụng thuật toán Dijkstra nhiều lần hoặc áp dụng thuật toán Floyd được trình bày dưới đây. Giả sử V={v1, v2, ..., vn} và có ma trận trọng số là W º W0. Thuật toán Floyd xây dựng dãy các ma trận vuông cấp n là Wk (0 £ k £ n) như sau: procedure Xác định Wn for i := 1 to n for j := 1 to n W[i,j] := m(vi,vj) {W[i,j] là phần tử dòng i cột j của ma trận W0} for k := 1 to n if W[i,k] +W[k,j] < W[i,j] then W[i,j] := W[i,k] +W[k,j] {W[i,j] là phần tử dòng i cột j của ma trận Wk} Chương 2 LÝ THUYẾT MỜ VÀ ỨNG DỤNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH DẠNG KHOẢNG Một trong nền tảng của toán học hiện đại và các ngành khoa học cơ bản liên quan đến toán học là lý thuyết tập hợp, những khái niệm mới, hệ tiên đề mới làm thay đổi khái niệm tập hợp, dẫn đến thay đổi toàn bộ hệ thống tư duy toán học. Năm 1965 lần đầu tiên nhà toán học người Ba Lan L.A. Zadeh đã đưa ra khái niệm tập hợp mờ. Dựa trên khái niệm mới này nhiều lĩnh vựa của toán học và các ứng dụng mới được phát triển mang lại hiệu quả bất ngờ. 2.1. Khái niệm tập mờ 2.1.1. Định nghĩa tập mờ Tập mờ A được xác định trên không gian nền kinh điển X là một tập mà mỗi phần tử của nó là một cặp trong đó x Î X và là ánh xạ Ánh xạ được gọi là hàm liên thuộc (hàm phụ thuộc) của tập mờ A. Hình 1.1. Tập mờ Giả sử tập mờ B các số tự nhiên nhỏ hơn nhiều so với 6. Xác định phụ thuộc hàm có dạng liệt kê sau: B = {(1,1),(2,1),(3,0.8),(4,0.7)} Các số tự nhiên 1 và 2 có độ phụ thuộc = 1 và=1 ; các số tự nhiên 3 và 4 có độ phụ thuộc nhỏ hơn 1 = 0,8 và = 0,07. Những số không được liệt kê đều có độ phụ thuộc bằng 0. Sử dụng hàm liên thuộc để tính độ phụ thuộc của phần tử x nào đó có ba cách: Tính trực tiếp (nếu cho trước dưới dạng công thức tường minh) hoặc Tra bảng (nếu dưới dạng bảng ) Tìm các giá trị tương ứng trên đồ thị (nếu được biểu diễn dạng đồ thị ) Trong nhiều tài liệu để biểu diễn tập mờ người ta cũng thường dùng ký hiệu sau: Cho các tập hữu hạn và cho tập vô hạn. Phép cộng (+) được hiểu là phép hợp. Ví dụ. Đồ thị hàm liên thuộc của tập mờ 1 m1 m2 m3 m4 Hình 2. 2 Đồ thị hàm liên thuộc của tập mờ Các hàm liên thuộc có dạng “trơn” như ở hình vẽ được gọi là hàm liên thuộc kiểu S. Đối với hàm liên thuộc kiểu S do các công thức biểu diễn có độ phức tạp lớn nên thời gian tính độ phụ thuộc cho một phần tử lâu. Bởi vậy trong kỹ thuật điều khiển mờ thông thường các hàm liên thuộc kiển S hay được thay gần đúng bằng một hàm tuyến tính từng đoạn. Một hàm liên thuộc có dạng tuyến tính từng đoạn được gọi là hàm liên thuộc có mức chuyển đổi tuyến tính. Hàm liên thuộc như ở hình vẽ với m1=m2 và m3=m4 chính là hàm thuộc của một tập kinh điển 2.1.2. Một số khái niệm của tập mờ Trong những ví dụ trên các hàm liên thuộc đều có độ cao bằng 1. Điều đó nói rằng các tập mờ đó đều có ít nhất một phần tử với độ phụ thuộc bằng 1. Trong thực tế không phải tập mờ nào cũng có phần tử có độ phụ thuộc bằng 1. Tương ứng với điều đó thì không phải mọi hàm liên thuộc đều có độ cao là 1. Định nghĩa 1. Độ cao của một tập mờ A trên không gian nền X là giá trị . Ký hiệu chỉ giá trị nhỏ nhất trong tất cả các giá trị chặn trên của hàm . Một tập mờ với ít nhất một phần tử có độ phụ thuộc bằng 1 được gọi là tập mờ chính tắc tức là h =1 ngược lại một tập mờ A với h < 1 được gọi là tập mờ không chính tắc. Bên cạnh khái niệm về độ cao mỗi tập mờ A còn có hai khái niệm quan trọng khác là: miền xác định và miền tin cậy Định nghĩa 2. Miền xác định của tập mờ A trên không gian nền X được ký hiệu bởi S là tập con của X thoả mãn Ký hiệu supp viết tắt của từ tiếng Anh support đã chỉ rõ là tập con trong X chứa các phần tử x mà tại đó hàm có giá trị dương Định nghĩa 3. Miền tin cậy của tập mờ tập mờ A trên không gian nền X được ký hiệu bởi T là tập con của X thoả mãn Định nghĩa 4. Miền biên của tập mờ tập mờ A trên không gian nền X được ký hiệu bởi U là tập con của X thoả mãn Miền U Miền tin cậy Miền xác định Hình 2.3. Miền của tập mờ Định nghĩa 5. Tập cắt a (aÎ [0,1]) của tập mờ tập mờ A trên không gian nền X được ký hiệu bởi Aa là tập con của X thoả mãn Aa = {x / mA(x) £ a } và được gọi là tập cắt mạnh nếu Aa+ = {x / mA(x) < a } Định nghĩa 6. Tập mức, hay là tập các nhát cắt của tập mờ tập mờ A trên không gian nền X được ký hiệu bởi L(A) là tập các tập con của X thoả mãn A = {x / mA(x) = a } với aÎ [0,1] Định nghĩa 7. Tập mờ A trên không gian nền X tuyến tính được gọi là tập mờ lồi nếu mA(x) thoả mãn mA(lx1 +(1-l)x2) ³ min{mA(x1), mA(x2)}I với " x1, x2Î X, " l Î [0,1] Định nghĩa 8. Lực lượng của tập mờ A trên không gian nền X được biểu diễn như sau: 2.1.3. Các ví dụ về tập mờ Ví dụ. Tập đánh giá nhiệt độ của thời tiết Lạnh = Ví dụ trên có thể được hiểu như sau: - Nếu nhiệt độ thấp hơn 10oC ( -45< x <10 ) tất cả mọi người đều đánh giá mức độ lạnh là 1 (tương ứng với 100%). - Nếu nhiệt độ đạt khoảng từ 10oC đến 20oC ( 10≤ x ≤20) thì số người đánh giá mức độ lạnh khác nhau nằm trong khoảng từ 0 ( 0% ) đến 1 (100%), đạt 15oC mức độ lạnh được đánh giá 0.5 (tương ứng với việc có 50% số người cho là lạnh), nếu nhiệt độ là 17oC mức độ lạnh được đánh giá 0.3 (tương ứng với việc có 30% số người cho là lạnh), . . . Ta có đồ thị sau: 1 10 15 17 20 0.5 0.3 Hình 2.4. Đồ thị đánh giá Ví dụ. Đánh giá nhiệt độ của thời tiết Lạnh = Mát = Ấm = Nóng = 1 10 20 30 40 m lạnh m mát m ấm m nóng Hình 2. 5. Đồ thị đánh giá nhiệt độ 2.2. Các phép toán trên tập mờ Những phép toán cơ bản trên tập mờ là phép hợp, phép giao và phép bù giống như định nghĩa về tập mờ các phép toán trên tập mờ cũng sẽ được định nghĩa thông qua các hàm liên thuộc được xây dựng tương tự như các hàm thuộc của các phép hợp, giao, bù giữa hai tập hợp kinh điển. Nói cách khác việc xây dựng các phép toán trên tập mờ được hiểu là việc xác định các hàm liên thuộc cho phép hợp AÈB, giao AÇB, bù A …từ những tập mờ A, B. Một nguyên tắc cơ bản trong việc xây dựng các phép toán trên tập mờ là không được mâu thuẫn với những phép toán đã có trong lý thuyết tập hợp kinh điển. Mặc dù không giống tập hợp kinh điển, hàm liên thuộc của các tập mờ AÈB, giao AÇ B , bù A… được định nghĩa cùng với tập mờ, song sẽ không mâu thuẫn với các phép toán tương tự của tập hợp kinh điển nếu như chúng thoả mãn những tính chất tổng quát được phát biểu như “tiên đề” của lý thuyết tập hợp kinh điển. Đó là các “tiên đề” cho phép giao AÇB, phép hợp và phép bù. 2.2.1. Các phép toán trên tập hợp. 2.2.1.1. Phép hợp Hợp của hai tập hợp A và B ký hiệu là A È B là một tập hợp chứa tất cả các phần tử của A và chứa tất cả các phần tử của B. A È B = {x/ xÎA hoặc xÎB } 2.2.1.2. Phép giao Giao của hai tập hợp A và B ký hiệu là AÇB là một tập hợp gồm các phần tử vừa thuộc A , vừa thuộc B. A Ç B = {x/ xÎA và xÎB } 2.2.1.3. Phép hiệu Cho hai tập hợp A và B. Hiệu của A và B ký hiệu là A\B một tập hợp gồm các phần tử thuộc A , nhưng không thuộc B. A \ B = {x/ xÎA và xÏB } 2.2.1.4. Phép lấy phần bù Cho A là tập con của tập X. Phần bù của A trong X ký hiệu là AX một tập hợp gồm các phần tử thuộc X , nhưng không thuộc A. AX = {x/ xÎX và xÏA } 2.2.1.5. Phép hiệu đối xứng Cho hai tập hợp A và B. Hiệu đối xứng của A và B ký hiệu là AÑ B một tập hợp gồm các phần tử thuộc A hoặc thuộc B, nhưng không thuộc A Ç B . AÑ B = (A È B) \ (A Ç B) = (A \ B)È (B \ A) Như vậy phép hiệu đối xứng cho phép đánh giá độ sai lệch giữa hai tập A và B. Đứng trên quan điểm so sánh ta có thể coi nếu N(AÑ B) càng “bé” thì tập A càng ít sai khác so với tập B. 2.2.1.6. Tích Đề các Cho hai tập hợp A và B. Tích Đề các của A và B ký hiệu là A X B một tập hợp mà mỗi phần tử của nó là một cặp có thứ tự phần tử (a,b) với a thuộc A và b thuộc B. A X B = { (a,b)/ aÎA; bÎB) } Ta có thể mở rộng cho tích Đề các của n tập hợp. A1 X A2 X . . . X An= { (a1,a2,...,an )/ ai ÎAi} 2.2.2. Khái niệm hàm liên thuộc Như trên đã trình bày, nếu A là một tập hợp trong không gian nền X, khi đó phần tử x bất kỳ của X, chỉ có thể có hai khả năng xảy ra, hoặc xÎA hoặc aÏA , như vậy để đánh giá khả năng thuộc vào tập A của các phần tử x trong không gian nền X, người ta có thể xây dựng một ánh xạ hàm gọi là hàm liên thuộc (Membership Function). Hàm liên thuộc định nghĩa cho tập A trên không gian nền X trong khái niệm tập hợp kinh điển chỉ có hai giá trị là 1 nếu xÎA hoặc 0 nếu xÏA. = Ví dụ . A = { xÎR/ 2 < x< 6 } Hình sau mô tả hàm thuộc của tập A : 2 6 Hình 2.6 Ví dụ hàm liên thuộc 2.3. Mệnh đề và công thức 2.3.1. Khái niệm mệnh đề Mệnh đề logic được hiểu như là một khẳng định chỉ cho phép trả lời đúng hoặc sai. Mệnh đề sơ cấp là mệnh đề không thể tách nhỏ hơn, nói cách khác nếu ta bỏ đi một phần của nó thì không còn là mệnh đề nữa. Ví dụ. "6 là một số chẵn" là một mệnh đề sơ cấp nhận giá trị "đúng" hay còn gọi có giá trị chân lý là 1. "Với mọi số nguyên dương n, đều có số nguyên lớn hơn nó" là một mệnh đề sơ cấp nhận giá trị "đúng" hay giá trị 1 "Mua hai vé xem ca nhạc vào tối mai " không phải là một mệnh đề. "2000 là một số chẵn và chia hết cho 10 " không phải là một mệnh đề sơ cấp, vì nó có thể tách thành hai mệnh đề đơn giản hơn. 2.3.2. Các kí hiệu Khi thành lập mệnh đề phức tạp từ các mệnh đề đã có, ta thường dùng các liên từ "hay", "và", "không", "nếu ... thì ..." các liên từ cũng dùng để biểu diễn các phép toán logic mà chúng ta sẽ đề cập ở mục sau. Các mệnh đề sơ cấp ta kí hiệu bằng các chữ cái A, B, C,....Các mệnh đề phức tạp được xây dựng từ các mệnh đề sơ cấp gọi là công thức. Giá trị của công thức là giá trị của các phép toán cho các trường hợp, sau khi các mệnh đề sơ cấp đã có những giá trị xác định. Giá trị của công thức thường được mô tả dạng bảng, theo các trường hợp tương ứng của các mệnh đề sơ cấp, bảng này còn gọi là bảng "chân lý" của công thức. Hai công thức được gọi là đồng nhất bằng nhau, nếu chúng cùng nhận giá trị như nhau cho mọi trường hợp giá trị của các mệnh đề sơ cấp tương ứng. 2.3.3. Các phép toán trên mệnh đề * Phép phủ định. Phủ định của một mệnh đề là một mệnh đề, nhận giá trị đúng nếu mệnh đề đã cho sai và nhận giá trị sai nếu mệnh đề đã cho đúng. Nếu A là mệnh đề, kí hiệu là phủ định của nó. Bảng 1.1. Phép phủ định A 0 1 1 0 Ví dụ. A = “Lan có tiền” khi đó sẽ là “Lan không có tiền” B= “Trái đất là hành tinh duy nhất có sự sống”, = “Trái đất không phải là hành tinh duy nhất có sự sống” * Phép “hoặc” hay còn gọi là phép cộng logic. Cho A và B là hai mệnh đề, liên kết A hoặc B là một mệnh đề chỉ nhận giá trị sai nếu cả hai mệnh đề đã cho cùng sai, kí hiệu AÚB. Bảng 1.2. Phép hoặc A B A Ú B 0 0 0 1 0 1 0 1 1 1 1 1 Ví dụ. A= “n là một số chẵn”, B= “n là một số chia hết cho 3” AÚB =” n là một số chẵn hoặc chia hết cho 3” Khi đó với n= 4 mệnh đề trên đúng, n= 9 mệnh đề trên đúng, n= 6 mệnh đề trên đúng, n= 7 mệnh đề trên sai. * Phép “và ” hay còn gọi là phép nhân logic. Cho A và B là hai mệnh đề, liên kết A và B là một mệnh đề chỉ nhận giá trị đúng nếu cả hai mệnh đề đã cho cùng đúng, kí hiệu AÙB. Bảng 1.3. Phép nhân logic A B A Ù B 0 0 0 1 0 0 0 1 0 1 1 1 Ví dụ. Cho A, B là các mệnh đề như trong ví dụ I.4, AÙB =” n là một số chẵn và chia hết cho 3” Khi đó với n= 4 mệnh đề trên sai, n= 9 mệnh đề trên sai, n= 7 mệnh đề trên sai, n= 6 mệnh đề trên đúng. * Phép cộng XOR. Cho A và B là hai mệnh đề, liên kết A XOR B là một mệnh đề chỉ nhận giá trị đúng nếu chỉ một trong hai mệnh đề đã cho đúng, kí hiệu AÅB. Bảng 1.4. Phép cộng XOR A B AÅB 0 0 0 1 0 1 0 1 1 1 1 0 Ví dụ. A=” n là một số chẵn”, B=” m là một số lẻ”, trong trường hợp này ta có thể định nghĩa AÅB = “n+m là một số chẵn” Khi đó với n=3 , m=4 mệnh đề trên sai; n=4, m=6 mệnh đề trên đúng, n= 7, m=3 mệnh đề trên đúng, n= 4, m=3 mệnh đề trên sai. Phép toán Å thường được sử dụng để kiểm tra tính chẵn lẻ. * Phép kéo theo. Cho A và B là hai mệnh đề, liên kết A kéo theo B (còn được phát biểu dạng nếu A thì B) là một mệnh đề chỉ nhận giá trị sai nếu A đúng, B sai, kí hiệu A ® B. Bảng 1.5. Phép kéo theo A B A ® B 0 0 1 1 0 0 0 1 1 1 1 1 Ví dụ. A=” n là một số chẵn”, B=” n là một số chia hết cho 2”, A ® B = “n là một số chẵn ” suy ra ” n chia hết cho 2” A=” Lan là một sinh viên chăm chỉ”, B=” Lan là một sinh viên giỏi”, A ® B = Nếu “Lan là một sinh viên chăm chỉ ” thì ” Lan là một sinh viên giỏi” * Phép tương đương (còn gọi là mệnh đề khi và chỉ khi). Cho A và B là hai mệnh đề, liên kết A tương đương B là một mệnh đề nhận giá trị đúng nếu cả hai mệnh đề đã cho cùng đúng, hoặc cùng sai, kí hiệu A«B. Bảng 1.6. Phép tương đương A B A « B 0 0 1 1 0 0 0 1 0 1 1 1 Ví dụ. A=” n là một số chẵn”, B=” n là một số chia hết cho 2”, A « B = ” n là một số chẵn” khi và chỉ khi ” n là một số chia hết cho 2” 2.3.4. Các tính chất 1. Công thức De Morgan Các công thức sau được gọi là công thức De Morgan logic (2.1) Để chứng minh các công thức này ta chỉ cần kiểm tra bảng chân lý sau: Bảng 1.7. Bảng chân lý A B A B 1 1 0 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 * Các tính chất Một số tính chất cơ bản sau đây ta có thể dễ dàng chứng minh bằng cách lập và so sánh các bảng chân lý tương ứng. a- b- A « B = ( A ® B ) Ù ( B ® A ) c- 2.4. Suy luận xấp xỉ dựa trên logic mờ Suy diễn xấp xỉ hay còn gọi là suy luận mờ đó là quá trình suy ra những kết luận dưới dạng các mệnh đề mờ trong điều kiện các quy tắc, các luật, dữ liệu đầu vào cho trước cũng không hoàn toàn xác định. Trong công trình của mình Zadeh đưa ra khái niệm lập luận xấp xỉ như sau: Bảng 1.8. Suy luận xấp xỉ Tiền đề 1 Nếu màu của quả cà chua nào đó là đỏ thì quả cà chua đó là chín. Điều kiện Màu của cà chua Q là rất đỏ. Kết luận Quả cà chua Q rất chín. Chúng ta thấy lược đồ này tương tự như luật Modus ponens trong logic kinh điển: A Þ B, có A cho phép ta rút ra kết luận B. Tuy nhiên ở lược đồ trên trong giả thiết (tiền đề) ta không có A mà có A' =' Rất đỏ' một biến tướng của A, khi đó ta có thể rút ra kết luận nào đó xấp xỉ B là B' = 'Rất chín' chẳng hạn. Vấn đề là cần xây dựng phương pháp luận cho phép lựa chọn kết luận B' như thế nào phù hợp với quy luật thực tiễn. Nhờ tính mềm dẻo của phương pháp lập luận mờ chúng ta sẽ có nhiều phương pháp suy diễn xấp xỉ. Xét lược đồ lập luận mờ đa điều kiện sau: Bảng 1.9. Bảng điều kiện suy diễn xấp sỉ Tiên đề 1 if X = A1 then Y = B1 Tiên đề 2 if X = A2 then Y = B2 : : : : Tiên đề n if X = An then Y = Bn Tiên đề n+1 if X = An+1 then Y = Bn+1 Kết luận Y = B0 Trong đó Ai và Bi là các điều kiện mờ, mô hình này mô tả quan hệ phụ thuộc giữa hai đại lượng A và B. Giá trị X = A0 được gọi là Input còn Y = B0 gọi là Output. Phương pháp lập luận xấp xỉ tính Y = B0 gồm các bước sau: Bước 1. Giải nghĩa các mệnh đề điều kiện: Chúng ta xem các khái niệm mờ Ai, Bi là các nhãn của tập mờ biểu thị ngữ nghĩa của Ai, Bi. Để cho tiện ta ký hiệu hàm giá trị chân lý tương ứng Ai(u) và Bi(v) trên không gian tham chiếu U và V. Một cách trực cảm, mỗi mệnh đề Nếu . . . thì được hiểu là một phép kéo theo logic mờ Ai(u) Þ Bi(v) . Khi u và v biến thiên, biểu thức này xác định ánh xạ hàm giá trị chân lý mi : UX V ® [0,1]. Bước 2. Kết nhập (aggregation): Qua các phép toán logic mờ chúng ta thu được công thức dạng trong đó @ là một trong các công thức mô tả giá trị chân lý của các phép toán logic hội và tuyển ( chẳng hạn ta có thể chọn các hàm tương ứng là ( Min và Max). Việc kết nhập như vậy bảo đảm m chứa các thông tin được cho bởi các mệnh đề if . . then dạng mệnh đề logic mờ. Bước 3. Tính OutputB0: Để tính B0 ta sử dụng công thức B0 = A0om , trong đó o là phép hợp thành của A0 và m. Bước 4. Khử mờ: Kết quả tính ở bước 3 là một giá trị mờ. Trong nhiều bài toán điều khiển người ta cần xác định giá trị thực của biến trong Y. Phương pháp tính giá trị thực "tương ứng" với giá trị chân lý của B0 được gọi là phương pháp khử mờ. Sẽ không có phương pháp nào "tốt nhất" được đưa ra mà chỉ có thể đánh giá theo một giá trị ngưỡng nào đó tuỳ thuộc quá trình thử nghiệm hoặc trực cảm nào đó. Ví dụ ta có thể khử mờ theo trung bình cộng có trọng số, được cho bởi công thức: Có thể hình dung phương phương pháp lập luận mờ bằng mô hình tổng quát sau: Input A0 Phương pháp lập luận và suy diễn xấp xỉ Output B0 Bảng 2.7. Mô hình suy diễn xấp sỉ 2.5. Ứng dụng logic mờ xây dựng bài toán tối ưu mờ 2.5.1. Tối ưu mờ Tối ưu mò (Fuzzy Optimization) hiện nay cũng được rất nhiều người quan tâm, các kết quả trong lĩnh vực này đã đạt được nhiều thành tựu quan trọng. Như chúng ta đều biết bản chất của bài toán tối ưu là tìm trong tập các phương án chấp nhận được, phương án tốt nhất theo tiêu chí nào đó mà có thể chấp nhận được là mờ. Bài toán hàm mục tiêu là mờ. Bài toán điều kiện tập chấp nhận được là mờ. Bài toán hàm mục tiêu và điều kiện tập chấp nhận được là mờ. 2.5.1.1. Quy hoạch tuyến tính mờ * Bài toán Xét bài toán quy hoạch tuyến tính tổng quát min{} (6) , với điều kiện (7) (8) Trong đó: (6) Hàm mục tiêu Là một tổ hợp tuyến tính của các biến số, biểu thị một đại lượng nào đó mà ta cần phải quan tâm của bài toán. (7) Các ràng buộc của bài toán Là các phương trình hoặc bất phương trình tuyến tính n biến số, sinh ra từ điều kiện của bài toán. (8) Các hạn chế về dấu của các biến số. Trong truờng hợp đặc biệt, bài toán quy hoạch tuyến tính có dạng min{} (9) với điều kiện (10) (11) Bài toán có dạng (9), (10), (11) được gọi là bài toán quy hoạch tuyến tính dạng chính tắc. Bài toán quy hoạch tuyến tính tổng quát có thể đưa về bài toán quy hoạch tuyến tính dạng chính tắc tương đương nhờ các quy tắc sau. + Nếu có bất đẳng thức hoặc thì ta đưa thêm ẩn phụ với hệ số hàm mục tiêu để có hoặc + Nếu có ẩn chưa ràng buộc về dấu, thì có thể thay nó bởi hai biến mới và không âm, với . Ví dụ: Đưa bài toán sau về dạng chính tắc min Với điều kiện Ta đưa thêm ẩn phụ và thay bởi với để có min Với điều kiện Như vậy từ nay về sau ta chỉ cần nghiên cứu bài toán quy hoạch tuyến tính ở dạng chính tắc. 2.5.1.2. Quy hoạch tuyến tính mờ dạng khoảng Trong phần này chúng ta xem xét bài toán quy hoạch tuyến tính mờ dạng khoảng như sau Với điều kiện (12) ở đây các tham số và được xem như các khoảng trong R. Ví dụ: và khi đó và là các giới hạn trên và dưới ứng với các khoảng, các giá trị hàm liên thuộc của và là các hàm số đặc trưng của khoảng. Chương 3 XÂY DỰNG GIẢI THUẬT GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT BIỂU DIỄN CUNG ĐƯỜNG ĐI LÀ SỐ MỜ DẠNG KHOẢNG Giả sử xét đồ thị có hướng G=(V,E) mỗi cung (u,v)E được đặt tương ứng là số mờ dạng khoảng. Các bài toán đường đi ngắn nhất được chia thành 3 dạng chính: Tìm đường đi ngắn nhất từ một nút nguồn đến một nút đích Tìm đường đi ngắn nhất từ một nút nguồn đến tất cả các nút đích Tìm đường đi ngắn nhất giữa hai nút bất kỳ. Bài toán được đề cập đến ở đây là bài toán ở dạng thứ nhất: tìm đường đi ngắn nhất từ một nút nguồn đến một nút đích cho trước. Input: Tập hữu hạn các đỉnh V, tập các cung E, nút nguồn 1; nút đích: n Tải năng (hoặc chiều dài) của các cung Output Đường đi ngắn nhất từ đỉnh 1 đến đỉnh n Mục đích chính là chuyển bài toán đường đi ngắn nhất về dạng bài toán quy hoạch tuyến tính. * Xây dựng đường đi trong đồ thị: Theo định nghĩa với bài toán đường đi ngắn nhất ta xây dựng đường đi trên cung i,j là một hàm x(i,j) thỏa mãn các tính chất sau: - xij=0 hoặc xij=1 ứng với việc có hay không sử dụng cung i,j trong đường đi Tổng đường đi ra tại nút nguồn bằng 1; tổng đường đi vào tại nút đích bằng 1 Tổng đường đi vào một nút i bất kỳ bằng tổng đường đi ra tại nút đó. * Giới hạn đường đi: Đường đi trên cung không vượt quá tải năng của cung * Cân bằng đường đi tại nút đỉnh: Tổng đường đi vào tại một đỉnh bằng tổng đường đi ra tại đỉnh đó (trừ đỉnh đầu và đỉnh đích) (với i là một đỉnh thông thường trong đồ thị) Tổng đường đi ra khỏi đỉnh nguồn bằng tổng đường đi vào đỉnh đích 3.1. Mô hình bài toán Gọi cij là chiều dài cung i,j. Bài toán đường đi ngắn nhất trong đồ thị được phát biểu như sau: * Hàm mục tiêu: Min * Các ràng buộc: hoặc 1 i=1,2,..,n j=1,2,..,n 3.2. Ví dụ 1 2 3 5 4 6 Giả sử có đồ thị G(u,v) như trong sơ đồ 1. Ta chuyển bài toán tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 6 về bài toán quy hoạch tuyến tính: Hàm mục tiêu: minimize Hình 3.1. Đồ thị G(u,v) có hướng Các ràng buộc: x12+x13 = 1 -x12 + x23 + x24+ x25 = 0 -x13 – x23 + x35 = 0 -x24 + x45 + x46 = 0 -x35 – x25 – x45 + x56 = 0 -x46 – x56 = -1 xij = 0 hoặc 1 3.3. Bài toán tìm đường đi ngắn nhất có các cung mờ Trong thực tế, chiều dài các cung của mạng không biểu thị bằng các số rõ mà hay được thể hiện thông qua các giá trị xấp xỉ. Ví dụ quãng đường từ A đến B khoảng 70 km. Trong những trường hợp này phải dùng số mờ để biểu diễn chiều dài các cung. Gọi là giá trị mờ của cung i,j. Khi đó bài toán đường đi ngắn nhất được phát biểu như sau: Hàm mục tiêu: Min Các ràng buộc: hoặc 1 i=1,2,..,n j=1,2,..,n Để giải quyết bài toán này, trước tiên chúng ta xem các cách biểu diễn số mờ . Sau đó trong chương sau sẽ giới thiệu thuật toán tìm đường đi ngắn nhất áp dụng trên các số mờ. 3.3.1. Xây dựng tập mờ Tập mờ A xác định trên không gian nền X là một tập hợp thỏa mãn: + Mỗi phần tử của A có dạng (x,mA(x)) + mA(x) là một ánh xạ từ X à [0,1] được gọi là hàm liên thuộc xác định độ thuộc của x vào tập A 3.3.2. Miền xác định của tập mờ: Miền xác định của tập mờ A trên không gian nền X là một tập con các phần tử của X được ký hiệu S thỏa mãn S= {xÎ X | mA(x) > 0} 3.3.3. Miền tin cậy của tập mờ Miền tin cậy của tập mờ A trên không gian nền X là một tập con các phần tử của X được ký hiệu T thỏa mãn T= {xÎ X | mA(x) = 1} 3.3.4. Miền biên của tập mờ Miền biên của tập mờ A trên không gian nền X là một tập con các phần tử của X được ký hiệu U thỏa mãn U= {xÎ X | 0< mA(x) <1} Ví dụ: Ta định nghĩa young - trẻ. Là tập hợp những người từ 20 tuổi trở xuống, những người từ 30 tuổi trở lên không còn trẻ nữa, nhưng những người từ 21 đến 30 tuổi vẫn thuộc tập Young với độ liên thuộc nào đó nhỏ hơn 1. Ta định nghĩa hàm liên thuộc của tập Young như sau: Hàm liên thuộc được thể hiện dưới dạng đồ thị như sau: 1 30 age(x) 20 Hình 3.2. Miền biên của tập mờ 3.4. Khái niệm số mờ 3.4.1. Định nghĩa số mờ Số mờ là một trường hợp đặc biệt của tập mờ khi hàm liên thuộc thỏa mãn các tính chất sau: - mA là normalized (miền tin cậy khác rỗng) - mA là singular (mỗi giá trị rõ phải thuộc miền tin cậy) - mA là đơn điệu tăng trên biên trái và đơn điệu giảm trên biên phải Trong ngôn ngữ nói, có thể mô tả số mờ với các từ như xấp xỉ, khoảng; gần đến,... 3.4.2. Số mờ dạng tam giác: - Là số mờ được mô tả kiểu "x xấp xỉ bằng a" - Biểu diễn một khoảng (a-a, a, a+b) - Hàm thuộc được xác định như sau: x 1 a3 a2 a1 x 0 Hình 3.3. Số mờ dạng tam giác 3.4.3. Số mờ dạng hình thang: - Là số mờ được mô tả kiểu "x khoảng từ a đến b" - Biểu diễn một khoảng (a-a, a, b,b+b) mA = - Hàm thuộc được xác định như sau: 1 a-a a b+b b Hình 3.4. Số mờ dạng hình thang Thường được biểu diễn qua bộ 4 số: Hình 3.4.Biểu diễn số mờ dạng hình thang 3.5. Một số phương pháp giải quyết bài toán 3.5.1. Phép toán thực hiện trên số mờ tam giác. Trình bày khái niệm về độ tương tự giữa hai số mờ tam giác và một giải thuật tìm đường đi ngắn nhất dựa trên các phép toán đã định nghĩa 3.5.1.1. Tổng hai số mờ: Giả sử có 2 số mờ dạng tam giác và Khi đó: 3.5.1.2. Chiều dài nhỏ nhất: Với hai số mờ tam giác và min min (a,b,c)=Min()=(min(a1,a2), min(b1,b2), min(c1,c2)) 3.5.1.3. Độ tương tự giữa hai số mờ: Giả sử có 2 số mờ dạng tam giác và Ta tìm cách thể hiện độ tương tự giữa hai số này. Khi giao của hai tam giác càng lớn thì độ tương tự giữa hai số mờ càng cao. Ký hiệu Si là độ tương tự giữa và 3.5.1.4. Giải thuật tìm đường đi mờ ngắn nhất Step1: Tìm tất cả các đường đi có thể từ đỉnh nguồn s đến đỉnh đích d Tính khoảng cách từng đường đi Step 2: Tìm min của tất cả các đường đi đã tính Step 3: Tính độ tương tự của từng đường đi với min Step 4: Đưa ra đường đi có độ tương tự lớn nhất 3.6. Ví dụ áp dụng bài toán: (56,58,72) 4 2 (88,92,134) * Ví dụ 1. Cho sơ đồ mạng như hình sau. Tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 6 (33,45,50) (32,40,46) 1 6 (51,79,85) (50,52,61) 5 (75,110,114) (42,57,61) 3 (43,55,60) Step1: Tính độ dài các đường đi có thể có từ đỉnh 1 đến đỉnh 6 P1: 1-2-3-5-6 à L1=(201,262,285) P2: 1-2-4-5-6 à L2=(196,253,282) P3: 1-2-4-6 à L3=(177,195,256) P4: 1-2-5-6 à L4=(159,234,249) P5: 1-3-5-6 à L5=(160,222,235) Step2: Tìm min Ta được min = (159,195,235) Step3: Tính độ tương tự giữa min và các Li Path S(L,min) Ranking P1: 1-2-3-5-6 6.81 5 P2: 1-2-4-5-6 9.11 4 P3: 1-2-4-6 36.70 2 P4: 1-2-5-6 27.9 3 P5: 1-3-5-6 36.76 1 Step4: Đưa ra đường đi có độ tương tự lớn nhất. Ta thu được kết quả đó là P5 đi qua các đỉnh 1-3-5-6. Chương 4 CÀI ĐẶT THỬ NGHIỆM 4.1. Một số giao diện của chương trình 4.1.1. Giao diện chính của chương trình Hình 4.1. Giao diện chính của chương trình 4.1.2. Các bước thực hiện chương trình. Hình 4.2. Các bước thực hiện 4.1.3. Các chức năng chính của chương trình 4.1.3.1. Thuật toán tìm đường đi ngắn nhất. Hình 4.3. Mô phỏng thuật toán 4.1.3.2. Chọn số đỉnh Hình 4.4. Chọn số đỉnh 4.1.3.3. Chọn số cung đường đi Hình 4.5. Chọn cung đường đi 4.1.3.4. Nhập các cung mờ Hình 4.6. Nhập các cung a, b, c và thông báo 4.1.3.5. Tìm tất cả các đường đi 4.1.3.5 Tìm tất cả các đường đi Hình 4.7. Tìm tất cả các đường đi 4.1.3.6. Tính giá trị L nhỏ nhất Hình 4.7. Tính giá trị Lmin 4.1.3.7. Tính độ tương tự Hình 4.8. Bảng độ tương tự 4.1.3.8. Tìm đường đi tối ưu Hình 4.9. Bảng thông báo kết quả tìm được 4.2. Cài đặt – thử nghiệm Chương trình được xây dựng bằng ngôn ngữ Visual studio 6.0, Sau khi chọn đỉnh chọn đường đi nhập dữ liệu cho các cung mờ của đồ thị. Hình 4.10. Chọn đỉnh nhập dữ liệu Hình 4.11. Kết quả kiểm tra xây dựng hàm liên thuộc Hình 4.9. Kết quả tất cả các đường đi Hình 4.9. Bảng kết quả tìm Lmin Hình 4.9. Bảng kết quả độ tương tự Hình 4.9. Bảng kết quả đường đi ngắn nhất 4.3. Đánh giá hiệu quả thuật toán đã xây dựng Qua quá trình nghiên cứu, xây dựng thuật toán tôi đã đề xuất trong báo cáo: ứng dụng các giải thuật tìm đường đi ngắn nhất cổ điển và logic mờ để cải tiến tìm đường đi ngắn nhất với dữ liệu cung mờ dạng khoảng. Giải thuật tìm đường đi ngắn nhất được xây dựng trên phương pháp là tìm tất cả các phương án đường đi từ đỉnh đầu đến đỉnh cuối và lọc ra phương án tối ưu nhất từ các cung mờ dạng khoảng. Chương trình đã được xây dựng dựa trên các giải thuật Tìm đường đi ngắn nhất nhưng chủ yếu áp dụng cho các trọng số được biểu diễn cung mờ dạng khoảng đã đưa ra kết quả tối ưu nhất cho bài toán. Với nghiên cứu của tôi đưa ra tập trung xoay quanh Kiểm tra hàm liên thuộc - Tìm ra tất cả các đường đi từ các cung mờ - Tìm ra độ dài cung mờ nhỏ nhất giá trị Lmin - Tính ra độ tương tự - Tìm ra đường đi ngắn nhất từ các cung mờ với độ tương tự cao nhất. Một vài hạn chế của phương pháp là chưa được quan tâm nhiều đến đa đỉnh >10 đa khoảng và Hệ tuyến tính đa mục tiêu. Chương trình xây dựng còn rất nghèo nàn chưa khoa học. KẾT LUẬN VÀ KIẾN NGHỊ 1. Kết luận Luận văn đã trình bày và giải quyết được một số vấn đề sau: Trình bày một cách tổng quan về lý thuyết đồ thị và thuật toán giải bài toán tìm đường đi ngắn nhất có trọng số xác định. Các giải thuật bao gồm ( Dijkstra, Bellman-Ford, Floyd...) và áp dụng giải bài toán mẫu theo giải thuật dijkstra. Lý thuyết mờ và ứng dụng giải bài toán quy hoạch tuyến tính dạng khoảng. Tìm ra phương án tối ưu trong bài toán: Bài toán hàm mục tiêu là mờ, bài toán điều kiện tập chấp nhận được là mờ, bài toán hàm mục tiêu và điều kiện tập chấp nhận được là mờ. Tập trung nghiên cứu xây dựng thuật toán xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất được biểu diễn dưới dạng cung đường đi là số mờ dạng khoảng. Các bài toán đường đi ngắn nhất được chia thành 3 dạng chính: Tìm đường đi ngắn nhất từ một nút nguồn đến một nút đích Tìm đường đi ngắn nhất từ một nút nguồn đến tất cả các nút đích Tìm đường đi ngắn nhất giữa hai nút bất kỳ. Bài toán được đề cập đến ở đây là bài toán ở dạng thứ nhất: tìm đường đi ngắn nhất từ một nút nguồn đến một nút đích cho trước. Mục đích chính là chuyển bài toán đường đi ngắn nhất về dạng bài toán quy hoạch tuyến tính dạng khoảng. Đồng thời chỉ ra được đường đi có các cung mờ ngắn nhất và đường đi tối ưu nhất dựa trên độ tương tự cao nhất 2. Kiến nghị Một trong những quan tâm hàng đầu là không chỉ tìm ra được đường đi có các cung mờ ngắn nhất và đường đi tối ưu nhất dựa trên độ tương tự cao nhất mà còn áp dụng được với bài toán dạng quy hoạch tuyến tính dạng khoảng và bài toán dạng quy hoạch tuyến đa mục tiêu. Như những hạn chế đã nêu ở phần trên thì hướng phát triển tiếp theo sẽ là quan tâm tới giải thuật bài toán quy hoạch tuyến đa mục tiêu TÀI LIỆU THAM KHẢO Tiếng Việt [1] PGS. TS Nguyễn Thiện Luận (2006), Toán rời rạc. Học Viện Kỹ Thuật Quân sự - Hà Nội. [2] PGS. TS Nguyễn Thiện Luận (2006), Lý thuyết mờ và ứng dụng. Học Viện Kỹ Thuật Quân sự - Hà Nội. [3] Nguyễn Doãn Phước (2001), Hệ mờ, mạng nơron và ứng dụng, NXB Khoa học kỹ thuật. [4] PGS. TS. Bùi Minh Trí (2006), Tối ưu hóa . Đại học Bách khoa - Hà Nội. Tiếng Anh [1] Bortolan, G. and R. Degani. 1985. A review of some methods for ranking fuzzy subsets, Fuzzy Sets and Systems 15, 1–19. [2] Buckley, J.J. 1987. The fuzzy mathematics of finance. Fuzzy Sets and Systems 21, 257–273. [3] Chen, S.-H .1985. Ranking Fuzzy Numbers with Maximizing Set and Minimizing Set, Fuzzy Sets and Systems 17, 113–129. [4] Cheng, C.-H. 1998. A New Approach for Ranking Fuzzy Numbers by Distance Method, Fuzzy Sets and Systems 95, 307–317. [5] Chuang T.N, Kung J.Y, 2005 .The fuzzy shortest path length and the corresponding shortest path in a network, Computers and Operations Research 32 , 1409–1428. [6] Delgado, M., J. L. Verdegay, and M. A. Vila. 1988. A Procedure for Ranking Fuzzy Numbers using Fuzzy Relations, Fuzzy Sets and Systems 26, 49–62. [7] Dubois D, Prade H. 1980. Fuzzy sets and systems: theory and applications. New York: Academic Press. [8] Dubois, D. and H. Prade. 1983. Ranking Fuzzy Numbers in the Setting of Possibility Theory, Information Sciences 30, 183–224. [9] Hansen P, Beckmann M, Kunzi HP. 1980. Multiple criteria decision making. In: Theory and applications, Lecture Note in Economics and in Mathematical Systems, vol. 177. Berlin: Springer, pp. 109–27. [10] Henig MI. 1994. Efficient interactive methods for a class of multi-attribute shortest path problems. Management Science, 40, 891–7. [11] Hyung LK, Song YS, Lee KM. 1994. Similarity measure between fuzzy sets and between elements. Fuzzy Sets and Systems, 62291–3. LÝ LỊCH TRÍCH NGANG Họ và tên: PHAN NHƯ MINH Ngày tháng năm sinh: 23/ 09/ 1978 Nơi sinh: Vĩnh Phúc Địa chỉ liên lạc: Khu tập thể . Trường CD GTVT – Vĩnh Yên – Vĩnh Phúc QUÁ TRÌNH ĐÀO TẠO - Từ tháng 9/1999 đến 7/2004: Học tại Đại học Khoa học tự nhiên - ĐHQGHN - Khoa tin học- Chuyên ngành tin học. QUÁ TRÌNH CÔNG TÁC - Từ 9/2004 đến 10/2008: Công tác tại Công ty máy tính Vinh Quang. Ngõ 16 – Khu tập thể Đại học thủy lợi. Đống đa – Hà Nội - Từ 15/2008 đến nay: Công tác tại trường Cao đẳng Giao thông vận tải.