1

無向マルチグラフ、つまり (G, E) ペアがあるとします。ここで、G はノードの有限集合であり、E はエッジの有限集合です。次の制約の下で、各ノードに単一の文字列値を割り当てるアルゴリズムを探しています。

1.

すべてのノードには、許容値を制限する一連の (空の可能性がある) 制約が与えられます。少なくとも次のタイプの値の制約をサポートしたいと思います。

  • min-length(x) (値は指定された文字数以上の長さ)、
  • max-length(x) (値は指定された文字数以下)、
  • regexp(x) (値は指定された正規表現に準拠します)、
  • 数値 (値は数字のみで構成されます)。

理想的には、将来的に新しいタイプの制約のサポートを追加できるようにする必要があります。

2.

エッジには次の 2 種類があります。

  • 違う、
  • 同じ、

関連するノードに異なる/同じ値を割り当てる必要があることを意味します(等しくない/等しい文字列を意味します)。

3.

最後に、すべてのノードに次のタイプの制約のセット (場合によっては空の) を割り当てることができます。

  • 異なる-から(x),
  • (x) に等しい、

つまり、指定されたノードには、指定された値とは異なるか等しい値が割り当てられる必要があります。

アルゴリズムが不一致を報告するか (そのような評価が存在しない場合)、基準を満たす評価のいずれか (理想的には小さいもの、つまり、割り当てられた値が少数の文字で構成されるもの) を返すことを期待します (そうでない場合)。 .

アルゴリズムの詳細な説明を提供してくれるとは思っていないことに注意してください。私を正しい軌道に乗せるために、あなたが提供できるヒントをいただければ幸いです。

4

1 に答える 1

1

いくつかの提案:

  • 「同じ」エッジで接続されたすべてのノードを 1 つのノードに結合することで、問題を単純化できます。(この単一ノードの制約は、すべての個々の制約の結合になることに注意してください。)

  • 削減された問題は、接続されたノードのラベルが異なるように各ノードのラベルを選択する必要があるため、グラフの色付けに非常に似ているようです。

  • 残念ながら、グラフの色付けは完全な NP であるため、ノードの数が非常に少ない場合を除き、効率的なアルゴリズムを取得するのに苦労する可能性があります。

グラフの色分けは計算が難しいです。k = 1 と k = 2 の場合を除いて、与えられたグラフが与えられた k に対して k-coloring を認めるかどうかを決定するのは NP 完全です。特に、彩色数を計算するのは NP 困難です。3-coloring 問題は、次数 4 の平面グラフでも NP 完全のままです。

于 2013-07-03T17:56:54.777 に答える