什麼算法來找到包含至少一個元素的最小集合（每個集合包含至少一個元素）

Question

因此，我有幾個集合，並且我需要找到包含所有集合中至少一個元素的最小集合數。爲了使這更具體，我有一組服務器名稱，並且每個服務器都有一個服務窗口。給定一個特定的持續時間，我想找到涵蓋所有給定服務器的最小服務窗口集。

我已經有代碼生成每個所需機器的所有不重疊N分鐘時間段的列表。我只是通過生成所有可能的組合來蠻力，然後選擇具有最少數量的獨特元素的組合，但這看起來效率非常低，即使我首先將該組縮小爲來自所有主機的唯一窗口（特別是更多比幾個系統）。

然後我想我會按照適合每個時間段的主機數量來排序時間段，選擇主機數量最多的時間段，然後重新生成未分配主機的所有時間段列表，挑選最受歡迎的插槽，重新計算等，直到所有主機都被佔用。雖然這會給我一個答案，但這並不能讓我有機會選擇最平衡的組合 - 第二個目標是找到一組服務窗口，其中每個服務的主機數量具有最小標準差窗口。所以，如果我有100個主機，我想優先考慮窗口，它給了我每個窗口50個主機，而不是做上述算法可能找到的三個「98,1和1」窗口。但是，如果我的選項是「98,1,1」或10個窗口，每個10個。我寧願做三個。

總之，似乎某種圖形可以用來表示這個問題，但我更關注的是硬件而不是我的CS路徑中的軟件，解決圖形問題從來沒有真正成爲我的特長。所以，我甚至會對如何閱讀關於這個特定問題或適當的搜索條件的更多建議表示感謝。 :)

Answer 1

這是集合覆蓋優化問題，這是NP-hard。這意味着在最壞情況中，你不可能比蠻力做得更好。這就是你可以快速找到一些套件的一些安排。但是，您絕對可以簡化問題 - 特別是使用真實世界的數據。

我會先對數據進行幾次轉換。想象你的套件是布爾的網格。每列表示一個服務器，每一行代表一個集合。在單元格中是真的意味着服務器存在於該集合中。

1. 很可能您有多個服務器屬於完全相同的集合。也就是說，這個矩陣中可能會有相同的列。您可以刪除任何重複的列。因此，如果A和B具有完全保存服務窗口，則獲取包含A的封面也將包含B.您可以通過使用此列中的值對每個服務器進行散列，然後檢查相同散列存儲桶中的每個服務器相同的成員資格。只保留一臺服務器，並創建一個「隨行」服務器列表。例如。從這一點開始，這些服務器將被視爲您的集合中的單個成員。

2. 刪除任何其他集合的子集。例如如果你有{1,2,3}和{1,2}。從問題中刪除{1,2}。爲您的覆蓋物挑選集合{1,2,3}將始終是更好的選擇。因此轉儲子集 - 例如刪除所有這些行。

3. 迭代每臺服務器（例如每列）。每個僅存在於一個集合中的服務器（例如列中的一個爲真）然後那個集合必須是是解決方案的一部分。因此，將該設置添加到解決方案中，並將其從矩陣中移除。現在，您可以從矩陣中刪除已刪除的集合中的所有列。說服務器A只存在於集合1中，即{A，B，C}。好套1 必須成爲解決方案的一部分。如果是，那麼我會自動知道服務器A，B，C將自動被覆蓋。所以我從矩陣和A，B，C的列中刪除了集合1。

4. 刪除每組中的任何服務器。他們將採取任何解決方案。

在此之後，您的真實問題集應該大大減少，除非您的數據集是「反常」。真實世界的數據可能會有序，足以使一堆行和列退出問題。

我確定有很好的方法可以找到一個答案，在實踐中，這個答案會給你提供非常接近於最佳覆蓋範圍的比真實世界數據更好的蠻力時間。

我會考慮DP或A-Star搜索解決方案。我沒時間了。我稍後可能會勾畫它。

Answer 2

考慮與每個時間段關聯的單個服務器集。您正在構建這些集合的一個子集，以使其聯合包含所有服務器。這被稱爲Set cover problem，已被證明是NP-complete。這意味着你不能比你在問題中描述的蠻力方法做得更好，所以儘可能降低來自所有主機的唯一窗口的數量。

---

P.S.我不知道爲什麼 templatetypedef刪除了他的答案 - 我認爲這是正確的。