たとえば 、入力文字列があるとすると、次のようにターゲット文字列がaab
与え
られます。次に、一連の変換ルールが与えられます。例えば：bababa
ab -> bba
b -> ba
Cで、ターゲット文字列を取得するために入力文字列に適用する必要のある変換の最小数を見つけるアルゴリズムをどのように実行できますか。
たとえば、この例では、番号は3になります。
1 - Apply rule 1 (abba)
2 - Apply rule 1 again (bbaba)
3 - Apply rule 2 (bababa)
入力とターゲットが与えられた場合、解決策がない可能性があり、それにも注意する必要があります。
私はこれを行うための戦略にかなり迷っています。オートマトンを作成することが頭に浮かびますが、この状況でどのように適用するかはわかりません。私は興味深い問題だと思います。私はオンラインで調査していますが、私が見つけることができるのはルールを与えられた変換だけであり、それが最小であることを保証する方法ではありません。
編集：提案された答えの1つとして、最初の文字列から開始してグラフを作成し、前のノードに変換を適用した結果であるノードを作成することができます。しかし、これは私の観点から、いくつかの問題をもたらします：
このような変換があると想像してください->ab。そして、私の最初の文字列は「a」です。そして、私の出力文字列は'c'です。だから、私はこのように変換（グラフを成長させる）を続けます：
a-> ab ab-> abb abb->abbb..。
グラフの作成を停止する必要がある場合、どうすればわかりますか？
- 次の文字列aaaaがあり、aa->bのような変換規則があるとします。新しいノードを作成するにはどうすればよいですか？つまり、その入力文字列からサブ文字列を見つけて覚えるにはどうすればよいでしょうか。