繰り返し検索は、私は名前と次のような問題に対する効率的な解決策を探しています収束

Question

まで置き換えますsに私は以下の文字列に到着することができます：

1. xycdef 
2. 123def 
3. 123dab 
4. 123dxy 

私の目標は、すべての（？ほとんどの）ルールは（：123dxyここで）適用されてきた「安定」状態に到達することです。

私の質問は、このタイプの問題に対処するための明確なアプローチがあるかどうかです。無限ループ（例えば、ab -> xy,xy -> ab）を避けるための規則には一般的な制約がありますか？反復回数の上限を決める方法はありますか？

関連する概念/関連作業へのあらゆる指針が評価されます。

Answer 1

これをグラフの問題に変換します。
あなたの場合、私はノードab、別のxy、xycなどを持っているでしょう。
ルールに従ってノード間に指示されたエッジが存在します。
ここ：V={ab, xy, xyc, 123, ef}; E={(ab,xy), (xyz.123), (ef, ab)}

基本チェック：
この段階で、あなたのグラフ内のループを持っている場合は、実際の問題を持っています。

接頭辞：
場合ab -> xyとxyc -> 123と私たちに与えられた文字列は、特定の方法で構築されていない限り、二つの規則が問題ではない問題を提供します。 （abcはxycとなる）。これは、特定の方法でマークされた有向エッジで確認できます。 ループを作成すると、特定の文字列で問題は発生しますが、他の文字列では発生しません。

これが役に立った。