亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

添加和刪??除人員的循環算法

添加和刪??除人員的循環算法

阿波羅的戰車 2023-11-11 21:26:04
好的,在這個 codepen 中我已經找到了循環賽調度算法:https://codepen.io/Piconey/pen/mwPamwvar players = [  {    playerName: 'Person 1',  },  {    playerName: 'Person 2',  },  {    playerName: 'Person 3',  },  {    playerName: 'Person 4',  },  {    playerName: 'Person 5',  },  {    playerName: 'Person 6',  },  {    playerName: 'Person 7',  },  {    playerName: 'Person 8',  },  {    playerName: 'Person 9',  },  {    playerName: 'Person 10',  },  {    playerName: 'Person 11',  },  {    playerName: 'Person 12',  },  {    playerName: 'Person 13',  },  {    playerName: 'Person 14',  },  {    playerName: 'Person 15',  },  {    playerName: 'Person 16',  },];var numberOfRounds = players.length - 1;function generateRounds() {  for(i = 0; i < numberOfRounds; i++) {    document.write('<h1 class="round">'+'Round ' + (i+1) + '</h1>');        for (var j = 0; j < players.length / 2; j++) {       document.write('<div class="match">' + players[j].playerName + " - " + players[players.length - 1 - j].playerName +'</div>');    }    players.splice(1, 0, players[15]);    players.pop();  }}generateRounds();我用它來快速約會,即使你可以和每個人約會。我的問題:每輪結束后,新人都可以加入活動或離開活動(如果他們感到無聊;)注意:遲到者不需要和所有人約會,因為他們已經錯過了 x 輪。 注 2:如果很多人離開,最好限制輪數,這樣人們就不需要在輪次之間等待那么長時間日期
查看完整描述

1 回答

?
動漫人物

TA貢獻1815條經驗 獲得超10個贊

對于二分匹配問題,例如分開的男性和女性組之間的快速約會,您可以使用最大流算法。

構建 4 層圖:

  1. 源節點S

  2. 每個人一個節點

  3. 每位女性一個節點

  4. 匯聚節點T

  • 完全連接第 1 層到第 2 層,邊緣容量為 1

  • 完全連接第 2 層至第 3 層,邊緣容量為 1

  • 完全連接第 3 層至第 4 層,邊緣容量為 1

當添加一個人時,將其添加為第 2 層或第 3 層中的新節點,并如上所述完全連接到相鄰層。

當一個人被移除時,移除他們在第 2 層和第 3 層的節點以及他們節點上的所有邊。

在每一輪中,使用最大流算法來識別您的配對。本輪結束后,將參與配對的第2層->第3層邊的容量設置為0。這樣可以防止相同的兩個人在后續輪次中再次匹配。


啟發式:您可以修改最大流算法,將日期最少或輪次最多的人員配對,因此,如果存在奇數人數,則最新的人和同一個人都不會坐在輪次中。

擴展:您可以通過過濾第 2 層和第 3 層之間添加的邊集來實現首選項來限制潛在匹配集。

時間:每輪大約 O(n^3)


對于任何人對任何人的匹配問題,您必須將最大流算法替換為更復雜的 Blossom 算法。

與最大流一樣,該算法通過查找增廣路徑然后修改其當前的匹配集來迭代地細化匹配。

該算法的輸入是:

  • 為每個人添加一個節點

  • 完全連接所有節點

與二分情況一樣,在每輪結束時,刪除與前幾輪匹配的所有邊,以防止相同的兩個人被匹配。

當有新人加入時,添加一個節點并將其與其他人完全連接起來。

當一個人離開時,刪除他們的節點和所有連接的邊。

查看完整回答
反對 回復 2023-11-11
  • 1 回答
  • 0 關注
  • 151 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號