6

次のアルゴリズムをどのようにプログラムしますか?

このような「事実」のリストを想像してみてください。文字は数値にバインドされた変数を表します。

x = 1
y = 2
z = 3
a = 1
b = 2
c = 3
a = x
b = z
c = z

これらの「事実」がすべて「真実」であるとは限らないことは明らかです。b=2 および z=3 の場合、b=z は不可能です。b=z または b=2 のいずれかが削除された場合、すべての事実は一貫しています。z=3 で、b=z または c=z のいずれかが削除された場合、すべての事実は一致しますが、上記よりも事実が 1 つ少なくなります。このセットには、そのような一貫したサブセットが多数含まれています。たとえば、a=1、b=2、c=3 は一貫したサブセットであり、他の多くのサブセットも同様です。

この例では、2 つの一貫したサブセットが他のどの一貫したサブセットよりも大きくなっています。

x = 1
y = 2
z = 3
a = 1
b = 2
c = 3
a = x
c = z

と

x = 1
y = 2
z = 3
a = 1
c = 3
a = x
b = z
c = z

適切なプログラミング言語 (私は PROLOG を考えていますが、間違っているかもしれません) を使用して、一貫性のある事実と一貫性のない事実を含む大きなセットをどのように処理し、一貫性のある事実の可能な最大のサブセット (または次のような複数のサブセット) を出力しますか?上記の例）？

4

2 に答える 2

5

これは、NP 困難な多元切断問題と非常に密接に関連しています。(重み付けされていない) マルチウェイ カット問題では、無向グラフと一連の終端頂点があります。目標は、各終端頂点が独自の接続されたコンポーネントにあるように、できるだけ少ないエッジを削除することです。

この問題では、各変数と各定数を頂点として解釈し、各等値を左辺から右辺への辺として解釈できます。終端の頂点は、定数に関連付けられたものです。

2 つの端末のみの場合、マルチウェイ カット問題は多項式時間で解ける最小カット問題です。最小カットを使用して、多項式時間の 2 近似を多項式カット問題に適用できます。これは、2 つの端子を分離する最も安価なカットを見つけ、関連するエッジを削除し、残りの接続されたコンポーネントを再帰することによって行われます。多方向カットに関する理論文献では、より良い比を持ついくつかの近似アルゴリズムが提案されています。

実際には、コンピュータ ビジョンへの応用では多方向カットが発生するため、正確な解を得るための作業がいくつかあると予想されます。でも、そこに何があるかわかりません。

于 2014-09-13T23:34:58.970 に答える
0

Prolog は便利な実装言語として機能する可能性がありますが、アルゴリズムについてのいくつかの考えでは、特殊なアプローチが有利である可能性があることが示唆されています。

これらの種類のステートメント (2 つの変数間または 1 つの変数と 1 つの定数の間の等値) の中で発生する唯一の矛盾は、2 つの異なる定数を接続するパスです。

したがって、異なる定数のペアを接続するすべての「不一致」パスを見つけた場合、これらのパスのすべてを切断する一連のエッジ (元の等値) を見つけることが必要かつ十分です。

ここでは貪欲なアルゴリズムが最適であると考えがちです。除去するエッジは、残りの「不一致」パスの最大数に共通するものを常に選択してください。したがって、私は提案します：

1) 2 つの異なる定数を接続するすべての単純なパスP(3 番目の定数を通過しない) を見つけ、これらのパスとそのエッジの間に結合構造を構築します。

E2)これらの「不一致」パスに沿って現れるエッジの頻度を数えますP。

3) 貪欲な戦略を追求し、最も頻繁に現れる次のエッジを削除し、それに応じて残りのパスのエッジのカウントを更新することにより、削除するのに十分な数のエッジを見つけます。

4) (ステートメントの一貫したサブセットを残すために) 削除する必要があるエッジの上限を考慮して、バックトラッキング戦略を適用して、より少ない数のエッジで十分かどうかを判断します。

質問の例に適用されるように、正確に 2 つの「矛盾」パスがあることがわかります。

    2 -- b -- z -- 3
 2 -- b -- z -- c -- 3

これらのパスの両方に共通の 2 つのエッジ2 -- bまたはのいずれかを削除すると、b -- z両方の「不一致」パスを切断するのに十分です (残りのステートメント間のすべての不一致を削除します)。

さらに、それを達成するには、他の単一のエッジを削除しても十分ではないことは明らかです。

于 2014-09-15T01:18:40.403 に答える