Послідовний метод компонування за зв’язністю. Звіт до лабораторної роботи з Алгоритми. Робота № 525296

Послідовний метод компонування за зв’язністю

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

РТ

Кафедра:

Не вказано

Інформація про роботу

Рік:

2013

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Алгоритми

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" Інститут КНІТ Кафедра ПЗ ЗВІТ До лабораторної роботи № 4 На тему: “Послідовний метод компонування за зв’язністю” З дисципліни: “Комбінаторні методи та алгоритми” Лектор: проф. кафедри ПЗ Базилевич Р.П. Львів – 2013 Тема роботи: Послідовний метод компонування за зв’язністю Мета роботи: Дослідження алгоритму послідовного методу компонування за зв’язністю. Теоретичні відомості Завданням даної лабораторної роботи є процес розбиття елементів графу на вузли за допомогою ілюстративної програми та тестування конкретних випадків з її допомогою. Як приклад, для порівняльної характеристики використати стандартну тестову задачу Штейнберга, а також графи з різною кількістю елементів для дослідження характеристик методу. В ході дослідження процесу розбиття на вузли елементів графу зробити висновки відносно обчислювальної складності та точності методу. Розглянемо загальну схему методу й особливості його конкретної реалізації на ЕОМ. Нехай задана схема множина елементів E={e1, ... , en} і матриця суміжності, яка описує зв’язки між цими елементами. Визначемо послідовний процес призначення елементів eiE (i=1, ..., n) у вузли Tr(r=1, 2, ..., ), на кожному кроці якого вибирається один із нерозподілених елементів і приписується черговому вузлу. Вузол вважається завершеним, якщо число елементів у вузлі дорівнює заданому числу k або призначення любого з нерозподілених елементів призводить до утворення такого числа зовнішніх зв'язків вузла, що перевищує гранично припустиме значення v. Після завершення чергового вузла аналогічна процедура повторюється для наступного вузла, причому кандидатами для призначення є елементи, не включені в попередні вузли. Процес закінчується, коли всі елементи з множини Е розподілені. Зауважимо, що елемент е0, що відповідає набору зовнішніх виводів схеми, рахується розподіленим у вузол T0. Тактика призначення елементів складається в наступному. n°1. На черговому кроці процесу виділяються ті з ще нерозподілених елементів, включення кожного з яких у даний вузол не порушує обмежень по числу елементів і виводів вузла. n°2. Елементом, який включений у вузол на черговому кроці, є той із вибраних у n°1 елементів, що має найбільше число зв'язків з елементами, уже поміщеними у вузол (максимальна кон’юнкція). При кількох таких елементах включається той з них, що має мінімальну диз'юнкцію з елементами вузла. Код програми namespace poslid { public partial class Form1 : Form { public struct pointS { public int x; public int y; public int color; public bool used; } pointS[] points = new pointS[1]; private void numericUpDown1_ValueChanged(object sender, EventArgs e) { int val = (int)numericUpDown1.Value; dataGridView1.Columns.Clear(); for (int i = 0; i < val; i++) { //col dataGridView1.Columns.Add('x' + (i + 1).ToString(), 'x' + (i + 1).ToString()); dataGridView1.Columns[dataGridView1.Columns.Count - 1].Width = 25; //row dataGridView1.Rows.Add(1); dataGridView1.Rows[dataGridView1.Rows.Count - 1].HeaderCell.Value = 'x' + (i + 1).ToString(); dataGridView1.RowHeadersWidth = 50; } Random r = new Random(); for (int i = 0; i < dataGridView1.Rows.Count; i++) for (int j = 0; j < dataGridView1.Columns.Count; j++) { double n =r.NextDouble() * 10 - r.NextDouble() * 10; if (n < 0) n = 0; if (i == j) n = 0; if (i > j) n = Double.Parse(dataGridView1.Rows[j].Cells[i].Value.ToString()); dataGridView1.Rows[i].Cells[j].Value = (int)(n); } points = new pointS[val]; for (int i = 0; i < val; i++) { points[i].x = r.Next(pictureBox1.Width); points[i].y = r.Next(pictureBox1.Height); } } private void button1_Click(object sender, EventArgs e) { Graphics g = pictureBox1.CreateGraphics(); g.Clear(SystemColors.Control); for (int i = 0; i < points.Length; i++) { g.FillEllipse(Brushes.Black, new Rectangle(points[i].x, points[i].y, 4, 4)); g.DrawString((i + 1).ToString(), SystemFonts.DefaultFont, Brushes.Black, new Point(points[i].x+2, points[i].y+2)); } } private void button2_Click(object sender, EventArgs e) { Graphics g = pictureBox1.CreateGraphics(); g.Clear(SystemColors.Control); for (int i = 0; i < points.Length; i++) { g.FillEllipse(Brushes.Black, new Rectangle(points[i].x, points[i].y, 4, 4)); g.DrawString((i + 1).ToString(), SystemFonts.DefaultFont, Brushes.Black, new Point(points[i].x + 2, points[i].y + 2)); } for (int i = 0; i < dataGridView1.Rows.Count; i++) for (int j = 0; j < dataGridView1.Columns.Count; j++) { if (i > j) continue; int pointFrom = i; int pointTo = j; if (int.Parse(dataGridView1.Rows[i].Cells[j].Value.ToString()) > 0) g.DrawLine(Pens.Gray, new Point(points[pointFrom].x, points[pointFrom].y), new Point(points[pointTo].x, points[pointTo].y)); } } private void numericUpDown2_ValueChanged(object sender, EventArgs e) { int val = (int)numericUpDown2.Value; dataGridView2.Columns.Clear(); for (int i = 0; i < val; i++) { //col dataGridView2.Columns.Add('G' + (i + 1).ToString(), 'G' + (i + 1).ToString()); dataGridView2.Columns[dataGridView2.Columns.Count - 1].Width = 30; } dataGridView2.Rows.Add(1); dataGridView2.RowHeadersVisible = false; Random r = new Random(); for (int j = 0; j < dataGridView2.Columns.Count; j++) { int sum = 0; for (int k = 0; k < j; k++) sum += int.Parse(dataGridView2.Rows[0].Cells[k].Value.ToString()); int n = r.Next(Math.Min(points.Length / 2 + 1, points.Length - sum + 1)); if (n == 0 && points.Length - sum > 0) n += 1; if (j == dataGridView2.Columns.Count - 1) n = points.Length - sum; dataGridView2.Rows[0].Cells[j].Value = n; } } private int getStep(int vert) { int step = 0; for (int i = 0; i < dataGridView1.Columns.Count; i++) { if (points[i].used) continue; step += int.Parse(dataGridView1.Rows[vert].Cells[i].Value.ToString()); } return step; } private int getMaxStep() { int maxStepPoint = -1; for (int i = 0; i < points.Length; i++) { if (points[i].used) continue; if (maxStepPoint == -1) maxStepPoint = i; else if (getStep(maxStepPoint) < getStep(i)) maxStepPoint = i; } return maxStepPoint; } private int getReberFromNotSelected(int vert, List<int> l) { int sumR = 0; for (int i = 0; i < dataGridView1.Columns.Count; i++) { if (points[i].used) continue; if (l.IndexOf(i) >= 0) continue; //it is in List sumR += int.Parse(dataGridView1.Rows[vert].Cells[i].Value.ToString()); } return sumR; } private int getReberFromSelected(int vert, List<int> l) { int sumR = 0; for (int i = 0; i < dataGridView1.Columns.Count; i++) { //if (points[i].used) continue; if (l.IndexOf(i) < 0) continue; //it is not in List sumR += int.Parse(dataGridView1.Rows[vert].Cells[i].Value.ToString()); } return sumR; } private void button3_Click(object sender, EventArgs e) { Random r = new Random(); List<int>[] G = new List<int>[dataGridView2.Columns.Count]; for (int curBlock = 0; curBlock < dataGridView2.Columns.Count; curBlock++) { int curBlockSize = int.Parse(dataGridView2.Rows[0].Cells[curBlock].Value.ToString()); List<int> H = new List<int>(); int m_s = getMaxStep(); H.Add(m_s); points[m_s].used = true; while (H.Count < curBlockSize) { int new_m_s = -1; for (int i = 0; i < points.Length; i++) { if(points[i].used) continue; if (new_m_s == -1) new_m_s = i; else if (getReberFromNotSelected(i, H) - getReberFromSelected(i, H) < getReberFromNotSelected(new_m_s, H) - getReberFromSelected(new_m_s, H)) { new_m_s = i; } } points[new_m_s].used = true; H.Add(new_m_s); } G[curBlock] = new List<int>(); G[curBlock].AddRange(H); } String s = ""; for (int curBlock = 0; curBlock < dataGridView2.Columns.Count; curBlock++) { s += (curBlock + 1).ToString() + ": "; for (int i = 0; i < G[curBlock].Count; i++) { s += (G[curBlock][i]+1)+" "; } s += "\n"; } MessageBox.Show(s); for (int i = 0; i < points.Length; i++) { points[i].used = false; points[i].color = 0; } } } Результат виконання Рис. 1 Розбиття графів Висновок На даній лабораторній роботі я розробив програму на мові C# для вирішення задачі компонування електричних схем за зв’язністю. Результати були задовільні, тому певні аспекти алгоритму були виведені у спрощеному варіанті. При необхідності програму можна доробити для більшої наочності та розфарбувати граф відповідно до групування.

Звіт до лабораторної роботи Алгоритми

19.12.2013 22:05

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись