predsort/3 意外行为

Question

我在 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).

我试过切换不同的变量仍然无法得到预期的结果。 keysort/2 是更好的选择吗？问题是我不知道如何结合自定义谓词来实现键排序。

Answer 1

拓扑排序才是你真正想要的。为此有top_sort/2。

predsort/3假定为总订单，但您只能提供部分订单。

换句话说，predsort/3 将查询您提供的比较谓词。它期望答案为 <、= 或 >。因此，您必须为所有节点对生成一个准确的答案。但是，对于某些人（那些无与伦比的人），您无法说出结果应该是什么。你只能猜测，这不会产生一致的总顺序。

Answer 2

我实现了@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).

predsort/3 意外行为

predsort/3 unexpected behavior

sorting

prolog

swi-prolog