Steiner Tree for iOS

Опис

Ова апликација израчунава Штајнерово дрвеће користећи еволуциони алгоритам. Можете постављати, превлачити и брисати тачке свог стабла. Израчунава се оптималан број и положај Штајнерових тачака. Минимално разапињуће стабло (МСТ) повезује дати скуп тачака у равни тако да је збир свих ивица минималан. Често се овај збир свих ивица може смањити ако се додају додатне тачке. Ове тачке се називају Штајнерове тачке, а одговарајуће минимално разапињуће стабло Штајнерово дрво. Ако је дато више од 3 тачке, тежак је проблем оптимизације израчунавање оптималног броја и положаја Штајнерових тачака. Ова апликација користи једноставан еволутивни алгоритам у сврху демонстрације. Користи популацију појединаца. Сваки појединац представља МСТ који садржи неке Штајнерове тачке. Популација се развија ка оптималном Штајнеровом стаблу у еволуционој петљи: У почетку, сваки појединац поставља насумичне Штајнерове тачке и конструише одговарајуће Штајнерово дрво. Чува се минимална дужина Штајнеровог дрвета у популацији. Сваки појединац сада има кондициону вредност, која је већа, што је дужина његовог Штајнеровог стабла ближа минималној дужини у популацији. Фикснији појединци имају више потомака репродукцијом, а мање способни изумиру. Да би се истражила боља решења, репродукција не ствара потомке који су идентични родитељској јединки, односно немају своје Штајнерове тачке на истој позицији. Уместо тога, ове позиције се насумично померају мутацијом, користећи Гаусову дистрибуцију. Колико су они у просеку померени зависи и од њихове кондиције: Добри појединци померају своје Штајнерове тачке мање од лошијих појединаца. Колико брзо се нађе добро решење, зависи од величине популације и јачине мутације.