如何搜索每對符合條件的最大子集？

假設我有一個接口：

public interface PairValidatable<T> 
{ 
    public boolean isValidWith(T); 
}

現在，如果我有一個大陣PairValidatables的，我怎麼找到最大的子集該數組中的每一對通過isValidWith測試？爲了說明，如果子集中有三個條目，則元素0和1應該通過isValidWith，元素1和2應該通過isValidWith，並且元素0和2應該通過isValidWith。

實施例，

public class Point implements PairValidatable<Point> 
{ 
    int x; 
    int y; 

    public Point(int xIn, int yIn) 
    { 
     x = xIn; 
     y = yIn; 
    } 

    public boolean isValidWith(Point other) 
    { 
     //whichever has the greater x must have the lesser (or equal) y 
     return x > other.x != y > other.y; 
    } 
}

The intuitive idea是保持點的向量，添加數組元素0，並且如果它通過與所述向量的每一個元素的驗證比較每個剩餘數組元素的矢量，將其添加向量，如果是這樣的話......但問題是元素0可能是非常嚴格的。例如，

Point[] arr = new Point[5]; 
arr[0] = new Point(1000, 1000); 
arr[1] = new Point(10, 10); 
arr[2] = new Point(15, 7); 
arr[3] = new Point(3, 6); 
arr[4] = new Point(18, 6);

迭代通過如上會給我們只含有元素0的子集，但元件1,2和4是其中每對通過驗證的較大子集的子集。然後該算法應返回存儲在元素1,2和4中的點。儘管元素3和4彼此有效，元素1和元素4彼此有效，但元素2和3不是元素1和元素3。包含1,2和4的子集是比3和4更大的子集。

我猜想某些樹或圖算法對於解決這個問題是最好的，但我不確定如何設置它。

該解決方案不一定是Java特有的，最好可以用任何語言實現，而不是依賴於Java內置插件。出於熟悉的原因，我剛剛使用了類似於Java的僞代碼。

來源

2017-02-21 Devsman

您是否試圖說您要針對數組中的每個條目運行相同的算法，並在針對所有其他條目進行檢查時返回導致最成功返回isValidWidth的那個算法？ – Stephan

@Stephan不完全。子集中的每一對都應該從isValidWith返回true。例如，a可能對b有效，而b可能對c有效，但c可能對a無效。那將意味着a或c將不得不被省略。我不確定我的示例方法是否會以這種方式行事，但解決方案應該包含方法。 – Devsman

您可以擴展您的問題以在示例中包含3個以上的條目，以及您期望輸出的內容是什麼？ – Stephan

推測isValidWith是可交換的 - 也就是說，如果x.isValidWith(y)然後y.isValidWith(x)。如果你對此知之甚少，你就有一個maximum clique problem的實例，它被稱爲NP-complete：

Skiena，S. S.「Clique and Independent Set」和「Clique」。算法設計手冊中的§6.2.3和8.5.1。 New York：Springer-Verlag，pp.144 and 312-314，1997.

因此，如果你想要一個高效的算法，你將不得不希望你的具體isValidWith函數具有更多的結構比純粹的交換性，你會必須利用這種結構。

爲了您的具體問題，您應該能夠做到以下幾點：

排序你增加x的順序座標點。
查找排序列表中y座標的longest decreasing subsequence。

每個操作都可以在O（n * log（n））時間內執行，因此您的特定問題可以有效地解決。

來源

2017-02-21 18:45:57

所以我想我會設置一個圖形，其中每個頂點代表一個數組元素，並且邊連接通過isValidWith的對？ – Devsman

@Devsman沒錯。 –

@Devsman我在我的答案中添加了一個部分，討論您的特定'isValidWith'函數。 –

如何搜索每對符合條件的最大子集？

回答

相關問題