Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Выбор структур данных





В качестве структур данных для аналитического представления гиперграфа будем использовать массивы динамических векторов, так как над ними выполняются только операции доступа. При работе алгоритма будут формироваться и использоваться массивы .

Над массивом мы будем выполнять следующие действия: последовательная выборка элементов, добавление выбранной вершины в конец массива. Таким образом, структура данных для - динамический вектор. В массив будем добавлять новые вершины-кандидаты и исключать из него вершину . Для массива целесообразно использовать одно- или двусвязный список. Над массивом будут выполняться только операции просмотра его элементов (последовательного доступа), так как его элементы после корректировки пересчитываются заново. Следовательно, структура данных массива - динамический вектор.

Основные пункты одного из вариантов алгоритма.

1. Включаем в формируемое множество некоторую вершину :

 

2. Определяем количество рёбер , соединяющих с :

 

3. Находим множество вершин - кандидатов на включение в :

, где

4. Для каждой вершины определяем множество инцидентных ей рёбер , подмножество рёбер, приходящих в разрез, и подсчитываем показатель . Для этого:

4.1.

4.2. для выполняем:

4.2.1. Находим множество вершин , входящих в ребро

4.2.2. Проверяем условие

Если условие не выполняется (ребро остаётся в разрезе) переходим к пп. 4.2.4. Выполнение условия означает, что ребро уходит из разреза – переходим к пп. 4.2.3.

Подсчитываем показатель и переходим к п. 4.2.

 

Проверяем условие

Если условие выполняется (ребро приходит в разрез при включении xi в Xl), переходим к пп. 4.2.5. При невыполнении условия переходим к анализу следующего ребра, т.е. к п.


4.2.

4.2.5. Включаем ребро в множество :

,

подсчитываем показатель :

и возвращаемся к п. 4.2.

4.3. Определяем значение :

и заносим его значение в массив :

 

5. Находим вершину , для которой минимально:

 

6. Подсчитываем количество рёбер , соединяющих множества и после включения в :

 

7. Проверяем ограничение на количество внешних выводов l -й части схемы:

Если условие выполняется, то переходим к п. 8, иначе – к п. 12.

 

8. Включаем вершину в множество и исключаем её из :

 

9. Проверяем условие:

, где nl – требуемое количество элементов в l -й части схемы.Если условие выполняется, то переходим к п.10, иначе – к п.13.

 

10. Определяем множество вершин, входящих в множество рёбер :

 

11. Корректируем множество вершин кандидатов :

и возвращаемся к п. 4.

 

12. Дальнейшее формирование невозможно из-за нарушения ограничения на число внешних выводов. Переход на окончание работы алгоритма к п. 14.

 

13. Вывод результатов.

 

14. Конец работы алгоритма.

 







Дата добавления: 2015-04-19; просмотров: 457. Нарушение авторских прав; Мы поможем в написании вашей работы!




Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

Тема 5. Анализ количественного и качественного состава персонала Персонал является одним из важнейших факторов в организации. Его состояние и эффективное использование прямо влияет на конечные результаты хозяйственной деятельности организации.

Билет №7 (1 вопрос) Язык как средство общения и форма существования национальной культуры. Русский литературный язык как нормированная и обработанная форма общенародного языка Важнейшая функция языка - коммуникативная функция, т.е. функция общения Язык представлен в двух своих разновидностях...

Патристика и схоластика как этап в средневековой философии Основной задачей теологии является толкование Священного писания, доказательство существования Бога и формулировка догматов Церкви...

Примеры решения типовых задач. Пример 1.Степень диссоциации уксусной кислоты в 0,1 М растворе равна 1,32∙10-2   Пример 1.Степень диссоциации уксусной кислоты в 0,1 М растворе равна 1,32∙10-2. Найдите константу диссоциации кислоты и значение рК. Решение. Подставим данные задачи в уравнение закона разбавления К = a2См/(1 –a) =...

Экспертная оценка как метод психологического исследования Экспертная оценка – диагностический метод измерения, с помощью которого качественные особенности психических явлений получают свое числовое выражение в форме количественных оценок...

В теории государства и права выделяют два пути возникновения государства: восточный и западный Восточный путь возникновения государства представляет собой плавный переход, перерастание первобытного общества в государство...

Studopedia.info - Студопедия - 2014-2025 год . (0.008 сек.) русская версия | украинская версия