presort/3 неожиданное поведение

У меня проблема с сортировкой списка задач [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 лучше? Проблема в том, что я не вижу, как реализовать сортировку по ключам в сочетании с пользовательским предикатом.


sorting prolog swi-prolog
person Timbo925    schedule 08.01.2015    source источник
comment
Что на самом деле означает 3-й пункт sort_dependency/3? Я предполагаю, что это должно быть ==. Но почему два объекта должны быть одинаковыми, если они не зависят друг от друга напрямую?   -  person false    schedule 09.01.2015
comment
Для меня я читаю это так: > используется как предикат, если обе задачи одинаковы, OR они не зависят друг от друга. Это должно быть эквивалентно, если я просто заменю его на sort_dependency(>, T, T2)., потому что, если оба предыдущих предложения не работают, третье всегда будет истинным. Проблема остается прежней, если я делаю это изменение.   -  person Timbo925    schedule 09.01.2015
comment
Имя этого должно быть скорее compare_xxx, а первый аргумент должен быть >, < или ==.   -  person false    schedule 09.01.2015

Ответы (2)


arrow_upward
2
arrow_downward

Топологическая сортировка - это то, что вам действительно нужно. Для этого есть top_sort/2.

predsort/3 предполагает общий заказ, но вы можете предоставить только частичный заказ.

Другими словами, predsort/3 запросит предоставленный вами предикат сравнения. И он ожидает в качестве ответов <, = или >. Таким образом, вы должны получить один точный ответ для всех пар узлов. Однако для некоторых (тех, которые несравнимы) вы не можете сказать, каким должен быть результат. Вы можете только догадываться, что не приведет к последовательному общему порядку.

person false    schedule 08.01.2015
comment
Интересно, спасибо, есть идеи, как сказать прологу использовать depends_on для top_sort/2? Документация не очень помогает новичкам. - person Timbo925; 09.01.2015
comment
Вам нужно преобразовать данные в график, а затем вы можете использовать его. - person false; 09.01.2015

arrow_upward
1
arrow_downward

Я реализовал решение, предложенное @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).
person Timbo925    schedule 09.01.2015