Блог

Я пытаюсь создать функцию в GProlog, которая, на мой взгляд, довольно проста, но у меня возникают проблемы с ее написанием.

Идея состоит в том, чтобы предположить, что взвешенный ориентированный граф описывается с помощью предиката edge/3, такого, что edge (X, Y, C) является истинным, если существует ребро от вершины X до вершины Y стоимостью C. Например, справа находится граф и его описание с использованием edge/3: ребро (a, c,1). ребро (a, d, 3). ребро (b,d,2). ребро (c, e,5). ребро (e, c,2). ребро (e,f,2). ребро (d,f,10).

Цель состоит в том, чтобы определить предикат cheaperPath/3, такой, чтобы cheaperPath(X, Y,N) был истинным, если существует путь от X до Y общей стоимостью меньше N. Предполагается, что предикат вызывается со всеми созданными экземплярами X, Y и N, например, для запроса cheaperPath(a, f,7) ответ должен быть no .

Вот что я сделал на данный момент в Gprolog, но цикл, похоже, продолжается и продолжается:

 edge(a, c,1).
edge(a,d,3).
edge(b,d,2).
edge(c,e,5).
edge(e, c,2).
edge(e,f,2).
edge(d,f,10).


cheaperPath(X,Y,N):-edge(X,Y,N1),N1@=<N.
cheaperPath(X,Y,N):-edge(X,Z,N1),cheaperPath(Z,Y,M),M is (N-N1).

 

Есть идеи, почему??

Вы должны уменьшить границу, когда берете ребро, поэтому:

 cheaperPath(X, Y, N) :-
    edge(X,Y,N1),
    N1 @=< N.
cheaperPath(X,Y,N):-
    edge(X,Z,N1),
    M is N-N1,
    M > 0,
    cheaperPath(Z,Y,M). 

В противном случае вы реализуете это способом генерации и тестирования, когда вы сначала генерируете весь путь, а затем проверяете, что это действительно более короткий путь.