Steiner Tree for iOS

Përshkrim

Ky aplikacion llogarit pemët Steiner duke përdorur një algoritëm evolucionar. Mund të vendosni, tërhiqni dhe fshini pikat e pemës suaj. Është llogaritur numri dhe pozicioni optimal i pikave Shtajner. Një pemë e shtrirjes minimale (MST) lidh një grup të caktuar pikash në një plan në mënyrë që shuma e të gjitha skajeve të jetë minimale. Shpesh kjo shumë e të gjitha skajeve mund të reduktohet nëse shtohen pika shtesë. Këto pika quhen pika Steiner, dhe pema përkatëse minimale që shtrihet pema Steiner. Nëse jepen më shumë se 3 pikë, është një problem i vështirë optimizimi për të llogaritur numrin dhe pozicionin optimal të pikave Shtajner. Ky aplikacion përdor një algoritëm të thjeshtë evolucionar për qëllime demonstrimi. Ai përdor një popullsi individësh. Çdo individ përfaqëson një MST që përmban disa pika Steiner. Popullata zhvillohet drejt pemës optimale të Shtajnerit në një lak evolucionar: Fillimisht, çdo individ vendos pika të rastësishme të Shtajnerit dhe ndërton pemën përkatëse të Shtajnerit. Gjatësia minimale e pemës Shtajner në popullatë ruhet. Çdo individ ka tani një vlerë fitnesi, e cila është sa më e lartë, aq më afër gjatësisë së pemës së tij Steiner është gjatësia minimale në popullatë. Individët më në formë kanë më shumë pasardhës nga riprodhimi dhe individët më pak të aftë vdesin. Për të eksploruar zgjidhje më të mira, riprodhimi nuk krijon pasardhës që janë identikë me individin prind, pra nuk kanë pikat e tyre Steiner në të njëjtin pozicion. Përkundrazi, këto pozicione zhvendosen rastësisht nga mutacioni, duke përdorur një shpërndarje Gaussian. Se sa larg janë zhvendosur mesatarisht përcaktohet edhe nga aftësia e tyre: Individët e mirë i zhvendosin pikët e tyre Steiner më pak se individët më të këqij. Sa shpejt gjendet një zgjidhje e mirë, varet kështu nga madhësia e popullatës dhe forca e mutacionit.