- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
试图在这里解决同构图问题。
任务信息:
e(1, 2).
f(1, 2).
try_bind
可以以更好的方式编写)或者可以提前告知更好的方法。
%define graph, i.e. graph is a list of edges
graph1(RES):-findall(edge(X,Y), e(X, Y), RES).
graph2(RES):-findall(edge(X,Y), f(X, Y), RES).
%define required predicate
iso:-graph1(G1), graph2(G2), iso_acc(G1, G2, [], _).
%same as above but outputs result
iso_w:-graph1(G1), graph2(G2), iso_acc(G1, G2, [], RES_MAP), write(RES_MAP).
iso_acc([], [], MAP, RES):-append(MAP, [], RES), !.
iso_acc([X|X_Rest], Y_LS, MAP, RES_MAP):-
select(Y, Y_LS, Y_Rest),
bind(X, Y, MAP, UPD_MAP),
iso_acc(X_Rest, Y_Rest, UPD_MAP, RES_MAP).
% if edges bind is successful then in RES or UPD_MAP updated binding map is returned (may return the same map
% if bindings are already defined), otherwise fails
bind([], [], MAP, RES):-append(MAP, [], RES), !.
bind(edge(X1, Y1), edge(X2, Y2), MAP, UPD_MAP):-
try_bind(b(X1, X2), MAP, RES),
try_bind(b(Y1, Y2), RES, UPD_MAP).
bind(edge(X1, Y1), edge(X2, Y2), MAP, UPD_MAP):-
try_bind(b(X1, Y2), MAP, RES),
try_bind(b(Y1, X2), RES, UPD_MAP).
%if an absolute member, we're OK (absolute member means b(X,Y) is already defined
try_bind(b(X, Y), MAP, UPD_MAP):-
member(b(X, Y), MAP),
append(MAP, [], UPD_MAP), !.
%otherwise check that we don't have other binding to X or to Y
try_bind(b(X, Y), MAP, UPD_MAP):-
member(b(X, Z), MAP),
%check if Z != Y
Z=Y,
append(MAP, [], UPD_MAP).
try_bind(b(X, Y), MAP, UPD_MAP):-
member(b(W, Y), MAP),
%check if W == X
W=X,
append(MAP, [], UPD_MAP).
%finally if we not an absolute member and if no other bindings to X and Y we add new binding
try_bind(b(X, Y), MAP, UPD_MAP):-
not(member(b(X, Z), MAP)),
not(member(b(W, Y), MAP)),
append([b(X, Y)], MAP, UPD_MAP).
最佳答案
首先,祝贺您很好地介绍了问题并提出了详尽的解决方案建议。
在下一段中,我将讨论您的解决方案的实现细节。
不幸的是,我必须说我看不到这种解决方案可扩展到更大尺寸的方法。假设有 10 条边的图。 iso_acc/4
尝试将第一条边分配给第二条边中的任何一条边(10 种可能性),第二条边也绑定(bind)到任何一条边(每个前面的 10 种可能性:10*10),...。如果不是一些运气,那就有 10^10 种可能性,10!考虑到它们中的大多数被修剪得更快。
次要意见是:
您可以跳过 append(X,[],Y)
的使用, 所以
bind([],[],MAP,RES) :- append(MAP,[],RES), !.
bind([],[],MAP,MAP).
try_bind/3
中的第二条和第三条规则似乎没有必要,在上一个中你已经验证了 no
b(X,Y)
属于
MAP
.换句话说,
member(b(X,Y),MAP)
相当于
member(b(X,Z),MAP), Z=Y
.
e
是:
+----3----+
1 ---2--+ | +---5
+----4----+
f
是:
+----3----+
2 ---5--+ | +---1
+----4----+
memb( X-A, [X-B|_] ) :- permutation(A,B).
memb( X, [_|Q] ) :- memb(X, Q).
match( [], _ ).
match( [H|Q], G2 ) :-
memb(H,G2),
match(Q,G2).
graph_equal(G1,G2,MAP) :-
bagof( X, graph_to_list(G1,X), L1 ),
length(MAP,40),
bagof( X, graph_to_list_vars(G2,MAP,X), L2 ), !,
length( L1, S ),
length( L2, S ),
match( L1, L2 ).
node-[peer1,peer2,...]
形式的项目列表。 .此转换的规则是:
bidir(G,X,Y) :- ( call(G,X,Y); call(G,Y,X) ).
bidir_vars(G,MAP,VX,VY) :-
bidir(G,X,Y), nth0(X,MAP,VX), nth0(Y,MAP,VY).
graph_to_list( G, N-XL ) :-
setof( X, bidir(G,N,X), XL).
graph_to_list_vars( G, MAP, N-XL ) :-
setof( X, bidir_vars(G,MAP,N,X), XL).
e(1,2).
e(2,3).
e(2,4).
e(3,4).
e(3,5).
e(4,5).
f(2,5).
f(3,5).
f(4,5).
f(3,4).
f(1,4).
f(1,3).
e
和
f
,结果是:
[debug] ?- graph_equal(e,f,MAP).
MAP = [_G2295, 5, 1, 3, 4, 2, _G2313, _G2316, _G2319|...] ;
MAP = [_G2295, 5, 1, 4, 3, 2, _G2313, _G2316, _G2319|...] ;
e:[5,1,3,4,2] => f:[1,2,3,4,5]
和
e:[5,1,4,3,2] => f:[1,2,3,4,5]
.
?- time( graph_equal(e,f,_) ).
% 443 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 1718453 Lips)
?- time( (graph_equal(e,f,_),fail) ).
% 567 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 2027266 Lips)
关于Prolog 同构图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30609969/
我正在学习序言。 在我看来,prolog 的规则(关系和简单的事实)是“肯定的”——他们说的是或可能是真的。 向 prolog 程序添加新的此类规则只会增加“正面”知识。它不能添加“负面”事实来说明某
希望你一切都好。我是 prolog 的新手,我在编写代码时遇到问题。这段代码的目的很简单。它将列表中的每个元素添加到最后一个。我可以用 Java 做的事情是: static void add(
在closed-world assumption下, what is not currently known to be true, is false Prolog 的语义通常被称为遵循封闭世界假设,
我正在 Prolog (swi-prolog) 中做我的第一步,但无法解决以下问题:如何将存在量化的规则包含在我的事实中;具体来说,我如何包含句子“每个人都是某人的 friend ”\forall x
我知道如何以过程方式(即,在 C++、Java 等中)对 BST 执行范围查询,但我发现很难转换为 Prolog 语言。 程序的方式应该是这样的: http://www.geeksforgeeks.o
Prolog 中是否有(相对)当前最佳实践的引用资料?一本适合没有学习过逻辑编程或“Prolog 的工艺”等高级文本的商业 Prolog 开发人员? 有很多通用教程,但我能找到的关于最佳实践的唯一一个
这是CFG: S -> T | V T -> UU U -> aUb | ab V -> aVb | aWb W -> bWa | ba 所以这将接受某种形式的: {a^n b^n a^m b^m |
我目前有以下问题,我想用 Prolog 解决。这是一个简单的例子,很容易在 Java/C/whatever 中解决。我的问题是,我认为与 Java 的思想联系太紧密,无法以利用 Prolog 逻辑能力
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
我无法理解差异列表,尤其是在这个谓词中: palindrome(A, A). palindrome([_|A], A). palindrome([C|A], D) :- palindrome(A
(这不是一个类(class)作业问题。只是我自己的个人学习。) 我正在尝试在 Prolog 中进行练习以从列表中删除元素。这是我的代码: deleteall([],X,[]). deleteall([
我最近试图了解 Prolog,它似乎可以很好地映射到很多领域,但我无法弄清楚它可能不擅长什么。 那么它有什么不好的(除了需要实时/无 gc 性能的东西)? 最佳答案 我同意你的一般评估,即 Prolo
我正在组装一个简单的元解释器,它输出证明的步骤。我无法将证明步骤作为输出参数。我的谓词 explain1 以我想要的详细形式返回证明,但不是作为输出参数。我的谓词 explain2 将证明作为输出参数
hi(g,plus(A,B),int) :- hi(g,A,int),hi(g,B,int),!. 在上面的语句中 '!' 是什么意思?在声明的末尾签名吗? 最佳答案 那是 cut operator
有没有一种简单的方法可以让 prolog 中的查询只返回每个结果一次? 例如我正在尝试类似的东西: deadly(Xn) :- scary(X), Xn is X - 1, Xp is X + 1,
我正在尝试学习 Prolog。这是我使用这种语言的第一步。作为练习,我想编写可以识别一些扑克手牌的程序(同花顺、同花顺、满屋等)。 我正在 Prolog 中寻找良好的卡片表示。我需要有可能检查一张卡片
我刚刚被介绍到 Prolog 并且正在尝试编写一个谓词来查找整数列表的最大值。我需要写一个从头开始比较,另一个从结尾比较。到目前为止,我有: max2([],R). max2([X|Xs], R):-
我试图在Prolog中编写谓词palindrome/1,当且仅当其列表输入包含回文列表时才为true。 例如: ?- palindrome([1,2,3,4,5,4,3,2,1]). 是真的。 有什么
我正在尝试编写一个程序,该程序将两个列表作为输入并检查适当的子集。我开始于: proper([A],[]). proper([],[A]). proper([A|T1],[A|T2]) :- prop
我是 Prolog 的新手,我正在使用 SWI-Prolog v6.6 在 *.pl 中存储断言文件。 :- dynamic fact/2. assert(fact(fact1,fact2)). 使用
我是一名优秀的程序员,十分优秀!