拓撲排序的有向圖頂點的子集

Question

我正在用C＃4.0編寫一個程序，我已經抽象出以下內容（我提及語言，以便您知道我必須使用哪些庫;沒有第三方庫） ：

---

讓S = { s1, s2, s3, ..., sn }。

對於所有si，sj在S，i != j，功能f(si, sj)是{ true, false }的元件。調用這個函數f是相當昂貴的，但是應該儘可能少地完成。

組給定的T = { t1, t2, t3, ..., tm }S一個非空的子集，計算其中含有的T使得f(ui, uj) == false所有元素用於所有i < j序列U = u1, u2, u3, ..., uo，和f(ui, s') == false用於S - U所有i和s'。你可能會認爲這樣的序列存在。

---

雖然這是沒有辦法的相關學校（它的工作），我喜歡的幫助最少讓我到你能想到的最優化的解決方案，讓我可以瞭解更多:)

---

提示（一些東西，我已經想過:)

1. 您需要訪問的每個節點至少一次。考慮T = { t }和f(t, s') == false的情況，對於所有s'的S - T和|S| >= 2。一旦在這種情況下也是足夠的。

2. 必須計算最小U。這種計算可以通過以下表示：與

   • ?項進行|S|x|S|鄰接矩陣：我不知道
   • 1：要看。
   • 0：不依賴於。
   • -：我不在乎。

考慮這個（我走自己通過一個實例來看看是否有到最佳電位檢查序列的模式，以幫助開發的算法）。 S = { a, b, c, d, e }T = { a, b, c }（由星表示）：

 a b c d e 
    ---------------- 
*a | - - - ? ? 
*b | - - - ? ? 
*c | - - - ? ? 
d | - - - - ? 
e | - - - ? - 

U = { a, b, c }最初。對角線爲-，因爲f在其操作數相等時未定義。由於a,b和c已經在集合中，所以任何人都依賴它們並不重要，因此-。

f(a, d)，f(a, e)，f(b, d)，f(b, e)，f(c, d)，f(c, e)是由於對稱性全部相等的候選人。假設我們選擇f(a, d)並且它返回false。我們的餐桌現在看起來是這樣的：

 a b c d e 
    ---------------- 
*a | - - - 0 ? 
*b | - - - ? ? 
*c | - - - ? ? 
d | - - - - ? 
e | - - - ? - 

案例1：U = { a, b, c }

要了解這一點，我們能做到這一點在3次檢查，如果我們很幸運，通過檢查f(b, d)，f(c, d)和f(e, d)和有他們都是false。

案例2：U = { a, b, c, d, e }

要了解這一點，我們能做到這一點在2次檢查，如果我們很幸運，通過檢查f(b, d)和f(a, e)，並讓他們都返回true。

（我還沒有想到過這些，完全的，但，我需要去吃飯感謝大家閱讀！）

案例3：U = { a, b, c, d }

案例4：U = { a, b, c, e }

Answer 1

我的理解是，你想要所有的節點，你可以訪問從子集T中的任何節點開始...如果這是你的意思，你可以嘗試這...

1. 用所有節點填充一個詞典（以節點作爲鍵和作爲值訪問布爾值（將此值設爲false））
2. 用子集T中的節點填充隊列（當您添加它們時搜索它們字典，並將其標記訪問）
3. 選擇在隊列檢查至極節點的第一個元素，你可以從它訪問，搜索，如果訪問了字典中，如果訪問跳過，如果沒有，將它們添加到隊列中，並將它們設置爲走訪，刪除隊列
4. 重複3的第一個元素，直到你有隊列中沒有項目

你節點的子集您可以訪問在t開始時你在字典

希望它可以幫助標明的...