我想知道這種情況是否有更好的解決方案：我有兩組物件 GroupA(A) 和 GroupB(B)，組 A 的物件連接到組 B 中的 2 個且只有 2 個元素，以及一個物件 A1來自組 A 的物件可以連接到與物件 A2 連接的相同物件。我的問題是我必須找到 GroupA 的最小物件集，這樣我才能到達 GroupB 中的所有物件。目前，我正在嘗試所有可能的選項并選擇可行的最小集合，但我拒絕相信這是唯一的解決方案。
這是我的第一篇文章，如果我不夠清楚，請原諒
uj5u.com熱心網友回復：
這是集合覆寫問題的一種變體。對于大型集合，嘗試每個選項都會非常緩慢，但這是獲得最佳解決方案的唯一方法。如果您能滿足于一個相當好的（但不是最優的）解決方案，那么您可以使用貪心演算法來近似解決方案。
基本思想是遍歷您的 GroupA 物件并選擇那些連接到您尚未涵蓋的大多數 GroupB 物件的物件。繼續這樣做，直到你有一個涵蓋所有 GroupB 的集合。
uj5u.com熱心網友回復：
由于 A 組中的每個物件都連接到 B 組中的兩個物件，那么您可以將問題視為一個圖——A 組物件是邊，B 組物件是節點。
然后你的問題是找到一個最小的邊緣覆寫：https ://en.wikipedia.org/wiki/Edge_cover
值得慶幸的是，有多項式時間解決方案。最簡單的一種是使用Blossom 演算法找到最大匹配，然后為未被覆寫的頂點選擇任意邊。
最大匹配中的每條邊（B 物件）覆寫 2 個不同的 A 物件，其余邊（B 物件）各覆寫一個新的 A 物件。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/415942.html
標籤：
上一篇：陣列演算法性能kata