paike.cs

这是一个机房排课系统

using System;
using System.Collections.Generic;
using System.Text;
using System.Xml;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
using System.Windows;
using System.Threading;
using System.Windows.Forms;
namespace WinPaike
{
    public class CoursePriority
    {
        public static int[] Priority = new int[ClassUnit.CourseCount] { 5, 5, 4, 4, 2, 1 };
    }
    public class PaiKe
    {
        int cc = 0;//当前要变异的班级序号
        const int MaxCourseWay = 10;
        List<string> ResolveList = new List<string>(); //保存最后结果
        int[] next;
        #region 线程操作所用
        public TextBox TxtBox;
        public Form Frm;
        public bool IsChongTu = true;
        public ToolStripProgressBar Bar;
        delegate  void SetNumber(int value, ToolStripProgressBar bar);
        delegate   void SetText(string text, Control txtbox);       
        SetText addtext ;//= new SetText(AddControlText);
        SetText settext ;//= new SetText(SetControlText);
        SetNumber setnumber;// = new SetNumber(SetControlNumber);
        SetNumber setmaxvalue ;//= new SetNumber(SetMaxValue);
        void AddControlText(string text, Control txtbox)
        {
            txtbox.Text += text;

        }
        void SetControlText(string text, Control txtbox)
        {
            txtbox.Text = text;

        }
        void SetControlNumber(int value, ToolStripProgressBar bar)
        {
            bar.Value = value;
        }
        void SetMaxValue(int value, ToolStripProgressBar bar)
        {
            bar.Maximum = value;
        }
        #endregion
        Random rnd = new Random();
        ClassUnit tClassUnit;
        List<ClassUnit> ClassList = new List<ClassUnit>();
        List<Course> CourseList = new List<Course>();
        //－－－－－－－－－－－－－－－惩罚值列表－－－－－－－－－－－－－－
        //冲突
        const int ChongTu = 200;
        //一天有2节相同的课
        const int OneDayForTowCourse = 150;
        //连续2天有2节相同课
        const int TowDayForTowCourse = 40;
        //课程优先级单位值
        const int CoursePr = 15;
        public PaiKe()
        {
             addtext = new SetText(AddControlText);
             settext = new SetText(SetControlText);
             setnumber = new SetNumber(SetControlNumber);
             setmaxvalue = new SetNumber(SetMaxValue);
        }
        //初始化
        void Init()
        {
            ResolveList.Clear();//结果清零             
            CourseList = CommonClass.GetCourseListFromDB("Course.dat");
            Course tcourse = new Course("自习", -1, "NO", 1);
            tcourse.ID = -1;
            CourseList.Add(tcourse);
            List<CourseInClass> courseinclasslist = new List<CourseInClass>();
            courseinclasslist = CommonClass.GetCourseInClassListFromDB("courseinclass.dat");
            ClassList = CommonClass.GetClassListFromDB("Class.dat");
            int[] txulie = new int[ClassList.Count];
            foreach (CourseInClass courseinclass in courseinclasslist)
            {
                for (int i = 0; i < courseinclass.Count; i++)
                {
                    int classid = courseinclass.ClassID - 1;
                    if (txulie[classid] < ClassUnit.CourseCount * ClassUnit.WeekDay)
                    {
                        ClassList[classid].XuLie[txulie[classid]++] = courseinclass.CourseID;
                    }
                }
            }
            //将未添满的课设置为自习课
            for (int i = 0; i < ClassList.Count; i++)
            {
                for (int j = txulie[i]; j < ClassUnit.CourseCount * ClassUnit.WeekDay; j++)
                {
                    ClassList[i].XuLie[j] = -1;
                }
            }
            //ClassList.RemoveAt(ClassList.Count-1);

            next = new int[ClassUnit.WeekDay * ClassUnit.CourseCount];
            Assign(next,ClassList[0].XuLie);
        }
         //得到单个班级的课程表
        string GetCourseTable(ClassUnit cu)
        {
            string re = "       ";
            for (int i = 0; i < ClassUnit.CourseCount; i++)
            {

                re += string.Format("第{0}节    ", i + 1);
            }
            re += string.Format("\r\n－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－\r\n");
            for (int i = 0; i < ClassUnit.WeekDay * ClassUnit.CourseCount; i++)
            {
                if ((i) % (ClassUnit.CourseCount) == 0)
                {
                    re += string.Format("周{0}:   ", i / ClassUnit.CourseCount + 1);
                }
                int tcourseid = cu.XuLie[i];
                if (tcourseid > 0)
                {
                    re += string.Format(CourseList[(cu.XuLie[i] - 1)].Name.ToString() + "     ");
                }
                else
                {
                    re += string.Format("自习" + "     "); 
                }
                if ((i + 1) % ClassUnit.CourseCount == 0)
                {
                    re += string.Format("\r\n");
                }
            }
            return re;
        }
        //得到所有班级的课程表
        string GetCourseTableList()
        {
            string re = "";
            for (int i = 0; i < ClassList.Count; i++)
            {
                re += string.Format("班级{0}:\r\n", ClassList[i].Name);
                re += GetCourseTable(ClassList[i]);
            }
            return re;
        }
        //复制数组
        void Assign(int[] c, int[] n)
        {
            for (int i = 0; i < c.Length; i++)
                c[i] = n[i];
        }
        //产生下一组解（班级课表变异）
        void CreateNext(int[] c, int[] n)
        {
            for (int i = 0; i < c.Length; i++)
                n[i] = c[i];
            int i1 = (int)(rnd.Next(ClassUnit.WeekDay * ClassUnit.CourseCount));
            int i2 = (int)(rnd.Next(ClassUnit.WeekDay * ClassUnit.CourseCount));
            int aux = n[i1];
            n[i1] = n[i2];
            n[i2] = aux;
        }
        //计算单个班级的除冲突外的惩罚代价
        int ComputeClassValue(int[] cu)
        {
            int Sum = 0;
            for (int i = 0; i < ClassUnit.WeekDay; i++)
            {
                int row = i * ClassUnit.CourseCount;
                for (int j = row; j < row + ClassUnit.CourseCount; j++)
                {
                    //一天2节
                    for (int k = j + 1; k < row + ClassUnit.CourseCount; k++)
                    {
                        if (cu[j] == cu[k])
                        {
                            Sum += OneDayForTowCourse;
                        }
                    }
                    //2天2节
                    for (int k = (j / ClassUnit.CourseCount + 1) * ClassUnit.CourseCount; k < (j / ClassUnit.CourseCount + 1) * ClassUnit.CourseCount + ClassUnit.CourseCount && k < ClassUnit.WeekDay * ClassUnit.CourseCount; k++)
                    {
                        if (cu[j] == cu[k] && j != k)
                        {
                            Sum += TowDayForTowCourse;
                        }
                    }
                    //4天2节
                    for (int k = (j / ClassUnit.CourseCount + 3) * ClassUnit.CourseCount; k < (j / ClassUnit.CourseCount + 3) * ClassUnit.CourseCount + ClassUnit.CourseCount && k < ClassUnit.WeekDay * ClassUnit.CourseCount; k++)
                    {
                        if (cu[j] == cu[k] && k != j)
                        {
                            Sum += TowDayForTowCourse;
                        }
                    }
                    int t1 = CoursePriority.Priority[j % ClassUnit.CourseCount];
                    if (cu[j] > 0)
                    {
                        int t2 = CourseList[cu[j] - 1].Priority;
                        if (t1 < t2)
                        {
                            Sum += CoursePr * (t2 - t1);// * (Math.Max((j % 4 + 1 - cu[j]), 0));
                        }
                    }

                }

            }
            return Sum;
        }
        //计算总的排课方案代价
        int ComputeValue()
        {
            int value;
            value = ComputeClassValue(next);
            for (int i = 0; i < ClassList.Count; i++)
            {
                if (i == cc) { continue; }
                value += ComputeClassValue(ClassList[i].XuLie); ;
            }
            value += ComputeConflictValue();
            return value;
        }
        //输出可行的排课方案
        string GetResolve()
        {
            string txt = "";
            txt += GetCourseTableList();
            return txt;

        }
        //计算冲突所产生的惩罚代价
        int ComputeConflictValue()
        {
            int Sum = 0;
            int t1, t2;
            int tcourseid1, tcourseid2;
            for (int i = 0; i < ClassUnit.WeekDay * ClassUnit.CourseCount; i++)
            {
                for (int j = 0; j < ClassList.Count; j++)
                {                    
                    if (j == cc)
                    {
                        tcourseid1 = next[i];
                    }
                    else
                    {
                        tcourseid1 = ClassList[j].XuLie[i];
                    }
                    if (tcourseid1==-1)
                    {
                        continue;
                    }                    
                    t1 = CourseList[tcourseid1-1].TeacherID;
                    for (int k = j + 1; k < ClassList.Count; k++)
                    {
                        if (k == cc)
                        {
                            tcourseid2 = next[i];
                        }
                        else
                        {
                            tcourseid2 = ClassList[k].XuLie[i];
                        }
                        if (tcourseid2 == -1)
                        {
                            continue;
                        }
                        t2 = CourseList[tcourseid2 - 1].TeacherID;
                        //int t1 = CourseList[ClassList[j].XuLie[i] - 1].TeacherID;
                        //int t2 = CourseList[ClassList[k].XuLie[i] - 1].TeacherID;
                        //if (j == cc) { t1 = CourseList[next[i] - 1].TeacherID; }
                        //if (k == cc) { t2 = CourseList[next[i] - 1].TeacherID; }
                        if (t1 == t2)
                        {
                            Sum += ChongTu;
                        }                       
                    }
                }
            }            
            if (Sum == 0)
            {
                IsChongTu = false;
            }
            else
            {
                IsChongTu = true;
            }
            return Sum;
        }
        //计算结束,输出排课方案
        void Finished()
        {
            SetText add = new SetText(AddControlText);
            if (ResolveList.Count == 0)
            {
                MessageBox.Show("对不起，没有找到可行解，请重新尝试！");
            }
            else
            {
                MessageBox.Show("成功完成！");
            }
            int ct = 0;
            foreach (string ss in ResolveList)
            {
                ct++;
                TxtBox.Invoke(add, new object[2] { string.Format("方案{0}\r\n", ct), TxtBox });
                TxtBox.Invoke(add, new object[2] { ss, TxtBox });
            }
        }
        //主函数，开始排课
        public void Run()
        {
            int iteration = -1;//迭代次数            
            double proba;//产生的0～1间的随机数
            double alpha = 0.999;//降温速率
            double temperature = 4000.0 + (100 * ClassList.Count) * (100 * ClassList.Count);//温度
            double temperature_copy = temperature;//温度副本
            double epsilon = 0.002;//终止温度
            double delta;//
            int i;
            double Value = 0;//当前代价
            #region 待优化(思想：将每个班的惩罚代价进行比较，然后尽量选取代价大的进行变异)
            /*            
            double[] XuanZhongGaiLv = new double[ClassList.Count];//每个班级的变异概率，总和＝1             
            for (i = 0; i < XuanZhongGaiLv.Length; i++)
            {
                XuanZhongGaiLv[i] = 1 / XuanZhongGaiLv.Length;
            }
            */
            #endregion
            //初始化班级，课程等信息            
            Init();
            Value = ComputeValue();
            Value += (Value + 20000); 
            int battc = 0;
            TxtBox.Invoke(setmaxvalue, new object[2] {(int)(temperature), Bar });
            //while the temperature didnt reach epsilon
            while (temperature > epsilon)
            {
                battc++;
                if (battc > 100)
                {
                    //Thread.Sleep(100);
                    TxtBox.Invoke(setnumber, new object[2] { (int)(temperature_copy-temperature), Bar });
                    battc = 0;
                }
                iteration++;
                cc = cc % ClassList.Count;
                //cc = rnd.Next(ClassList.Count);
                CreateNext(ClassList[cc].XuLie, next);
                delta = ComputeValue() - Value;
                if (delta == 0 && ResolveList.Count <MaxCourseWay && !IsChongTu)
                {
                    ResolveList.Add(GetResolve());
                }
                #region 如果新生成的解更优，则替换以前的，否则以接受概率接受新解
                //如果新生成的解更优，则替换以前的
                if (delta < 0)
                {
                    Assign(ClassList[cc].XuLie, next);
                    Value = delta + Value;
                    if (!IsChongTu)
                    {
                        ResolveList.Clear();
                        //输出代价
                        TxtBox.Invoke(settext, new object[2] { "自动排课" + "------当前最优值:(" + Value.ToString() + ")", Frm });
                        ResolveList.Add(GetResolve());
                    }
                }
                else
                {
                    proba = rnd.Next();
                    if (proba < Math.Exp(-delta / temperature))
                    {
                        Assign(ClassList[cc].XuLie, next);
                        Value = delta + Value;
                    }
                }
                #endregion
                //降温
                temperature *= alpha;
                cc++;

            }
            Finished();
        }
    }
}