Prolog深度优先迭代加深

Question

我正在尝试实现一个状态空间图的深度优先迭代加深搜索算法。我的图有三个顶点，其中有两条激活边和两条抑制边。每个节点都有一个二进制值，这是图形的状态。通过查看一个节点是否高于或低于阈值（从所有传入节点的总和计算）可以将图转换为新状态。每次转换最多只会更改一个节点。由于有三个节点，因此每个状态在状态转换图中都有三个状态转换边。 我认为我的state_change/3函数工作得很好，例如我可以查询:

?-g_s_s(0,1,1,Begin),node(Arc),state_change(g_s(Begin),Second,Arc).

并且它给出了我三个正确答案：

Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
Arc = v1,
Second = g_s([node(v1, 1), node(v2, 1), node(v3, 1)]) ;

Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
Arc = v2,
Second = g_s([node(v1, 0), node(v2, 0), node(v3, 1)]) ;

Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
Arc = v3,
Second = g_s([node(v1, 0), node(v2, 1), node(v3, 0)]) 

我正在尝试使用Bratkos Prolog for A.I书中提供的谓词id_path解决11.3问题，但我在使用/调整时遇到了问题。 我想创建一条从起始节点到其他节点的路径，而不会陷入循环-我不希望它有重复元素或在不存在路径时卡住。 我希望路径显示起始状态，然后是可以从起始状态访问的一系列状态。如果存在自环，我希望每种方法都包括一次。也就是说，我想跟踪到达状态空间的方式，并使其唯一，而不仅仅是路径中状态空间的唯一性。

例如，对于011，我希望找到所有长度为1的三条路径及其弧。

 ?-id_path(g_s([node(v1,0),node(v2,1),node(v3,1)],Last,[Temp],Path).
Path = [[node(v1,0),node(v2,1),node(v3,1)],to([node(v1,1),node(v2,1),node(v3,1)],v1)];
Path =[[node(v1,0),node(v2,1),node(v3,1)], to([node(v1,0),node(v2,0),node(v3,1)],v2)];
Path=[[node(v1,0),node(v2,1),node(v3,1)],to([node(v1,1),node(v2,1),node(v3,0)],v3)];

然后，在下一层，显示具有三个节点的所有路径，显示到达节点所需的两个弧，然后在下一层，显示具有四个节点的所有路径，显示需要三个弧等

如果有帮助的话，我也已将我的代码放在SWISH中？（这是第一次尝试？！）

http://pengines.swi-prolog.org/apps/swish/p/HxBzEwLb.pl#&togetherjs=xydMBkFjQR

a(v1,v3). %a activating edge
a(v3,v1).
i(v1,v2). %a inhibition edge
i(v2,v3).

nodes([v1,v2,v3]).

node(X):- nodes(List),member(X,List). %to retrieve a node in graph a) or an arc in graph b)

g_s_s(X,Y,Z,g_s([node(v1,X),node(v2,Y),node(v3,Z)])). %graph_state_simple - I use this to simply set a starting graph state.

sum_list([], 0).
sum_list([H|T], Sum) :-
   sum_list(T, Rest),
   Sum is H + Rest.

invert(1,0).
invert(0,1).

state_of_node(Node,g_s(List),State):-
   member(node(Node,State),List).

%all activating nodes in a graph state for a node
all_a(Node,As,Ss,g_s(NodeList)):-
   findall(A, a(A,Node),As),
   findall(S,(member(M,As),member(node(M,S),NodeList)),Ss).

%all inhibiting nodes in a graph state for a node
all_i(Node,Is,Ss,g_s(NodeList)):-
   findall(I, i(I,Node),Is),
   findall(S,(member(M,Is),member(node(M,S),NodeList)),Ss).

%sum of activating nodes of a node in a state
sum_a(Node,g_s(NodeList),Sum):-
   all_a(Node,_As,Ss,g_s(NodeList)),
   sum_list(Ss,Sum).

%sum of inhibiting nodes of a node in a state
sum_i(Node,g_s(NodeList),Sum):-
   all_i(Node,_Is,Ss,g_s(NodeList)),
   sum_list(Ss,Sum).

above_threshold(Threshold,Node,g_s(NodeList),TrueFalse):-
   sum_a(Node,g_s(NodeList),Sum_A),
   sum_i(Node,g_s(NodeList),Sum_I),
   TrueFalse = true,
   Threshold < (Sum_A-Sum_I),
   !.
above_threshold(Threshold,Node,g_s(NodeList),TrueFalse):-
   sum_a(Node,g_s(NodeList),Sum_A),
   sum_i(Node,g_s(NodeList),Sum_I),
   TrueFalse = false,
   Threshold >= (Sum_A-Sum_I).

%arc needs to be instantiated
state_change(g_s(State1),g_s(State1),Arc):-
   above_threshold(0,Arc,g_s(State1),true),
   state_of_node(Arc,g_s(State1),1).
state_change(g_s(State1),g_s(State2),Arc):-
   above_threshold(0,Arc,g_s(State1),false),
   state_of_node(Arc,g_s(State1),1),
   my_map(State1,State2,Arc).
state_change(g_s(State1),g_s(State2),Arc):-
   above_threshold(0,Arc,g_s(State1),true),
   state_of_node(Arc,g_s(State1),0),
   my_map(State1,State2,Arc).
state_change(g_s(State1),g_s(State1),Arc):-
   above_threshold(0,Arc,g_s(State1),false),
   state_of_node(Arc,g_s(State1),0).

%
my_map([],[],_).
my_map([X|T],[Y|L],Arc):-
   X= node(Node,Value1),
   Node =Arc,
   invert(Value1,Value2),
   Y = node(Node,Value2),
   my_map(T,L,Arc).
my_map([X|T],[Y|L],Arc):-
   X= node(Node,Value1),
   Node \= Arc,
   Y = node(Node,Value1),
   my_map(T,L,Arc).

%this is the def in the book which I can not adapt.
path(Begin,Begin,[start(Begin)]).
path(First, Last,[First,Second|Rest]):-
   state_change(First,Second,Arc),
   path(Second,Last,[Second|Rest]).

%this is the def in the book which I can not adapt.
id_path(First,Last,Template,Path):-
   Path = Template,
   path(First,Last,Path)
;  copy_term(Template,P),
   path(First,_,P),
   !,
   id_path(First,Last,[_|Template],Path).

- user27815

---

我的路径和id_path不起作用。所以我正在尝试调试它们。我希望能够生成不会无限循环的路径。 - user27815

在这里寻求调试帮助，需要提供一个能够产生问题的最小代码/调用示例。一眼看去，id_path/4 调用了 path/3，但除了它自己（递归调用）之外，没有任何东西调用 id_path/4。因此，如果 path/3 不起作用，让我们从那里开始，稍后再回到 id_path/4。 - hardmath

路径的书本示例为：path(First,First,[First]). path(First,Last,[First,Second|Rest]):- state_change(First,Second,Arc), path(Second,Last,[Second|Rest]), append([Arc], Rest, NewRest).我的不同之处在于，我等价于 s/2 的是 state_change/3，其中我还想将弧放入找到的路径的状态空间图中。 - user27815

回到大局观。path/3是找不到你想要的路径，找到你不想要的路径，还是以其他方式（如陷入无限循环）表现不良？ - hardmath

如果我按照书上指定的方式使用path/3，它不起作用，因为我需要将state_change/3的第三个参数实例化，否则会导致不正确的行为。因此，如果我修改path/3，在之前调用node(Arc)，那么我认为它可以按预期工作以找到路径，但会陷入无限循环。例如：g_s_s(1,1,1,Begin),path(g_s(Begin),Last,Path)只会返回g_s([node(v1, 1), node(v2, 1), node(v3, 1)]。我希望能够在其中加入状态空间弧，以便通过弧进行的每一步都是唯一的。 - user27815

Answer 1

由于状态空间是有限的，因此只会有有限数量的最小环或终端路径。以下选项可用于表示图中的最小循环。

- 有理项：一些Prolog系统支持有理项，因此重复路径[0,1,2,2,2,...]可以表示为X=[0,1|Y]，Y=[2|Y]。

- 非有理项：当然，您也可以将重复路径表示为一对。前面的例子将变为([0,1],[2])。

通过以下代码可以检测循环模式，并查找不仅是循环还是循环部分。append谓词将执行搜索：

?- append(X, [2|Y], [0,1,2,3]).
X = [0, 1],
Y = [3] 

所以我们知道，当我们已经找到了一条路径[0,1,2,3]，并且当我们看到一个节点2时，我们已经找到了一个循环，并且可以用Omega词表示找到的循环，如下所示[0,1][2,3]^ω。这是一个简单的回溯代码：

path(P, P).
path((C,[]), P) :-
   last(C, X), edge(X, Y),
   extend(C, Y, A, B), path((A,B), P).

extend(C, Y, A, [Y|B]) :-
   append(A, [Y|B], C), !.
extend(C, Y, A, []) :-
   append(C, [Y], A).

这是一个运行示例：

?- path(([s(0,1,1)],[]), X).
X = ([s(0,1,1)],[]) ;
X = ([s(0,1,1),s(0,1,0)],[]) ;
X = ([s(0,1,1),s(0,1,0),s(0,0,0)],[]) ;
X = ([s(0,1,1),s(0,1,0)],[s(0,0,0)]) ;
X = ([s(0,1,1)],[s(0,1,0)]) ;
X = ([s(0,1,1),s(1,1,1)],[]) ;
...

- user502187