3

2 つの数式が実際に同じかどうかをチェックするプロローグ プログラムを作成しています。たとえば、数式の目標が (a + b) + c の場合、次の式はどれも同じと見なされます。

(a+b)+c

a+(b+c)

(b+a)+c

(c+a)+b

a+(c+b)

c+(a+b)

と他の組み合わせ

確かに、式はそれよりも複雑になる可能性があるため、考えられる答えの組み合わせをチェックするつもりはありません。

現在、これが私のアプローチです。たとえば、 a + b *c が c*b+a などの別の式と同じかどうかを確認したい場合、両方の式を再帰的にバイナリ式として保存し、最初の式と 2 番目の式の「値」を与える ValueOf などのルール。次に、両方の式の「値」が同じかどうかを確認するだけで、両方の式が同じであると言えます。問題は、式の内容が数値ではなく識別子であるため、プロローグの「is」キーワードを使用して値を取得できないことです。

なにか提案を？

どうもありがとう

% represent a + b * c
binExprID(binEx1).
hasLeftArg(binEx1, a).
hasRightArg(binEx1, binEx2).
hasOperator(binEx1, +).

binExprID(binEx2).
hasLeftArg(binEx2, b).
hasRightArg(binEx2, c).
hasOperator(binEx2, *).

% represent c * b + a
binExprID(binEx3).
hasLeftArg(binEx3, c).
hasRightArg(binEx3, b).
hasOperator(binEx3, *).

binExprID(binEx4).
hasLeftArg(binEx4, binEx3).
hasRightArg(binEx4, a).
hasOperator(binEx4, +).

goal:- valueOf(binEx1, V),
       valueOf(binEx4, V).
4

1 に答える 1

5

数式は非常に複雑になる可能性があります。代わりに算術について言及していると思います。通常の形式 (私の言い回しが適切であることを願っています) は「単項式の和」です。

とにかく、一般的に解決するのは簡単な作業ではなく、要求にはあいまいさがあります。2 つの式が構文的に異なる (つまり、構文ツリーが異なる) 場合がありますが、それでも値は同じです。これは明らかに、0 の加算/減算など、値を変更しない操作によるものです。

あなたの説明から、あなたは「評価された」アイデンティティに興味があると思います。次に、等しいかどうかを比較する前に、両方の式を正規化できます。

構文上の同一性を評価するには、すべての括弧を削除し、加数に「分散」要素を加えます。式は乗法項のリストになります。基本的に、「値」を変更せずにソートできるリストのリストを取得します。

式が平坦化された後、すべての乗法定数を累積する必要があります。

簡単な例:

a+(b+c)*5[[1,a],[b,5],[c,5]]間になりa+5*(c+b)ます[[1,a],[5,c],[5,b]]

いくつかの改善後に編集します。これは非常に重要な正規化手順です。

:- [library(apply)].

arith_equivalence(E1, E2) :-
    normalize(E1, N),
    normalize(E2, N).

normalize(E, N) :-
    distribute(E, D),
    sortex(D, N).

distribute(A, [[1, A]]) :- atom(A).
distribute(N, [[1, N]]) :- number(N).
distribute(X * Y, L) :-
    distribute(X, Xn),
    distribute(Y, Yn),
    % distribute over factors
    findall(Mono, (member(Xm, Xn), member(Ym, Yn), append(Xm, Ym, Mono)), L).
distribute(X + Y, L) :-
    distribute(X, Xn),
    distribute(Y, Yn),
    append(Xn, Yn, L).

sortex(L, R) :-
    maplist(msort, L, T),
    maplist(accum, T, A),
    sumeqfac(A, Z),
    exclude(zero, Z, S),
    msort(S, R).

accum(T2, [Total|Symbols]) :-
    include(number, T2, Numbers),
    foldl(mul, Numbers, 1, Total),
    exclude(number, T2, Symbols).

sumeqfac([[N|F]|Fs], S) :-
    select([M|F], Fs, Rs),
    X is N+M,
    !, sumeqfac([[X|F]|Rs], S).
sumeqfac([F|Fs], [F|Rs]) :-
    sumeqfac(Fs, Rs).
sumeqfac([], []).

zero([0|_]).
mul(X, Y, Z) :- Z is X * Y.

いくつかのテスト:

?- arith_equivalence(a+(b+c), (a+c)+b).
true .

?- arith_equivalence(a+b*c+0*77, c*b+a*1).
true .

?- arith_equivalence(a+a+a, a*3).
true .

重複が失われないように、include/3、exclude/3、foldl /5、msort /2 などの SWI-Prolog ビルトインを使用しました。

これらは基本的なリスト操作のビルトインで、システムにない場合でも簡単に実装できます。

編集

SWI-Prolog apply.pl で定義されている foldl/4:

:- meta_predicate
    foldl(3, +, +, -).

foldl(Goal, List, V0, V) :-
    foldl_(List, Goal, V0, V).

foldl_([], _, V, V).
foldl_([H|T], Goal, V0, V) :-
    call(Goal, H, V0, V1),
    foldl_(T, Goal, V1, V).

取扱区分

除算により多少の複雑さが生じますが、これは想定内のことです。結局のところ、それは数の完全なクラスである有理数を導入します。

ここに変更された述語がありますが、コードにはさらに多くのデバッグが必要になると思います。したがって、このマイクロ書き換えシステムが解決できることの「単体テスト」も主張します。また、自分で否定を導入したわけではないことに注意してください。必要な変更があれば解決できることを願っています。

/*  File:    arith_equivalence.pl
    Author:  Carlo,,,
    Created: Oct  3 2012
    Purpose: answer to http://stackoverflow.com/q/12665359/874024
             How to check if two math expressions are the same?
         I warned that generalizing could be a though task :) See the edit.
*/

:- module(arith_equivalence,
      [arith_equivalence/2,
       normalize/2,
       distribute/2,
       sortex/2
      ]).

:- [library(apply)].

arith_equivalence(E1, E2) :-
    normalize(E1, N),
    normalize(E2, N), !.

normalize(E, N) :-
    distribute(E, D),
    sortex(D, N).

distribute(A, [[1, A]]) :- atom(A).
distribute(N, [[N]]) :- number(N).
distribute(X * Y, L) :-
    distribute(X, Xn),
    distribute(Y, Yn),
    % distribute over factors
    findall(Mono, (member(Xm, Xn), member(Ym, Yn), append(Xm, Ym, Mono)), L).
distribute(X / Y, L) :-
    normalize(X, Xn),
    normalize(Y, Yn),
    divide(Xn, Yn, L).
distribute(X + Y, L) :-
    distribute(X, Xn),
    distribute(Y, Yn),
    append(Xn, Yn, L).

sortex(L, R) :-
    maplist(dsort, L, T),
    maplist(accum, T, A),
    sumeqfac(A, Z),
    exclude(zero, Z, S),
    msort(S, R).

dsort(L, S) :- is_list(L) -> msort(L, S) ; L = S.

divide([], _, []).
divide([N|Nr], D, [R|Rs]) :-
    (   N = [Nn|Ns],
        D = [[Dn|Ds]]
    ->  Q is Nn/Dn,  % denominator is monomial
        remove_common(Ns, Ds, Ar, Br),
        (   Br = []
        ->  R = [Q|Ar]
        ;   R =  [Q|Ar]/[1|Br]
        )
    ;   R = [N/D]    % no simplification available
    ),
    divide(Nr, D, Rs).

remove_common(As, [], As, []) :- !.
remove_common([], Bs, [], Bs).
remove_common([A|As], Bs, Ar, Br) :-
    select(A, Bs, Bt),
    !, remove_common(As, Bt, Ar, Br).
remove_common([A|As], Bs, [A|Ar], Br) :-
    remove_common(As, Bs, Ar, Br).

accum(T, [Total|Symbols]) :-
    partition(number, T, Numbers, Symbols),
    foldl(mul, Numbers, 1, Total), !.
accum(T, T).

sumeqfac([[N|F]|Fs], S) :-
    select([M|F], Fs, Rs),
    X is N+M,
    !, sumeqfac([[X|F]|Rs], S).
sumeqfac([F|Fs], [F|Rs]) :-
    sumeqfac(Fs, Rs).
sumeqfac([], []).

zero([0|_]).
mul(X, Y, Z) :- Z is X * Y.

:- begin_tests(arith_equivalence).

test(1) :-
    arith_equivalence(a+(b+c), (a+c)+b).

test(2) :-
    arith_equivalence(a+b*c+0*77, c*b+a*1).

test(3) :-
    arith_equivalence(a+a+a, a*3).

test(4) :-
    arith_equivalence((1+1)/x, 2/x).

test(5) :-
    arith_equivalence(1/x+1, (1+x)/x).

test(6) :-
    arith_equivalence((x+a)/(x*x), 1/x + a/(x*x)).

:- end_tests(arith_equivalence).

単体テストの実行:

?- run_tests(arith_equivalence).
% PL-Unit: arith_equivalence ...... done
% All 6 tests passed
true.
于 2012-10-01T00:02:07.120 に答える