队友查找应用程序的装箱算法？

Question

问题

• 我可以使用装箱算法从试图寻找队友的动态玩家队列中组建 5 人团队吗？

背景 我正在制作一个队友查找应用程序，其中：

• 玩家选择角色和地区
• 玩家点击查找匹配项
• 玩家被放入匹配队列
• 一个大厅只有5个角色位
• 玩家根据自己的角色选择一个角色位置
• 玩家被放置在一个合适的箱子（大厅）中，其中考虑了玩家的MMR（排名）、地区、角色和KDA。
• 如果玩家不适合现有大厅，程序将创建一个新大厅
• 大厅组是根据玩家的MMR和地区创建的，并根据排名等级和地区进行放置

  rank_tier = Math.round(MMR/1000) and lobby_group_key=(rank_tier+region) ex. region=America MMR=3333 rank_tier=3 key=3America; region=EU MMR=3500 rank_tier=4 key=4EU

• 大厅被放置在大厅组中
• 不适合的玩家将被放置在新大厅
• 移动到下一个玩家并尝试放置，直到队列中没有玩家
• 一旦大厅被填满，它就被认为是最终的，并从暂定列表中删除

伪代码

这是我想到的伪代码，但我不知道它是否正是装箱算法。我对算法真的很陌生

let tentative_lobbies = new Map()
let player_queue = new Map()

//player joins queue
function playerJoins(){
    tryPlacePlayer(player)
}

// try to place player in a lobby(bin)
function tryPlacePlayer(player){
    if lobby group doesn't exist
        //make a lobby group based on player MMR and region
        rank_tier = Math.round(player.MMR/1000)
        lobby_group_key = rank_tier+player.region
        lobby_key = ranktier+``+1
    else
        for each lobby that exist for player's rank and region
            if lobby's roleslot is not yet taken
                //place player into the lobby and recalculate the lobby's average kda

            if lobby's roleslots are all filled 
                //remove lobby from tentative_lobbies

        if player didn't fit in any of the lobbys in his rank tier
            //Make a new Lobby based on player's rank and region
            rank_tier = Math.round(player.MMR/1000)
            lobby_group_key = rank_tier+player.region
            lobby_key = ranktier+``+lobby_group.size + 1
            //calculate the average kda for the new lobby
            //place the lobby into tentative_lobbies
}

Answer 1

在经典的装箱问题中，您试图将加权元素放入最小数量的容量箱中。 您正在解决的问题对我来说更像是一个匹配问题。

您正在描述一个“贪婪算法”，您可以在其中对每个新玩家做出迭代的最终决定。您可以将其称为“最佳插入策略”。它肯定会产生一个可行的解决方案，使用“少量”大厅，并且似乎完全适合您想要实现的目标。 但是，如果您寻求在 MMR、位置等方面拥有最平衡的大厅集合，那么这不会产生最佳解决方案。 例如，以 MMR 0 的 p1、MMR 5 的 p2 和 MMR 15 的 p3 以及兼容的角色为例，并说只有当新玩家与平均 MMR 的距离为 时，您才接受新玩家 使用顺序（p2，p3，p1），它们将在同一个大厅中被接受，但使用顺序（p1，p2，p3）则不会，这将创建另一个大厅。 我在这里看到两个想法：

<= 10.

设计验收标准来克服这个问题

设计一个例程来定期尝试合并大厅