Steiner Tree for iOS

Deskripsi

Aplikasi ini menghitung pohon Steiner menggunakan algoritma evolusioner. Anda dapat menempatkan, menyeret, dan menghapus titik pohon Anda. Jumlah dan posisi titik Steiner yang optimal dihitung. Sebuah pohon merentang minimal (MST) menghubungkan sekumpulan titik tertentu dalam sebuah bidang sehingga jumlah semua sisinya minimal. Seringkali jumlah semua sisi ini dapat dikurangi, jika poin tambahan ditambahkan. Titik-titik ini disebut titik Steiner, dan pohon merentang minimal yang sesuai Pohon Steiner. Jika lebih dari 3 poin diberikan, itu adalah masalah optimasi yang sulit untuk menghitung jumlah dan posisi optimal poin Steiner. Aplikasi ini menggunakan algoritma evolusioner sederhana untuk tujuan demonstrasi. Ini menggunakan populasi individu. Setiap individu mewakili MST yang berisi beberapa poin Steiner. Populasi berkembang menuju pohon Steiner yang optimal dalam lingkaran evolusi: Awalnya, setiap individu menetapkan titik Steiner acak, dan membangun pohon Steiner yang sesuai. Panjang minimal pohon Steiner dalam populasi disimpan. Setiap individu sekarang memiliki nilai fitness, yang semakin tinggi, semakin dekat panjang pohon Steinernya dengan panjang minimal dalam populasi. Individu yang lebih bugar memiliki lebih banyak keturunan melalui reproduksi, dan individu yang kurang fit akan mati. Untuk mencari solusi yang lebih baik, reproduksi tidak membuat keturunan yang identik dengan individu induk, yaitu tidak memiliki titik Steiner pada posisi yang sama. Sebaliknya posisi ini digeser secara acak oleh mutasi, menggunakan distribusi Gaussian. Seberapa jauh mereka bergeser rata-rata ditentukan juga oleh kebugaran mereka: Individu yang baik menggeser poin Steiner mereka lebih sedikit daripada individu yang lebih buruk. Seberapa cepat solusi yang baik ditemukan, bergantung pada ukuran populasi, dan kekuatan mutasi.