游戏自动分配算法讨论
比如一款麻将游戏。每个人点开始游戏后。系统会自动进行组合，选出4个人作为一个房间，这个算法如何设计？
假设我点击开始游戏后，将我申请进入一局游戏的请求发送给服务器，就进入等待环节，服务器在可以组成一个房间后，向该房间成员发出通知。满足要求的人数不够等无法组成房间时，就等待。玩家等不及了，可退出等待环节。
要求：
①保证同一IP玩家不会被分到一个房间里（防止个人作弊，防止距离很近的人合伙算计他人）
②尽量使组成一个房间的四个人水平大致相当（假设有一个整数的属性表明该玩家水平，值越大水平越高）
③允许玩家提出附加要求，比如只和xx等级以上玩家玩（注意提出该要求的玩家可以和符合该要求但未提出要求的玩家 或 同时符合双方要求的玩家 组合）
④效率，复杂度，内存占用等。尽量不在数据库中操作。
难度逐级增大啊，喜欢琢磨的琢磨一下吧。
PS.腾讯的游戏好像都是手动找座位的，国外的有些麻将游戏就是这样分配的。
坦桑尼亚造船厂
12 years, 8 months ago
Answers
1,2,3其实是三条rule。简单算法如下，
- 挑选一个人坐在某桌作为起始
- 首先抽取本桌candidate的集合set，（比如最近等待5分钟的全部的人），问题转换为从一个set里面随机抽取三个人满足条件1,2,3的问题。
- 依次遍历集合的每个人，最先符合条件的三个人坐下剩下的三个空位
- 剩下N-3的人用3/4的概率任意替换前面4人中的某人。集合遍历结束可以得到随机的四个人。
- 为了速度和效率，在抽取candidate集合的可以用一些算法加快。比如实现根据rank形成不同的队列加快partition的过程。
本答案思路来自google的一道面试题：
You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
莱茵的黄金
answered 12 years, 8 months ago