Steiner Tree for iOS

Опис

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