predsort/3意外行爲

我在排序Prolog中的任務列表[t7, t1, t6, t2, t4, t3, t5]時遇到問題。爲了排序，我想使用預定義的公式predsort/3，因爲它看起來像是正確的方法。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更好的選擇？問題是我沒有看到如何結合自定義謂詞來實現keysort。

來源

2015-01-08 Timbo925

「sort_dependency/3」的第3個子句究竟意味着什麼？我認爲它應該是'=='。但是，如果兩個物體不直接相互依賴，爲什麼兩個物體應該是相同的呢？ – false

對我來說，我認爲這是因爲，如果兩個任務都是相同的，或者它們彼此不相互依賴，那麼使用'>'作爲謂詞。如果我用'sort_dependency（>，T，T2）'替換它，它應該是等價的，因爲如果前兩個子句都失敗了，第三個子句總是成立。如果我做這個改變，問題仍然是一樣的。 – Timbo925

這個名字應該是'compare_xxx'，第一個參數必須是'>'，'<'或'=='。 – false

拓撲排序是你真正想要的。這裏有top_sort/2。

predsort/3假設總訂單，但您只能提供部分訂單。

換句話說，predsort/3將查詢您提供的比較謂詞。它期望的答案爲<,=或>。所以你必須爲所有節點對生成一個確切的答案。然而，對於一些（無法比擬的），你不能說出結果應該是什麼。你只能猜測，這不會產生一致的總量。

來源

2015-01-08 22:56:17 false

有趣的感謝，任何想法如何告訴序言使用'depends_on'的'top_sort/2'？對於初學者來說，文檔似乎沒有多大幫助。 – Timbo925

您需要將數據轉換爲圖形，然後才能使用它。 – false

我實施了@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).

來源

2015-01-09 03:11:24 Timbo925

predsort/3意外行爲

回答

相關問題