求教一个关于算法的问题

喵呜喵5

有n名学生各自选择了十门课中的五门
每门课都只有一节，在五周里每周都有开课
，
每周上课的人数固定，十门课程的上课人数总和等于学生个数

现在每名学生都选好了课程，同时每门课的学生总数等于这门课每周的学生上限*5
求一个安排方法使每一个学生每周都能听到一节课且只听这节课

寒冷魔王

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-18 23:45

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

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

50名学生在这五周中都上了五节不同的课
每门课的人数都刚刚好，不会出现超过的情况
学生上的课的安排是随机的

寒冷魔王

喵呜喵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
    
15. 
    
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 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,]]

复制代码

寒冷魔王

喵呜喵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]]
   
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:29
数据结构
学生个人课表：@s  数组大小为学生人数，每个数组元素为单个人的课表。@s[*i]中元素为0..4周课程 ...

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

（五楼测试数据中，ts的值并没有按周次排序，而仅仅只是按大小排序）

taroxd

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

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

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

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

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

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

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

寒冷魔王

taroxd 发表于 2014-11-19 17:57
首先声明，我没学过算法，也没参加过信息竞赛，所以别抱太大指望。
这段代码是自修课上写的，无环境测试， ...

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

1. 
   
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法：

1. 
   
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

复制代码

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

1. 
   
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

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

思考的痛苦过程：
努力通过数学方法寻找最优策略（失败）->考虑贪心法（失败）->考虑动态规划（递推式建立不能，放弃）->考虑穷举（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 代码复制

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
    // 问题参数（其实是个命名空间，C#规定namespace结构下不能有常量）
    class Parameters
    {
        // 课程总数
        public const int CourseNumber = 10;
        // 学生总数
        public const int StudentNumber = 50;
        // 每个课程人数限制
        public const int CourseLimit = 5;
        // 持续的周数（这个也可以理解为学生选的课程数目）
        public const int Weeks = 5;
    }
    class CourseMonitor
    {
        public int Energy;
        public int[,] Data;
        public int[,] Schedule;
        public CourseMonitor()
        {
            this.Energy = 0;
            this.Data = new int[Parameters.CourseNumber, Parameters.Weeks];
            this.Schedule = null;
        }
        // 根据课程排列计算每门课每周理论上课人数（即假定没有人数限制）
        public void Check()
        {
            if (this.Schedule == null) return;
            for (int i = 0; i < this.Schedule.GetLength(0); i++)
            {
                for (int j = 0; j < this.Schedule.GetLength(1); j++)
                {
                    this.Data[Schedule[i, j], j] += 1;
                }
            }
            foreach (int n in this.Data) this.Energy += n > Parameters.CourseLimit ? Parameters.CourseLimit : n;
        }
    }
    // 模拟退火参数，实际是对模拟退火算法的刻画
    class SAParameters
    {
        // 起始温度
        public const double StartTemp = 300;
        // 在每个温度下的迭代次数
        public const int Iterate = 500;
        // 温度衰减比率
        public const double DecreaseRatio = 0.85;
        // 终止温度
        public const double FinalTemp = 0.05;
    }
    class Program
    {
        static Random rnd = new Random();
        static void Main(string[] args)
        {
            CourseMonitor monitor = new CourseMonitor();
            monitor.Schedule = new int[Parameters.StudentNumber, Parameters.Weeks];
            InitSchedule(monitor.Schedule);
            monitor.Check();
            double temp = SAParameters.StartTemp;
            int newEnergy = 0, course1, course2;
            int[] swapArr = new int[3];
            bool terminate = false;
            while (temp > SAParameters.FinalTemp && !terminate)
            {
                for (int i = 0; i < SAParameters.Iterate; i++)
                {
                    if (monitor.Energy == Parameters.StudentNumber * Parameters.Weeks)
                    {
                        terminate = true;
                        break;
                    }
                    newEnergy = monitor.Energy;
                    GenerateSwap(swapArr);
                    course1 = monitor.Schedule[swapArr[0], swapArr[1]];
                    course2 = monitor.Schedule[swapArr[0], swapArr[2]];
                    if (monitor.Data[course1, swapArr[1]] <= Parameters.CourseLimit) newEnergy -= 1;
                    if (monitor.Data[course2, swapArr[2]] <= Parameters.CourseLimit) newEnergy -= 1;
                    if (monitor.Data[course1, swapArr[2]] < Parameters.CourseLimit) newEnergy += 1;
                    if (monitor.Data[course2, swapArr[1]] < Parameters.CourseLimit) newEnergy += 1;
                    if (newEnergy > monitor.Energy || rnd.NextDouble() < Math.Exp((newEnergy - monitor.Energy) / temp))
                    {
                        monitor.Energy = newEnergy;
                        monitor.Data[course1, swapArr[1]] -= 1;
                        monitor.Data[course2, swapArr[2]] -= 1;
                        monitor.Data[course1, swapArr[2]] += 1;
                        monitor.Data[course2, swapArr[1]] += 1;
                        Swap(monitor.Schedule, swapArr);
                    }
                }
                temp *= SAParameters.DecreaseRatio;
            }
            Print(monitor.Schedule);
        }
        // 随机初始化
        static void InitSchedule(int[,] schedule)
        {
            int r;
            int[] dummy = new int[Parameters.Weeks];
            for (int i = 0; i < Parameters.StudentNumber; i++)
            {
                for (int k = 0; k < dummy.Length; k++) dummy[k] = -1;
                for (int j = 0; j < Parameters.Weeks; j++)
                {
                    while (true)
                    {
                        r = rnd.Next(Parameters.CourseNumber);
                        if (dummy.All<int>(a => a != r))
                        {
                            dummy[j] = r;
                            break;
                        }
                    }
                }
                for (int k = 0; k < dummy.Length; k++) schedule[i, k] = dummy[k];
            }
        }
        // 产生简单变换
        static void GenerateSwap(int[] result)
        {
            result[0] = rnd.Next(Parameters.StudentNumber);
            result[1] = rnd.Next(Parameters.Weeks);
            while (result[1] == (result[2] = rnd.Next(Parameters.Weeks))) ;
        }
        // 根据变换对课程排列进行交换
        static void Swap(int[,] data, int[] swapArr)
        {
            int temp = data[swapArr[0], swapArr[1]];
            data[swapArr[0], swapArr[1]] = data[swapArr[0], swapArr[2]];
            data[swapArr[0], swapArr[2]] = temp;
        }
        static void Print(int[,] data)
        {
            for (int i = 0; i < data.GetLength(0); i++)
            {
                for (int j = 0; j < data.GetLength(1); j++)
                {
                    System.Console.Write("" + data[i, j] + '\t');
                }
                System.Console.Write('\n');
            }
        }
    }
}

using System;


using System.Collections.Generic;


using System.Linq;


using System.Text;


using System.Threading.Tasks;


namespace ConsoleApplication1


{


    // 问题参数（其实是个命名空间，C#规定namespace结构下不能有常量）


    class Parameters


    {


        // 课程总数


        public const int CourseNumber = 10;


        // 学生总数


        public const int StudentNumber = 50;


        // 每个课程人数限制


        public const int CourseLimit = 5;


        // 持续的周数（这个也可以理解为学生选的课程数目）


        public const int Weeks = 5;


    }


    class CourseMonitor


    {


        public int Energy;


        public int[,] Data;


        public int[,] Schedule;


        public CourseMonitor()


        {


            this.Energy = 0;


            this.Data = new int[Parameters.CourseNumber, Parameters.Weeks];


            this.Schedule = null;


        }


        // 根据课程排列计算每门课每周理论上课人数（即假定没有人数限制）


        public void Check()


        {


            if (this.Schedule == null) return;


            for (int i = 0; i < this.Schedule.GetLength(0); i++)


            {


                for (int j = 0; j < this.Schedule.GetLength(1); j++)


                {


                    this.Data[Schedule[i, j], j] += 1;


                }


            }


            foreach (int n in this.Data) this.Energy += n > Parameters.CourseLimit ? Parameters.CourseLimit : n;


        }


    }


    // 模拟退火参数，实际是对模拟退火算法的刻画


    class SAParameters


    {


        // 起始温度


        public const double StartTemp = 300;


        // 在每个温度下的迭代次数


        public const int Iterate = 500;


        // 温度衰减比率


        public const double DecreaseRatio = 0.85;


        // 终止温度


        public const double FinalTemp = 0.05;


    }


    class Program


    {


        static Random rnd = new Random();


        static void Main(string[] args)


        {


            CourseMonitor monitor = new CourseMonitor();


            monitor.Schedule = new int[Parameters.StudentNumber, Parameters.Weeks];


            InitSchedule(monitor.Schedule);


            monitor.Check();


            double temp = SAParameters.StartTemp;


            int newEnergy = 0, course1, course2;


            int[] swapArr = new int[3];


            bool terminate = false;


            while (temp > SAParameters.FinalTemp && !terminate)


            {


                for (int i = 0; i < SAParameters.Iterate; i++)


                {


                    if (monitor.Energy == Parameters.StudentNumber * Parameters.Weeks)


                    {


                        terminate = true;


                        break;


                    }


                    newEnergy = monitor.Energy;


                    GenerateSwap(swapArr);


                    course1 = monitor.Schedule[swapArr[0], swapArr[1]];


                    course2 = monitor.Schedule[swapArr[0], swapArr[2]];


                    if (monitor.Data[course1, swapArr[1]] <= Parameters.CourseLimit) newEnergy -= 1;


                    if (monitor.Data[course2, swapArr[2]] <= Parameters.CourseLimit) newEnergy -= 1;


                    if (monitor.Data[course1, swapArr[2]] < Parameters.CourseLimit) newEnergy += 1;


                    if (monitor.Data[course2, swapArr[1]] < Parameters.CourseLimit) newEnergy += 1;


                    if (newEnergy > monitor.Energy || rnd.NextDouble() < Math.Exp((newEnergy - monitor.Energy) / temp))


                    {


                        monitor.Energy = newEnergy;


                        monitor.Data[course1, swapArr[1]] -= 1;


                        monitor.Data[course2, swapArr[2]] -= 1;


                        monitor.Data[course1, swapArr[2]] += 1;


                        monitor.Data[course2, swapArr[1]] += 1;


                        Swap(monitor.Schedule, swapArr);


                    }


                }


                temp *= SAParameters.DecreaseRatio;


            }


            Print(monitor.Schedule);


        }


        // 随机初始化


        static void InitSchedule(int[,] schedule)


        {


            int r;


            int[] dummy = new int[Parameters.Weeks];


            for (int i = 0; i < Parameters.StudentNumber; i++)


            {


                for (int k = 0; k < dummy.Length; k++) dummy[k] = -1;


                for (int j = 0; j < Parameters.Weeks; j++)


                {


                    while (true)


                    {


                        r = rnd.Next(Parameters.CourseNumber);


                        if (dummy.All<int>(a => a != r))


                        {


                            dummy[j] = r;


                            break;


                        }


                    }


                }


                for (int k = 0; k < dummy.Length; k++) schedule[i, k] = dummy[k];


            }


        }


        // 产生简单变换


        static void GenerateSwap(int[] result)


        {


            result[0] = rnd.Next(Parameters.StudentNumber);


            result[1] = rnd.Next(Parameters.Weeks);


            while (result[1] == (result[2] = rnd.Next(Parameters.Weeks))) ;


        }


        // 根据变换对课程排列进行交换


        static void Swap(int[,] data, int[] swapArr)


        {


            int temp = data[swapArr[0], swapArr[1]];


            data[swapArr[0], swapArr[1]] = data[swapArr[0], swapArr[2]];


            data[swapArr[0], swapArr[2]] = temp;


        }


        static void Print(int[,] data)


        {


            for (int i = 0; i < data.GetLength(0); i++)


            {


                for (int j = 0; j < data.GetLength(1); j++)


                {


                    System.Console.Write("" + data[i, j] + '\t');


                }


                System.Console.Write('\n');


            }


        }


    }


}