Фрагмент для ознакомления
яз.", "1", "инд.пр", "1", "астрономия", "1" },newstring[] { "матем", "5", "русск", "2", "литер", "3", "ф-ра", "3", "англ", "3", "история", "2", "физика", "3", "химия", "2", "геогр", "1", "биол", "2", "общест", "1", "ИВТ", "1", "ОБЖ", "1", "род.яз.", "1", "инд.пр", "1", "МХК", "1" }};private string[][] Synonims = new string[][] { // Таблицасинонимовnew string[] { "МХК", "ИЗО" },new string[] { "ОПК", "ОРКСЭ", "ОДНК" }};privatestring[][] DeniedAfter = newstring[][] { // Запреты некоторых предметов после указанного первымnewstring[] { "ф-ра", "русск", "матем" } };privatestring[] DeniedFirst = newstring[] { "русск", "матем" }; // Предметы, запрещенные первымиprivatestring[] DeniedLast = newstring[] { "русск", "матем" }; // Предметы, запрещенные последнимиprivatestring[] DeniedSimult_1to4_5to11 = newstring[] { "англ", "ф-ра" }; // Предметы, по которым запрещены совпадения между 1_4 и 5_11 классамиprivate Random rnd = new Random();privatebool stopped = false; // Флагпрерываниярасчетаprivate Dictionary Cache = new Dictionary();publicintAntiQuality(string[] variant) { // Вычислениенекачественностиintresult = 0; // Здесь будет результатinthash = 0;intnn = 0;foreach (string s in variant) {if (s == "") {hash ^= ((int)'|') << (nn % 24);nn++; }elseforeach (char c in s) {hash ^= ((int)c) << (nn % 24);nn++; } }if (Cache.ContainsKey(hash))return Cache[hash];// Проверяем первый урок в понедельник для всех классовfor (int c = 0; c < nClasses; c++){if (variant[c] != "") // Он должен быть свободным, потом заменим его на AlwaysFirstOnMondayresult++; }for (inti = 0; i < Days; i++) { // Циклподнямintj = i == 0 ? 1 : 0; // Индекс первого "настраиваемого" урока для данного дня // Проверяем наличие "дыр" и начало с первого урока в расписании каждого класса // Проверяем первый и последний уроки и сочетания уроковfor (int c = 0; c < nClasses; c++) {int first = i * MaxPerDay * nClasses + c;int k1 = j;while (k1 < MaxPerDay-1 && variant[first + nClasses*k1] == "") {result++;k1++; }int k2 = MaxPerDay-1;while (k2 >= k1 && variant[first + nClasses * k2] == "") {k2--; } // Проверяемпервыйурокif (k1 >= 0 && k1 < MaxPerDay)foreach (string s in DeniedFirst)if (variant[first + nClasses * k1] == s)result++; // Проверяемпоследнийурокif (k2 >= 0 && k2 >= k1 && k2 < MaxPerDay)foreach (string s in DeniedLast)if (variant[first + nClasses * k2] == s)result++; // Проверяем "дыры" // Проверяем число уроковintntot = 0;for (int k = k1; k <= k2; k++)if (variant[first + nClasses * k] == "")result += 3;elsentot++;if (ntot < 2) result += 2 - ntot;// Проверяем отсутствие одинаковых предметов в один деньHashSet D = new HashSet();for (int k = k1; k <= k2; k++)if (variant[first + nClasses * k] != "")if (D.Contains(variant[first + nClasses * k]))result++;elseD.Add(variant[first + nClasses * k]);// Проверяем запрещенные сочетанияfor (intk = k1 + 1; k <= k2; k++){foreach (string[] st in DeniedAfter)if (variant[first + nClasses * (k - 1)] == st[0])for (int p = 1; p < st.Length; p++)if (variant[first + nClasses * k] == st[p])result++; } }/**/ // Проверяем наличие дополнительной перемены для 1 класса в положенное времяif (variant[i * MaxPerDay * nClasses + (nAdditionalForClass1 - 1) * nClasses] != AdditionalForClass1)result++; // Совпадения 1_4 и 5_11foreach (string s in DeniedSimult_1to4_5to11) {for (intjj = j; jj < MaxPerDay; jj++) {int similar = 0;int first = i * MaxPerDay * nClasses + jj * nClasses;for (intc = 0; c < 4; c++){ // Проверяем совпаденияif (variant[first + c] == s)similar++; }if (similar > 1) result += similar;similar = 0;for (int c = 4; c < nClasses; c++){ // Проверяемсовпаденияif (variant[first + c] == s)similar++; }if (similar > 1) result += similar; } } // Совпадения 5_11for (intjj = j; jj < MaxPerDay; jj++) {HashSet D = new HashSet();int first = i * MaxPerDay * nClasses + jj * nClasses;for (int c = 4; c < nClasses; c++){ // Проверяемсовпаденияif (variant[first + c] != "") {if (D.Contains(variant[first + c]))result++;else{ // Синонимыforeach (string[] st in Synonims) {foreach (string s in st)if (variant[first + c] == s) {foreach (string s1 in st)if (D.Contains(s1))result++;break; } }D.Add(variant[first + c]); } } } }/**/ }Cache.Add(hash, result);return result;} // Создание случайного варианта расписанияpublicstring[] CreateVariant() {string[] result = new string[Days*MaxPerDay*nClasses];for (inti = 0; i < result.Length; i++)result[i] = "";for (int c = 0; c < nClasses; c++) { Dictionary D = new Dictionary();int n = 0;for (int k = 0; k < Lessons[c].Length; k += 2) {D.Add(Lessons[c][k], int.Parse(Lessons[c][k + 1])); n += int.Parse(Lessons[c][k + 1]); }for (int p = 1; p <= n; p++) {KeyValuePair K = D.ElementAt(rnd.Next(0, D.Count));intidx = (p % Days) * MaxPerDay * nClasses + (p / Days) * nClasses + c;result[idx] = K.Key;D[K.Key]--;if (D[K.Key] == 0) D.Remove(K.Key);} }returnresult; } // Скрещивание двух расписаний (по типу многоточечного кроссинговера по какому либо классу)public void CrossingOver(string[] parent1, string[] parent2, out string[] child1, out string[] child2) { child1 = new string[parent1.Length]; child2 = new string[parent1.Length];for (int p = 0; p < parent1.Length; p++) {child1[p] = parent1[p];child2[p] = parent2[p]; }intnn = rnd.Next(1, 4);for (int q = 0; q < nn; q++) {int k = 1 + rnd.Next(0, MaxPerDay * Days - 1);int c = rnd.Next(0, nClasses);for (int p = 1; p < MaxPerDay * Days; p++) {if (child2[p] == child1[k]) {stringbuf = child1[c + p * nClasses]; child1[c + p * nClasses] = child1[c + k * nClasses]; child1[c + k * nClasses] = buf;break; } }for (int p = 1; p < MaxPerDay * Days; p++) {if (child1[p] == child2[k]) {stringbuf = child2[c + p * nClasses]; child2[c + p * nClasses] = child2[c + k * nClasses]; child2[c + k * nClasses] = buf;break; } } } } // Мутация (перестановка по каким-либо классам)public string[] Mutate(string[] variant) {string[] result = new string[variant.Length];for (int p = 0; p < variant.Length; p++) {result[p] = variant[p]; }intnn = rnd.Next(1, 4);for (inti = 0; i < nn; i++) {int c = rnd.Next(0, nClasses);int day1 = rnd.Next(0, Days);int day2 = rnd.Next(0, Days);int k1 = rnd.Next(1, MaxPerDay);int k2 = rnd.Next(1, MaxPerDay);for (; k1 < MaxPerDay && k2 < MaxPerDay; k1++, k2++) {stringbuf = result[c + day1 * MaxPerDay * nClasses + k1 * nClasses];result[c + day1 * MaxPerDay * nClasses + k1 * nClasses] = result[c + day2 * MaxPerDay * nClasses + k2 * nClasses];result[c + day2 * MaxPerDay * nClasses + k2 * nClasses] = buf;} }returnresult; } // Сортируем популяцию по возрастанию Антикачестваpublic void Sort(List Population) { // Сортировкаfor (inti = 0; i < Population.Count; i++)AntiQuality(Population[i]);Population.Sort((x, y) => AntiQuality(x).CompareTo(AntiQuality(y))); }public Form1() {InitializeComponent(); } // Обработканажатиянакнопкурешенияprivate void btSolve_Click(object sender, EventArgs e) { List Population = new List(); // Популяцияif (btSolve.Text != "Решение") {stopped = true;btSolve.Text = "Решение"; }else {btSolve.Text = "Прервать";stopped = false;Cache.Clear();nInits = Decimal.ToInt16(edPopulSize.Value);lbSolution.BackColor = Color.Aqua; // Создаемпервичнуюпопуляциюfor (inti = 0; i < nInits; i++){Population.Add(CreateVariant()); } // Сортируем по возрастанию антикачестваSort(Population);string[] Best = null; // ЛучшийвариантintBestQ = 10000; // Антикачестволучшеговариантаfor (inti = 0; i < nEpochs && BestQ > 0 && !stopped; i++){ // Циклэтаповэволюции List NewPopulation = new List(); // Новаяпопуляция// Первая четверть лучших хромосом переходит в новую популяцию (первая четверть).for (int j = 0; j < nInits / 4; j++)NewPopulation.Add(Population[j]); // Первая 0..1/8 лучших хромосом скрещивается с прочими и дает потомство (1/4).for (int j = 0; j < nInits / 8; j++) {string[] child1;string[] child2;CrossingOver(Population[j], Population[rnd.Next(0, Population.Count/4)], out child1, out child2);NewPopulation.Add(child1);NewPopulation.Add(child2);} // Первая четверть лучших хромосом мутирует и переходят в новую популяцию (четвертаячетверть)for (int j = 0; j < 3*nInits / 8; j++)NewPopulation.Add(Mutate(Population[j])); // Добавляем 1/8 новыхпредставителейfor (int j = NewPopulation.Count; j < Population.Count; j++)NewPopulation.Add(CreateVariant()); // Новаяпопуляциястановитсятекущей Population = NewPopulation; // Сортируем по возрастанию антикачестваSort(Population); // Проверяемлучшийвариантint Q = AntiQuality(Population.First());if (Q < BestQ) {BestQ = Q; Best = Population.First();lbQuality.Text = "Показательантикачества: " + BestQ.ToString("F3");lbSolution.Items.Clear();lbSolution.Items.Add("| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |");int q = 0;for (int d = 0; d < Days; d++) {for (int j = 0; j < MaxPerDay; j++) {string line = "";for (int c = 0; c < nClasses; c++) {string s = "|";if (q < nClasses) s += "разг.оваж.";else s += Best[q];if (s.Length < 12) s += new string(' ', 12 - s.Length);line += s;q++; }lbSolution.Items.Add(line + "|"); }lbSolution.Items.Add("+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+"); }Application.DoEvents(); } }if (BestQ == 0) {lbSolution.BackColor = Color.Gold; }stopped = true;btSolve.Text = "Решение";} } // Вызывается при нажатии на кнопку сохранения результатовprivate void btSave_Click(object sender, EventArgs e) {if (saveFileDialog.ShowDialog() == DialogResult.OK) {StreamWriter writer = new StreamWriter(saveFileDialog.FileName, false);foreach (String s in lbSolution.Items) // Циклсохранениястрокwriter.WriteLine(s);writer.Close(); } } }}
