Steiner Tree for iOS

説明

このアプリは、進化的アルゴリズムを使用してシュタイナー木を計算します。ツリーのポイントを配置、ドラッグ、および削除できます。シュタイナー ポイントの最適な数と位置が計算されます。最小スパニング ツリー (MST) は、すべてのエッジの合計が最小になるように、平面内の特定のポイント セットを接続します。多くの場合、追加のポイントを追加すると、このすべてのエッジの合計を減らすことができます。これらの点はシュタイナー点と呼ばれ、対応する最小全域木シュタイナー木です。 3 つ以上のポイントが与えられた場合、シュタイナー ポイントの最適な数と位置を計算するのは困難な最適化問題です。このアプリは、デモンストレーション目的で単純な進化的アルゴリズムを使用しています。個人の集団を使用します。各個体は、いくつかのシュタイナー ポイントを含む MST を表します。個体群は、進化のループで最適なシュタイナー ツリーに向かって開発されます。最初に、各個体はランダムなシュタイナー ポイントを設定し、対応するシュタイナー ツリーを構築します。母集団内のシュタイナー ツリーの最小の長さが格納されます。各個体の適応度の値は高くなり、スタイナー ツリーの長さが母集団の最小の長さに近づくほど高くなります。より健康な個体は生殖によってより多くの子孫を持ち、より健康でない個体は死にます。より良い解決策を模索するために、生殖は親個体と同一の子孫を作成しません。つまり、同じ位置にシュタイナー ポイントを持たないことです。むしろ、これらの位置は、ガウス分布を使用して突然変異によってランダムにシフトされます。平均してどれだけシフトするかは、適応度によっても決まります。良い人は、悪い人よりもシュタイナー ポイントのシフトが少なくなります。したがって、良い解が見つかる速度は、母集団のサイズと突然変異の強さに依存します。