Tìm kiếm giới hạn độ sâu trong prolog (vanilla meta-interpreter)

Question

Tôi cần sửa đổi trình thông dịch meta vanilla để thực hiện tìm kiếm có độ sâu giới hạn. Tôi đang sử dụng đoạn mã sau để thử nghiệm sollution tôi:

value(wire1,1). 
connected(wire2, wire1). 
connected(wire3, wire2). 
connected(wire4, wire3). 
connected(wire5, wire4). 
connected(wire6, wire5). 
connected(wire7, wire6). 
connected(wire8, wire7). 
connected(wire9, wire8). 
value(W,X):-connected(W,V), value(V,X). 

Và mục tiêu là một cái gì đó như:

solve(value(w9,X), 3).  /*depth =3, it should return false*/ 
solve(value(w9,X), 20). /*depth=20 is enought for returning X=1*/ 

Bằng cách này mã của tôi là

solve(true,_):-!. 
solve((A,B),D) :-!, solve(A,D), solve(B,D). 
solve(A,D) :- clause(A, B),solve(B,D2),D=D2+1,D>0). 

Nhưng nó don 't làm việc tài sản. Bạn có thể giúp tôi được không? Cảm ơn rất nhiều trước

Answer 1

Một trang thú vị về lập trình meta đến từ một nhà phát triển giỏi: Markus Triska. Here (Một cặp siêu thông dịch viên trong Prolog) bạn tìm thấy cả lý thuyết và thực hành. Ví dụ:

... Một nhóm tiện ích mở rộng khác nhằm cải thiện chiến lược tính toán mặc định chưa hoàn chỉnh. Chúng tôi bắt đầu từ một MI giới hạn độ sâu của cây tìm kiếm:

 mi_limit(Goal, Max) :- 
       mi_limit(Goal, Max, _). 

     mi_limit(true, N, N). 
     mi_limit((A,B), N0, N) :- 
       mi_limit(A, N0, N1), 
       mi_limit(B, N1, N). 
     mi_limit(g(G), N0, N) :- 
       N0 > 0, 
       mi_clause(G, Body), 
       N1 is N0 - 1, 
       mi_limit(Body, N1, N). 

Answer 2

Bạn sắp sửa ở đó. Chỉ có điều khoản cuối cùng cần có một sắp xếp lại nhẹ:

solve(A, D) :- clause(A, B), D1 is D - 1, D1 > 0, solve(B, D1). 

?- solve(value(wire9, X), 9).  ===> false. 
?- solve(value(wire9, X), 10).  ===> X = 1. 

Answer 3

dls(X,X,[X],L):- 
    L >0 goal(X). 
dls(X,Y,[A|p],L):- 
    L > 0 ,goal(Y) , 
    move(X,Y), 
    L1 is L - 1 , 
    dls(Z,Y ,P,L1).