Послідовний метод розбиття електричних схем

Автор работы: Пользователь скрыл имя, 16 Декабря 2012 в 20:31, лабораторная работа

Описание работы

Основний критерій розбиття графа на частини – мінімум зовнішніх з’єднувальних ребер mзн графа. Якщо формувати частини Gі=(Xі,Uі) графа G так, щоб кожна частина в множині Uii містила максимально велику кількість ребер, то неважко побачити, що при цьому отримується локальний мінімум сумарного числа К з’єднувальних ребер. Таке формування частин є основою послідовних алгоритмів розбиття.

Файлы: 1 файл

ЛР 3.doc

— 112.00 Кб (Скачать файл)


Тема: Послідовний метод розбиття електричних схем.

Мета: Вивчення та дослідження послідовних методів розбиття електричних схем та особливостей їх програмної реалізації. Реалізувати один із послідовних алгоритмів розбиття електричної схеми при представленні схеми у вигляді мультиграфа.

Мета  роботи:

Теоретичні відомості

Основний критерій розбиття графа  на частини – мінімум зовнішніх  з’єднувальних ребер 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(minIndexes);

            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(verticesGroup);

            }

 

            while (verticesGroup.Count > elementsCount)

            {

                verticesGroup = removeElementFromSet(verticesGroup);

            }

 

            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]) - a;

 

                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> 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(elementToRemoveIndex);

            return set;

        }

    }

}

 

 

 

Результат виконання програми

 

 

Рис. 1 Результати виконання програми

 

Висновок

На лабораторній роботі було реалізовано послідовний алгоритм розбиття  
електричних схем.


Информация о работе Послідовний метод розбиття електричних схем