Bài toán cây Steiner hay bài toán tìm đường đi ngắn nhất từ 2 điểm cho trước được phát triển dựa trên bài toán Fermat của nhà toán học nổi tiếng người Pháp.

Vào thế kỷ thứ 19, Steiner đã tổng quát bài toán của Fermat bằng cách không hạn chế số điểm cần tìm. Thực ra, ngay từ thời Gauß, người ta đã biết tới những loại bài toán kiểu như thế này. Trong cuốn sách What is Mathematics của Robbins và Courant xuất bản năm 1941, bài toán của Gauß được công bố dưới tên của Steiner: Bài toán Steiner.

Thuật toán

Cho đồ thị G=(V,E) có trọng số (V: tập các đỉnh; E tập các cạnh của đồ thị) và tập W ⊂ V. Tìm cây T =(W’, F) trong G nhỏ nhất bao trùm tất cả các đỉnh của W. Cây T gọi là Cây Steiner của W, và W’-W gọi là các điểm Steiner của W ứng với cây T. Cây Steiner là mạng tối ưu trong bài toán Steirner. Mạng này phải liên thông và không có chu trình (do điều kiện tối ưu của nó, nếu có chu trình ta có bỏ bớt một cạnh trên chu trình mà không ảnh hưởng tới sự liên thông của đồ thị).

Tư tưởng của thuật toán

Xét đồ thị G sau: Đồ thị G

Cho tập W={3,4,5,6}. Đồ thị R sinh bởi W có tập đỉnh {3,4,5,6} và tập cạnh là {(3,4),(3,5),(4,5),(4,6),(5,6)}. Dễ dàng thấy được cây khung nhỏ nhất của R có các cạnh {(3,4),(4,6),(6,5)} với tổng trọng số là 13. Tuy nhiên với tập đỉnh {3,4,5,6,1} có cây khung là {(3,4),(4,1),(1,6),(6,5)} chỉ có tồng trọng số là 12 < 13. Ở đây 1 được gọi là điểm Steiner. Ta sẽ xây dựng phương pháp giải bài toán Steiner bằng cách sử dụng thuật toán Floyd-Warshall tìm khoảng cách và đường đi ngắn nhất và thuật toán Kruskal để tìm cây khung nhỏ nhất.

Mã giả

Bước 1: Đọc file dữ liệu đầu vào của đồ thị G đã cho (file có cấu trúc) Đối với file dữ liệu đầu vào aij = 0 khi không có đường đi từ i->j, thủ tục đọc file sẽ chuyển các giá trị 0 này thành 99999 (vô cực dương).

Bước 2: Gọi thủ tục tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị bằng thuật toán Floyd-Warshall.

Bước 3: Gọi thủ tục tìm cây khung nhỏ nhất cho từng đồ thị con của G’ tìm được ở bước 2, G’=(V,E,w’) (đồ thị con <W∪S> sinh bởi W∪S trong G’ với S ⊂ V-W, card(S) ≤ m-2). Trong các cây phủ đó tìm cây T’ có tổng trọng số nhỏ nhất.

Bước 4: Xây dựng cây Steiner cho cây phủ T’ tìm được ở bước 3.

Bước 5: Kết xuất giá trị sang file lưu trữ.

Bước 6: Kết thúc.

Ứng dụng của thuật toán

Trong thực tế hiện nay có rất nhiều ứng dụng cần dùng đến bài toán Steiner để giải quyết. Cụ thể các ứng dụng của cây Steiner là: Bố trí mạch điện trong bo mạch điện tử. Nối hệ thống mạng với chi phí nhỏ nhất. *Và các ứng dụng liên quan đến tìm khoảng cách nhỏ nhất trong mặt phẳng như: hệ thống giao thông, hệ thống cấp nước, hệ thống cung cấp điện, cáp mạng…