нужен совет с прологом? - PullRequest
Новая
       25

нужен совет с прологом?

1 голос
/ 02 марта 2011

в этой задаче у меня есть база данных Prolog, заполненная, например, ребром (1,0), ребром (2,0), ребром (1,3)

ребро означает, что две точки соединены.

Меня просят написать функцию, которая называется досягаемостью (i, j, k), где i - начальная точка, j - конечная точка, а k - количество шагов, которые вы можете использовать.K необходим для остановки цикла рекурсии, например,

Предположим, что единственное полученное мной преимущество идет от 1 до 3, и я пытаюсь добраться до 6. Тогда я не могу получить от 1 до 6 за один раз.поэтому я поищу где-нибудь, куда смогу добраться, и посмотрю, смогу ли я добраться оттуда до 6. Первое место, куда я могу добраться за один раз, это 3, поэтому я постараюсь оттуда добраться до 6.

я сделал это так: 

    %% Can you get there in one step (need two rules because all links are
%% from smaller to greater, but we may need to get from greater to smaller.

reach1(I, J,_K) :-
    edge(I, J).
reach1(I, J,_K) :-
    edge(J, I).
%% Chhose somewhere you can get to in one step: can you get from there
%% to your target?
reach1(I,J,K) :-
    K>1,
    edge(I, B),
    K1 is K-1,
    reach1(B,J,K1).

reach1(I,J,K) :-
    K>1,
    edge(B, I),
    K1 is K-1, 
    reach1(B,J,K1).

это работает, однако я застрял со второй частью, в которой нас просят не использовать k, а использовать "cut", чтобы сделать это.

Кто-нибудь знает, как это сделать, или может дать мне несколько советов?

1 Ответ

0 голосов
/ 30 апреля 2011

Сокращение гарантирует, что после того, как цель была решена одним способом, она не ищет другого пути.

пример: 

reach(I, J,_K) :-
    edge(I, J).

нет сокращения - если по какой-то причинеПролог возвращается, он попытается добраться от меня к J другим путем.Вы можете почувствовать, что нет смысла добираться до этого узла другим способом, если работает простое ребро, и в этом случае вы можете сделать: 

reach(I, J,_K) :-
    edge(I, J),
    !.

, который «режет» любую альтернативу этой цели, но тот, который обнаружил Пролог.

...