Steiner Tree for iOS

Açıklama

Bu uygulama, evrimsel bir algoritma kullanarak Steiner ağaçlarını hesaplar. Ağacınızın noktalarını yerleştirebilir, sürükleyebilir ve silebilirsiniz. Steiner noktalarının optimal sayısı ve konumu hesaplanır. Minimal yayılan ağaç (MST), bir düzlemdeki belirli bir nokta kümesini, tüm kenarların toplamı minimum olacak şekilde birleştirir. Ek noktalar eklenirse, genellikle tüm kenarların bu toplamı azaltılabilir. Bu noktalara Steiner noktaları ve karşılık gelen minimum yayılan ağaç Steiner ağacı denir. 3'ten fazla puan verilirse, Steiner noktalarının optimal sayısını ve konumunu hesaplamak zor bir optimizasyon problemidir. Bu uygulama, gösterim amacıyla basit bir evrimsel algoritma kullanır. Bir birey popülasyonu kullanır. Her birey, bazı Steiner noktalarını içeren bir MST'yi temsil eder. Popülasyon, evrimsel bir döngüde optimal Steiner ağacına doğru gelişir: Başlangıçta, her birey rastgele Steiner noktaları belirler ve karşılık gelen Steiner ağacını oluşturur. Popülasyondaki Steiner ağacının minimum uzunluğu depolanır. Artık her bireyin bir uygunluk değeri vardır, bu değer ne kadar yüksekse, Steiner ağacının uzunluğu popülasyondaki minimum uzunluğa o kadar yakın olur. Fit bireyler üreme yoluyla daha fazla torun sahibi olur ve daha az fit bireyler ölür. Daha iyi çözümler keşfetmek için üreme, ebeveyn bireyle aynı olan, yani Steiner noktaları aynı konumda olmayan torunlar yaratmaz. Bunun yerine, bu konumlar bir Gauss dağılımı kullanılarak mutasyon yoluyla rastgele kaydırılır. Ortalama olarak ne kadar uzağa kaydırıldıkları aynı zamanda uygunlukları tarafından da belirlenir: İyi bireyler Steiner puanlarını daha kötü bireylere göre daha az kaydırır. İyi bir çözümün ne kadar hızlı bulunduğu, bu nedenle popülasyon büyüklüğüne ve mutasyon gücüne bağlıdır.