Steiner Tree for iOS

Beschreibung

Diese App berechnet Steiner-Bäume mit einem evolutionären Algorithmus. Sie können Punkte Ihres Baums platzieren, ziehen und löschen. Die optimale Anzahl und Position von Steiner-Punkten wird berechnet. Ein minimaler Spannbaum (MST) verbindet eine gegebene Menge von Punkten in einer Ebene so, dass die Summe aller Kanten minimal ist. Oft kann diese Summe aller Kanten reduziert werden, wenn zusätzliche Punkte hinzugefügt werden. Diese Punkte werden Steiner-Punkte genannt und der entsprechende minimale Spannbaum Steiner-Baum. Wenn mehr als 3 Punkte gegeben sind, ist es ein schwieriges Optimierungsproblem, die optimale Anzahl und Position von Steiner-Punkten zu berechnen. Diese App verwendet zu Demonstrationszwecken einen einfachen evolutionären Algorithmus. Es verwendet eine Population von Individuen. Jedes Individuum stellt einen MST dar, der einige Steiner-Punkte enthält. Die Population entwickelt sich in einer Evolutionsschleife hin zum optimalen Steiner-Baum: Zunächst setzt jedes Individuum zufällige Steiner-Punkte und konstruiert den entsprechenden Steiner-Baum. Die minimale Länge des Steinerbaums in der Population wird gespeichert. Jedes Individuum hat nun einen Fitnesswert, der umso höher ist, je näher seine Steinerbaumlänge an der Mindestlänge in der Population liegt. Fittere Individuen haben durch Fortpflanzung mehr Nachkommen, und weniger fitte Individuen sterben aus. Um bessere Lösungen zu erforschen, erzeugt die Reproduktion keine Nachkommen, die mit dem Elternindividuum identisch sind, dh ihre Steiner-Punkte nicht an derselben Position haben. Vielmehr werden diese Positionen unter Verwendung einer Gaußschen Verteilung zufällig durch Mutation verschoben. Wie weit sie im Durchschnitt verschoben werden, wird auch von ihrer Fitness bestimmt: Gute Individuen verschieben ihre Steiner-Punkte weniger als schlechtere Individuen. Wie schnell eine gute Lösung gefunden wird, hängt also von der Populationsgröße und der Mutationsstärke ab.