Chương 4 Thuật toán tham lam

TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN KHOA KHOA HỌC MÁY TÍNH -----------***----------- THUẬT TOÁN (Algorithms) Nguyễn Thanh Cẩm Nguyễn Thanh Cẩm Nội Dung THUẬT TOÁN VÀ ĐỘ PHỨC TẠPC1 CHIA ĐỂ TRỊC2 QUY HOẠCH ĐỘNGC3 THUẬT TOÁN THAM LAMC4 THUẬT TOÁN QUAY LUIC5 Nguyễn Thanh Cẩm 4.1 4.2 Thuật toán tham lam Một số bài toán minh họa THUẬT TOÁN THAM LAM Nguyễn Thanh Cẩm 4.1 4.1.1 4.1.2 Thuật toán tham lam Đặc điểm chung của thuật toán tham lam Thuật toán tham lam THUẬT TOÁN THAM LAM Sự khác nhau giữa thuật toán tham lam và thuật toán quy hoạch động4.1.3 Nguyễn Thanh Cẩm 4.1.1 Đặc điểm chung của thuật toán tham lam Một bài toán thực hiện cấu trúc con tối ưu (optimal substructure) nếu cách giải quyết tối ưu của bài toán chứa đựng cách giải quyết tối ưu những bài toán con của nó.  Đối với nhiều bài toán, thuật toán tham lam hầu như không cho ra lời giải tối ưu toàn cục, vì chúng thường không chạy trên tất cả các trường hợp. Tuy nhiên, các thuật toán này vẫn hữu ích vì chúng dễ thiết kế và cho ra các ước lượng tốt về lời giải tối ưu.  Nếu một thuật toán tham lam cho ra kết quả tối ưu toàn cục cho một lớp bài toán nào đó, thì thuật toán thường sẽ được chọn lựa, vì nó chạy nhanh hơn các phương pháp tối ưu hóa khác như quy hoạch động … Nguyễn Thanh Cẩm 4.1.2 Thuật toán tham lam Thuật tham lam có 05 thành phần: Một tập hợp các ứng viên C (candidate), để từ đó tạo ra lời giải. Một hàm lựa chọn Select(C), để theo đó lựa chọn ứng viên tốt nhất để bổ sung vào lời giải. Một hàm khả thi Feasible(S  x), dùng để quyết định nếu một ứng viên có thể được dùng để xây dựng lời giải. Một hàm mục tiêu Solution(S), ấn định giá trị của lời giải hoặc một lời giải chưa hoàn chỉnh. Một hàm đánh giá, chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh. Nguyễn Thanh Cẩm 4.1.2 Thuật toán tham lam Thuật tham lam: void Greedy; //Giả sử C là tập các ứng cử viên { S = ; // S là lời giải xây dựng theo thuật toán While ( (C  0) and not Solution(S)) { x  Select(C); C = C\x; If (Feasible(S  x)) S = S  x } If (Solution(S) ) Return S } Nguyễn Thanh Cẩm 4.1.2 Thuật toán tham lam  Chúng minh tính đúng đắn:  Để chỉ ra thuật toán không cho lời giải đúng chỉ cần đư-a ra một phản ví dụ  Việc chứng minh thuật toán đúng khó hơn nhiều và ta sẽ nghiên cứu cụ thể trong phần sau đây :  Lập luận biến đổi (Exchange Argument)  Giả sử cần chứng minh thuật toán A cho lời giải đúng. A(I) là lời giải tìm được bởi thuật toán A đối với bộ dữ liệu I. Còn O là lời giải tối ưu của bài toán với bộ dữ liệu này.  Ta cần tìm cách xây dựng phép biến đổi  để biến đổi O thành O’ sao cho:  O’ cũng tốt không kém gì O (Nghĩa là O’ vẫn tối ưu).  O’ giống với A(I) nhiều hơn O.  Giả sử đã xây dựng được phép biến đổi vừa nêu. Để chứng minh tính đúng đắn dựa vào hai sơ đồ chứng minh sau  1) Chứng minh bằng phản chứng: Giả sử A không đúng đắn, hãy tìm bộ dữ liệu I sao cho A(I) khác với lời giải tối ưu của bài toán. Gọi O là lời giải tối ưu giống với A(I) nhất => A(I) khác O. Dùng phép biến đổi  chúng ta có thể biến đổi O  O’ sao cho O’ vẫn tối ưu và O’ giống với A(I) hơn => mâu thuẫn giả thiết O là lời giải tối ưu giống với A(I) nhất.  2) Chứng minh trực tiếp: O là lời giải tối ưu. Biến đổi O  O’ giống với A(I) hơn là O. Nếu O’ = A(I) thì A(I) chính là phương án tối ưu ngược lại biến đổi O’  O’’ giống với A(I) hơn. Cứ thế ta thu được dãy O’, O’’ ,O’’’ …..ngày càng giống hơn, và chỉ có một số hữu hạn điều kiện để so sánh nên chỉ sau một số hữu hạn lần phép biến đổi sẽ kết thúc và đó là tại A(I). Nguyễn Thanh Cẩm 4.1.3 Sự khác nhau giữa thuật toán tham lam và thuật toán quy hoạch động  Toàn bộ phương pháp tối ưu có thể đạt được, từ việc chọn tối ưu trong từng bước chọn. Về khía cạnh này, thuật toán tham lam khác với thuật toán quy hoạch động ở chỗ:  Trong quy hoạch động chúng ta thực hiện chọn cho từng bước, nhưng việc lựa chọn này phụ thuộc vào cách giải quyết các bài toán con.  Với thuật toán tham lam, tại mỗi bước chúng ta chọn bất cứ cái gì là tốt nhất vào thời điểm hiện tại, và sau đó giải quyết các vấn đề phát sinh từ việc chọn này. Vấn đề chọn thực hiện bởi thuật toán tham lam không phụ thuộc vào việc lựa chọn trong tương lai hay cách giải quyết các bài toán con.  Vì vậy khác với quy hoạch động, giải quyết các bài toán con theo kiểu bottom-up (từ dưới lên), thuật toán tham lam thường sử dụng giải pháp top-down (từ trên xuống). Nguyễn Thanh Cẩm 4.2 4.2.1 4.2.2 Một số bài toán minh họa Bài toán đường đi của người giao hàng Bài toán các đoạn thẳng không giao nhau THUẬT TOÁN THAM LAM Bài toán cái ba lô4.2.3 Bài toán cây khung nhỏ nhất4.2.4 Nguyễn Thanh Cẩm 4.2.1 Bài toán đường đi của người giao hàng  Bài toán: Có một người đi giao hàng, cần đi giao hàng tai n thành phố. Xuất phát tại một thành phố nào đó đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến 1 lần khoảng cách từ một thành phố đến các thành phố khác là xác định. Giả thiết rằng, mỗi thành phố đều có đường đi đến các thành phố còn lại. Khoảng cách giữa hai thành phố có thể là khoảng cách địa lý, có thể là cước phí di chuyển hoặc thời gian di chuyển. Ta gọi chung là độ dài. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất, hay nói cách khác là tìm một phương án có giá trị nhỏ nhất. Bài toán này cũng được gọi là bài toán người du lịch.  Một cách tổng quát, có thể không tồn tại một đường đi giữa hai thành phố a và b nào đó. Trong trường hợp đó ta cho đường đi ảo giữa a và b với độ dài bằng ∞ Nguyễn Thanh Cẩm 4.2.1 Bài toán đường đi của người giao hàng  Bài toán này có nhiều ứng dụng rất quan trọng. Thí dụ một máy hàn các điểm được điều khiển bởi máy tính. Nhiệm vụ của nó là hàn một số điểm dự định ở trên một tấm kim loại. Người thợ hàn bắt đầu từ một điểm ở bên ngoài tấm kim loại và kết thúc tại chính điểm này, do đó tấm kim loại phải được di chuyển đến điểm cần hàn được đưa vào vị trí hàn ( tương tự như ta đưa tấm vải vào đầu mũi kim của máy khâu). Cần tìm một phương án di chuyến tấm kim loại sao cho việc di chuyến ít nhất.  Hình ảnh sau minh họa bài toán trên:            Nguyễn Thanh Cẩm 4.2.1 Bài toán đường đi của người giao hàng  Với phương pháp véc cạn ta xét tất cả các chu trình, mỗi chu trình tính tổng độ dài các cạnh của nó rồi chọn một chu trình có tổng độ dài nhỏ nhất.  Tuy nhiên chúng ta cần xét tất cả (n-1)! chu trình. Thật vậy do mỗi chu trình đi qua tất cả các đỉnh (thành phố) nên ta cố định một đỉnh. Từ đỉnh này ta có n-1 cạnh tới n-1 đỉnh khác nên ta có n-1 cách chọn cạnh đầu tiên của chu trình. Sau khi đã chọn được cạnh đầu tiên chúng ta có n-2 cách chọn cạnh thứ hai, do đó ta có (n-1)(n-2) cách chọn hai cạnh. Cứ lý luận như vậy ta sẽ có (n-1)! cách chọn chu trình khác nhau. Và đó là một thuật toán với thời gian lớn hơn hàm mũ. Nguyễn Thanh Cẩm 4.2.1 Bài toán đường đi của người giao hàng  Áp dụng kỹ thuật tham lam ta có: B1: Sắp xếp các cạnh theo thứ tự tăng của độ dài B2: Xét các cạnh có độ dài từ nhỏ đến lớn để đưa vào chu trình B3: Một cạnh sẽ được đưa vào chu trình sẽ thỏa mãn: Không tạo thành một chu trình con Không tạo thành một đỉnh có cấp >= 3 Lặp lại bước ba cho đến khi được một chu trình. Nguyễn Thanh Cẩm 4.2.1 Bài toán đường đi của người giao hàng  Thí dụ: cho bài toán TSP với 6 đỉnh được cho bởi các tọa độ sau: c(1,7) d(15,7) b(4,3) e(15,4) a(0,0) f(18,0)  6 thành phố có tất cả 15 cạnh. Đó là các cạnh ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, ef. Độ dài các cạnh ở đây là khoảng cách Euclide trong đó cạnh de = 3 là nhỏ nhất nên de được chọn vào chu trình. Kế đến là 3 cạnh ab,bc ef đều có độ dài 5 cả 3 cạnh đều thỏa mãn hai điều kiện nói trên nên đều được chọn vào chu trình, cạnh có độ dài nhỏ nhất kế tiếp là ac = 7.08 nhưng không thể đưa cạnh này vào chu trình vì nó sẽ tạo ra chu trình con (abca) cạnh df cũng bị lý do tương tự. Cạnh be cũng được xem xét rồi cũng bị loại do tạo ra đỉnh b và đỉnh e có cấp 3, tương tự chúng ta cũng loại bd. cd là cạnh tiếp theo được xét và được chọn cuối cùng ta có chu trình abcdefa với tổng độ dài là 50. Đây chỉ là một phương án tốt. Phương án tối ưu là chu trình acdefba với tổng độ dài là 48.39 Nguyễn Thanh Cẩm 4.2.1 Bài toán đường đi của người giao hàng c(1,7) d(15,7) c(1,7) d(15,7) b(4,3) e(15,4) b(4,3) e(15,4) a(0,0) f(18,0) a(0,0) f(18,0) Nguyễn Thanh Cẩm 4.2.1 Bài toán đường đi của người giao hàng  Thuật toán: void Tsp { chutrinh = 0 // sắp xếp các cạnh trong E theo thứ tự tăng của độ dài Gia = 0 while E0 do { if(cạnh có thể chọn) //không tạo thành chu trình Chutrinh = chutrinh + [e] Gia = gia + đồdàicủa e } E = E – [e] }  Độ phức tạp của thuật toán: Với đồ thị n đỉnh đầy đủ ta có n(n-1)/2 cạnh. Hơn nữa thuật toán chỉ phụ thuộc vào việc sắp xếp theo sự không giảm theo độ dài của các cạnh. Nên độ phức tạp của thuật toán cỡ O(n) nếu chọn phương pháp sắp xếp QuickSort. Nguyễn Thanh Cẩm 4.2 4.2.1 4.2.2 Một số bài toán minh họa Bài toán đường đi của người giao hàng Bài toán các đoạn thẳng không giao nhau THUẬT TOÁN THAM LAM Bài toán cái ba lô4.2.3 Bài toán cây khung nhỏ nhất4.2.4 Nguyễn Thanh Cẩm 4.2.2 Bài toán các đoạn thẳng không giao nhau  Bài toán  Đầu vào: Cho họ các đoạn thẳng mở  Đầu ra: Tập các đoạn thẳng không giao nhau có lực lượng lớn nhất. Ứng dụng thực tế: Bài toán xếp thời gian biểu cho các hội thảo, bài toán phục vụ khách hành trên một máy, bài toán lựa chọn hành động (Ví dụ có n lời mời dự tiệc bắt đầu bởi ai kết thúc bởi bj, hãy lựa chọn sao cho đi đ-ược nhiều tiệc nhất). Nguyễn Thanh Cẩm 4.2.2 Bài toán các đoạn thẳng không giao nhau  Đề xuất các thuật toán:  Greedy 1: Sắp xếp các đoạn thẳng theo thứ tự tăng dần của đầu mút trái, bắt đầu từ tập S là tập rỗng, ta lần lượt xếp các đoạn thẳng trong danh sách đã sắp xếp và bổ sung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. Thuật toán: void Greedy1; { S = ; //S là tập các đoạn thẳng cần tìm While (C  0) { (ai, bi)  đoạn đầu tiên trong C; C = C\(ai, bi); If () S = S  (ai, bi) } } Nguyễn Thanh Cẩm 4.2.2 Bài toán các đoạn thẳng không giao nhau  Độ phức tạp của thuật toán chủ yếu là nằm ở thủ tục sắp xếp. Nếu có n đoạn thẳng thì ta cần cỡ O(nlogn) để sắp xếp bằng phương pháp sắp xếp MergeSort.  Tuy nhiên Greedy1 không cho lời giải tối ưu.  Ví dụ  Ta thấy rằng thuật toán sẽ lựa chọn dạ tiệc 1, trong khi phương án tối ưu của bài toán là (Dạ tiệc 2, Dạ tiệc 3) Nguyễn Thanh Cẩm 4.2.2 Bài toán các đoạn thẳng không giao nhau Greedy2: Ta chọn đoạn có độ dài ngắn nhất bổ xung vào S. Tuy nhiên thuật toán tham lam này cũng không cho kết quả tối ưu.  Sau đây là ví dụ  Khi đó thuật toán sẽ lựa chọn (dạ tiệc 1) trong khi lời giải tối ưu của thuật toán là (dạ tiệc 2, dạ tiệc 3). Nguyễn Thanh Cẩm 4.2.2 Bài toán các đoạn thẳng không giao nhau Greedy3: Xắp xếp các đoạn thẳng theo thứ tự không giảm của mút phải. Bắt đầu từ tập S là tập rỗng, ta lần lượt xét các đoạn trong danh sách theo thứ tự đã sắp xếp và bổ xung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. (Dạ tiệc nào kết thúc sớm sẽ được xét trước). Nguyễn Thanh Cẩm 4.2.2 Bài toán các đoạn thẳng không giao nhau  Mệnh đề 1: Thuật toán Greedy3 cho lời giải tối ưu của bài toán về các đoạn thẳng không giao nhau.  Chứng Minh: Giả sử Greedy3 không cho lời giải đúng. Phải tìm bộ dữ liệu C sao cho thuật toán không cho lời giải tối ưu. Giả sử G3(C) là lời giải tìm được bởi Greedy3. Gọi O là lời giải tối ưu có số đoạn thẳng chung với G3(C) là lớn nhất. Gọi X là đoạn thẳng đầu tiên có trong G3(C) nhưng không có trong O. Đoạn này là tồn tại, vì nếu trái lại thì G3(C)  O ( mâu thuẫn vì đã giả thiết G3(C)  O ) hay G3(C)  O ( Cũng mâu thuẫn vì khi đó thuật toán phải chọn đoạn thẳng X) (O cũng được sắp xếp giống G3(C)).  Gọi Y là đoạn đầu tiên kể từ bên trái của O không có mắt trong G3(C). Đoạn Y cũng phải tồn tại (Chứng minh tương tự như trên).  Khi đó mút phải của đoạn X phải ở bên trái (nhỏ hơn) mút phải của đoạn Y, vì nếu trái lại thuật toán sẽ chọn Y thay vì X. Xét Rõ ràng  O’ gồm các đoạn thẳng không giao với nhau, bởi vì X không giao với bất kì đoạn nào ở bên trái nó trong O’ (do G3(C) là chấp nhận được) cũng như không giao với bất cứ đoạn nào ở bên phải nó trong O’ (Do mút phải của X nhỏ hơn mút phải của Y và Y không giao với bất cứ đoạn nào ở bên phải Y trong O’).  Do O’ có cùng lực lượng với O nên O’ cũng là tối ưu  Tuy nhiên ta thấy rằng O’ giống với G3(C) hơn là O => mâu thuẫn với giả thiết.  Độ phức tạp tính toán:  Độ phức tạp của thuật toán chủ yếu phụ thuộc vào thủ tục sắp xếp. Nguyễn Thanh Cẩm 4.2 4.2.1 4.2.2 Một số bài toán minh họa Bài toán đường đi của người giao hàng Bài toán các đoạn thẳng không giao nhau THUẬT TOÁN THAM LAM Bài toán cái ba lô4.2.3 Bài toán cây khung nhỏ nhất4.2.4 Nguyễn Thanh Cẩm 4.2.3 Bài toán cái ba lô Bài toán:  Một nhà thám hiểm cần sắp n vật vào ba lô của mình để thực hiện một cuộc thám hiểm ở bắc cực,  vật thứ i có khối lượng là wi, có giá trị là ci (wi, ci N),  ba lô chỉ có thể mang được khối lượng tối đa là b (b  N).  Vậy nhà thám hiểm cần chọn mang những vật nào?  Ta có thể tóm tắt bài toán như sau:  C = {1,2,3,..n}: tập chỉ số của đồ vật.  Tìm I  C. Sao cho ; Nguyễn Thanh Cẩm 4.2.3 Bài toán cái ba lô Đề xuất thuật toán tham lam  Greedy1: Sắp xếp theo thứ tự không tăng của giá trị.  Xét các đồ vật theo thứ tự đã xếp, lần lượt chất các đồ vật đang xét vào ba lô nếu dung lượng còn lại trong ba lô đủ chứa nó.  Tham số của bài toán là n = 3; b = 19.  Đồ vật 1 2 3  Giá trị 20 16 8  Trọng lượng 14 10 6  Thuật toán sẽ lựa chọn đồ vật 1 với tổng giá trị là 20, trong khi lời giải tối ưu của bài toán là lựa chọn (đồ vật 2, đồ vật 3 ) với tổng giá trị là 24. Nguyễn Thanh Cẩm 4.2.3 Bài toán cái ba lô  Greedy2: Sắp xếp đồ vật không giảm của trọng lượng.  Lần lượt chất các đồ vật vào ba lô theo thứ tự đã sắp xếp.  Tham số của bài toán là n = 3; b = 11  Đồ vật 1 2 3  Giá trị 10 16 28  Trọng lượng 5 6 10  Thuật toán sẽ lựa chọn (đồ vật 1, đồ vật 2) với tổng giá trị là 26, trong khi lời giải tối ưu của bài toán là (đồ vật 3) với tổng giá trị là 28 Nguyễn Thanh Cẩm 4.2.3 Bài toán cái ba lô  Greedy3: Sắp xếp các đồ vật theo thứ tự không tăng của giá trị một đơn vị trọng lượng (ci /wi). Lần lượt xét:  Tham số của bài toán: n = 2; b  2.  Khi đó thuật toán chỉ lựa chọn được đồ vật 1 với tổng giá trị là 10, trong khi lời giải tối ưu của bài toán lựa chọn đồ vật 2 với tổng giá trị là 10b-1 ( 10.2-1 = 19 > 10). Nguyễn Thanh Cẩm 4.2.3 Bài toán cái ba lô  Greedy4: Gọi Ij là lời giải thu được theo thuật toán Greedyj (j = 1, 2, 3). Gọi  Định lý: Lời giải I4 thoả mãn bất đẳng thức  Trong đó f* là giá trị tối ưu của bài toán. Nguyễn Thanh Cẩm 4.2 4.2.1 4.2.2 Một số bài toán minh họa Bài toán đường đi của người giao hàng Bài toán các đoạn thẳng không giao nhau THUẬT TOÁN THAM LAM Bài toán cái ba lô4.2.3 Bài toán cây khung nhỏ nhất4.2.4 Nguyễn Thanh Cẩm 4.2.4 Bài toán cây khung nhỏ nhất  Bài toán  Cho G = (V, E) là đồ thị vô hướng liên thông với  tập đỉnh V = {1, 2,…, n} và  tập cạnh E gồm m cạnh.  Mỗi cạnh e của đồ thị G được gán với một số thực c(e) gọi là độ dài của nó.  Giả sử H = (V, T) là cây khung của đồ thị G.  Ta gọi độ dài c(H) của cây khung H là tổng độ dài của các cạnh của nó.  Bài toán đặt ra là, trong số tất cả các cây khung của đồ thị G, hãy tìm cây khung có độ dài nhỏ nhất Nguyễn Thanh Cẩm 4.2.4 Bài toán cây khung nhỏ nhất  Thí dụ: Nguyễn Thanh Cẩm 4.2.4 Bài toán cây khung nhỏ nhất  Giải bài toán cây khung nhỏ nhất:  liệt kê tất cả các cây khung của đồ thị và  chọn trong số chúng cây khung nhỏ nhất.  Phương pháp như vậy trong trường hợp đồ thị đầy đủ sẽ đòi hỏi thời gian cỡ nn-2 ->không thể thực hiện được.  Thuật toán Kruskal và thuật toán Prim.  Cả hai thuật toán Kruskal và Prim đều dựa trên tư tưởng của các giải thuật tham lam  Ở mỗi bước của thuật toán ta chọn và bổ sung vào cây khung cạnh có trọng số nhỏ nhất có thể. Nguyễn Thanh Cẩm 4.2.4 Bài toán cây khung nhỏ nhất Thuật toán Kruskal:  Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H = (V, T) theo các bước:  B1: Sắp xếp các cạnh của đồ thị G theo thứ tự không giảm của độ dài.  B2: T = Ø,  B3: Trong khi |T|0  Chọn cạnh có trọng số nhỏ nhất bổ sung vào T sao cho T không tạo thành chu trình.  Thuật toán sẽ kết thúc khi ta thu được tập T gồm n-1 cạnh. Nguyễn Thanh Cẩm 4.2.4 Bài toán cây khung nhỏ nhất void Kruskal; { T = Ø; while ((|T| Ø)) { chọn e là cạnh nhỏ nhất trong E; E = E\[e]; if (T U [e] không chứa chu trình) T = T U [e]; } if (|T| < n-1) thông báo đồ thị không liên thông; } Nguyễn Thanh Cẩm 4.2.4 Bài toán cây khung nhỏ nhất Tìm cây khung nhỏ nhất của đồ thị 1 2 4 3 5 6 22 33 17 20 16 9 8 14 4 T = {(3,5), (4,6), (4,5), (1,3),(1,2)} là cây khung nhỏ nhất cần tìm Với trọng lượng: 4+8+9+17+20 =58 Nguyễn Thanh Cẩm 4.2.4 Bài toán cây khung nhỏ nhất Thuật toán Prim  Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị dày (đồ thị với số cạnh m ≈ n(n-1)/2).  Trong trường hợp đó thuật toán Prim tỏ ra hiệu quả hơn.  Thuật toán Prim còn được gọi là phương pháp lân cận gần nhất. Nguyễn Thanh Cẩm 4.2.4 Bài toán cây khung nhỏ nhất  Thuật toán Prim  Trong phương pháp này, bắt đầu từ một đỉnh s tùy ý của đồ thị G, đầu tiên ta nối s với đỉnh lân cận gần nó nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các cạnh kề với đỉnh s, cạnh (s,y) có độ dài nhỏ nhất.  Tiếp theo trong số các cạnh kề với hai đỉnh s hoặc y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba z, và ta thu được cây bộ phận gồm ba đỉnh và hai cạnh.  Quá trình này sẽ được tiếp tục cho đến khi ta thu được cây gồm n đỉnh và n-1 cạnh sẽ chính là cây khung nhỏ nhất cần tìm. Nguyễn Thanh Cẩm 4.2.4 Bài toán cây khung nhỏ nhất  Giả sử đồ thị cho ta bởi ma trận trọng số C={c[i,j], i, j = 1..n}.  Trong qua trình thực hiện thuật toán, ở mỗi bước để có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị sẽ được gán cho các nhãn.  Nhãn của một đỉnh v sẽ gồm hai phần và có dạng [d[v], near[v]], trong đó near[v] dùng để ghi nhận độ dài của cạnh có độ dài nhỏ nhất trong các cạnh nối đỉnh v với các đỉnh của cây khung đang xây dựng (ta sẽ gọi là khoảng cách từ đỉnh v đến tập đỉnh của cây khung),  nói một cách chính xác d[v] = min{c[v,w]: w thuộc VH} (= c[v,z]), còn near[v] ghi nhận đỉnh của cây khung gần v nhất (near[v] = z). Nguyễn Thanh Cẩm 4.2.4 Bài toán cây khung nhỏ nhất void Prim; { Chọn s là một đỉnh nào đó của đồ thị; VH = [s]; T = 0; D[s] = 0; near[s] = s; for (v thuộc V\VH ) { d[v] = c[s,v]; Near[v] = s; } Stop = false; while (not stop) { tìm u thuộc V\VH thỏa mãn: d[u] = min {d[v]: u thuộc V\VH}; VH = VH hợp [u]; T = T hợp {(u, near[u])}; if (|VH| = n) { H = (VH, T) là cây khung nhỏ nhất của đồ thị; Stop = true; } else for (v thuộc V\VH ) if (d[v] > c[u, v] ) { d[v] = c[u,v]; Near[v] = u; } } } TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN KHOA KHOA HỌC MÁY TÍNH -----------***----------- camcntt@yahoo.com