Programa Evolver para Árvores de Steiner Ponderadas
Apresentamos um algoritmo quase-ótimo inspirado em um experimento físico usando películas de sabão para o problema de Steiner ponderado no plano. Tal problema é NP-hard, mesmo em sua versão retilinear e devido a isso algoritmos heurísticos vêm sendo usados para encontrar árvores próximas da mínima. O algoritmo é implementado na linguagem de programação Evolver, que já contém muitas rotinas internas de minimização de energia. Algumas são chamadas pelo programa, o que permite que ele consista de 183 de código-fonte. Nosso algoritmo reproduz o experimento físico de uma película de sabão que se desprende de pinos conectados para chegar a uma configuração estável. Adicionalmente, no caso não-ponderado são feitas comparações com o GeoSteiner. Ao longo do texto, apresentamos diversos resultados de Geometria, Teoria dos Grafos e Física que modelam e nos d ̃ao uma visão do problema sob diferentes ângulos.