计算序言中边缘颜色的出现次数
Counting occurrences of edge color in prolog
我有一个这样定义的图表：
edge(a1,c1,7,blue).
edge(a1,d1,3,blue).
edge(a1,l1,8,red).
edge(b1,c1,11,blue).
edge(d1,e1,2,red).
....
等等。
我知道如何编写代码来检查是否存在路径并计算权重和最短路径。 但我想要做的是输出 2 个整数：一个用于 no.of 蓝色，一个用于 no.of 从 X 到 Y 路径中的红色边缘。
本质上，我想要这样的东西：
colour(X,Y,C).
returns:
"blue" if all the edges in the path are blue(or Red for all red)
"false" if there are mixed edges.
或类似的东西：
blue:5 red:2 if there are 7 edges
我是 Prolog 的新手，对如何创建 "counter" 类型变量感到非常困惑。
使用您显示的数据库片段和库(aggregate):
?- aggregate(count,X^Y^W^edge(X,Y,W,C),N).
C = blue,
N = 3 ;
C = red,
N = 2.
对于您的 edge/4 谓词，可能还有两种方法来计算相同颜色的边数：
1) 使用谓词查找所有解决方案，例如 findall/3:
opt1 :-
findall(_,edge(_,_,_,blue),ListBlue), % collect all blue edges in ListBlue
length(ListBlue,L), % find out the length of ListBlue
display('blue: '),display(L),nl. % print output
_ 符号代表一个 "anonymous variable"，一个您不关心其绑定的变量。
这个解决方案的缺点是它不是资源明智的：首先你通过所有 edge/4 事实（不可避免的成本），然后你使用额外的内存来存储 ListBlue 列表和那么你必须遍历这个列表。
2) 在失败驱动的循环中使用 side effects (see below) and dynamic 谓词（谓词妓女子句可以是 added/deleted on 运行-time）：
Side effects 是从一种程序状态转换到另一种程序状态时可以做的一些额外的事情，例如在为变量赋值（直接效果）的操作期间打印文本（副作用）。
:- dynamic counter/2. % a dynamic predicate to be used as a mutable counter
opt2 :-
retractall(counter(_,_)), % \_ delete any old value of a counter from previous
asserta(counter(blue,0)), % / runs and set it to 0 for the blue edges
%
count_edges(blue,NBlue),
display('blue: '),display(NBlue),nl.
count_edges(Col,_N) :-
edge(_,_,_,Col), % locate an edge of desired color Col
counter(Col,N), % \
N1 is N + 1, % \_ update the counter value
retract(counter(Col,N)), % /
asserta(counter(Col,N1)), % /
fail. % fail to force backtracking
count_edges(Col,N) :-
counter(Col,N). % read the current counter value
强制回溯允许探索 edge(_,_,_,Col) 查询的所有可能解决方案，从而找到所有蓝色边缘。
我试过代码 online 并且成功了。
我想要 post 一些 基准测试 可能有助于比较 @s0nata post 编辑的两个不错的解决方案。这是一个额外的答案，主要是因为评论太长了。
Prolog 是一种很好的设计语言和 运行 基准，还因为可以通过单个查询轻松描述大量基准。
临时 基准测试
例如，让我们使用以下查询对使用 findall/3 的 选项 1 进行基准测试：
?- length(_, E),
N #= 2^E,
portray_clause(E),
forall(between(1, N, _), assertz(edge(x, y, 1, blue))),
time(opt1),
false.
请注意，我们正在使用 assertz/1 为 edge/4 创建更多 事实 。这非常不优雅，这意味着我们必须 重新启动 Prolog 在这样的 运行 之间或再次清除数据库以便从头开始。我把让它变得更优雅作为练习。
在任何情况下，这都会导致以下 输出：
0.
'blue: '1
% 3,454 inferences, 0.001 CPU in 0.009 seconds (16% CPU, 2364134 Lips)
1.
'blue: '3
% 22 inferences, 0.000 CPU in 0.000 seconds (76% CPU, 785714 Lips)
2.
'blue: '7
% 26 inferences, 0.000 CPU in 0.000 seconds (74% CPU, 1181818 Lips)
3.
'blue: '15
% 34 inferences, 0.000 CPU in 0.000 seconds (77% CPU, 1478261 Lips)
4.
'blue: '31
% 50 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 1851852 Lips)
... lines omitted ...
21.
'blue: '4194303
% 4,194,322 inferences, 1.301 CPU in 1.439 seconds (90% CPU, 3224179 Lips)
为了比较，我们得到 选项 2:
?- length(_, E),
N #= 2^E,
portray_clause(E),
forall(between(1, N, _), assertz(edge(x, y, 1, blue))),
time(opt2),
false.
0.
'blue: '1
% 3,448 inferences, 0.001 CPU in 0.009 seconds (16% CPU, 2347175 Lips)
1.
'blue: '3
% 20 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 769231 Lips)
2.
'blue: '7
% 32 inferences, 0.000 CPU in 0.000 seconds (80% CPU, 1142857 Lips)
3.
'blue: '15
% 56 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 888889 Lips)
4.
'blue: '31
% 104 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 1350649 Lips)
... lines omitted ...
21.
'blue: '4194303
% 12,582,920 inferences, 10.100 CPU in 10.305 seconds (98% CPU, 1245782 Lips)
比较漂亮
为了更优雅地推理此类基准，我们现在将稍微 更改 opt1/0 和 opt2/0 以便这些谓词 不弄乱我们自己的基准输出。也就是说，我们将从这些谓词中 删除所有副作用 ，从而通过使实际计数器可用作为 testing 这些谓词也变得容易得多一个 参数 。我们可以这样写：
opt1(L) :-
findall(_,edge(_,_,_,blue),ListBlue),
length(ListBlue, L).
opt2(NBlue) :-
retractall(counter(_,_)),
asserta(counter(blue,0)),
count_edges(blue, NBlue).
此外，让我们引入以下辅助定义来获取执行目标所需的 wall time。这可能包括由于其他任务、垃圾收集等引起的轻微扰动，但重要的是要考虑执行目标所需的 实际 时间（以秒为单位）：
wall_time(Goal, T) :-
statistics(walltime, [T0|_]),
Goal,
statistics(walltime, [T1|_]),
T is (T1 - T0)/1000.
现在让我们post举例：
?- format("~tE~t~5+~tNum~t~15+~tT1~10+~tT2~10+~n"),
length(_, E),
N #= 2^E,
forall(between(1, N, _), assertz(edge(x, y, 1, blue))),
wall_time(opt1(Num), T1),
wall_time(opt2(Num), T2),
format("~t~w~5+~t~w~15+~t~2f~10+~t~2f~10+~n", [E,Num,T1,T2]),
false.
结果如下 table：
E Num T1 T2
0 1 0.00 0.00
1 3 0.00 0.00
2 7 0.00 0.00
3 15 0.00 0.00
4 31 0.00 0.00
5 63 0.00 0.00
6 127 0.00 0.00
7 255 0.00 0.00
8 511 0.00 0.00
9 1023 0.00 0.00
10 2047 0.00 0.01
11 4095 0.00 0.01
12 8191 0.00 0.03
13 16383 0.01 0.04
14 32767 0.02 0.08
15 65535 0.02 0.16
16 131071 0.04 0.32
17 262143 0.09 0.64
18 524287 0.18 1.31
19 1048575 0.37 2.55
20 2097151 0.74 5.14
21 4194303 1.44 10.29
在比较这两个解决方案时，请同时考虑这些实际基准。在 Prolog 中，很多时候，杂质也会导致很多效率低下。
注意我们还如何利用这个机会验证两个选项产生相同的结果！
我有一个这样定义的图表：
edge(a1,c1,7,blue).
edge(a1,d1,3,blue).
edge(a1,l1,8,red).
edge(b1,c1,11,blue).
edge(d1,e1,2,red).
....
等等。
我知道如何编写代码来检查是否存在路径并计算权重和最短路径。 但我想要做的是输出 2 个整数：一个用于 no.of 蓝色，一个用于 no.of 从 X 到 Y 路径中的红色边缘。
本质上，我想要这样的东西：
colour(X,Y,C).
returns:
"blue" if all the edges in the path are blue(or Red for all red)
"false" if there are mixed edges.
或类似的东西：
blue:5 red:2 if there are 7 edges
我是 Prolog 的新手，对如何创建 "counter" 类型变量感到非常困惑。
使用您显示的数据库片段和库(aggregate):
?- aggregate(count,X^Y^W^edge(X,Y,W,C),N).
C = blue,
N = 3 ;
C = red,
N = 2.
对于您的 edge/4 谓词，可能还有两种方法来计算相同颜色的边数：
1) 使用谓词查找所有解决方案，例如 findall/3:
opt1 :-
findall(_,edge(_,_,_,blue),ListBlue), % collect all blue edges in ListBlue
length(ListBlue,L), % find out the length of ListBlue
display('blue: '),display(L),nl. % print output
_ 符号代表一个 "anonymous variable"，一个您不关心其绑定的变量。
这个解决方案的缺点是它不是资源明智的：首先你通过所有 edge/4 事实（不可避免的成本），然后你使用额外的内存来存储 ListBlue 列表和那么你必须遍历这个列表。
2) 在失败驱动的循环中使用 side effects (see below) and dynamic 谓词（谓词妓女子句可以是 added/deleted on 运行-time）：
Side effects 是从一种程序状态转换到另一种程序状态时可以做的一些额外的事情，例如在为变量赋值（直接效果）的操作期间打印文本（副作用）。
:- dynamic counter/2. % a dynamic predicate to be used as a mutable counter
opt2 :-
retractall(counter(_,_)), % \_ delete any old value of a counter from previous
asserta(counter(blue,0)), % / runs and set it to 0 for the blue edges
%
count_edges(blue,NBlue),
display('blue: '),display(NBlue),nl.
count_edges(Col,_N) :-
edge(_,_,_,Col), % locate an edge of desired color Col
counter(Col,N), % \
N1 is N + 1, % \_ update the counter value
retract(counter(Col,N)), % /
asserta(counter(Col,N1)), % /
fail. % fail to force backtracking
count_edges(Col,N) :-
counter(Col,N). % read the current counter value
强制回溯允许探索 edge(_,_,_,Col) 查询的所有可能解决方案，从而找到所有蓝色边缘。
我试过代码 online 并且成功了。
我想要 post 一些 基准测试 可能有助于比较 @s0nata post 编辑的两个不错的解决方案。这是一个额外的答案，主要是因为评论太长了。
Prolog 是一种很好的设计语言和 运行 基准，还因为可以通过单个查询轻松描述大量基准。
临时 基准测试
例如，让我们使用以下查询对使用 findall/3 的 选项 1 进行基准测试：
?- length(_, E), N #= 2^E, portray_clause(E), forall(between(1, N, _), assertz(edge(x, y, 1, blue))), time(opt1), false.
请注意，我们正在使用 assertz/1 为 edge/4 创建更多 事实 。这非常不优雅，这意味着我们必须 重新启动 Prolog 在这样的 运行 之间或再次清除数据库以便从头开始。我把让它变得更优雅作为练习。
在任何情况下，这都会导致以下 输出：
0. 'blue: '1 % 3,454 inferences, 0.001 CPU in 0.009 seconds (16% CPU, 2364134 Lips) 1. 'blue: '3 % 22 inferences, 0.000 CPU in 0.000 seconds (76% CPU, 785714 Lips) 2. 'blue: '7 % 26 inferences, 0.000 CPU in 0.000 seconds (74% CPU, 1181818 Lips) 3. 'blue: '15 % 34 inferences, 0.000 CPU in 0.000 seconds (77% CPU, 1478261 Lips) 4. 'blue: '31 % 50 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 1851852 Lips) ... lines omitted ... 21. 'blue: '4194303 % 4,194,322 inferences, 1.301 CPU in 1.439 seconds (90% CPU, 3224179 Lips)
为了比较，我们得到 选项 2:
?- length(_, E), N #= 2^E, portray_clause(E), forall(between(1, N, _), assertz(edge(x, y, 1, blue))), time(opt2), false. 0. 'blue: '1 % 3,448 inferences, 0.001 CPU in 0.009 seconds (16% CPU, 2347175 Lips) 1. 'blue: '3 % 20 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 769231 Lips) 2. 'blue: '7 % 32 inferences, 0.000 CPU in 0.000 seconds (80% CPU, 1142857 Lips) 3. 'blue: '15 % 56 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 888889 Lips) 4. 'blue: '31 % 104 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 1350649 Lips) ... lines omitted ... 21. 'blue: '4194303 % 12,582,920 inferences, 10.100 CPU in 10.305 seconds (98% CPU, 1245782 Lips)
比较漂亮
为了更优雅地推理此类基准，我们现在将稍微 更改 opt1/0 和 opt2/0 以便这些谓词 不弄乱我们自己的基准输出。也就是说，我们将从这些谓词中 删除所有副作用 ，从而通过使实际计数器可用作为 testing 这些谓词也变得容易得多一个 参数 。我们可以这样写：
opt1(L) :-
findall(_,edge(_,_,_,blue),ListBlue),
length(ListBlue, L).
opt2(NBlue) :-
retractall(counter(_,_)),
asserta(counter(blue,0)),
count_edges(blue, NBlue).
此外，让我们引入以下辅助定义来获取执行目标所需的 wall time。这可能包括由于其他任务、垃圾收集等引起的轻微扰动，但重要的是要考虑执行目标所需的 实际 时间（以秒为单位）：
wall_time(Goal, T) :-
statistics(walltime, [T0|_]),
Goal,
statistics(walltime, [T1|_]),
T is (T1 - T0)/1000.
现在让我们post举例：
?- format("~tE~t~5+~tNum~t~15+~tT1~10+~tT2~10+~n"),
length(_, E),
N #= 2^E,
forall(between(1, N, _), assertz(edge(x, y, 1, blue))),
wall_time(opt1(Num), T1),
wall_time(opt2(Num), T2),
format("~t~w~5+~t~w~15+~t~2f~10+~t~2f~10+~n", [E,Num,T1,T2]),
false.
结果如下 table：
E Num T1 T2
0 1 0.00 0.00
1 3 0.00 0.00
2 7 0.00 0.00
3 15 0.00 0.00
4 31 0.00 0.00
5 63 0.00 0.00
6 127 0.00 0.00
7 255 0.00 0.00
8 511 0.00 0.00
9 1023 0.00 0.00
10 2047 0.00 0.01
11 4095 0.00 0.01
12 8191 0.00 0.03
13 16383 0.01 0.04
14 32767 0.02 0.08
15 65535 0.02 0.16
16 131071 0.04 0.32
17 262143 0.09 0.64
18 524287 0.18 1.31
19 1048575 0.37 2.55
20 2097151 0.74 5.14
21 4194303 1.44 10.29
在比较这两个解决方案时，请同时考虑这些实际基准。在 Prolog 中，很多时候，杂质也会导致很多效率低下。
注意我们还如何利用这个机会验证两个选项产生相同的结果！