Thực hiện tìm kiếm Prolog

Question

Tôi đã được giao nhiệm vụ triển khai phiên bản tìm kiếm trong Prolog mà không sử dụng bất kỳ Prolog nào được xây dựng ngoại trừ không và cắt - về cơ bản là Prolog thuần túy.

Tôi đang cố gắng để tìm kiếm một cái cây cho tất cả hậu duệ trực tiếp và trả lại kết quả trong một danh sách

parent(a, b). 
parent(b, c). 
parent(b, d). 
parent(e, d). 

Những gì tôi có cho đến nay là:

find(X, L) :- find2(X, [], L). 
find2(X, Acc, L) :- parent(Y, X), find2(Y, [Y|Acc], L). 
find2(_, Acc, Acc). 

Những gì tôi muốn được nhận khi tôi nhập ví dụ:

find(a,X). 

sẽ là:

X = [b, c, d] 

(thứ tự không quan trọng)

Tuy nhiên thay vì tôi nhận được:

X = [b, c] ; 
X = [b, d] ; 
X = [b] ; 
X = []. 

Tôi mới để Prolog vì vậy bất kỳ sự giúp đỡ về vấn đề này sẽ được nhiều đánh giá cao.

Cảm ơn

Answer 1

Cảm ơn bạn đã giúp mọi người. Tôi quản lý để sovle nó cuối cùng bằng cách thêm một vị mà kiểm tra từng hạng mục so với danh sách hiện tại, và thất bại nếu nó đã hiện diện:

find(X, Loa) :- find(X, [], Loa), !. 
find(X, Acc, Loa) :- dec(Y, X), uList(Y, Acc, AccNew), find(X, AccNew, Loa). 
find(_, Acc, Acc). 

dec(X,Y) :- parent(X,Y). 
dec(X,Y) :- parent(X,Z), dec(Z,Y). 

uList(X, [], [X]) :- !. 
uList(H, [H|_], _) :- !, fail. 
uList(X, [H|T], L) :- uList(X, T, Rtn), L = [H|Rtn]. 

Answer 2

Hãy xem this solution. Lưu ý rằng giải pháp này sử dụng biến vị ngữ động có tên là hàng đợi để lưu trữ tất cả các giải pháp cho đến khi tất cả các khả năng bị cạn kiệt. Khi không còn giải pháp nào nữa, việc triển khai sẽ thu hồi tất cả các sự kiện và soạn danh sách.

Đây tất nhiên là một giải pháp đơn giản hóa bit, hãy tưởng tượng điều gì sẽ xảy ra nếu hai tìm kiếm sẽ hoạt động cùng một lúc. Nó cũng hơi mỏng manh về ngữ nghĩa chính xác của khẳng định và rút lại nếu thực hiện prolog cụ thể

Answer 3

Bên cạnh việc xác nhận dữ liệu như bạn thực hiện, bạn cũng có thể sử dụng biến vị ngữ thừa logic như nb_setarg/3. Sau đó, một khi cha mẹ được tìm thấy, bạn không trở lại quá khứ nb_setarg và tìm một phụ huynh khác. Tất cả các giải pháp đã tìm thấy trước đó nên ở trong thuật ngữ bạn đã thực hiện nb_setarg, sau khi tất cả các kết quả đã cạn kiệt, thuật ngữ nb_setarg là câu trả lời. Ví dụ SWI-Prolog là tốt, nhưng nó chỉ là một bộ đếm. Hãy thử làm điều đó với một danh sách (hoặc tốt hơn chưa: danh sách khác biệt) mà xây dựng như bạn đi.

Answer 4

Đây là một giải pháp mà sử dụng hàng đợi SWI-Prolog và chủ đề. Nó sử dụng API hiện có cũ và thực hiện điều gì đó dọc theo Tarau's Engines. Tôi cho rằng việc tạo luồng sẽ sao chép mẫu và mục tiêu. Và sau đó tôi giả định rằng việc gửi hàng đợi một lần nữa sẽ làm một bản sao của mỗi giải pháp.

Vì vậy, so với tìm kiếm cổ điển, bạn sẽ có thặng dư trên một mẫu và bản sao mục tiêu, nhưng nếu không nó cũng sẽ sao chép từng giải pháp như tìm kiếm cổ điển. Nguồn trên gist here. Nhưng bằng cách sửa đổi threadall2, bộ sưu tập nào, cũng có thể triển khai tất cả các loại tập hợp:

% threadall(+Term, +Goal, -List) 
threadall(T, G, L) :- 
    message_queue_create(J, [max_size(1)]), 
    thread_create(threadall3(T, G, J), _, [detached(true)]), 
    thread_get_message(J, A), 
    threadall2(J, A, L), 
    message_queue_destroy(J). 

% threadall3(+Term, +Goal, +Queue) 
threadall3(T, G, J) :- 
    G, thread_send_message(J, the(T)), fail. 
threadall3(_, _, J) :- 
    thread_send_message(J, no). 

% threadall2(+Queue, +Term, -List) 
threadall2(J, the(T), [T|L]) :- !, 
    thread_get_message(J, A), 
    threadall2(J, A, L). 
threadall2(_, no, []). 

Đây là một ví dụ. Tôi hy vọng tôi đã thực hiện việc kế toán một cách chính xác. Các chủ đề đã được tạo ra với tách (đúng), vì vậy chúng tôi không cần xử lý một số khi các chủ đề chấm dứt.Hàng đợi tin nhắn bị phá hủy rõ ràng. Dưới đây là một số ví dụ chạy trong SWI-Prolog, chúng ta thấy rằng nó hoạt động như mong đợi:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.23) 
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam 

?- threadall(X, between(0, 5, X), L). 
L = [0, 1, 2, 3, 4, 5]. 

?- threadall(X-Y, (between(0, 2, X), 
        threadall(Z, between(0, 2, Z), Y)), L). 
L = [0-[0, 1, 2], 1-[0, 1, 2], 2-[0, 1, 2]]. 

Mã của chúng tôi chỉ thực hiện con đường hạnh phúc thông thường: Chúng tôi chỉ triển khai thông báo the/1 và no/0. Hơn nữa kể từ khi chúng tôi không sử dụng setup_call_cleanup/3 nó cũng không an toàn để sử dụng các giải pháp với ngắt. Ngoài ra đối số cuối cùng cũng không kiên định. Tất cả điều này được để lại như một bài tập để người đọc thực hiện các yêu cầu bổ sung này và các đường dẫn thay thế tương ứng.