нужен совет по сокращению пролога?

в этой задаче у меня есть база данных 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, а использовать для этого «разрез».

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


recursion prolog prolog-cut
person learner123    schedule 02.03.2011    source источник
comment
Возможно, вы захотите взглянуть на stackoverflow .com / questions / 3970977 /, где обсуждается обход графа. В решении там тоже нет разреза, но я считаю, что оно намного элегантнее. Конечно, вы можете переписать это решение, чтобы использовать разрез для обрезки дерева обратного отслеживания, когда вы дойдете до уже посещенного узла.   -  person gusbro    schedule 02.03.2011
comment
Я не понимаю, что означало бы сделать это, но не использовать K, поскольку он является частью спецификации range1 / 3. Кроме того, ваши первые два правила, одноэтапные случаи, предположительно должны иметь не _K, а 1 в качестве третьего аргумента для охвата1. Общая проблема с поиском путей заключается в том, как избежать бесконечной рекурсии, например переход от 1 к 2, обратно к 1, обратно к 2 и так далее, никогда не продвигаясь к реальной цели. Возможно, первоначальное упражнение было направлено на изучение различных способов предотвращения такого зацикливания. Трудно сказать из настоящего запроса.   -  person hardmath    schedule 02.03.2011

Ответы (1)


arrow_upward
0
arrow_downward

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

пример:

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

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

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

который «отсекает» любую альтернативу этой цели, кроме той, которую нашел Prolog.

person boisvert    schedule 29.04.2011