Определение пути / тропы / прогулки

Question

Определение пути / тропы / прогулки

Многие предикаты определяют своего рода ациклический путь, построенный из ребер, определенных через бинарное отношение, очень похоже на определение транзитивного замыкания. Таким образом, требуется общее определение.

Обратите внимание, что понятия, определенные в теории графов, не всегда совпадают с ожидаемыми. В частности, нас не интересуют имена ребер.

Хуже того, теория графов немного изменилась, введя понятие ходьбы, отметив

Традиционно путь называется тем, что сейчас обычно называют открытой прогулкой. В настоящее время, когда указывается без какой-либо квалификации, путь обычно понимается как простой, что означает, что никакие вершины (и, следовательно, нет ребер) не повторяются. (Термин цепочка также использовался для обозначения обхода, в котором все вершины и ребра различны.)

Поэтому мой вопрос: как назвать и определить эту функциональность?

На данный момент я определил:

path(Rel_2, Path, X0,X)

Первым аргументом должно быть продолжение отношения. Затем приходит либо Path или пара вершин.

Пример использования

n(a, b).
n(b, c).
n(b, a).

?- path(n,Xs, a,X).
Xs = [a], X = a ;
Xs = [a, b], X = b ;
Xs = [a, b, c], X = c ;
false.

Реализация

:- meta_predicate path(2,?,?,?).

:- meta_predicate path(2,?,?,?,+).

path(R_2, [X0|Ys], X0,X) :-
   path(R_2, Ys, X0,X, [X0]).

path(_R_2, [], X,X, _).
path(R_2, [X1|Ys], X0,X, Xs) :-
   call(R_2, X0,X1),
   non_member(X1, Xs),
   path(R_2, Ys, X1,X, [X1|Xs]).

non_member(_E, []).
non_member(E, [X|Xs]) :-
   dif(E,X),
   non_member(E, Xs).

46

graph prolog meta-predicate

Источник

user772868 19 май '15 в 14:24

3 ответа

Другие вопросы по тегам graph prolog meta-predicate

user4609915 30 июл '15 в 12:39 2015-07-30 12:39 · Answer 1 · 2015-07-30 12:39

Как насчет определения path/4 как это?

path(R_2, Xs, A,Z) :-                   % A path `Xs` from `A` to `Z` is ...
   walk(R_2, Xs, A,Z),                  % ... a walk `Xs` from `A` to `Z` ...
   all_dif(Xs).                         % ... with no duplicates in `Xs`.

Чтобы помочь всеобщему расторжению, мы поменяем две цели в вышеуказанном соединении

path(R_2, Xs, A,Z) :-
   all_dif(Xs),                         % enforce disequality ASAP
   walk(R_2, Xs, A,Z).

... и использовать следующую ленивую реализацию all_dif/1:

all_dif (Xs): -% обеспечивает неравенство парных членов
   заморозить (Xs, all_dif_aux(Xs,[])).      % (может быть отложено)

all_dif_aux ([], _).
all_dif_aux ([E | Es], Vs): -               
   maplist(dif (E), Vs),% никогда не задерживается
   заморозить (Es, all_dif_aux(Es,[E|Vs])).  % (может быть отложено)

walk/4 определяется как path/4 а также path/5 данный ОП:

:- meta_predicate walk(2, ?, ?, ?).
walk(R_2, [X0|Xs], X0,X) :-
   walk_from_to_step(Xs, X0,X, R_2).

:- meta_predicate walk_from_to_step(?, ?, ?, 2).
walk_from_to_step([], X,X, _).
walk_from_to_step([X1|Xs], X0,X, R_2) :-
   call(R_2, X0,X1),
   walk_from_to_step(Xs, X1,X, R_2).

ИМО выше path/4 проще и доступнее, особенно для новичков. Вы согласны?

user4609915 02 июн '15 в 11:49 2015-06-02 11:49 · Answer 2 · 2015-06-02 11:49

Я хочу сосредоточиться на названии предиката.

В отличие от maplist/2 порядок аргументов здесь не имеет первостепенного значения.
Имя предиката должно прояснить значение соответствующих аргументов.

Пока что мне нравится path_from_to_edges лучше, но у него есть свои плюсы и минусы тоже.

path_from_to_edges(Path,From,To,Edges_2) :-
    path(Edges_2,Path,From,To).

Давайте выберем это отдельно:

про: path это существительное, оно не может быть неправильно прочитано глагол. Для меня список вершин подразумевается.
про: from обозначает вершину, и так же to,
против: edges является несколько расплывчатым, но использование лямбд здесь - самый универсальный выбор.
con: согласно Википедии, путь - это тропа, в которой все вершины (кроме, возможно, первой и последней) различны. Так что это должно быть уточнено в описании.

Использование лямбд для списков соседних вершин Ess:

?- Ess  = [a-[b],b-[c,a]], 
   From = a,
   path_from_to_edges(Path,From,To,\X^Y^(member(X-X_neibs,Ess),member(Y,X_neibs))).
Ess = [a-[b],b-[c,a]], From = a, To = a, Path = [a]     ;
Ess = [a-[b],b-[c,a]], From = a, To = b, Path = [a,b]   ;
Ess = [a-[b],b-[c,a]], From = a, To = c, Path = [a,b,c] ;
false.

Редактировать 2015-06-02

Еще один выстрел в лучшем названии! Это опирается больше на стороне maplist/2...

graph_path_from_to(P_2,Path,From,To) :-
   path(P_2,Path,From,To).

Вот, graph Конечно, это существительное, а не глагол.

Что касается значения "путь": пути определенно должны позволять From=To и не исключаем, что по умолчанию (с попарно неравенствами). Это легко исключить дополнительным dif(From,To) цель, но не наоборот.

user4886927 31 май '15 в 09:25 2015-05-31 09:25 · Answer 3 · 2015-05-31 09:25

Я не вижу смысла определять в path/4 аргументы "начальный узел" и "конечный узел". Кажется, что простого пути /2 с правилом и списком узлов должно быть достаточно.

Если пользователь хочет получить список, начинающийся с некоторого узла (например, "a"), он может запросить оператор как: путь ( some_rule, ['a'|Q]).

Например, пользователь может запросить путь, длина которого равна 10: длина (P,10), путь (some_rule, P).

* Приложение 1 *

Некоторые полезные цели могут быть легко добавлены, но они не являются основной темой. Пример, путь /3 с начальным узлом:

path( some_rule, [start|Q], start ) :- 
  path ( some_rule, [start|Q ] ).

* Приложение 2 *

Добавление последнего узла в качестве аргумента может дать ложное представление о том, что этот аргумент управляет алгоритмом, но это не так. Предположим на примере:

n(a, b).
n(a, c).
n(a, d).

и проследить выполнение алгоритма для запроса:

[trace]  ?- path( n, P, X, d ).
   Call: (6) path(n, _G1025, _G1026, d) ? creep
   Call: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Exit: (7) path(n, [], d, d, [d]) ? creep
   Exit: (6) path(n, [d], d, d) ? creep
P = [d],
X = d ;
   Redo: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Call: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, b) ? creep

   Call: (8) non_member(b, [a]) ? creep
   Call: (9) dif:dif(b, a) ? creep
   Exit: (9) dif:dif(b, a) ? creep
   Call: (9) non_member(b, []) ? creep
   Exit: (9) non_member(b, []) ? creep
   Exit: (8) non_member(b, [a]) ? creep
   Call: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Call: (9) n(b, _G1118) ? creep
   Fail: (9) n(b, _G1118) ? creep
   Fail: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Redo: (9) non_member(b, []) ? creep
   Fail: (9) non_member(b, []) ? creep
   Fail: (8) non_member(b, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, c) ? creep

   Call: (8) non_member(c, [a]) ? creep
   Call: (9) dif:dif(c, a) ? creep
   Exit: (9) dif:dif(c, a) ? creep
   Call: (9) non_member(c, []) ? creep
   Exit: (9) non_member(c, []) ? creep
   Exit: (8) non_member(c, [a]) ? creep
   Call: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Call: (9) n(c, _G1118) ? creep
   Fail: (9) n(c, _G1118) ? creep
   Fail: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Redo: (9) non_member(c, []) ? creep
   Fail: (9) non_member(c, []) ? creep
   Fail: (8) non_member(c, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, d) ? creep

   Call: (8) non_member(d, [a]) ? creep
   Call: (9) dif:dif(d, a) ? creep
   Exit: (9) dif:dif(d, a) ? creep
   Call: (9) non_member(d, []) ? creep
   Exit: (9) non_member(d, []) ? creep
   Exit: (8) non_member(d, [a]) ? creep
   Call: (8) path(n, _G1113, d, d, [d, a]) ? creep
   Exit: (8) path(n, [], d, d, [d, a]) ? creep
   Exit: (7) path(n, [d], a, d, [a]) ? creep
   Exit: (6) path(n, [a, d], a, d) ? creep
P = [a, d],
X = a .

как вы можете видеть, в этом случае алгоритм не работает грубо. По этой причине, если алгоритм не улучшен, я предлагаю не добавлять "конечный узел" в качестве аргумента "путь".