共線點的所有子集 - Prolog

我想在Prolog中創建一個回溯程序來確定共線點的所有子集。問題：計劃中有n個點（用其座標表示）。編寫一個謂詞來確定共線點的所有子集。共線點的所有子集 - Prolog

實施例：

輸入：[[1,1]，[2,2]，[3,3]，[0,0]，[4,8]，[1,2]，[輸出：[[[1,1]，[2,2]，[3,3]]，[[1,1]]，[1,1,2] ，[2,2]，[0,0]]，[[2,2]，[3,3]，[0,0]]，[[1,1]，[3,3]，[0， 0]，...]

到目前爲止，我在檢查thaught如果3點通過檢查這個公式是共線：
(Xc - Xa)/ (Xb - Xa) = (Yc - Ya)/ (Yb - Ya).

但是，我不要認爲這會起作用，因爲我需要使用回溯來解決問題。我應該在每個函數調用中接受一個候選人，看看它是否與其他函數匹配。

你能否建議我檢查3點共線的正確方法？

來源

2016-12-09 GritcoAndreea

你描述的內容根本不清楚！你至少應該給出一個輸入和期望輸出的簡單例子......從我理解的內容如果你有一個點的列表，你可以遞歸地檢查它們是否在3線上，看看它們是否是共線的，並且作爲最後3點的基本情況.... – coder

@coder，我把這裏的例子。對不起，我完全忘了。是的，我需要遞歸地找到共線的3個點的所有子集。 – GritcoAndreea

輸入沒有意義作爲序言開始查詢......但總的來說，你有正確的想法。如果a，b和b，c的斜率相同（但是對於任何輸入順序），則三個點a，b，c是共線的。 –

我假設你的程序的查詢將是這樣的：

?- findColinears([[1,1],[2,2],[3,3],[0,0],[4,8],[1,2],[6,7],[8,9],[10,11]], Out).

很顯然，我不會提供代碼來解決整個問題對你，但一般一個自上而下的方法可能涉及類似的謂詞如下：

colinear(P1, P2, P3) :- slope(P1, P2, S), slope(P1, P3, S). 
colinear(P1, P2, P3) :- slope(P1, P2, S), slope(P2, P3, S). 
colinear(P1, P2, P3) :- slope(P1, P3, S), slope(P2, P3, S). 

slope(P1, P2, S) :- 
    P1 = p(X1, Y1), 
    P2 = p(X2, Y2), 
    S is ((Y2-Y1)/(X2-X1)). 

findColinearTriplet(ListOfPoints, Triplet) :- 
    member(P1, ListOfPoints), 
    member(P2, ListOfPoints), dif(P1, P2), 
    member(P3, ListOfPoints), dif(P1, P3), dif(P2, P3), 
    colinear(P1, P2, P3), 
    Triplet = [P1, P2, P3].

然後，您可以使用這些查找所有可能的Triplet統一。
當然，一些三元組是相當的（例如[p(1,1), p(2,2), p(3,3)]和[p(3,3), p(1,1), p(2,2)]）。另外，一些將會重複。如果你想要唯一的三元組，你必須從收集的所有非唯一三元組中手動構建這樣一個唯一的列表。

你最終findColinears謂詞例如，可能看起來像：

findColinears(ListOfPairs, Out) :- 
    convertToPoints(ListOfPairs, ListOfPts), 
    findall(Triplet, findColinearTriplet(ListOfPts, Triplet), ListOfTriplets), 
    discardDuplicates(ListOfTriplets, Out).

的適當定義convertToPoints和discardDuplicates謂詞。

來源

2016-12-09 20:58:21

非常感謝你@Tasos！ – GritcoAndreea

- Cu placere :) –

共線點的所有子集 - Prolog

回答

相關問題