Steiner Tree for iOS

Descrição

Este aplicativo calcula árvores Steiner usando um algoritmo evolutivo. Você pode colocar, arrastar e excluir pontos de sua árvore. O número e a posição ideais dos pontos de Steiner são calculados. Uma árvore geradora mínima (MST) conecta um determinado conjunto de pontos em um plano de modo que a soma de todas as arestas seja mínima. Muitas vezes, esta soma de todas as arestas pode ser reduzida, se forem adicionados pontos adicionais. Esses pontos são chamados de pontos de Steiner e a árvore geradora mínima correspondente. Se mais de 3 pontos forem dados, é um problema de otimização difícil calcular o número e a posição ideais dos pontos de Steiner. Este aplicativo usa um algoritmo evolutivo simples para fins de demonstração. Ele usa uma população de indivíduos. Cada indivíduo representa um MST contendo alguns pontos de Steiner. A população se desenvolve em direção à árvore de Steiner ótima em um loop evolutivo: inicialmente, cada indivíduo define pontos de Steiner aleatórios e constrói a árvore de Steiner correspondente. O comprimento mínimo da árvore de Steiner na população é armazenado. Cada indivíduo tem agora um valor de aptidão, que é quanto maior, quanto mais próximo o comprimento da árvore de Steiner estiver do comprimento mínimo na população. Indivíduos mais aptos têm mais descendentes por reprodução e indivíduos menos aptos morrem. Para explorar melhores soluções, a reprodução não cria descendentes idênticos ao indivíduo-pai, ou seja, não possuem seus pontos de Steiner na mesma posição. Em vez disso, essas posições são deslocadas aleatoriamente por mutação, usando uma distribuição gaussiana. O quanto eles são deslocados em média também é determinado por sua aptidão: Bons indivíduos deslocam seus pontos Steiner menos do que indivíduos piores. A rapidez com que uma boa solução é encontrada depende, portanto, do tamanho da população e da força da mutação.