Steiner Tree for iOS

Lýsing

Þetta app reiknar Steiner tré með því að nota þróunaralgrím. Þú getur sett, dregið og eytt punktum úr trénu þínu. Ákjósanlegur fjöldi og staðsetning Steiner punkta er reiknuð út. Lágmarksspennutré (MST) tengir tiltekið mengi punkta í plani þannig að summa allra brúna er í lágmarki. Oft er hægt að minnka þessa summa allra brúna, ef fleiri stigum er bætt við. Þessir punktar eru kallaðir Steiner-punktar og samsvarandi lágmarksspennandi tré Steiner-tré. Ef fleiri en 3 stig eru gefin er erfitt hagræðingarvandamál að reikna út ákjósanlegasta fjölda og staðsetningu Steiner stiga. Þetta app notar einfalt þróunaralgrím til sýnikennslu. Það notar hóp einstaklinga. Hver einstaklingur táknar MST sem inniheldur nokkur Steiner stig. Þjóðin þróast í átt að ákjósanlegu Steiner-trénu í þróunarlykkju: Í upphafi setur hver einstaklingur tilviljunarkenndar Steiner-punkta og smíðar samsvarandi Steiner-tré. Lágmarkslengd Steinertrésins í stofninum er geymd. Hver einstaklingur hefur nú líkamsræktargildi, sem er því hærra, því nær Steiner-tréslengd hans er lágmarkslengd í stofninum. Sterkari einstaklingar eignast fleiri afkomendur eftir æxlun og einstaklingar sem eru ekki hressari deyja út. Til að kanna betri lausnir skapar fjölgun ekki afkomendur sem eru eins og foreldris einstaklingsins, þ.e.a.s. hafa ekki Steiner punktana sína í sömu stöðu. Þessum stöðum er frekar breytt af handahófi með stökkbreytingum, með því að nota Gaussdreifingu. Hversu langt þeir eru færðir að meðaltali ræðst einnig af hæfni þeirra: Góðir einstaklingar færa Steiner-punkta sína minna en verri einstaklingar. Hversu hratt góð lausn finnst, fer því eftir stofnstærð og stökkbreytingarstyrk.