擴展基於LINQ的規範模式以實現包含

組合規範模式有許多基於LINQ的實現。我還沒有看到一個使用了包容的。擴展基於LINQ的規範模式以實現包含

是否有任何這樣的例子已被記錄（博客等）或發佈爲開源？通過讓ExpressionVisitor將每個規範轉換爲規範的邏輯形式（CNF/DNF），我對此有一個想法和概念證明，但我擔心這太過複雜。有沒有更好的辦法？

來源

2012-12-04 smartcaveman

你的意思是有條件在Linq的where子句中嗎？ –

我擔心這過於複雜。有沒有更好的辦法？

簡短的回答是「沒有，沒有」

長的回答是：「過於複雜」抓住了問題的本質：它是NP難。下面是一個簡短的非正式證明依賴於一個事實，即satisfiability problem is NP-complete：

假設您有兩個布爾公式，A和B
您需要測試如果A意味着B，或等效¬A | B的所有任務變量A和B取決於。換句話說，你需要一個證明F = ¬A | B是一個重言式。
假設重複測試可以在多項式時間內執行
考慮¬F，F的倒數。 F是可滿足當且僅當¬F不是同義反復
使用假設多項式算法測試¬F，作爲一個同義反復
的答案爲「是F令人滿意」的答案的倒數「是¬F重言式「
因此，多項式重言式檢查器的存在意味着可滿足性問題在P和P=NP。

當然事實上，這個問題是NP難的，並不意味着對於實際案例將不會有解決方案：事實上，您轉換爲規範形式的方法可能在許多實時操作中產生OK結果，世界的情況。然而，缺乏已知的「好」算法經常會阻礙實際解決方案的積極開發。

隨着強制性「除非 P=NP」的免責聲明。

除非「相當好」的解決方案能夠做到，如果您允許出現「漏報」，您的問題可能就是這種情況。

來源

2012-12-11 20:12:16 dasblinkenlight

+1，問題：你在詞的形式邏輯意義上使用重言式還是在CS中有類似但不同的定義？我的理解是，一個命題是同源的，如果它可以來自空白的SC句子集合。這並不足以描述我想證明的內容，因爲我也有一個廣泛的知識庫/數據庫。另一方面，這個問題很難，但之前已經有效地解決了。現在，我正在研究Prolog，Euler和Microsoft Solver Foundation。 – smartcaveman

@smartcaveman我在這個詞的形式邏輯意義上使用了重言式：爲了證明表達式'A'包含'B'，你需要證明'A => B'總是爲真，即可以從空一套房屋。我提到它的唯一原因是爲了達到可滿足性問題，該問題被稱爲NP完全性。請注意，只有'A => B'必須是重言式;單個表達式'A'和'B'可以是，並且在所有不平凡的情況下，將基於非空的一組處所。這個集合越大，越難證明'A'包含'B'。 – dasblinkenlight

所以我對如何更實際地解決這個問題有了另一個想法 - 仍然是解決問題的方法。而不是純粹的重寫，我可以爲每個謂詞創建一個平方反對模型，並要求我的所有謂詞都是三段論形式。這似乎可以減輕複雜性，B/C的內容將被規範化，而不是正式的表示 - 因爲我的域名是一個商業應用程序，我認爲它可能足以表達。有什麼想法嗎？ – smartcaveman

擴展基於LINQ的規範模式以實現包含

回答

相關問題