Steiner Tree for iOS

Описание

Это приложение вычисляет деревья Штейнера, используя эволюционный алгоритм. Вы можете размещать, перетаскивать и удалять точки вашего дерева. Вычисляется оптимальное количество и положение точек Штейнера. Минимальное остовное дерево (MST) соединяет заданный набор точек на плоскости так, чтобы сумма всех ребер была минимальной. Часто эту сумму всех ребер можно уменьшить, если добавить дополнительные точки. Эти точки называются точками Штейнера, а соответствующее минимальное остовное дерево — деревом Штейнера. Если дано более 3 точек, вычисление оптимального количества и положения точек Штейнера является сложной проблемой оптимизации. Это приложение использует простой эволюционный алгоритм для демонстрационных целей. Он использует популяцию особей. Каждый индивидуум представляет собой MST, содержащую несколько точек Штейнера. Популяция развивается к оптимальному дереву Штейнера в эволюционном цикле: сначала каждый человек устанавливает случайные точки Штейнера и строит соответствующее дерево Штейнера. Сохраняется минимальная длина дерева Штейнера в популяции. У каждой особи теперь есть значение пригодности, которое тем выше, чем ближе длина дерева Штейнера к минимальной длине в популяции. Более приспособленные особи имеют больше потомков в результате размножения, а менее приспособленные особи вымирают. Чтобы найти лучшие решения, воспроизводство не создает потомков, идентичных родительской особи, то есть не имеющих точек Штейнера в одном и том же положении. Скорее эти позиции смещаются случайным образом в результате мутации с использованием распределения Гаусса. То, насколько они сдвинуты в среднем, определяется также их приспособленностью: хорошие особи смещают свои точки Штейнера меньше, чем худшие особи. Насколько быстро будет найдено хорошее решение, зависит, таким образом, от размера популяции и силы мутации.