Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Послідовний метод компонування за зв’язністю
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
РТ
Кафедра:
Не вказано
Інформація про роботу
Рік:
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# для вирішення задачі компонування електричних схем за зв’язністю. Результати були задовільні, тому певні аспекти алгоритму були виведені у спрощеному варіанті. При необхідності програму можна доробити для більшої наочності та розфарбувати граф відповідно до групування.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора