Автор работы: Пользователь скрыл имя, 16 Декабря 2012 в 20:31, лабораторная работа
Основний критерій розбиття графа на частини – мінімум зовнішніх з’єднувальних ребер mзн графа. Якщо формувати частини Gі=(Xі,Uі) графа G так, щоб кожна частина в множині Uii містила максимально велику кількість ребер, то неважко побачити, що при цьому отримується локальний мінімум сумарного числа К з’єднувальних ребер. Таке формування частин є основою послідовних алгоритмів розбиття.
Тема: Послідовний метод розбиття електричних схем.
Мета: Вивчення та дослідження послідовних методів розбиття електричних схем та особливостей їх програмної реалізації. Реалізувати один із послідовних алгоритмів розбиття електричної схеми при представленні схеми у вигляді мультиграфа.
Мета роботи:
Теоретичні відомості
Основний критерій розбиття графа на частини – мінімум зовнішніх з’єднувальних ребер mзн графа. Якщо формувати частини Gі=(Xі,Uі) графа G так, щоб кожна частина в множині Uii містила максимально велику кількість ребер, то неважко побачити, що при цьому отримується локальний мінімум сумарного числа К з’єднувальних ребер. Таке формування частин є основою послідовних алгоритмів розбиття.
Розглянемо вибраний послідовний
алгоритм. Нехай схема задана
графом G=(X,U), який необхідно розбити на k частин G1,…,Gk з числом вершин в кожній
відповідно n1,...,nk,
(n1 +…+ nk
= n).
В графі G вибираємо першу вершину xiÎХ з мінімальним локальним степенем r(xi)=minxiÎХr(xi).
Якщо таких вершин декілька, то перевага віддається тій вершині, яка має більше число кратних ребер, що йдуть до однієї вершини.
З вершини xi починається побудова частини G1. В неї початково включаються всі вершини, суміжні до xi, і сама ця вершина. Позначимо множину внесених вершин через Гxi. Якщо отримане число вершин рівне n1, то перша частина утворена.
Якщо це число є більше ніж n1, то усуваємо “зайві” вершини, тобто вершини, які зв’язані з тими, що залишились у визнаній частині, меншою кількістю ребер.
Якщо потужність множини Гxi менша за n1, то з Гxi вибирається вершина xj, яка відповідає умові:
s(xj) =r(xj)-aj= maxxjÎГхis(xj) , (5)
де aj – число ребер, які з’єднують вершину xj з усіма невибраними вершинами, r(xj) – локальна степінь вершини xj. Будуємо множину вершин Гxj, суміжних до xj, і процес вибірки вершин частини G1 повторюється. Після утворення частини G1 усуваємо її з вихідного графа G. Отримаємо граф G*= (X*, U*) , де X*=X \ X1, U*=U\U1 [4].
Аналогічно в графі G* вибираємо вершину з найменшою локальною степінню і з неї починаємо побудову частини G2. Процес повторюється доти, доки граф G не буде розбитий на k частин. Неважко побачити, що описаний алгоритм є дуже простий і дозволяє швидко отримати результат. Але в загальному випадку він призводить до неоптимальних результатів. Цей алгоритм найбільш ефективний для графа, в якому кількість вершин G значно більша кількості вершин в будь-якій частині: n>>n1 ,n2 ,…., nk, оскільки існує багато можливостей для вибору вершин.
Код програми
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SequentionalPartioning
{
class Algorithm
{
private int verticesCount;
private int[,] graph;
private int[] elementsInGroup;
private bool[] bannedElements;
public void setMatrixSize(int matrixSize)
{
verticesCount = matrixSize;
graph = new int[verticesCount, verticesCount];
}
public void setMatrixElement(int value, int x, int y)
{
if (x < 0 && x > verticesCount - 1) return;
if (y < 0 && y > verticesCount - 1) return;
graph[y, x] = value;
graph[x, y] = value;
}
public int GroupsCount
{
get { return (elementsInGroup != null) ? elementsInGroup.Length : -1; }
set { elementsInGroup = new int[value]; }
}
public void setElemetsCountInGroup(int group, int elementsCount)
{
elementsInGroup[group] = elementsCount;
}
private int powerOfVertice(int vertice)
{
int sum = 0;
for (int i = 0; i < verticesCount; i++)
{
if (bannedElements[i]) continue;
sum += graph[vertice, i];
}
return sum;
}
public List<List<int>> calculate()
{
bannedElements = new bool[verticesCount];
for (int i = 0; i < verticesCount; i++)
bannedElements[i] = false;
List<List<int>> groups = new List<List<int>>();
for (int i = 0; i < elementsInGroup.Length - 1; i++)
{
List<int> part = makePart(elementsInGroup[i]);
groups.Add(part);
for (int j = 0; j < part.Count; j++)
bannedElements[part[j]] = true;
}
List<int> lastPart = new List<int>();
for (int i = 0; i < verticesCount; i++)
{
if (!bannedElements[i])
lastPart.Add(i);
}
groups.Add(lastPart);
return groups;
}
private List<int> makePart(int elementsCount)
{
int vert = -1, min = -1;
for (int i = 0; i < verticesCount; i++)
{
if (!bannedElements[i])
{
vert = i;
min = powerOfVertice(i);
break;
}
}
List<int> minIndexes = new List<int>();
minIndexes.Add(vert);
for (int i = vert + 1; i < verticesCount; i++)
{
if (bannedElements[i]) continue;
int temp = powerOfVertice(i);
if (min > temp)
{
min = temp;
minIndexes.Clear();
minIndexes.Add(i);
}
else if (min == temp)
minIndexes.Add(i);
}
if (minIndexes.Count > 1)
vert = selectIndexOfBestElement(
else
vert = minIndexes[0];
List<int> verticesGroup = new List<int>();
while (verticesGroup.Count < elementsCount)
{
verticesGroup.Clear();
verticesGroup.Add(vert);
for (int i = 0; i < verticesCount; i++)
if (!bannedElements[i] && graph[vert, i] > 0)
verticesGroup.Add(i);
if (verticesGroup.Count < elementsCount)
vert = pickOtherElement(
}
while (verticesGroup.Count > elementsCount)
{
verticesGroup = removeElementFromSet(
}
return verticesGroup;
}
private int pickOtherElement(List<int> verticesList)
{
int sigma = 0;
int max = 0;
int index = -1;
for (int i = 0; i < verticesList.Count; i++)
{
int current = verticesList[i];
int a = 0;
for (int j = 0; j < verticesCount; j++)
{
if (!bannedElements[j] && verticesList.IndexOf(j) < 0 && graph[current, j] > 0)
a += graph[current, j];
}
sigma = powerOfVertice(verticesList[i]
if (sigma > max)
{
max = sigma;
index = verticesList[i];
}
else if (sigma == max)
{
index = new Random().Next() % verticesList.Count;
}
}
return index;
}
private int selectIndexOfBestElement(List<
{
int minIndex = -1;
int min = Int32.MaxValue;
for (int i = 0; i < list.Count; i++)
{
int current = list[i];
int max = 0;
for (int j = 0; j < verticesCount; j++)
{
if (bannedElements[j]) continue;
if (graph[current, j] > max)
{
max = graph[current, j];
}
}
if (min > max)
{
min = max;
minIndex = list[i];
}
}
return minIndex;
}
private int getEdgesCount(List<int> set, int element)
{
int sum = 0;
for (int i = 0; i < set.Count; i++)
{
if (set[i] != element)
sum += graph[set[element], set[i]];
}
return sum;
}
private List<int> removeElementFromSet(List<int> set)
{
int mainElement = set[0];
int elementToRemoveIndex = 1;
int minEdgesCount = getEdgesCount(set, elementToRemoveIndex);
for (int i = 2; i < set.Count; i++)
{
int temp = getEdgesCount(set, i);
if (temp < minEdgesCount)
{
minEdgesCount = temp;
elementToRemoveIndex = i;
}
}
set.RemoveAt(
return set;
}
}
}
Результат виконання програми
Рис. 1 Результати виконання програми
Висновок
На лабораторній роботі було реалізовано
послідовний алгоритм розбиття
електричних схем.
Информация о работе Послідовний метод розбиття електричних схем