新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 算法理论与分析 』 → 想请教一个实用问题，关于排列和分组的[求助] ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 7116 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 想请教一个实用问题，关于排列和分组的[求助] 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     SteveGY 帅哥哟，离线，有人找我吗？
      
      等级：大一新生
      文章：2
      积分：64
      门派：XML.ORG.CN
      注册：2005/5/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给SteveGY发送一个短消息 把SteveGY加入好友 查看SteveGY的个人资料 搜索SteveGY在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看SteveGY的博客楼主
    发贴心情 想请教一个实用问题，关于排列和分组的[求助]

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

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

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


       收藏   分享  
    顶(0)
      




    ----------------------------------------------
    培训管理软件 http://www.lvup.com/tms

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/5/26 22:07:00
     
     eyounx 帅哥哟，离线，有人找我吗？金牛座1982-5-3
      
      
      威望：9
      等级：大四(GRE考了1400分!)(版主)
      文章：272
      积分：1260
      门派：GOOGLEBBS.NET
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给eyounx发送一个短消息 把eyounx加入好友 查看eyounx的个人资料 搜索eyounx在『 算法理论与分析 』的所有贴子 访问eyounx的主页 引用回复这个贴子 回复这个贴子 查看eyounx的博客第2楼
    发贴心情 
    1。随机分组。随机抽人分组，则如果这些约束是相互独立，则每一组各种人的期望是均匀的。这个只是提供一种能行性
    2。可以使用GA，可以提供近似解，而且运行时间可以由用户控制

    ----------------------------------------------
    member of LAMDA, CS, NJU
    http://lamda.nju.edu.cn/
    http://lamda.nju.edu.cn/yuy

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/5/27 16:37:00
     
     SteveGY 帅哥哟，离线，有人找我吗？
      
      等级：大一新生
      文章：2
      积分：64
      门派：XML.ORG.CN
      注册：2005/5/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给SteveGY发送一个短消息 把SteveGY加入好友 查看SteveGY的个人资料 搜索SteveGY在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看SteveGY的博客第3楼
    发贴心情 
    Thank u for the reply.
    But,
    What is the "GA"? 是不是可以描述的清楚一些，或者有什么地方可以参考一下的，thanks.
    还有一个问题，对结果如何验证？比如，每次重排的结果都是不一样的，但如何验证呢，比如怎么证明结果1比结果2更好或更差？对条件赋权值，然后计算所有分组的权值。。。？

    ----------------------------------------------
    培训管理软件 http://www.lvup.com/tms

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/5/28 8:45:00
     
     wwyygg_123 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究汇编)
      文章：35
      积分：210
      门派：XML.ORG.CN
      注册：2005/6/14

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给wwyygg_123发送一个短消息 把wwyygg_123加入好友 查看wwyygg_123的个人资料 搜索wwyygg_123在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看wwyygg_123的博客第4楼
    发贴心情 [分享]
    是啊
    楼上得兄弟可以说的更详细一点吗？
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/6/14 21:18:00
     
     wwyygg_123 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究汇编)
      文章：35
      积分：210
      门派：XML.ORG.CN
      注册：2005/6/14

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给wwyygg_123发送一个短消息 把wwyygg_123加入好友 查看wwyygg_123的个人资料 搜索wwyygg_123在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看wwyygg_123的博客第5楼
    发贴心情 [分享]
    对了
    还有楼上的朋友可以把GA大概的介绍一下吗？
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/6/14 21:20:00
     
     cqiao 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：2
      积分：68
      门派：XML.ORG.CN
      注册：2006/1/3

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给cqiao发送一个短消息 把cqiao加入好友 查看cqiao的个人资料 搜索cqiao在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看cqiao的博客第6楼
    发贴心情 
    GA--genetic algorithm，即遗传算法。网上很多资料，我就不多说了。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/1/7 22:56:00
     
     binaryluo 帅哥哟，离线，有人找我吗？
      
      
      威望：6
      等级：研二(Pi-Calculus看得一头雾水)(版主)
      文章：679
      积分：5543
      门派：IEEE.ORG.CN
      注册：2005/2/19

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给binaryluo发送一个短消息 把binaryluo加入好友 查看binaryluo的个人资料 搜索binaryluo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看binaryluo的博客第7楼
    发贴心情 
    以下是引用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条规则是不是需要对每一条都要按照一定的要求排序？

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/1/8 22:18:00
     
     SteveGY 帅哥哟，离线，有人找我吗？
      
      等级：大一新生
      文章：2
      积分：64
      门派：XML.ORG.CN
      注册：2005/5/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给SteveGY发送一个短消息 把SteveGY加入好友 查看SteveGY的个人资料 搜索SteveGY在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看SteveGY的博客第8楼
    发贴心情 
    呵呵，确实是以上面这样排序好的条件列出的，如果用客户需求描述的方式，“要求平均分布”，所以理解起来就是在分组后要得到一个大致平均的分布。
    这个问题，已经提出太久了，实际上，问题是以一种和客户沟通后采取的折衷方案，模拟了用户的手工操作方式，就是发扑克牌的类似方法，先按上述的条件排序，再随机在分组中轮流抽取，这样的分布大致可以符合要求。其实，这样的方法在分步概率不平衡的情况下一定无法满足条件，但因为实际的操作在这种情况下并没有太严格的要求，所以用户也就接受了。

    ----------------------------------------------
    培训管理软件 http://www.lvup.com/tms

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/2/1 11:39:00
     
     binaryluo 帅哥哟，离线，有人找我吗？
      
      
      威望：6
      等级：研二(Pi-Calculus看得一头雾水)(版主)
      文章：679
      积分：5543
      门派：IEEE.ORG.CN
      注册：2005/2/19

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给binaryluo发送一个短消息 把binaryluo加入好友 查看binaryluo的个人资料 搜索binaryluo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看binaryluo的博客第9楼
    发贴心情 
    如果跟扑克牌类似的话可以用“基数排序”，这种排序方法就是针对于有多关键字的一种排序方法。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/2/1 23:30:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/10 17:33:56

    本主题贴数9，分页： [1]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 82.031ms