19.6 HYPER. .
19.6. HYPER. prove/ 19.2
I HYPER (HYPothesis refinER! i
:- (500, xfx,:}.
4 induce (Hyp):
19.
% Hyp % -
induce!. Hyp):-initcounts,!,
start_hyps(Hyps), best_search[ Hyps, _;Hyp)
% I % %
% best_search[ CandidateHyps, FinalHypothesis)
best_search[ [Hyp I Hypsl, Hyp):-
%
Hyp = 0:, % Cost = 0; ,
%
complete[>. %
be3t_search(!C0;HO I HypsO], ):-
write!'Refining hypo with cost '}, write (CO),
write(:J, nl, show_hyp (HO), nl,.
all_refinements(HO, NewHs), %
add_hyps(NewHs, HypsO, Hyps),!,
addl (refined), % !!
best_search(Hyps, H).
all_refinements(HO, Hyps):-findalK C:H,
1 refine_hyp(HO,H), % H -
once ((addl(generated), %
%
complete(H), addl(complete), eval[H,C) |
% :
4 -
))) -Hyps).
% add_hyps! Hypsl, Kyps2, Hyps):
% Hypsl Kyps2
* Hyps
add_hyps(Hypsl, Hyps2, Hyps):-merge sort! Hypsl, OrderedHypsl), merge (Hyps2, OrderedHypsl, Hyps).
Complete! Hyp):- % Hyp
not (ex?), %
once- prove) P, Hyp, Answ)), % Hyp
Answ \ ]. % ,
% eval! Hypothesis, Cost):
% Cost - Size + 10
i
* ___,
Size
eval! Hyp, Cost):-size! Hyp, S), covers_neg Hyp, (N - 0, "!, Cost is 0; Cost is S + 10*N).
% I
% size { Hyp, Size):
% Size = kl _ + k2
% * ___1,;
% : kl=10, k2=l
II. Prolog
!< [ ], 0).
_ [CsO/VsO 1 RestHyp], Size]:-
sngth(CsO, LO),
sngtht VsO, MO),
iaet RestKyp, SizeRest),
ize is 10*LQ + NO + SizeRest.
overs_neg[ H, K):
N - , , , . , , , prcve/ '.-- '
|
|
■ers_nea(Hyp, N):- % N indall'(1, (nex(E), once(prove(E,Hyp,Answ)), Answ \== no), L),.ength(L, N).
msatisfiablef Clause, Hyp): Clause - ; , Clause Hyp
satisfiabie; [Head Body], Hyp):-
once prove(Body, Hyp, Answ)), Answ = no.
art_hyps (Hyps):- ~t - max_clauses (M), setof[ C:K,
(start_hyp(H,M), addl(generated), complete(H), addl(complete), eval(H,C)), Hyps).
start_hyp(Hyp, MaxClauses):
Hyp - , MaxClauses
:art_hyp! [), _).
: - % |
cart_hyp< [ I Cs], ) > 0, Ml is M-l, start_clause[ ), start_hypt Cs, Ml).
refine_hyp(HypO, Hyp):
, Hyp
efine_hyp{ HypO, Hyp):-choose_clauset HypO, ClauseO/VarsO, Clauses!, Clauses2), I conc(Clauses 1, [Clause/Vars [ Clauses2], Hyp), t
refine ClauseO, VarsO, Clause, Vars), -
%
non_redundant(Clause), I Clause
not unsatisfiable[ Clause, Hyp). % Clause
i
choose_clauset Hyp, Clause, Clausesl, Clauses2):- % ,
% Clause
{ Clausesl, [Clause | Clauses2], Hyp), %
(), %
prove! E, [Clause], yes), % Clause
%
Clausesl, [Clause | Clauses2], Hyp). i!
%
19.
* refinet Clause, Args, NewClause, MewArgs):
% , Clause
% Args NewClause NewArgs
%
refine(Clause, Args, Clause, HewArgs):-
conct Argsl, [A | Args2], Args), ' i
me.Tlber (A, Args2),
Argsl, Args2, NewArgs).
%
refine(Clause, ArgsO, Clause, Argsl:-
del(Var:Type, ArgsO, Argsl), Var:Type
i ArgsO
term'' Type, Var, Vars), % var Type
(Argsl, Vars, Args). 4
%
refine(Clause, Args, NewClause, KewArgs):-
length(Clause, L),
max_clause_length (MaxL),
L < MaxL,
backliteral(Lit, InArgs, RestArgs), %
cone! Clause, [Lit], NewClause], -
connect_inputs i. Args, InArgs}, %
!
cone! Args, RestArgs, KewArgs). i
■ redundant; Clause): , Clause
%
xiQn_redundant ([_]). %
|
|
non_redundant({Litl I Lits]):-not literaljnember ■: Litl, Lits), nor. redundant! Lits).
literal_member(X, [XI I Xs]):- % :■'
% X == XI,!
literaljnember [ X, Xs).
% show_hyp(Hypothesis}:
% , Hypothesis ,
% , ,
show_hyp([]):- nl.
show_hyp([C/Vars | Cs]):- nl, copy term(C/Vars, Cl/Varsl),
s~vars(Varsl, ['A', ' ', ' ',' D', ' E ', ?','G','R', ' I ', ' J', ' ', " L ', '', "N']j, show_clause[ CD, show_hyp(Cs),!.
show_clause((Head | Body]):-
write [ Head},
(Body = []; write (':-'), nl), write_body(Body).
write_body([]}:-
write { '. '),!.
466 II. Prolog
write_body! |G [ Gs]):-!, tab(2), write(G!, (Gs = [],!, write ('.'} nl
write!', '), nl, write_bodyt Gs)
).
name_vars { [], _).
name_varst [Kame:Type I Xs], [Name i Names]i:-name_vars[ Xs, Names).
* connect_inputs(Vars, Inputs):
, Inputs I Vars
eor.nect_inputs (_, []).
connect_inputsf S, [X I Xs]):-membert x, S), conr.ect_in.puts (s, Xs).
% merge! LI, L2, L3): , ,
% ,
merge ([], L, L):-!.
merge (L, [ ], L): -!.
merge! [Xl|Ll], [X2IL2], [X1IL3]):-
XI g = < X2,!, % XI " " 2 ( )
merge(LI, 1X2|L2), L3]. merge) LI, [X2|L2], [X21L3]):-
merge(Ll, L2, L3).
4 mergesort[ Ll, L2): , Ll, L2
mergesort ([], []):-!.
mergesort! [x:, [X]):-!.
mergesort! L, s):-split! L, Ll, L2), mergesort! Ll, El), mergesort! L2, S2), merge! SI, S2, 5).
% split! L, Ll, L2): , L %
split. ([], [], []).
split [ [X], [X], []>
split! (XI,2 I L], [XI [X2iL2]):-split! L, Ll, L2).
I ,
init_counts:-
retract! counteri_,_)!, fail %
assert! counter! generated, 0) J, %
%
19.
assert (counter (complete, 01), % assert (counter! refined, 0)). %
%
addl! Counter):-
retract! countei(Counter, ),!, N1 is N + l, assert (counter! Counter, N1)).
show counts:-
counter generated, KG), counter! refined, NR), counter! complete, NO,
nl, write! 'Hypotheses generated: ■), write(KG),
nl, write! 'Hypotheses refined: '), write (NR),
ToBeRefined is NC - NR,
nl, write! 'To be refined: '), write (ToBeRefined), nl.
max_proof_length | 6). %
%
max_clauses(4). %
ma>;^clause_lerigth (5). %
refine hyp (HypO, Hyp). ,
Hyp,
.
refine (Clause, Vars, NewClause, NewVars). ,
Clause
Vars NewClause
NewVars.
Vars,
Vars
, Clause.
induce_hyp { Hyp). , Hyp . best_search/2.
|
|
best_search< Hyps, Hyp). ,
Hyps, stazt_hyps/l, , Hyp. . Cost: Hypothesis. ( ) .
prove t Goal, Hyp, Answer). , 19.2.
eval i Hyp, Cost). . Cost Hyp , . ,
Cos- = 0.
start_hyps(Hyps). , Hyps
.
,
MaxClauses. MaxClauses
468 II. Prolog
clauses. start_clause.
show hyp { Hyp). , Hyp Prolog.
init counts, show_counts, add! (Counter). , , . : ( ), ( , ) ( ).
start_clause (Clause].
( ),
:
start_clause([ member (X,L! ] / [ K:item, L:list]).
max proof length 0), clauses (MaxClauses), max clause lengthCMaxLength).
, :
,
. ,
member/2 /3 MaxClauses=2.
, 19.6, :
max_proof_Iength(). max_clause3(4). max_clause_length(5}.
19.6 , not/1, once/1, member/2, cone/3, del/3, length/2, copy_term/2.
HYPER member (X, L). HYPER, Prolog , 19.4. :?- induce (), 5how_hyp!H).
HYPER (, ), , . :
Hypotheses generated: 105 t
Hypotheses refined: 26 *
be refined: 15 % ,
|
|
(&, (AjB]).
member(, [|]): -member (, ).
, . , 105 , 26 , 15 . 105 - 26 - 15-51 , . 5 (. 19,5). , . () HYPER, . HYPER ( 10%). , ( , ) .
19,
19.5. cone (LI, L2, L3) , 19.4, HYPER , , . , HYPER.