Steiner Tree for iOS

Təsvir

Bu proqram təkamül alqoritmindən istifadə edərək Steiner ağaclarını hesablayır. Siz ağacınızın nöqtələrini yerləşdirə, sürükləyə və silə bilərsiniz. Steiner nöqtələrinin optimal sayı və mövqeyi hesablanır. Minimal yayılan ağac (MST) bütün kənarların cəminin minimal olması üçün müstəvidə verilmiş nöqtələr dəstini birləşdirir. Tez-tez əlavə nöqtələr əlavə edilərsə, bütün kənarların bu cəmi azaldıla bilər. Bu nöqtələrə Steiner nöqtələri və müvafiq minimal yayılan ağac Steiner ağacı deyilir. Əgər 3-dən çox xal verilirsə, Steiner nöqtələrinin optimal sayını və mövqeyini hesablamaq çətin bir optimallaşdırma problemidir. Bu proqram nümayiş məqsədləri üçün sadə təkamül alqoritmindən istifadə edir. Fərdlərin populyasiyasından istifadə edir. Hər bir fərd bəzi Steiner nöqtələrini ehtiva edən MST-ni təmsil edir. Populyasiya təkamül dövrəsində optimal Ştayner ağacına doğru inkişaf edir: Əvvəlcə hər bir fərd təsadüfi Ştayner nöqtələrini təyin edir və müvafiq Ştayner ağacını qurur. Populyasiyada Ştayner ağacının minimum uzunluğu saxlanılır. Hər bir fərdin indi fitnes dəyəri var, bu nə qədər yüksəkdirsə, onun Ştayner ağacının uzunluğu populyasiyadakı minimum uzunluğa nə qədər yaxındırsa. Güclü fərdlərin çoxalma yolu ilə daha çox nəsli var və daha az uyğun fərdlər ölür. Daha yaxşı həll yollarını araşdırmaq üçün çoxalma ana fərdlə eyni olan, yəni eyni mövqedə Ştayner nöqtələrinə malik olmayan nəsillər yaratmır. Əksinə, bu mövqelər Gauss paylanmasından istifadə edərək mutasiya ilə təsadüfi olaraq dəyişdirilir. Onların orta hesabla nə qədər yerdəyişmələri onların uyğunluğuna görə də müəyyən edilir: Yaxşı fərdlər Ştayner xallarını daha pis fərdlərdən daha az dəyişirlər. Yaxşı bir həllin nə qədər tez tapılması populyasiyanın sayından və mutasiya gücündən asılıdır.