预排序/3意外行为
预排序/3意外行为
提问于 2015-01-08 22:34:12
我在Prolog中排序任务列表( [t7, t1, t6, t2, t4, t3, t5] )有问题。为了对此进行排序，我希望使用预定义的公式predsort/3，因为它似乎是正确的方法。
我的自定义谓词如下所示：
sort_dependency(<, T, T2) :-
depends_on(T,T2,_).
sort_dependency(>, T, T2) :-
depends_on(T2,T,_).
sort_dependency(>, T, T2) :-
T == T2;
not(depends_on(T,T2,_)),
not(depends_on(T2,T,_)). 在测试这一点时，我得到以下内容：
?- predsort(sort_dependency, [t7, t1, t6, t2, t4, t3, t5], Sorted).
Sorted = [t5, t4, t3, t7, t2, t6, t1] .这不对。正确的答案应该是类似于[t1 , t2, t3, t4, t5, t6, t]的东西。为了测试目的，这里是depends_on的事实。
depends_on(t7,t2,0).
depends_on(t7,t6,0).
depends_on(t6,t4,0).
depends_on(t6,t5,0).
depends_on(t2,t1,0).
depends_on(t4,t3,0).
depends_on(t3,t1,0).
depends_on(t5,t3,0).我试着把不同的变量转到be上还是不能得到预期的结果。keysort/2是一个更好的选择吗？问题是，我不知道如何结合自定义谓词来实现keysort。
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-01-08 22:56:17
拓扑排序是你真正想要的。这里有top_sort/2。
predsort/3假定为总顺序，但只能提供部分订单。
换句话说，predsort/3将查询所提供的比较谓词。它希望答案是<、=或>。所以你必须为所有的节点生成一个精确的答案。然而，对于一些人(那些无与伦比的)来说，你不知道结果应该是什么。您只能猜测，这不会产生一致的总顺序。
Stack Overflow用户
发布于 2015-01-09 03:11:24
我实现了@false提出的解决方案。将任务转换为一个图，用depends_on设置边，然后对结果使用top_sort/2。
希望这对一些人有用。
sort_tasks(ToSort, Sorted) :-
vertices_edges_to_ugraph(ToSort,[],Gr), %Gr is graph wiht nodes as the tasks
add_my_edges(Gr, ToSort, GrN),
top_sort(GrN,Sorted).
add_my_edges(Gr,[],Gr).
add_my_edges(Gr,[T|TR], GrReturn) :-
findall(X,depends_on(X,T,_),L), %L moet na T gebeuren
add_my_edge(Gr, T, L, GrN),
add_my_edges(GrN,TR,GrReturn).
add_my_edge(Gr, _,[], Gr).
add_my_edge(Gr, T, [LH|LR], GrReturn) :-
add_edges(Gr, [T-LH], GrN),
add_my_edge(GrN, T, LR, GrReturn).页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27850760
复制相关文章
相似问题
腾讯云开发者
