分組算法要求

Question

所以我正在寫一個算法，給出一組來自不同地方的人的時候，它會組織成基於關閉三個一組的幾個參數：

1. 沒有兩個人一組來自同一個地方
2. 沒有兩個人在一組以前
3. 每個人組中，可滿足在同一天
4. 不超過1人是18
歲以下的滿足

我在我的數據結構中有一個變量，用於上述所有必需的prereq。我想知道是否有解決這個問題的好方法？目前我正在使用Gale-Shapely算法的變體（穩定婚姻問題的解決方案）。這個解決方案工作得比較好，但更常見的是，這不需要我進入並對最終組進行一些小調整。

任何人有任何想法/建議嗎？

我很欣賞提前的幫助。

Answer 1

這是一個graph partitioning問題，因此幾乎可以肯定是NP-Hard（當你只有一個約束時，那麼問題可以在多項式時間內解決 - 這與穩定的婚姻問題類似 - 但是當你已經有了多重限制，然後複雜性就會出現）。解決這些問題的一個好方法是應用啓發式（您使用Gale-Shapely算法進行處理），然後解決與本地回溯搜索的任何衝突（這聽起來像您目前正在進行的操作） 。我的建議是保持目前的啓發式，如果它似乎適合你，並且添加一個自動化的本地回溯算法來解決由啓發式引發的任何衝突（例如，如果你有一個單獨的組，有兩個人誰18歲以下，然後將這些人中的一人與18歲以上的人交換，並且不違反其他三種限制條件;如果這不可行，那麼選擇超過18人違反最少限制的人，然後交換爲了滿足現在違反的約束;在N次迭代失敗後，算法拋出它的手並要求人工干預）