Thuật toán Kruskal - xây dựng một khuôn khổ tối ưu

Trong hình học đầu thế kỷ 19 Jakob Steiner từ Berlin thiết lập các nhiệm vụ như thế nào để kết nối ba ngôi làng để chiều dài của họ là ngắn nhất. Sau đó, ông tóm tắt các vấn đề: nó là cần thiết để tìm một điểm trong một mặt phẳng, khoảng cách từ nó đến n điểm khác là thấp nhất. Trong thế kỷ 20, nó tiếp tục làm việc về chủ đề này. Đó là quyết định để có một vài điểm và kết nối chúng theo cách như vậy mà khoảng cách giữa chúng là ngắn nhất. tất cả điều này là một trường hợp đặc biệt của vấn đề đang được nghiên cứu.

"Tham lam" thuật toán

Thuật toán Kruskal đề cập đến các thuật toán "tham lam" (còn gọi là gradient). Bản chất của những người - chiến thắng cao nhất trên mỗi bước. Không phải lúc nào, các thuật toán "tham lam" cung cấp giải pháp tốt nhất cho vấn đề. Có một lý thuyết, cho thấy rằng trong ứng dụng của họ với nhiệm vụ cụ thể mà họ cung cấp cho các giải pháp tối ưu. Đây là lý thuyết về matroids. Thuật toán Kruskal đề cập đến vấn đề như vậy.

Tìm một cân thịt tối thiểu

thuật toán xem xây dựng một số khung tối ưu. Các vấn đề của nó là như sau. Dan vô hướng đồ thị mà không cạnh song song và vòng, và tập các cạnh được đưa ra chức năng cân w, mà gán số cho mỗi cạnh e - sườn cân - w (e). Trọng lượng của mỗi tập hợp con của đa số xương sườn là tổng trọng số của các cạnh của nó. Cần thiết để tìm ra bộ xương của một trọng lượng nhỏ.

miêu tả

Thuật toán Kruskal hoạt động. Thứ nhất, tất cả các cạnh của đồ thị ban đầu được sắp xếp theo thứ tự tăng dần của trọng số. Ban đầu, khung không chứa bất kỳ xương sườn nhưng bao gồm tất cả các đỉnh. Sau bước tiếp theo của thuật toán cho phần đã xây dựng của thân thịt, đó là một khu rừng trải rộng, một cạnh được thêm vào. Nó không phải là lựa chọn tùy ý. Tất cả các cạnh của đồ thị, không thuộc khung, có thể được gọi là màu đỏ và màu xanh lá cây. Đầu mỗi cạnh màu đỏ là trong cùng một thành phần dưới kết nối rừng xây dựng, và ngọn xanh - khác nhau. Do đó, nếu bạn thêm vào mép đỏ, có một chu kỳ, và nếu màu xanh lá cây - như nhận được sau bước này các thành phần gỗ kết nối sẽ ít hơn một. Do đó, việc xây dựng kết quả không thể thêm không có cạnh màu đỏ, nhưng bất kỳ cạnh màu xanh lá cây có thể được thêm vào để có được rừng. Và thêm một lợi thế cạnh màu xanh lá cây với trọng lượng tối thiểu. Kết quả là một khuôn khổ cân tối thiểu.

thực hiện

Biểu thị rừng hiện tại F. Nó chia tập các đỉnh trong lĩnh vực kết nối (hình thức công đoàn của họ F, và họ rời nhau). Ở cả hai cạnh của đỉnh đỏ họ nằm trong một mảnh. Phần (x) - chức năng rằng đối với mỗi đỉnh x trả về một phần của tên, nó thuộc x. Unite (x, y) - một thủ tục mà xây dựng một phân vùng mới, bao gồm kết hợp các bộ phận của x và y và tất cả các bộ phận khác. Cho n - số cạnh. Tất cả những khái niệm có trong Thuật toán Kruskal. Thực hiện:

1. Sắp xếp tất cả các cạnh của đồ thị từ 1 đến trọng lượng tăng dần n-thứ. (Ai, bi - i với số cạnh đỉnh).

2. cho i = 1 đến n làm.

3. x: = Phần (ai).

4. y: = Phần (bi).

5. Nếu x không y như nhau thì Unite (x, y), bao gồm với số cạnh F i.

đúng đắn

Hãy T - khung của đồ thị ban đầu được xây dựng bằng cách sử dụng thuật toán Kruskal và S - khung tùy ý của nó. Chúng ta phải chứng minh rằng w (T) là không lớn hơn w (S).

Hãy M - đa số vây S, P - một đa số vây T. Nếu S là không bằng T, sau đó có một et sườn khung T, không thuộc S. S. et tiếp giáp với chu kỳ, nó được gọi là C. C loại bỏ từ bất kỳ es cạnh, thuộc S. Chúng tôi có được một khung mới, bởi vì các cạnh và đỉnh là như nhau. trọng lượng của nó là không lớn hơn w (S), vì w (et) không còn w (es) trong một cường quốc thuật toán Kruskal. Thao tác này (thay thế xương sườn T S trên xương sườn) sẽ được lặp lại chừng nào nhận T. Trọng lượng của mỗi frame nhận tiếp theo là không lớn hơn trọng lượng trước, trong đó hàm ý rằng w (T) là không lớn hơn w (S).

Sự vững mạnh của Thuật toán Kruskal sau từ định lý của Rado-Edmonds trên matroids.

Ứng dụng Ví dụ thuật toán Kruskal

Dan đồ thị với các nút a, b, c, d, đ và xương sườn (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Các trọng số của các cạnh được thể hiện trong bảng và trong hình. Ban đầu, rừng xây dựng F chứa tất cả các đỉnh của đồ thị và không chứa bất kỳ xương sườn. Thuật toán Kruskal đầu tiên thêm sườn (a, e), kể từ khi trọng lượng có mức thấp nhất, và các đỉnh a và e là trong các thành phần khác nhau kết nối gỗ F (sườn (a, e) là màu xanh lá cây), sau đó các xương sườn (c, d), vì rằng ít nhất này cân mép cạnh đồ thị, không thuộc F, và nó là màu xanh lá cây, sau đó vì những lý do tương tự tích luỹ cạnh (a, b). Nhưng cạnh (b, e) được thông qua, mặc dù anh và trọng lượng tối thiểu của các cạnh còn lại, bởi vì nó là màu đỏ: các đỉnh b và e thuộc về các thành phần kết nối cùng của rừng F, có nghĩa là, nếu chúng ta thêm vào F rìa (b, e), được hình thành chu kỳ. Sau đó thêm vào cạnh màu xanh lá cây (b, c), được truyền mép đỏ (c, e), và sau đó d, e. tuần tự Như vậy, cạnh được thêm vào (a, e), (c, d), (a, b), (b, c). Từ nihera khung tối ưu và bao gồm các đồ thị ban đầu. Vì vậy, trong trường hợp này nó hoạt động một thuật toán Kruskal. Một ví dụ được hiển thị.

Con số này cho thấy một đồ thị, trong đó bao gồm hai thành phần được kết nối. Các dòng đậm chỉ ra xương sườn khung tối ưu (màu xanh) được xây dựng bằng cách sử dụng thuật toán Kruskal.

Bức tranh đầu cho thấy đồ thị ban đầu, và phía dưới - một bộ xương của trọng lượng tối thiểu, được xây dựng cho anh ta bằng cách sử dụng các thuật toán.

Trình tự của xương sườn gia tăng (1.6); (0,3), (2,6) hoặc (2,6), (0,3) - là không quan trọng; (3,4); (0,1), (1,6) hoặc (1,6), (0,1), cũng quan tâm (5,6).

Thuật toán Kruskal tìm thấy ứng dụng thực tế, ví dụ, để tối ưu hóa các thông tin liên lạc gasket, đường giao thông trong khu nhà ở mới trên địa bàn ở mỗi nước, cũng như trong các trường hợp khác.