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

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

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





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

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

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

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. Нарушение авторских прав; Мы поможем в написании вашей работы!




Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...


Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...


Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...


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

Тема: Изучение фенотипов местных сортов растений Цель: расширить знания о задачах современной селекции. Оборудование:пакетики семян различных сортов томатов...

Тема: Составление цепи питания Цель: расширить знания о биотических факторах среды. Оборудование:гербарные растения...

В эволюции растений и животных. Цель: выявить ароморфозы и идиоадаптации у растений Цель: выявить ароморфозы и идиоадаптации у растений. Оборудование: гербарные растения, чучела хордовых (рыб, земноводных, птиц, пресмыкающихся, млекопитающих), коллекции насекомых, влажные препараты паразитических червей, мох, хвощ, папоротник...

Плейотропное действие генов. Примеры. Плейотропное действие генов - это зависимость нескольких признаков от одного гена, то есть множественное действие одного гена...

Методика обучения письму и письменной речи на иностранном языке в средней школе. Различают письмо и письменную речь. Письмо – объект овладения графической и орфографической системами иностранного языка для фиксации языкового и речевого материала...

Классификация холодных блюд и закусок. Урок №2 Тема: Холодные блюда и закуски. Значение холодных блюд и закусок. Классификация холодных блюд и закусок. Кулинарная обработка продуктов...

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