朋友選擇算法

Question

在我們有一組兩種類型的200人.NET項目，可以說x和y，需要被分成7個或8

組我們有一個網頁，誰人們寫下他們想要成爲一個團體的其他成員。每個人建立一個通緝成員的名單。

在此之後，應該有一個算法來構建7-8成員組考慮到人的評級，並且以下條件：每個組每個類型至少有2個人（x/y）。

我敢肯定，必須有一個衆所周知的算法類似於此，但沒有找到一個。任何人都知道如何做到這一點？

Answer 1

這個問題有味道NP-Hard，所以我建議使用人工智能工具。

可能的方法是steepest ascent hill climbing [SAHC] 首先，我們將定義我們的效用函數（讓它爲u），如問題的評論中所述。 [每個用戶組中的朋友總數]。讓我們爲u(illegal) = -1定義非法解決方案。
接下來，我們定義我們的'世界'：S is the group of all possible solutions]。
對於S中的每個解決方案，我們定義：
next(s)={all possibilities moving one person to a different group}

現在我們所要做的就是運行SAHC隨機重啓：

1. best<- -INFINITY 
2. while there is more time 
3. choose a random legal solution 
4. NEXT <- next(s) 
5. if max{ U(NEXT) } < u(s): //s is the top of the hill 
    5.1. if u(s) > best: best <- u(s) //if s is better then the previous result - store it. 
    5.2. go to 2. //restart the hill climbing from a different random point. 
6. else: 
    6.1. s <- max{ NEXT } //climb on the steepest hill. 
    6.2. goto 4. 
7. return best //when out of time, return the best solution found so far. 

這是anytime algorithm，這意味着它會得到一個更好的結果，你給它更多的時間來運行，並最終[在無限時間]它會找到最佳結果。