私は、同じ数字のない整数シーケンス（一般性を失わずに、シーケンスが の順列であると仮定しましょう1,2,...,n）を自然増加順（つまり1,2,...,n）にソートする作業に取り組んでいます。私は、最小限のスワップ回数で要素を直接スワップする（要素の位置に関係なく、言い換えれば、スワップは任意の 2 つの要素に対して有効です）ことを考えていました（以下は実行可能な解決策かもしれません）。
2 つの要素を、その一方または両方を正しい位置に交換するという制約付きで交換します。すべての要素が正しい位置に配置されるまで行います。
しかし、上記の解決策が最適かどうかを数学的に証明する方法がわかりません。誰か助けてくれませんか?
ベストアンサー1
私はこれを証明できたグラフ理論. そのタグを追加した方がいいかもしれません:)
n頂点を持つグラフを作成します。位置の要素が正しい順序で位置にある必要がある場合n_iは、ノードからエッジを作成します。これで、交差しない複数のサイクルで構成されるグラフが作成されます。グラフを正しく順序付けるために必要なスワップの最小数は、n_jij
M = sum (c in cycles) size(c) - 1
少し時間を取って、それを納得してください... 2 つのアイテムが循環している場合、1 回のスワップでそれらを処理できます。3 つのアイテムが循環している場合、ペアを交換して 1 つを適切な場所に配置できますが、2 つのサイクルが残ります。nアイテムが循環している場合は、n-1スワップが必要です。(これは、すぐ隣のアイテムとスワップしない場合でも常に当てはまります。)
これを踏まえると、アルゴリズムがなぜ最適であるかがわかるでしょう。スワップを実行し、少なくとも 1 つのアイテムが正しい位置にある場合、 の値が常にM1 減少します。長さ のサイクルではn、要素を、その隣の要素が占める正しい位置にスワップすることを検討してください。これで、正しく順序付けられた要素と、長さ のサイクルが得られますn-1。
はMスワップの最小数であり、アルゴリズムはMスワップごとに常に 1 ずつ減少するため、最適である必要があります。