6

私は表現をしていると思います、

a = 1 && (b = 1 || b != 0 ) && (c >= 35 || d != 5) && (c >= 38 || d = 6)

私はそれがに減らされることを期待しています、

a = 1 && b != 0 && (c >= 38 || d = 6)

誰か提案はありますか？アルゴリズムへのポインタ？

Nota Bene： Karnaugh MapまたはQuine-McCluskeyは、ここではオプションではないと思います。これらのメソッドは灰色のケースを処理しないためです。つまり、表現は、AまたはA'または何もない、または黒または白または色の欠如のようなものである場合にのみ減らすことができます。しかし、皆さんが見ることができるように、ここでは灰色の色合いがあります。

解決策：このためのプログラムをClojureで作成しました。関数を値として含むマップのマップを使用しました。それは非常に便利で、いくつかの組み合わせに対するいくつかのルールがあり、あなたは良いです。有益な回答をありがとうございます。

4

2 に答える 2

2

制約処理ルールを使えば、思い通りのことができるはずだと思います。OR式とAND式を単純化するルールを作成する必要があります。

主な問題は、ドロップできるパーツを示す制約含意チェックです。たとえば、（c> = 35 || d！= 5）&&（c> = 38 || d = 6）は、前者が後者を伴うため、（c> = 38 || d = 6）に簡略化されます。後者はより具体的です。ただし、OR式の場合は、より一般的な部分を選択する必要があります。

Googleは、ユーザー定義の制約の含意チェックを備えたCHRの拡張に関する論文を見つけました。そのような拡張機能が必要かどうかを判断するのに十分なCHRがわかりません。

于 2012-02-28T16:13:40.900 に答える
1

このようなことは、制約論理プログラミングで定期的に行われていると思います。残念ながら、私はより正確な詳細を提供するのに十分な経験がありませんが、それは良い出発点になるはずです。

一般的な原則は単純です。バインドされていない変数は任意の値を持つことができます。不等式に対してテストすると、可能な値のセットが1つ以上の間隔で制限されます。これらの間隔が単一のポイントに収束する場合、その変数はその値にバインドされます。OTOHで、これらの不等式のいずれかが区間内のすべての値で解決できないと見なされた場合、[プログラミング]論理障害が発生します。

swi-prologを使用してこれが実際にどのように行われるかの例については、これも参照してください。うまくいけば、基礎となるアルゴリズムへのリンクまたは参照が見つかるので、選択したプラットフォームでそれらを再現できます（おそらく既製のライブラリを見つけることさえできます）。

更新： swi-prologとclpfdを使用して例を再現しようとしましたが、期待した結果が得られず、近いものしか得られませんでした。これが私のコードです：

?- [library(clpfd)].
simplify(A,B,C,D) :-
    A #= 1 ,
    (B #= 1 ; B #\= 0 ) ,
    (C #>= 35 ; D #\= 5) ,
    (C #>= 38 ; D #= 6).

そして、私の結果、バックトラック（読みやすくするために改行が挿入されています）：

10 ?- simplify(A,B,C,D).

A = 1,
B = 1,
C in 38..sup ;

A = 1,
B = 1,
D = 6,
C in 35..sup ;

A = 1,
B = 1,
C in 38..sup,
D in inf..4\/6..sup ;

A = 1,
B = 1,
D = 6 ;

A = 1,
B in inf.. -1\/1..sup,
C in 38..sup ;

A = 1,
D = 6,
B in inf.. -1\/1..sup,
C in 35..sup ;

A = 1,
B in inf.. -1\/1..sup,
C in 38..sup,
D in inf..4\/6..sup ;

A = 1,
D = 6,
B in inf.. -1\/1..sup.

11 ?-

したがって、プログラムは、あなたが興味を持った2つ（5番目と8番目）のうち、8つの結果をもたらしました。

A = 1,
B in inf.. -1\/1..sup,
C in 38..sup ;

A = 1,
D = 6,
B in inf.. -1\/1..sup.

もう1つは冗長であり、単純で自動化可能なロジックルールを使用して排除できる可能性があります。

1st or 5th ==> 5th          [B == 1  or B != 0 --> B != 0]
2nd or 4th ==> 4th          [C >= 35 or True   --> True  ]
3rd or 1st ==> 1st ==> 5th  [D != 5  or True   --> True  ]
4th or 8th ==> 8th          [B == 1  or B != 0 --> B != 0]
6th or 8th ==> 8th          [C >= 35 or True   --> True  ]
7th or 3rd ==> 3rd ==> 5th  [B == 1  or B != 0 --> B != 0]

私はそれが一般的な解決策になるのにかなり遅れていることを知っています、しかし私が言ったように、うまくいけばそれは始まりです...

PS私は「通常の」ANDとOR（,と;）を使用しました。clpfdのもの（#/\と#\/）は私が自分自身を理解できない非常に奇妙な結果をもたらしたからです...多分もっと経験豊富な誰かがそれに光を当てることができます...

于 2012-02-28T07:30:12.067 に答える