| Wersja | 3.0 |
|---|---|
| Wydawca | Reinhard MAENNER |
| Data wydania | 11 cze 2016 |
| Data dodania | 21 sty 2013 |
| Wymagania systemu operacyjnego | iOS |
| Wymagania | Compatible with: iphone3gs, iphone3gs, ipadwifi, ipadwifi, ipad3g, ipad3g, ipodtouchthirdgen, ipodtouchthirdgen, iphone4, iphone4, ipodtouchfourthgen, ipodtouchfourthgen, ipad2wifi, ipad2wifi, ipad23g, ipad23g, iphone4s, iphone4s, ipadthirdgen, ipadthirdgen, ipadthirdgen4g, ipadthirdgen4g, iphone5, iphone5, ipodtouchfifthgen, ipodtouchfifthgen, ipadfourthgen, ipadfourthgen, ipadfourthgen4g, ipadfourthgen4g, ipadmini, ipadmini, ipadmini4g, ipadmini4g |
| Całkowita liczba pobrań | 3 |
| Cena £ | Free |
Opis
Ta aplikacja oblicza drzewa Steinera za pomocą algorytmu ewolucyjnego. Możesz umieszczać, przeciągać i usuwać punkty swojego drzewa. Obliczana jest optymalna liczba i położenie punktów Steinera. Minimalne drzewo rozpinające (MST) łączy dany zbiór punktów na płaszczyźnie tak, aby suma wszystkich krawędzi była minimalna. Często tę sumę wszystkich krawędzi można zmniejszyć, dodając dodatkowe punkty. Punkty te nazywane są punktami Steinera i odpowiadającym im minimalnym drzewem rozpinającym drzewo Steinera. Jeśli podano więcej niż 3 punkty, obliczenie optymalnej liczby i położenia punktów Steinera jest trudnym problemem optymalizacyjnym. Ta aplikacja wykorzystuje prosty algorytm ewolucyjny do celów demonstracyjnych. Wykorzystuje populację osobników. Każda osoba reprezentuje MST zawierający kilka punktów Steinera. Populacja rozwija się w kierunku optymalnego drzewa Steinera w pętli ewolucyjnej: Początkowo każda osoba ustawia losowe punkty Steinera i konstruuje odpowiadające mu drzewo Steinera. Przechowywana jest minimalna długość drzewa Steinera w populacji. Każdy osobnik ma teraz wartość przystosowania, która jest tym wyższa, im długość jego drzewa Steinera jest bliższa minimalnej długości w populacji. Bardziej sprawne osobniki mają więcej potomków przez rozmnażanie, a mniej sprawne osobniki wymierają. W celu zbadania lepszych rozwiązań, reprodukcja nie tworzy potomków identycznych z osobnikiem rodzicielskim, tj. nie ma ich punktów Steinera w tej samej pozycji. Raczej te pozycje są przesuwane losowo przez mutację, przy użyciu rozkładu Gaussa. O tym, jak daleko są one przesunięte przeciętnie, decyduje również ich przystosowanie: dobre osobniki przesuwają swoje punkty Steinera mniej niż osobniki gorsze. Szybkość znalezienia dobrego rozwiązania zależy zatem od wielkości populacji i siły mutacji.
