0

問題: ラベル付き (1..n) 無向グラフが与えられた場合、Gecode でモデルを作成して、特定のシーケンス次数を持つスーパーグラフを見つけます。

難しさ: 主な難しさは、それ以上の度数を正確に表現する派手なモデルを見つけることです:

隣接行列ではないのはなぜですか? グラフは大きくてまばらになりがちなので

エッジリストではないのはなぜですか? エッジを追加しますが、それらの数はわかりません。CP には定義済みの数の変数が必要です (私は正しいですか?)

隣接リストがないのはなぜですか？すべての i, j に対して制約をプッシュする必要があるセットのリストとしてのモデル化問題: (j in a[i] <=> i in a[j])

4

1 に答える 1

2

「隣接リスト」を使用して提供する可能性では、おそらく最良のものになります。

あなたの懸念は、セット間をチャネリングするために多くのプロパゲーターが必要になることです。ただし、Gecode には、セット間でチャネリングするための特別なチャネリング プロパゲータが含まれています: http://www.gecode.org/doc-latest/reference/classGecode_1_1Set_1_1Channel_1_1ChannelSet.html。このプロパゲーターは、あなたが説明した方法とまったく同じように機能し、セットの一貫性を維持するために費やす労力を最小限に抑える必要があります。

于 2016-11-30T15:12:03.303 に答える