2

次の問題の名前と効率的な解決策を探しています。文字列s='abcdef'と一連の検索/置換ルールがあるとします。Pn

P1: ab -> xy
P2: xyc -> 123
P3: ef -> ab

これらのルールを順番に適用sすると、次の文字列に到達できます。

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

私の目標は、すべての (ほとんどの?) ルールが適用された「安定した」状態に到達することです (ここでは: 123dxy)。

だから私の質問は、この種の問題に対処するための明確に定義されたアプローチはありますか? ルールに無限ループを回避するための一般的な制約がありますか (例: ab -> xy、xy -> ab)。最大反復回数の境界を決定する方法はありますか?

関連する概念/関連作業へのポインタは大歓迎です。

4

1 に答える 1

1

これをグラフの問題に変換します。
あなたの場合、ab、別xyのxyc、などの名前のノード
があります。ルールに従ってノード間に有向エッジが存在します。
ここ：V={ab, xy, xyc, 123, ef}; E={(ab,xy), (xyz.123), (ef, ab)}

基本的なチェック:
この段階でグラフにループがある場合は、実際に問題があります。

プレフィックス:と
のケースでは、特定の文字列が特定の方法で構築されていない限り、2 つのルールは問題にならないという問題が生じます。（になります）。これは、特定の方法でマークされた有向エッジで確認できます。それらがループを作成すると、特定の文字列で問題が発生しますが、他の文字列では問題が発生しません.ab -> xyxyc -> 123abcxyc

これが役に立ったことを願っています。

于 2016-08-31T08:07:34.057 に答える