Project1

标题: 求教一个关于算法的问题 [打印本页]
作者: 喵呜喵5    时间: 2014-11-18 01:23
标题: 求教一个关于算法的问题
有n名学生各自选择了十门课中的五门
每门课都只有一节，在五周里每周都有开课
，
每周上课的人数固定，十门课程的上课人数总和等于学生个数

现在每名学生都选好了课程，同时每门课的学生总数等于这门课每周的学生上限*5
求一个安排方法使每一个学生每周都能听到一节课且只听这节课
作者: 寒冷魔王    时间: 2014-11-18 23:45
本帖最后由 寒冷魔王 于 2014-11-18 23:54 编辑
  1. ## 初始下落物
  2. # 学生总数
  3. N = 50
  4. # 课程上限
  5. @m = Array.new(10,1)
  6. @m[9] += N-10
  7. class Drop
  8.   ## 初始化数据
  9.   def initialize(d)
  10.     @f = [d.clone] # 我们是朋友*^_^*
  11.     @t = d.clone   # 我是临时负责人
  12.     [url=home.php?mod=space&uid=133944]@w[/url] = Array.new  # 我在等待命运的邂逅
  13.   end
  14.   ## 检查下落可能性
  15.   # 单查
  16.   def check(dat,i)
  17.     return if i.nil?
  18.     return if !(0...dat.size).include?(i)
  19.     return if dat[i].nil? || dat[i-1].nil?
  20.     return dat[i]>dat[i-1]+1
  21.   end
  22.   # 通查
  23.   def checks(dat)
  24.     b = 0; w = Array.new
  25.     1.upto(dat.size-1) do |i|
  26.       if check(dat,i)
  27.         b+=1; w.push i
  28.       end
  29.     end
  30.     return b,w
  31.   end
  32.   ## 下落
  33.   # 单落
  34.   def drop(dat,i)
  35.     if check(dat,i)
  36.       dat[i]-=1
  37.       dat[i-1]+=1
  38.       @f.push dat.clone
  39.       return dat
  40.     else
  41.       return nil
  42.     end
  43.   end
  44.   # 分落
  45.   def drops(data)
  46.     dat,a = data
  47.     t = Array.new
  48.     a.each{|i|t.push drop(dat.clone,i)}
  49.     t.each do |n|
  50.       ch = checks(n)
  51.       @w.push [n.clone,ch[1]] if ch[0]>0 && [email protected]?(n)
  52.     end
  53.   end
  54.   def start
  55.     ## 主路线
  56.     loop do
  57.       ch = checks(@t)
  58.       @w.push [@t.clone,ch[1]] if ch[0]>1
  59.       @t = drop(@t,ch[1].shift)
  60.       break if @t.nil?
  61.     end
  62.     ## 命运的邂逅来了～
  63.     until @w.empty? do drops(@w.shift) end
  64.     ## 善后处理
  65.     n = Array.new
  66.     @f.each{|f|n.push f if !n.include?(f)}
  67.     return @f = n.clone
  68.   end
  69. end
  70. ## 求各个课程上限数
  71. # 特别说明，那个N的值不要太大，我用手机测N=500反正是死机了，尽管做了一定的算法优化，但是还是不行(我会告诉你我优化前N=50都死了吗？)所以别指望太多。。。ヽ(≧Д≦)ノ
  72. p Drop.new(@m).start
  73. # 按照我的分析求出上限数这个问题差不多就解决了(其实我后面的没看懂(≧ω≦))，5周都一样，N是总学生数。也可以改为变量。。
  74. # 反正这段代码也没神马用(算得都死机了= =|#)。就当作喵呜君告诉我那个非常非常好用的||=的谢礼吧～
  75. # 喵呜喵5:233
  76. nil
复制代码
作者: 喵呜喵5    时间: 2014-11-19 00:33
寒冷魔王 发表于 2014-11-18 23:45

好吧...直接带数字比较容易理解

有10门课，50名学生，5周时间
其中5门课每节只允许有6人上课，另外5门每节只允许有4人上课
求一个算法为50名学生安排一个上课表，使得:

50名学生在这五周中都上了五节不同的课
每门课的人数都刚刚好，不会出现超过的情况
学生上的课的安排是随机的
作者: 寒冷魔王    时间: 2014-11-19 13:24
本帖最后由 寒冷魔王 于 2014-11-19 13:40 编辑
喵呜喵5 发表于 2014-11-19 00:33
好吧...直接带数字比较容易理解

有10门课，50名学生，5周时间

  1. # 学生数
  2. N = 50
  3. @s = Array.new(N){Array.new}
  4. # 周数
  5. @weeks = 5
  6. # 课程上限
  7. @m = Array.new(@weeks){Array.new(5,6)+Array.new(5,4)}
  8. # 为便于分析和计算，将课程和学生编号写出
  9. @dc = Array.new(10){|n|n}
  10. @ds = Array.new(N){|n|n}
  11. @dw = Array.new(@weeks){|n|n}
  12. def randa(a)
  13.   return a.delete_at(rand(a.size))
  14. end

  16. def copy(da)
  17.   return da.clone if da[0].class!=Array
  18.   nda = Array.new
  19.   da.each{|a|nda.push a.clone}
  20.   return nda
  21. end
  22. def check(tm,tw,ts,ic,is)
  23.   return if tm[tw].nil?||ts.nil?
  24.   return if tm[tw][ic]<1||ts[is].size>5
  25.   return if ts[is].include?(ic)
  26.   return if !ts[is][tw].nil?
  27.   return true
  28. end
  29. def collect(ts)
  30.   c = Array.new(5){Array.new(10,0)}
  31.   ts.each do |s|
  32.     5.times do |w|
  33.       next if s[w].nil?
  34.       c[w][s[w]]+=1
  35.     end
  36.   end
  37.   return c
  38. end
  39. def start
  40. loop do
  41.   ts = copy(@s)
  42.   tm = copy(@m)
  43.   #dw = @dw.clone
  44.   @weeks.times do |tw|
  45.     #tw = randa(dw); dc = @dc.clone
  46.     10.times do |ic|
  47.       #ic = randa(dc);
  48.       ds = @ds.clone
  49.       N.times do
  50.         is = randa(ds)
  51.         next if !check(tm,tw,ts,ic,is)
  52.         tm[tw][ic] -= 1;ts[is][tw] = ic
  53.       end
  54.     end
  55.   end
  56.   return ts if collect(ts)==@m
  57. end
  58. end
  59. p ts = start
  60. p collect(ts)
  61. nil
  62. # 这个是采用随机数分配，有很大的偶然性。我这里随机一个变量(先前是三个，结果很慢)，至少这种算法我的手机可以运行出来。(优化前要看幸运度(≧▽≦))
  63. # 实例变量都是模板，每次循环会被复制。为了简练，我这里采用copy复制二维数组。至于深度复制神马的，都是浮云。(又要被T君说了≥﹏≤)
复制代码


作者: 喵呜喵5    时间: 2014-11-19 14:51
寒冷魔王 发表于 2014-11-19 13:24

每名学生的课程之前已经通过随机的方式选好了，

就是说，学生先通过抽签选好了自己总共要上的课程，之后需要为学生排序

这边给一组你自己的算法生成的选课情况（顺序已打乱）作为测试数据：
  1. [[1,3,4,8,9,],[0,2,4,6,9,],[0,1,2,3,6,],[1,2,4,6,9,],[0,1,3,5,9,],[0,1,2,4,8,],[1,4,5,6,9,],[0,1,2,3,5,],[0,2,3,4,7,],[0,3,5,6,7,],[0,1,2,3,9,],[1,3,4,6,9,],[0,3,4,5,8,],[0,5,6,8,9,],[0,1,3,4,9,],[0,1,2,6,8,],[0,1,3,4,9,],[0,4,6,7,8,],[1,2,5,7,9,],[0,1,3,7,8,],[1,2,3,5,7,],[1,2,3,4,8,],[0,1,4,6,7,],[2,3,4,7,9,],[0,2,3,4,5,],[0,1,2,3,6,],[1,3,4,6,7,],[0,2,4,7,8,],[0,3,4,6,7,],[3,6,7,8,9,],[2,3,6,8,9,],[0,1,2,3,8,],[1,2,4,5,7,],[0,3,7,8,9,],[0,3,4,7,8,],[0,1,2,3,4,],[2,4,5,6,7,],[1,5,7,8,9,],[1,4,5,7,8,],[0,1,4,5,9,],[0,2,3,4,5,],[2,3,7,8,9,],[1,2,4,5,6,],[2,3,4,6,8,],[0,1,2,4,5,],[1,2,3,5,6,],[0,1,2,4,5,],[2,4,7,8,9,],[0,2,5,8,9,],[0,1,2,3,6,]]
复制代码
作者: 寒冷魔王    时间: 2014-11-19 16:29
本帖最后由 寒冷魔王 于 2014-11-19 16:37 编辑
喵呜喵5 发表于 2014-11-19 14:51
每名学生的课程之前已经通过随机的方式选好了，

就是说，学生先通过抽签选好了自己总共要上的课程，之后 ...
  1. ts=[[5, 3, 7, 4, 0], [4, 8, 1, 9, 2], [0, 1, 7, 3, 6], [1, 0, 3, 4, 2], [8, 3, 2, 9, 0], [1, 7, 5, 4, 6], [2, 4, 5, 6, 7], [2, 0, 3, 1, 6], [2, 1, 0, 9, 3], [7, 6, 9, 0, 5], [9, 6, 1, 7, 4], [3, 9, 8, 1, 4], [6, 3, 8, 0, 4], [4, 2, 7, 5, 0], [2, 6, 4, 5, 3], [4, 8, 2, 3, 9], [1, 0, 5, 3, 6], [8, 4, 6, 1, 5], [3, 4, 8, 6, 1], [0, 4, 6, 2, 8], [6, 1, 0, 8, 2], [0, 9, 3, 4, 7], [1, 0, 2, 5, 3], [9, 1, 3, 8, 7], [1, 7, 9, 4, 3], [5, 8, 1, 2, 9], [2, 6, 0, 1, 7], [3, 2, 4, 1, 0], [2, 5, 1, 0, 8], [5, 3, 0, 7, 1], [3, 2, 5, 1, 8], [3, 7, 2, 8, 9], [5, 3, 0, 4, 1], [7, 0, 1, 9, 2], [7, 9, 2, 0, 3], [6, 4, 7, 0, 1], [8, 4, 6, 7, 9], [8, 5, 4, 3, 2], [4, 2, 8, 6, 1], [1, 5, 6, 2, 4], [0, 2, 4, 3, 5], [0, 8, 1, 2, 4], [4, 9, 3, 5, 0], [3, 0, 4, 8, 1], [0, 3, 4, 7, 5], [6, 7, 9, 2, 0], [9, 1, 2, 0, 3], [9, 2, 0, 3, 4], [7, 1, 9, 2, 8], [4, 5, 3, 6, 2]]

  3. def get(ts)
  4.   cl=Array.new(@weeks){Array.new(10){[]}}
  5.   ts.each_index{|is|ts[is].each_index{|w|cl[w][ts[is][w]].push is}}
  6.   return cl
  7. end
  8. p get(ts)
复制代码
数据结构
学生个人课表：@s  数组大小为学生人数，每个数组元素为单个人的课表。@s[*i]中元素为0..4周课程的编号。
课程上限：@m 数组大小为周数，元素为每周课程上限。
刚刚那个：ts是学生课表，cl是课程人类。cl数组大小为周数（这和课程上限相同），cl[*i]为某周的课程情况，包含该周上该课的学生编号。

说明一下，先前那个学生课表数据已经排好了各个周的上课情况，只要读取出来就行了。
作者: 喵呜喵5    时间: 2014-11-19 16:40
寒冷魔王 发表于 2014-11-19 16:29
数据结构
学生个人课表：@s  数组大小为学生人数，每个数组元素为单个人的课表。@s[*i]中元素为0..4周课程 ...


使用五楼的测试数据得出的结果是错误的

（五楼测试数据中，ts的值并没有按周次排序，而仅仅只是按大小排序）
作者: taroxd    时间: 2014-11-19 17:57
本帖最后由 taroxd 于 2014-11-20 12:30 编辑

首先声明，我没学过算法，也没参加过信息竞赛，所以别抱太大指望。
这段代码是自修课上写的，无环境测试，所以就当提供一个(效率极差的)思路吧。

这种题拿深度优先来枚举，感觉算到世界末日也算不完……只能希望碰巧遇到一个正解了吧……

代码最后忘了写了，请加上
try_from 0
p $stack

另外 success? 方法只要预先建立好索引，显然是不需要这么多循环的。反正不是真写代码只是提供思路，知道什么意思就好了(不就是写不下+懒得擦掉重写了嘛pia)

还有，ruby 真的不适合做这种问题。建议还是拿 C++ 来实现吧。

另外手写代码真是醉了……

顺便再求个数据规模小点的例子，拿来测试用(虽然我工作日是不太会有时间的……)

IMG_20141119_185029.jpg (490.76 KB, 下载次数: 32)

IMG_20141119_185029.jpg
作者: 寒冷魔王    时间: 2014-11-19 22:37
本帖最后由 寒冷魔王 于 2014-11-19 22:40 编辑
taroxd 发表于 2014-11-19 17:57
首先声明，我没学过算法，也没参加过信息竞赛，所以别抱太大指望。
这段代码是自修课上写的，无环境测试， ...


我有两个个方法在理论上能解决问题，但是手机测试不出来(≧ω≦)

  2. loop do
  3. nnd = Array.new
  4. @data.each do |d|
  5.   nd = Array.new
  6.   5.times{
  7.   cd = d.clone
  8.   nd.push randa(cd)
  9.   }
  10.   nnd.push nd
  11. end
  12. break if collect(nnd)==@m
  13. end
复制代码
judge法：

  2. @s = Array.new(N){Array.new(5)}
  3. def init(data=@data)
  4.   dat = gets(data)
  5.   dat.each{|d|order(d)}
  6. # dat = divids(dat)
  7. # nda = copy(dat)
  8. # dat.clear
  9. # nda.each{|da|nd=[];da.each{|d| nd=rands(d)};dat.push nd}
  10.   return dat
  11. end
  12. def judge(dat)
  13.   s = copy(@s)
  14.   10.times do |ic|
  15.     @weeks.times do |w|
  16.       dat[ic][w].each do |i|
  17.         return if !s[i][w].nil?
  18.         s[i][w] = ic
  19.       end
  20.     end
  21.   end
  22.   return s
  23. end
  24. #然后loop do随机dat，judge
复制代码

目前我的一个想法是，用下面的函数

  2. def gets(dat)
  3.   cl = Array.new(10){[]}
  4.   dat.each_index{|i|
  5.   dat[i].each{|e|cl[e].push i}}
  6.   return cl
  7. end
复制代码

依次判断，并移动学生数据。不过貌似比SRPG的Map处理还要复杂≥﹏≤。。。
想要保证效率的算法真的好难ヽ(≧Д≦)ノ

另外你的做法（手写）跟我当年一样，，不过那时没有手机，，周末电脑时间也很少，所以就耽误了。。。
作者: RyanBern    时间: 2014-11-19 23:00
本帖最后由 RyanBern 于 2014-11-20 08:41 编辑

看到算法题于是前来回答作死。
其实我能说这个问题我看了半天才理解吗？其实昨天我就看过了，只是一直没看懂。

思考的痛苦过程：
努力通过数学方法寻找最优策略（失败）->考虑贪心法（失败）->考虑动态规划（递推式建立不能，放弃）->考虑穷举（DFS， BFS， 因心疼自己的爱机而放弃）
以上方法均失败，不得不动用大杀器解不出来题时的救命稻草——模拟退火算法。
有关模拟退火算法，我只能说是不得已而为之，如果非要找到一个解的话。虽然选取合适的参数，模拟退火算法可以以概率1给出解（注意是以概率1给出解，并不是一定给出解），但是如果它真的给不出来解，那么就多试几次吧（pia）。

在这里为了方便，假设所有的课程上限人数为5.

需要求解的无非就是所有学生的课表，它是一个50 * 5的Table。在总共的空间中有(5!) ^ 50 种状态（课表的排列），这个数已经很多了。如果穷举的话，复杂度为O(M! ^ N)
当然，这里面的状态有一大部分都不能满足题意，即在某一星期上同一节课的人已经超过了该门课限制人数。

在某个特定的课表排列下，设第i周第j节课的有效上课人数为r(i, j)，注意，在这个课表排列下，要上某节课的学生人数可能超过限制人数，那么此时r(i, j)=5（即认为多出来那部分学生因为人数过多而没上成课），显然，需要寻找的课表排列应该满足Σr(i ,j) = 50 * 5

定义总共上课人次E=Σr(i, j)

所以，可以设计模拟退火如下：
1.设定初始温度T，初始状态S。
2.计算当前E，如果E == 250，则直接结束算法
3.对S做简单变换，变为S'，并计算新的E'
4.如果E' > E则取新状态S = S'，否则，以概率exp((E'-E) / T)取新状态S'，以概率(1 - exp((E' - E) / T))保留原状态S
5.经过多次迭代，温度T按指数衰减。
6.当T小于终止温度时结束。

其中，对S的变换可取随机交换某个学生第i周和第j周的课程，这样计算新的E'变得很简单。

如果模拟退火算法结束时，输出的课程排列对于的E == 250，那么这个就是你要的排课方式；如果输出的E < 250，或者是模拟退火算法没有找到解，或者是给定的初值根本不存在这样的解（例如选第一门课的人数超过25，那么无论如何5周过后都不可能完成教学任务了）

最后附上代码如下（代码不是Ruby的）：
CSHARP 代码复制
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. namespace ConsoleApplication1
  7. {
  8.     // 问题参数（其实是个命名空间，C#规定namespace结构下不能有常量）
  9.     class Parameters
  10.     {
  11.         // 课程总数
  12.         public const int CourseNumber = 10;
  13.         // 学生总数
  14.         public const int StudentNumber = 50;
  15.         // 每个课程人数限制
  16.         public const int CourseLimit = 5;
  17.         // 持续的周数（这个也可以理解为学生选的课程数目）
  18.         public const int Weeks = 5;
  19.     }
  20.     class CourseMonitor
  21.     {
  22.         public int Energy;
  23.         public int[,] Data;
  24.         public int[,] Schedule;
  25.         public CourseMonitor()
  26.         {
  27.             this.Energy = 0;
  28.             this.Data = new int[Parameters.CourseNumber, Parameters.Weeks];
  29.             this.Schedule = null;
  30.         }
  31.         // 根据课程排列计算每门课每周理论上课人数（即假定没有人数限制）
  32.         public void Check()
  33.         {
  34.             if (this.Schedule == null) return;
  35.             for (int i = 0; i < this.Schedule.GetLength(0); i++)
  36.             {
  37.                 for (int j = 0; j < this.Schedule.GetLength(1); j++)
  38.                 {
  39.                     this.Data[Schedule[i, j], j] += 1;
  40.                 }
  41.             }
  42.             foreach (int n in this.Data) this.Energy += n > Parameters.CourseLimit ? Parameters.CourseLimit : n;
  43.         }
  44.     }
  45.     // 模拟退火参数，实际是对模拟退火算法的刻画
  46.     class SAParameters
  47.     {
  48.         // 起始温度
  49.         public const double StartTemp = 300;
  50.         // 在每个温度下的迭代次数
  51.         public const int Iterate = 500;
  52.         // 温度衰减比率
  53.         public const double DecreaseRatio = 0.85;
  54.         // 终止温度
  55.         public const double FinalTemp = 0.05;
  56.     }
  57.     class Program
  58.     {
  59.         static Random rnd = new Random();
  60.         static void Main(string[] args)
  61.         {
  62.             CourseMonitor monitor = new CourseMonitor();
  63.             monitor.Schedule = new int[Parameters.StudentNumber, Parameters.Weeks];
  64.             InitSchedule(monitor.Schedule);
  65.             monitor.Check();
  66.             double temp = SAParameters.StartTemp;
  67.             int newEnergy = 0, course1, course2;
  68.             int[] swapArr = new int[3];
  69.             bool terminate = false;
  70.             while (temp > SAParameters.FinalTemp && !terminate)
  71.             {
  72.                 for (int i = 0; i < SAParameters.Iterate; i++)
  73.                 {
  74.                     if (monitor.Energy == Parameters.StudentNumber * Parameters.Weeks)
  75.                     {
  76.                         terminate = true;
  77.                         break;
  78.                     }
  79.                     newEnergy = monitor.Energy;
  80.                     GenerateSwap(swapArr);
  81.                     course1 = monitor.Schedule[swapArr[0], swapArr[1]];
  82.                     course2 = monitor.Schedule[swapArr[0], swapArr[2]];
  83.                     if (monitor.Data[course1, swapArr[1]] <= Parameters.CourseLimit) newEnergy -= 1;
  84.                     if (monitor.Data[course2, swapArr[2]] <= Parameters.CourseLimit) newEnergy -= 1;
  85.                     if (monitor.Data[course1, swapArr[2]] < Parameters.CourseLimit) newEnergy += 1;
  86.                     if (monitor.Data[course2, swapArr[1]] < Parameters.CourseLimit) newEnergy += 1;
  87.                     if (newEnergy > monitor.Energy || rnd.NextDouble() < Math.Exp((newEnergy - monitor.Energy) / temp))
  88.                     {
  89.                         monitor.Energy = newEnergy;
  90.                         monitor.Data[course1, swapArr[1]] -= 1;
  91.                         monitor.Data[course2, swapArr[2]] -= 1;
  92.                         monitor.Data[course1, swapArr[2]] += 1;
  93.                         monitor.Data[course2, swapArr[1]] += 1;
  94.                         Swap(monitor.Schedule, swapArr);
  95.                     }
  96.                 }
  97.                 temp *= SAParameters.DecreaseRatio;
  98.             }
  99.             Print(monitor.Schedule);
  100.         }
  101.         // 随机初始化
  102.         static void InitSchedule(int[,] schedule)
  103.         {
  104.             int r;
  105.             int[] dummy = new int[Parameters.Weeks];
  106.             for (int i = 0; i < Parameters.StudentNumber; i++)
  107.             {
  108.                 for (int k = 0; k < dummy.Length; k++) dummy[k] = -1;
  109.                 for (int j = 0; j < Parameters.Weeks; j++)
  110.                 {
  111.                     while (true)
  112.                     {
  113.                         r = rnd.Next(Parameters.CourseNumber);
  114.                         if (dummy.All<int>(a => a != r))
  115.                         {
  116.                             dummy[j] = r;
  117.                             break;
  118.                         }
  119.                     }
  120.                 }
  121.                 for (int k = 0; k < dummy.Length; k++) schedule[i, k] = dummy[k];
  122.             }
  123.         }
  124.         // 产生简单变换
  125.         static void GenerateSwap(int[] result)
  126.         {
  127.             result[0] = rnd.Next(Parameters.StudentNumber);
  128.             result[1] = rnd.Next(Parameters.Weeks);
  129.             while (result[1] == (result[2] = rnd.Next(Parameters.Weeks))) ;
  130.         }
  131.         // 根据变换对课程排列进行交换
  132.         static void Swap(int[,] data, int[] swapArr)
  133.         {
  134.             int temp = data[swapArr[0], swapArr[1]];
  135.             data[swapArr[0], swapArr[1]] = data[swapArr[0], swapArr[2]];
  136.             data[swapArr[0], swapArr[2]] = temp;
  137.         }
  138.         static void Print(int[,] data)
  139.         {
  140.             for (int i = 0; i < data.GetLength(0); i++)
  141.             {
  142.                 for (int j = 0; j < data.GetLength(1); j++)
  143.                 {
  144.                     System.Console.Write("" + data[i, j] + '\t');
  145.                 }
  146.                 System.Console.Write('\n');
  147.             }
  148.         }
  149.     }
  150. }







欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1