状態空間グラフの深さ優先反復深化検索を実装しようとしています。3 つの頂点を持つグラフがあり、それらは 2 つの活性化エッジと 2 つの抑制エッジです。各ノードにはバイナリ値があり、集合的にこれがグラフの状態です。グラフは、ノードの 1 つがしきい値を超えているか、しきい値を下回っているか (すべての受信ノードの合計から計算) を確認することで、新しい状態に遷移できます。各遷移で最大 1 つのノードが変更されます。それらは 3 つのノードであるため、状態遷移グラフ内の各状態を離れる 3 つの状態遷移エッジがあります。
たとえば、次のクエリを実行できます。
?-g_s_s(0,1,1,Begin),node(Arc),state_change(g_s(Begin),Second,Arc).
そして、それは私に3つの正しい答えを与えます:
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 AI book で与えられた述語 id_path を使用しようとしていますが、質問 11.3 の解決策ですが、使用/適応に問題があります。 ループに入らずに、開始ノードから他のノードへのパスを作成したい - 繰り返し要素を持たせたり、パスが存在しないときに立ち往生したりしたくない. 開始状態と、開始状態からアクセスできる一連の状態を示すパスが必要です。自己ループがある場合は、そこに到達するすべての方法でこれを 1 回含める必要があります。つまり、状態空間に到達した方法を追跡し、状態空間がパスで一意であるだけでなく、これを一意にしたいのです。
たとえば、011 から、長さ 1 の 3 つのパスすべてが円弧で見つかるようにします。
?-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)];
次のレベルでは、ノードに到達するために必要な 2 つのアークを示す 3 つのノードを持つすべてのパスが表示され、次のレベルでは、必要な 3 つのアークを示す 4 つのノードを持つすべてのパスが表示されます。
これが役立つ場合、コードを 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).