Steiner Tree for iOS

Popis

Táto aplikácia počíta Steinerove stromy pomocou evolučného algoritmu. Môžete umiestňovať, ťahať a odstraňovať body svojho stromu. Vypočíta sa optimálny počet a poloha Steinerových bodov. Minimálny kostra (MST) spája danú množinu bodov v rovine tak, že súčet všetkých hrán je minimálny. Tento súčet všetkých hrán sa často môže znížiť, ak sa pridajú ďalšie body. Tieto body sa nazývajú Steinerove body a zodpovedajúci minimálny kostrový strom Steinerov strom. Ak je zadaných viac ako 3 body, je to ťažký optimalizačný problém vypočítať optimálny počet a polohu Steinerových bodov. Táto aplikácia používa na demonštračné účely jednoduchý evolučný algoritmus. Používa populáciu jednotlivcov. Každý jednotlivec predstavuje MST obsahujúci niekoľko Steinerových bodov. Populácia sa vyvíja smerom k optimálnemu Steinerovmu stromu v evolučnej slučke: Spočiatku každý jednotlivec nastaví náhodné Steinerove body a vytvorí zodpovedajúci Steinerov strom. Je uložená minimálna dĺžka Steinerovho stromu v populácii. Každý jednotlivec má teraz fitness hodnotu, ktorá je tým vyššia, čím je dĺžka jeho Steinerovho stromu bližšie k minimálnej dĺžke v populácii. Vhodnejšie jedince majú rozmnožovaním viac potomkov a menej zdatné jedince vymierajú. Aby bolo možné preskúmať lepšie riešenia, reprodukcia nevytvára potomkov, ktorí sú identickí s rodičovským jedincom, t. j. nemajú svoje Steinerove body na rovnakej pozícii. Tieto polohy sú skôr náhodne posunuté mutáciou pomocou Gaussovho rozdelenia. O to, ako ďaleko sa v priemere posunuli, rozhoduje aj ich zdatnosť: Dobrí jedinci posúvajú svoje Steinerove body menej ako horší jedinci. Ako rýchlo sa nájde dobré riešenie, závisí teda od veľkosti populácie a sily mutácie.