Steiner Tree for iOS

Описание

Това приложение изчислява дърветата на Steiner с помощта на еволюционен алгоритъм. Можете да поставяте, плъзгате и изтривате точки от вашето дърво. Изчислява се оптималният брой и позиция на точките на Щайнер. Минимално обхващащо дърво (MST) свързва даден набор от точки в равнина, така че сумата от всички ръбове да е минимална. Често тази сума от всички ръбове може да бъде намалена, ако се добавят допълнителни точки. Тези точки се наричат ​​точки на Щайнер, а съответното минимално обхващащо дърво дърво на Щайнер. Ако са дадени повече от 3 точки, е труден проблем за оптимизация да се изчисли оптималният брой и позиция на точките на Щайнер. Това приложение използва прост еволюционен алгоритъм за демонстрационни цели. Той използва популация от индивиди. Всеки индивид представлява MST, съдържащ някои точки на Steiner. Популацията се развива към оптималното дърво на Щайнер в еволюционен цикъл: Първоначално всеки индивид задава произволни точки на Щайнер и конструира съответното дърво на Щайнер. Минималната дължина на дървото на Steiner в популацията се съхранява. Сега всеки индивид има стойност на годност, която е толкова по-висока, колкото по-близо е дължината на дървото на Steiner до минималната дължина в популацията. По-здравите индивиди имат повече потомци чрез възпроизвеждане, а по-малко годните индивиди измират. За да се изследват по-добри решения, възпроизвеждането не създава потомци, които са идентични с родителския индивид, т.е. нямат точките на Щайнер на една и съща позиция. По-скоро тези позиции се изместват на случаен принцип чрез мутация, като се използва разпределение на Гаус. Колко далеч са изместени средно се определя и от тяхната пригодност: Добрите индивиди изместват точките си на Щайнер по-малко от по-лошите индивиди. Колко бързо се намира добро решение зависи следователно от размера на популацията и силата на мутацията.