Steiner Tree for iOS

Descriere

Această aplicație calculează arbori Steiner folosind un algoritm evolutiv. Puteți plasa, trage și șterge puncte din arborele dvs. Se calculează numărul optim și poziția punctelor Steiner. Un arbore de întindere minim (MST) conectează un anumit set de puncte într-un plan, astfel încât suma tuturor muchiilor să fie minimă. Adesea, această sumă a tuturor marginilor poate fi redusă, dacă se adaugă puncte suplimentare. Aceste puncte sunt numite puncte Steiner, iar arborele de întindere minim corespunzător arborele Steiner. Dacă sunt date mai mult de 3 puncte, este o problemă dificilă de optimizare să se calculeze numărul optim și poziția punctelor Steiner. Această aplicație folosește un algoritm evolutiv simplu în scopuri demonstrative. Utilizează o populație de indivizi. Fiecare individ reprezintă un MST care conține câteva puncte Steiner. Populația se dezvoltă către arborele Steiner optim într-o buclă evolutivă: Inițial, fiecare individ stabilește puncte Steiner aleatoare și construiește arborele Steiner corespunzător. Lungimea minimă a arborelui Steiner în populație este stocată. Fiecare individ are acum o valoare de fitness, care este cu atât mai mare, cu cât lungimea arborelui lui Steiner este mai aproape de lungimea minimă din populație. Indivizii mai în formă au mai mulți descendenți prin reproducere, iar indivizii mai puțin apți mor. Pentru a explora soluții mai bune, reproducerea nu creează descendenți care sunt identici cu individul părinte, adică nu au punctele Steiner în aceeași poziție. Mai degrabă, aceste poziții sunt deplasate aleatoriu prin mutație, folosind o distribuție Gauss. Cât de departe sunt deplasați, în medie, este determinat și de fitness-ul lor: indivizii buni își schimbă punctele Steiner mai puțin decât indivizii mai rău. Cât de repede este găsită o soluție bună, depinde astfel de mărimea populației și de puterea mutației.