Bài toán cây Steiner

Bách khoa toàn thư mở Wikipedia
(Đổi hướng từ Cây Steiner)

Bài toán cây Steiner[1] 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[2] 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[sửa | sửa mã nguồ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[sửa | sửa mã nguồn]

Xét đồ thị G sau:

Đồ thị G

Mã giả[sửa | sửa mã nguồn]

  1. 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).
  2. 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.
  3. 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.
  4. Bước 4: Xây dựng cây Steiner cho cây phủ T’ tìm được ở bước 3.
  5. Bước 5: Kết xuất giá trị sang file lưu trữ.
  6. Bước 6: Kết thúc.

Ứng dụng của thuật toán[sửa | sửa mã nguồ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à:

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Takahashi, Hiromitsu, and Akira Matsuyama. "An approximate solution for the Steiner problem in graphs." Math. Japonica 24.6 (1980): 573-577.
  2. ^ “What Is Mathematics? An Elementary Approach to Ideas and Methods: Richard Courant, Herbert Robbins, Ian Stewart: 9780195105193: Amazon.com: Books”. Truy cập 12 tháng 2 năm 2015.
  3. ^ Garey, Michael R., and David S. Johnson. "The rectilinear Steiner tree problem is NP-complete." SIAM Journal on Applied Mathematics 32.4 (1977): 826-834.
  4. ^ Steiner, Jennifer G., Clifford Neuman, and Jeffrey I. Schiller. "Kerberos: An authentication service for open network systems." USENIX conference proceedings. Vol. 191. 1988.
  5. ^ KHOKHANI, K. H.; PATEL, A. M. The chip layout problem: A placement procedure for lsi. In: Proceedings of the 14th Design Automation Conference. IEEE Press, 1977. p. 291-297.

Tài liệu[sửa | sửa mã nguồn]

  • Trần Quốc Chiến, Giáo trình lý thuyết đồ thị, Đại học Sư phạm Đà Nẵng.
  • V.K. Balakrishnan, Theory and Problems of Graph Theory. McGRAW-HILL 1997 (bản điện tử)
  • Nguyễn Xuân Quỳnh, Cơ sở Toán rời rạc và ứng dụng. Nhà xuất bản Giáo dục. Hà Nội 1995]]
  • Derek R. Dreyer, Michael L. Overton, Two Heuristics for the Euclidean Steiner Tree Problem, ngày 30 tháng 9 năm 2002.
  • M. R. Garey, R. L. Graham, D. S. Johnson. The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics, 32(4):835–859, June 1977.
Lấy từ “https://vi.wikipedia.org/w/index.php?title=Bài_toán_cây_Steiner&oldid=70404859”