Найти желаемое решение без многократного использования call_nth / 2 или использования findall / 3? - PullRequest
Новая
       35

Найти желаемое решение без многократного использования call_nth / 2 или использования findall / 3?

1 голос
/ 19 апреля 2019

Насколько я понимаю, call_nth (: Goal,? Nth) возвращает N-е решение цели, но в то же время тайно вычисляет все предыдущие решения (от 1-го до (N-1) -го) и просто игнорирует их.,Если мы хотим сравнить X-е с (X + 1) -ым решением для каждого X между 1 и N-1, call_nth становится очень дорогостоящим, потому что он в основном продолжает вычислять решения, которые уже были вычислены на предыдущих этапах.Мне было интересно, если есть более эффективный способ решения проблем этой формы, без использования findall / 3, конечно.

(Типичным примером этого будет сценарий ниже, который находит ЦЕЛЬ или ближайшиймаксимум, если цель не существует в предикатах.) 

num(10).
num(20).
num(30).
num(40).
num(50).

search_for_goal(GOAL,RESULT):-
    search_for_goal(GOAL,0,1,RESULT).

search_for_goal(GOAL,_,COUNTER,GOAL):-
    call_nth(num(GOAL),COUNTER),!.
search_for_goal(GOAL,CURRENT_MAX,COUNTER,RESULT):-
    call_nth(num(X),COUNTER),
    COUNTER2 is COUNTER+1,
    (  X=<CURRENT_MAX->
       search_for_goal(GOAL,CURRENT_MAX,COUNTER2,RESULT)
    ;  search_for_goal(GOAL,X,COUNTER2,RESULT)
    ).
search_for_goal(_,CURRENT_MAX,COUNTER,CURRENT_MAX):-
    \+call_nth(num(_),COUNTER).

1 Ответ

2 голосов
/ 23 мая 2019

Используя SWI-Prolog, этого можно достичь с помощью двигателей Prolog.Чтобы проиллюстрировать это, рассмотрим мою собственную версию предиката findall / 3, которая возвращает только четные решения. 

my_findall(Templ, Goal, List) :-
    setup_call_cleanup(
    engine_create(Templ, Goal, E),
    get_answers(E, List),
    engine_destroy(E)).

get_answers(E, [H|T]) :-
    /* Skip next solution. */
    engine_next(E, _),
    /* Take next solution. */
    engine_next(E, H),
    !,
    get_answers(E, T).

get_answers(_, []).

Запрос с: 

my_findall(X,member(X,[1,2,3,4]),Y)

Возвращает только n-е решениягде n чётно. 

Y = [2, 4]
...