在我們有一組兩種類型的200人.NET項目,可以說x
和y
,需要被分成7個或8朋友選擇算法
組我們有一個網頁,誰人們寫下他們想要成爲一個團體的其他成員。每個人建立一個通緝成員的名單。
在此之後,應該有一個算法來構建7-8
成員組考慮到人的評級,並且以下條件:每個組每個類型至少有2個人(x/y
)。
我敢肯定,必須有一個衆所周知的算法類似於此,但沒有找到一個。任何人都知道如何做到這一點?
在我們有一組兩種類型的200人.NET項目,可以說x
和y
,需要被分成7個或8朋友選擇算法
組我們有一個網頁,誰人們寫下他們想要成爲一個團體的其他成員。每個人建立一個通緝成員的名單。
在此之後,應該有一個算法來構建7-8
成員組考慮到人的評級,並且以下條件:每個組每個類型至少有2個人(x/y
)。
我敢肯定,必須有一個衆所周知的算法類似於此,但沒有找到一個。任何人都知道如何做到這一點?
這個問題有味道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,這意味着它會得到一個更好的結果,你給它更多的時間來運行,並最終[在無限時間]它會找到最佳結果。
當然,您可以使用任何不依賴於漸變而不是SAHC的優化器(模擬退火,遺傳算法......) –
指標是什麼?如果沒有完美的解決方案,您如何評估哪個解決方案比另一個更好? – amit
每個人都選擇朋友,所以最好的選擇是讓儘可能多的人成爲一個擁有多少選定朋友的人。當然還要考慮類型條件。 –
因此,對於用戶中的每個用戶,度量標準應該是Sigma(#friends_in_group(u))? [僅限法律解決方案]? – amit