Steiner Tree for iOS

Опис

Оваа апликација пресметува стејнерови дрвја користејќи еволутивен алгоритам. Можете да поставувате, влечете и бришете точки од вашето дрво. Се пресметуваат оптималниот број и позиција на Штајнерови точки. Минималното опкружувачко дрво (MST) поврзува дадена група точки во рамнината така што збирот на сите рабови е минимален. Често овој збир на сите рабови може да се намали, ако се додадат дополнителни точки. Овие точки се нарекуваат Штајнерови точки, а соодветното минимално опфатено дрво Штајнерово дрво. Ако се дадени повеќе од 3 поени, тешко е да се пресмета оптималниот број и позицијата на Штајнеровите точки. Оваа апликација користи едноставен еволутивен алгоритам за демонстративни цели. Таа користи популација на поединци. Секој поединец претставува MST кој содржи некои Steiner точки. Популацијата се развива кон оптималното стејнерово дрво во еволутивна јамка: Првично, секој поединец поставува случајни точки на Штајнер и го конструира соодветното стејнерово дрво. Се чува минималната должина на дрвото Штајнер во популацијата. Секој поединец сега има фитнес вредност, која е поголема, толку е поблиску должината на неговото дрво Штајнер до минималната должина во популацијата. Подобрите поединци имаат повеќе потомци со размножување, а помалку способните поединци изумираат. Со цел да се истражат подобри решенија, репродукцијата не создава потомци кои се идентични со родителот, односно немаат нивните точки на Штајнер на иста позиција. Наместо тоа, овие позиции се поместуваат случајно со мутација, користејќи Гаусова распределба. Колку далеку се поместени во просек се определува и од нивната кондиција: Добрите поединци ги поместуваат своите Стајнерови поени помалку од полошите поединци. Колку брзо ќе се најде добро решение зависи од големината на популацијата и јачината на мутацијата.