所以，我正在做一個涉及機器學習的個人專案，我想設定一個訓練資料集和一個測驗資料集，這樣訓練資料集就不會污染測驗資料集。
我正在嘗試預測在線游戲中的獲勝球隊。
我有 10,000 個左右的游戲。每場比賽都有10名球員參加。一些球員參加了多場比賽。我想將 10,000 人分成兩個不同的組，這樣第 1 組的玩家就不會參加第 2 組的游戲。
什么是有效的演算法來做到這一點？
我只能嘗試暴力破解它。拿出 10,000 場比賽中的 2,000 場，然后檢查每場比賽中 2,000 場比賽中沒有玩家在剩余的 8,000 場比賽中，如果該玩家是，則遍歷 10,000 場比賽以找到沒有的與剩余的游戲共享一個玩家。
但是，我擔心這會花費很長時間。
編輯：答案似乎是從游戲開始的廣度優先搜索，然后通過共享玩家將所有游戲連接到它，并這樣做直到搜索結束，創建一個集群。這樣做直到沒有游戲剩下并且您擁有所有單獨的集群。
uj5u.com熱心網友回復：
您可以使用Disjoint-set 資料結構來執行此任務。
演算法：
ds // disjoint set object or data structure
for each round x:
for each player_a in round x:
for each player_b in round x:
ds.union(player_a, player_b)
簡單地說，在每一輪中對所有參加同一輪比賽的球員進行聯合。這將創建不相交的集合，其中每個不相交的集合都代表一組嚴格相互比賽的玩家。
應用上述演算法后，
- 如果您正好有兩個不相交的集合，那么您可以說第 1 組中的玩家沒有與第 2 組中的任何玩家一起玩。
- 如果你只有一套，那么這樣的磁區是不可能的。
- 如果存在兩個以上不相交的集合，您可以將一些集合組合在一起，直到只剩下 2 個集合。
考慮到 10,000 輪和每輪 10 名玩家，上述演算法將粗略計算 10 6 * log 2 (10 6 ) 次操作，大約為 2 * 10 7 次操作。這可以在任何現代筆記本電腦/個人電腦上輕松計算在一秒鐘內。
有用的實施視頻
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/395983.html
標籤：算法