prolog - 为下一次测试生成并测试累积有效答案
问题描述
我知道如何进行简单的生成和测试以单独返回每个答案。在以下示例中,仅返回大于的项目1
。
item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).
gen_test(Item) :-
item(Item), % generate
Item > 1. % test
?- gen_test(Item).
Item = 2 ;
Item = 3 ;
Item = 7 ;
Item = 4.
我还可以使用bagof/3将结果作为列表返回
gen_test_bagof(List) :-
bagof(Item,(item(Item),Item > 1), List).
?- gen_test_bagof(List).
List = [2, 3, 7, 4].
现在我希望能够更改测试,以便它使用member/2和一个列表,其中列表是所有先前有效答案的累积。
我试过这个
gen_test_acc_facts(L) :-
gen_test_acc_facts([],L).
gen_test_acc_facts(Acc0,R) :-
item(H), % generate
(
member(H,Acc0) % test
->
gen_test_acc_facts(Acc0,R) % Passes test, don't accumulate, run generate and test again.
;
gen_test_acc_facts([H|Acc0],R) % Fails test, accumulate, run generate and test again.
).
但由于它是递归的,每次调用都会item/1
导致使用相同的第一个事实。
我怀疑答案将需要像mat在这个答案中所做的那样消除回溯,因为这需要保留信息而不是回溯。
细节
给出的示例是实际问题的简化版本,它是生成具有 N 个顶点的图,其中边是无向的,没有 循环(自引用),没有权重并且顶点被标记,并且没有根顶点和集合graphs 只是同构图。为 N 生成所有图很容易,虽然我可以先将所有图累积到一个列表中,然后再对它们进行测试;一旦N = 8,内存就会耗尽。
?- graph_sizes(N,Count).
N = 0, Count = 1 ;
N = Count, Count = 1 ;
N = Count, Count = 2 ;
N = 3, Count = 8 ;
N = 4, Count = 64 ;
N = 5, Count = 1024 ;
N = 6, Count = 32768 ;
N = 7, Count = 2097152 ;
ERROR: Out of global stack
然而,由于生成了许多冗余的同构图,通过随着列表的增长对其进行修剪,可以增加 N 的大小。请参阅:枚举所有特定大小的非同构图
gen_vertices(N,L) :-
findall(X,between(1,N,X),L).
gen_edges(Vertices, Edges) :-
findall((X,Y), (member(X, Vertices), member(Y, Vertices), X < Y), Edges).
gen_combination_numerator(N,Numerator) :-
findall(X,between(0,N,X),L0),
member(Numerator,L0).
comb(0,_,[]).
comb(N,[X|T],[X|Comb]) :-
N>0,
N1 is N-1,
comb(N1,T,Comb).
comb(N,[_|T],Comb) :-
N>0,
comb(N,T,Comb).
gen_graphs(N,Graph) :-
gen_vertices(N,Vertices),
gen_edges(Vertices,Edges),
length(Edges,Denominator),
gen_combination_numerator(Denominator,Numerator),
comb(Numerator,Edges,Graph).
graph_sizes(N,Count) :-
length(_,N),
findall(.,gen_graphs(N,_), Sols),
length(Sols,Count).
Prolog 中的同构图测试。
生成的图表示例:
?- gen_graphs(1,G).
G = [] ;
false.
?- gen_graphs(2,G).
G = [] ;
G = [(1, 2)] ;
false.
?- gen_graphs(3,G).
G = [] ;
G = [(1, 2)] ;
G = [(1, 3)] ;
G = [(2, 3)] ;
G = [(1, 2), (1, 3)] ;
G = [(1, 2), (2, 3)] ;
G = [(1, 3), (2, 3)] ;
G = [(1, 2), (1, 3), (2, 3)] ;
false.
正在生成的所有图表 ( A006125 ) 与所需图表 ( A001349 ) 之间的差异。
A006125 A001349 Extraneous
0 1 - 1 = 0
1 1 - 1 = 0
2 2 - 1 = 1
3 8 - 2 = 6
4 64 - 6 = 58
5 1024 - 21 = 1003
6 32768 - 112 = 32656
7 2097152 - 853 = 2096299
8 268435456 - 11117 = 268424339
9 68719476736 - 261080 = 68719215656
10 35184372088832 - 11716571 = 35184360372261
11 36028797018963968 - 1006700565 = 36028796012263403
12 73786976294838206464 - 164059830476 = 73786976130778375988
13 302231454903657293676544 - 50335907869219 = 302231454853321385807325
14 2475880078570760549798248448 - 29003487462848061 = 2475880078541757062335400387
15 40564819207303340847894502572032 - 31397381142761241960 = 40564819207271943466751741330072
使用 geng 和 listg
这两个程序都包含在主页上nauty and Traces
的下载链接中。(用户指南)
程序是用Linux编写C
的make
,可以在Linux上运行。代替在 Windows 上使用 Cygwin,可以安装WSL。
源代码可以使用下载
wget "http://pallini.di.uniroma1.it/nauty26r11.tar.gz"
然后
tar xvzf nauty26r11.tar.gz
cd nauty26r11
./configure
make
nauty默认以 graph6格式生成输出,但可以使用listg转换为边列表,例如
eric@WINDOWS-XYZ:~/nauty26r11$ ./geng 3 | ./listg -e
>A ./geng -d0D2 n=3 e=0-3
>Z 4 graphs generated in 0.00 sec
Graph 1, order 3.
3 0
Graph 2, order 3.
3 1
0 2
Graph 3, order 3.
3 2
0 2 1 2
Graph 4, order 3.
3 3
0 1 0 2 1 2
程序的有用选项
耿
-help : options
-c : only write connected graphs (A001349)
-u : do not output any graphs, just generate and count them
例子
eric@WINDOWS-ABC:~/nauty26r11$ ./geng -c -u 10
>A ./geng -cd1D9 n=10 e=9-45
>Z 11716571 graphs generated in 5.09 sec
请注意,这11716571
是10
来自 A001349 的大小
如何使用 WSL 在 Windows 上创建文件
由于 WSL 可以访问 Windows 文件系统,因此可以将 WSL 命令的输出定向到 Windows 文件,例如
touch /mnt/c/Users/Eric/graphs.txt
不需要触摸步骤,但我先使用它创建一个空文件,然后验证它在 Windows 上是否存在,以确保我输入了正确的路径。
这是一个在用户目录中为 A001349 创建图形边列表的示例。
.geng -c 1 | .listg -e >> /mnt/c/Users/Eric/graphs.txt
.geng -c 2 | .listg -e >> /mnt/c/Users/Eric/graphs.txt
解决方案
在SWI-Prolog中,您可以将值存储在全局 vars中:
- 可回溯
b
:b_setval
,b_getval
- 不可回溯
nb
:nb_setval
,nb_getval
除了使用动态谓词: assert/retract
。
item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).
解决方案 1 使用常规列表
gen_test(Item) :-
nb_setval(sofar, []),
item(Item), % generate
once(
(
nb_getval(sofar, SoFar),
(Item > 1, \+ member(Item, SoFar)), % test custom + on membership in earlier tests
nb_setval(sofar, [Item | SoFar])
)
;
true
),
fail; true.
解决方案 2 使用开放列表
gen_test1(Item) :-
(
item(Item), % generate
Item > 1, lookup(Item, SoFar, ItemExists)),
ItemExists == true -> fail; true
);
append(SoFar, [], SoFar ), % stubbing open list
nb_setval(sofar, Sofar).
lookup( I, [ I | _ ], true).
lookup( I, [ _ | L ], false) :-
var( L ); L == [].
lookup( I, [ _ | L ] ItemExists ):-
lookup( I, L, ItemExists ).
推荐阅读
- angular - CORS 策略已阻止对 XMLHttpRequest 的访问
- ios - UITableView 多个动作
- r - 如何在ggplot中为每个方面添加图例?
- azure - 使用 Python SDK 调用时如何验证 Microsoft Azure 存储帐户的身份验证
- ios - 如果我的消耗性 IAP 被退款,我会收到任何通知吗?
- python - Python从文本文件中拆分数字
- matlab - 以下 MATLAB 脚本的答案是否正确?
- javascript - asp.net mvc 应用程序中的导航栏不适用于引导程序
- c# - 在 WPF 树视图中单击时如何更改 TreeViewItem 的背景颜色?
- xamarin - 如何将视图模型属性绑定到 XAML 控件