以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  想请教一个实用问题，关于排列和分组的[求助]  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=18885)

--  作者：SteveGY
--  发布时间：5/26/2005 10:07:00 PM

--  想请教一个实用问题，关于排列和分组的[求助]
实际的问题是这样的：
需要为所有的应聘者安排面试的轮次，但安排在一个轮次中的应聘者有一些特殊的排列组合的条件
例如：性别应尽可能的平衡，来自各个不同的地区，考试成绩各不相同（可能有好中差），学历也尽可能的有些区别…………

实际的规则是以下的8条，每次安排轮次时，可以从中选择需要的规则加以应用
1. 学校所在地(上海&非上海）；
2. 现在地（城市）；
3. 笔试成绩；
4. 性别；
5. 专业；
6. 部门意向；
7. 学历；
8. 学校。

我大致的想了一下，不太确定这属于哪个领域的问题：（，似乎可以通过对参与者进行分组，再使用类似发扑克牌的原理在不同的分组分别抽出参与者进行编组，并在在分组中删除被抽出者，缩小范围，直到所有参与者都被编组为止。
但似乎分组的行为条件就和以上所述的8个条件的具体属性的分布概率有关，例如：性别，只可能有2种属性，而“笔试成绩”可能有多达10个等级，第2条的“现在地”有可能更多的不同属性，假定面试一轮可能有10个参与者，要同时（或几乎可以参考）符合上面这样8个条件的组合，应该使用什么样的解决方法呢？
这个问题实际有可能的规模大概在一次有4000人的参与者需要编组，每组10人。
不会真是NP-hard问题吧，这里可以容忍比较大的不均衡性。求一个工程的、近似的计算方法。

--  作者：eyounx
--  发布时间：5/27/2005 4:37:00 PM

--  
1。随机分组。随机抽人分组，则如果这些约束是相互独立，则每一组各种人的期望是均匀的。这个只是提供一种能行性
2。可以使用GA，可以提供近似解，而且运行时间可以由用户控制
--  作者：SteveGY
--  发布时间：5/28/2005 8:45:00 AM

--  
Thank u for the reply.
But,
What is the "GA"? 是不是可以描述的清楚一些，或者有什么地方可以参考一下的，thanks.
还有一个问题，对结果如何验证？比如，每次重排的结果都是不一样的，但如何验证呢，比如怎么证明结果1比结果2更好或更差？对条件赋权值，然后计算所有分组的权值。。。？
--  作者：wwyygg_123
--  发布时间：6/14/2005 9:18:00 PM

--  [分享]
是啊
楼上得兄弟可以说的更详细一点吗？
--  作者：wwyygg_123
--  发布时间：6/14/2005 9:20:00 PM

--  [分享]
对了
还有楼上的朋友可以把GA大概的介绍一下吗？
--  作者：cqiao
--  发布时间：1/7/2006 10:56:00 PM

--  
GA--genetic algorithm，即遗传算法。网上很多资料，我就不多说了。
--  作者：binaryluo
--  发布时间：1/8/2006 10:18:00 PM

--  
以下是引用SteveGY在2005-5-26 22:07:00的发言：
实际的问题是这样的：
需要为所有的应聘者安排面试的轮次，但安排在一个轮次中的应聘者有一些特殊的排列组合的条件
例如：性别应尽可能的平衡，来自各个不同的地区，考试成绩各不相同（可能有好中差），学历也尽可能的有些区别…………

实际的规则是以下的8条，每次安排轮次时，可以从中选择需要的规则加以应用
1. 学校所在地(上海&非上海）；
2. 现在地（城市）；
3. 笔试成绩；
4. 性别；
5. 专业；
6. 部门意向；
7. 学历；
8. 学校。

我大致的想了一下，不太确定这属于哪个领域的问题：（，似乎可以通过对参与者进行分组，再使用类似发扑克牌的原理在不同的分组分别抽出参与者进行编组，并在在分组中删除被抽出者，缩小范围，直到所有参与者都被编组为止。
但似乎分组的行为条件就和以上所述的8个条件的具体属性的分布概率有关，例如：性别，只可能有2种属性，而“笔试成绩”可能有多达10个等级，第2条的“现在地”有可能更多的不同属性，假定面试一轮可能有10个参与者，要同时（或几乎可以参考）符合上面这样8个条件的组合，应该使用什么样的解决方法呢？
这个问题实际有可能的规模大概在一次有4000人的参与者需要编组，每组10人。
不会真是NP-hard问题吧，这里可以容忍比较大的不均衡性。求一个工程的、近似的计算方法。


我想问下楼主，你提供的8条规则是不是需要对每一条都要按照一定的要求排序？

--  作者：SteveGY
--  发布时间：2/1/2006 11:39:00 AM

--  
呵呵，确实是以上面这样排序好的条件列出的，如果用客户需求描述的方式，“要求平均分布”，所以理解起来就是在分组后要得到一个大致平均的分布。
这个问题，已经提出太久了，实际上，问题是以一种和客户沟通后采取的折衷方案，模拟了用户的手工操作方式，就是发扑克牌的类似方法，先按上述的条件排序，再随机在分组中轮流抽取，这样的分布大致可以符合要求。其实，这样的方法在分步概率不平衡的情况下一定无法满足条件，但因为实际的操作在这种情况下并没有太严格的要求，所以用户也就接受了。
--  作者：binaryluo
--  发布时间：2/1/2006 11:30:00 PM

--  
如果跟扑克牌类似的话可以用“基数排序”，这种排序方法就是针对于有多关键字的一种排序方法。
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 62.500ms