使用序言从通用开始和结束节点在树中进行路径搜索

Question

我正在使用一些通用定义搜索路径。例如，当我搜索A到B时，我实际上想找到像A到B、A_1到B_2这样的路径， A 到 B_1，或 A_5 到 B。

根据树中的连接，遍历的中间节点可能有也可能没有类似 _N 的后缀。我的序言语句如下。

path(A,B,Path) :-
  travel(A,B,[A],Q),
  reverse(Q,Path).

travel(A,B,P,[B|P]) :-
  arc(A,B).
travel(A,B,Visited,Path) :-
  arc(A,C),
  C \== B,
  \+member(C,Visited),
  travel(C,B,[C|Visited],Path).

使用这个序言代码，我可以找到一些路径，但找不到其他路径。例如，对于通用搜索条件 A -->15

Paths like (A, 1, 4, 7, 15) are ok,

Paths like (A, 1_1, 4_3, 7, 15) are also ok

Paths like

(A_1, X, X, X, 15)

(A, X, X, X, 15_2),

(A_3, X, X, X, 15_1)

are not ok

注意：X 是任何带下划线或不带下划线的节点的占位符。

你能帮我找出问题吗？

非常感谢，费尔达

Answer 1

我会扩展 arc/2 谓词，或者更好，会引入服务 arc_ext/2，并相应地更改 travel/4：

travel(A,B,P,[B|P]) :- arc_ext(A,B).
travel(A,B,Visited,Path) :- arc_ext(A,C),...

% TBD: optimize, when the logic has been tested
arc_ext(A,B) :-
  arc(X,Y),
  sub_atom(X,0,_,_,A), % X starts with A
  sub_atom(Y,0,_,_,B).

Answer 2

添加这一行解决了问题。

path_generic(A,B,Path) :- path(X,Y,Path),sub_atom(X,0,_,_,A), sub_atom(Y,0,_,_,B).

使用序言从通用开始和结束节点在树中进行路径搜索

Path search in a tree from generic start and end nodes using prolog

prolog