Steiner Tree for iOS

Descripción

Esta aplicación calcula los árboles de Steiner utilizando un algoritmo evolutivo. Puede colocar, arrastrar y eliminar puntos de su árbol. Se calcula el número y la posición óptimos de los puntos de Steiner. Un árbol de expansión mínimo (MST) conecta un conjunto dado de puntos en un plano para que la suma de todos los bordes sea mínima. A menudo, esta suma de todos los bordes se puede reducir si se agregan puntos adicionales. Estos puntos se denominan puntos de Steiner y el correspondiente árbol de expansión mínima árbol de Steiner. Si se dan más de 3 puntos, es un problema de optimización difícil calcular el número y la posición óptimos de los puntos de Steiner. Esta aplicación utiliza un algoritmo evolutivo simple con fines de demostración. Utiliza una población de individuos. Cada individuo representa un MST que contiene algunos puntos de Steiner. La población se desarrolla hacia el árbol de Steiner óptimo en un bucle evolutivo: inicialmente, cada individuo establece puntos de Steiner aleatorios y construye el árbol de Steiner correspondiente. Se almacena la longitud mínima del árbol de Steiner en la población. Cada individuo tiene ahora un valor de aptitud, que es mayor cuanto más se acerca la longitud de su árbol de Steiner a la longitud mínima de la población. Los individuos más aptos tienen más descendientes por reproducción, y los individuos menos aptos mueren. Para explorar mejores soluciones, la reproducción no crea descendientes que sean idénticos al individuo progenitor, es decir, que no tengan sus puntos de Steiner en la misma posición. Más bien, estas posiciones se desplazan aleatoriamente por mutación, utilizando una distribución gaussiana. La medida en que se desplazan en promedio también está determinada por su aptitud: los buenos individuos cambian sus puntos de Steiner menos que los peores individuos. La rapidez con la que se encuentra una buena solución depende, por lo tanto, del tamaño de la población y de la fuerza de la mutación.