algorithm - 特定のアナグラムを別のアナグラムにするために必要なスワップの最小数

Question

2 つのアナグラム S1 と S2 が与えられた場合、S1 アナグラムを S2 アナグラムに変換します。これに必要な隣接スワップの最小数を見つける必要があります。

例: S1:CAT および S2:ACT。ここで、スワップの最小数は 1 だけです。C を A にスワップして S2 を取得します。

動的計画法を使用してどのようにそれを行うことができますか。出来ますか？

Answer 1

最適解を得る 1 つのアプローチは、問題を最短経路問題に縮小することです。

ここでは、各頂点は、指定された文字を使用した 1 つの可能なアナグラムです。2 つの頂点 (アナグラム) 間のエッジは、1 回のスワップで一方から他方に移動できる場合にのみ存在します。

入力アナグラムから目的のアナグラムへの最短経路を見つけると、最適な数の経路が得られます。

重み付けされていないグラフの最短経路問題は、 BFS、双方向BFS またはA* アルゴリズムで解決できます。