Steiner Tree for iOS

Penerangan

Aplikasi ini mengira pokok Steiner menggunakan algoritma evolusi. Anda boleh meletakkan, menyeret dan memadam titik pokok anda. Nombor dan kedudukan optimum mata Steiner dikira. Pokok rentang minimum (MST) menghubungkan set titik tertentu dalam satah supaya jumlah semua tepi adalah minimum. Selalunya jumlah semua tepi ini boleh dikurangkan, jika mata tambahan ditambah. Titik ini dipanggil mata Steiner, dan pokok rentang minimum yang sepadan dengan pokok Steiner. Jika lebih daripada 3 mata diberikan, ia adalah masalah pengoptimuman yang sukar untuk mengira nombor dan kedudukan optimum mata Steiner. Aplikasi ini menggunakan algoritma evolusi mudah untuk tujuan demonstrasi. Ia menggunakan populasi individu. Setiap individu mewakili MST yang mengandungi beberapa mata Steiner. Populasi berkembang ke arah pokok Steiner yang optimum dalam gelung evolusi: Pada mulanya, setiap individu menetapkan titik Steiner rawak, dan membina pokok Steiner yang sepadan. Panjang minimum pokok Steiner dalam populasi disimpan. Setiap individu kini mempunyai nilai kecergasan, iaitu semakin tinggi, semakin hampir panjang pokok Steinernya dengan panjang minimum dalam populasi. Individu yang lebih cergas mempunyai lebih banyak keturunan melalui pembiakan, dan individu yang kurang cergas akan mati. Untuk meneroka penyelesaian yang lebih baik, pembiakan tidak menghasilkan keturunan yang sama dengan individu induk, iaitu tidak mempunyai mata Steiner mereka pada kedudukan yang sama. Sebaliknya kedudukan ini dialihkan secara rawak melalui mutasi, menggunakan taburan Gaussian. Sejauh mana mereka dianjak secara purata juga ditentukan oleh kecergasan mereka: Individu yang baik mengalihkan mata Steiner mereka kurang daripada individu yang lebih teruk. Seberapa cepat penyelesaian yang baik ditemui, bergantung pada saiz populasi, dan kekuatan mutasi.