Steiner Tree for iOS

Sự miêu tả

Ứng dụng này tính toán cây Steiner bằng cách sử dụng một thuật toán tiến hóa. Bạn có thể đặt, kéo và xóa các điểm trên cây của mình. Số lượng và vị trí tối ưu của các điểm Steiner được tính toán. Cây khung tối thiểu (MST) kết nối một tập hợp các điểm nhất định trong một mặt phẳng sao cho tổng tất cả các cạnh là nhỏ nhất. Thường thì tổng này của tất cả các cạnh có thể bị giảm đi, nếu các điểm bổ sung được thêm vào. Những điểm này được gọi là điểm Steiner, và cây bao trùm tối thiểu tương ứng là cây Steiner. Nếu nhiều hơn 3 điểm được cho, đó là một bài toán tối ưu hóa khó để tính toán số lượng và vị trí tối ưu của các điểm Steiner. Ứng dụng này sử dụng một thuật toán tiến hóa đơn giản cho mục đích trình diễn. Nó sử dụng một quần thể các cá nhân. Mỗi cá nhân đại diện cho một MST chứa một số điểm Steiner. Quần thể phát triển theo hướng cây Steiner tối ưu trong một vòng tiến hóa: Ban đầu, mỗi cá nhân đặt các điểm Steiner ngẫu nhiên và xây dựng cây Steiner tương ứng. Chiều dài tối thiểu của cây Steiner trong quần thể được lưu trữ. Mỗi cá thể hiện có một giá trị thể lực, giá trị này càng cao thì chiều dài cây Steiner của nó càng gần với chiều dài tối thiểu trong quần thể. Những cá thể khỏe mạnh hơn có nhiều con cháu hơn bằng cách sinh sản, và những cá thể kém phù hợp hơn sẽ chết. Để khám phá các giải pháp tốt hơn, việc sinh sản không tạo ra con cháu giống với cá thể bố mẹ, tức là không có các điểm Steiner của chúng ở cùng một vị trí. Thay vào đó, các vị trí này được thay đổi ngẫu nhiên do đột biến, sử dụng phân phối Gauss. Mức độ dịch chuyển trung bình của chúng cũng được xác định bởi thể trạng của chúng: Những cá thể tốt dịch chuyển điểm Steiner của họ ít hơn những cá thể kém hơn.