Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Доклад: Модификация алгоритма определения клик графа с параметрической адаптацией

Название: Модификация алгоритма определения клик графа с параметрической адаптацией
Раздел: Рефераты по информатике, программированию
Тип: доклад Добавлен 18:32:17 12 апреля 2005 Похожие работы
Просмотров: 205 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

В.А. Литвиненко И.Ю. Черненко

1. Основные положения

Кликой графа называется максимальный полный подграф, который не входит ни в один полный подграф более высокого порядка /1/ .

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

Рассматривается класс нериентированных графов без петель и кратных ребер.

Комбинаторная сложность точных алгоритмов определения клик графа приводит к необходимости использовать приближенные методы при решении задач большой размерности. К таким задачам, в частности, относятся различные задачи конструкторского проектирования интегральных схем, в которых алгоритмы определения клик графа применяются в качестве алгоритмов проектных операций . Известные алгоритмы /1,2/ позволяют определять только такие семейства клик графа, свойства и мощность которых зависят от структуры решаемых графов и последовательности выполнения самого алгоритма. От качественного решения алгоритмов проектных операций существенно зависит качество решения алгоритмов проектных процедур.

Основными факторами, влияющими на качество выполнения алгоритмов проектных операций, являются:

требуемая точность решения;

ресурс времени, отведенный на выполнение проектной операции;

размерность конкретной задачи.

Из указанных факторов известные приближенные методы позволяют учитывать только ограничение на время выполнения алгоритма - ресурс времени путем прерывания решения в момент его истечения /2/ .

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

Возможность алгоритмическими методами учитывать такие случаи позволяет оптимизировать время выполнения алгоритма проектной операции проектной процедуры и тем самым повышать эффективность использования математического и программного обеспечения САПР.

2. Базовый алгоритм

В /3/ разработан алгоритм определения клик графа, отличающийся от известных возможностью адаптации к изменению ресурса времени, требуемой точности и размерности самой задачи, предназначенный для исследования неориентированных графов без петель и кратных ребер. В основу алгоритма положен метод параметрической адаптации, который позволяет с помощью входных параметров “настраивать” алгоритм определения клик графа на получение решений с различной степенью точности. При этом точность решения может изменяться от получения точного решения задачи определения клик графа, т.е. определения всех клик графа, до определения такого количества клик графа, которого достаточно для получения решения проектной процедуры, для которой задача определения клик графа используется в качестве алгоритма проектной операции.

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

В основу базового алгоритма положена следующая теорема, доказанная в работе /4/.

Пусть в графе G=(X,U) имеется вершина и определена клика с множеством вершин , где . Тогда, если выделены все клики, то и будут выделены все клики.

Практическое значение этой теоремы заключается в следующем.

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

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

Если для каждой вершины исключать из рассмотрения вершины, смежные с и вошедшие только в одну клику, то в результате выполнение базового алгоритма будут выделены все клики графа. В том случае, если для каждой вершины исключать из рассмотрения вершины, образующие несколько таких клик графа, то базовый алгоритм будет выделять не все клики, а только некоторое их подмножество, так как часть клик будет потеряна. Точность решения задачи определения клик графа в этом случае будет уменьшаться с увеличением числа клик, вершины которых исключаются из рассмотрения.

Обозначим такое число клик l. Тогда, задавая значения l, можно “управлять” точностью решения, получаемого базовым алгоритмом, настраиваивая его на получение решение с различной степенью точности.В таком случае l является параметром базового алгоритма определения клик графа. Использование параметра для адаптации алгоритма к внешним условиям – требуемой точности решения и послужило введением названия класса алгоритмов – алгоритмы с параметрической адаптацией.

Отметим, что при увеличении l в предельном случае точность решения, которую можно получить с помощью базового алгоритма, соответствует количеству клик графа, которое может быть получена с помощью алгоритма определения клик, покрывающих все ребра графа /1,2/.Это означает, что с помощью базового алгоритма нельзя получить решение с нулевой точностью.

Рассмотренный базовый алгоритм положен в основу модифицированного алгоритма, предлагаемого в дипломной работе.

3. Модифицированный алгоритм

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

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

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

4. Оценка сложности модифицированного алгоритма

Оценим сложность модифицированного алгоритма.Оценка сложности производится с целью показать аналитически правильность сделанного выше предположения.

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

Пусть n – количество столбцов первой строки матрицы, а b - средняя мощность клик в графе. Тогда, если оценивать количество операций логического умножения элементов двух столбцов двух строк матрицы смежности, то количество операций определения одной клики будет составлять сумму членов арифметической прогрессии с шагом 1, первый член которой равен (n-1), а количество членов прогресси равно (b-1), т.е.

0,5(b-1)(2n-b-n).

Так как вершины каждой первой выделенной клики из рассмотрения исключаются, то количество операций логического умножения элементов строки со строками матрицы, номерам которых в строке соответствуеют значения, равные 1, в худшем случае будет равно (b-1).

Таким образом оценка числа операций логического умножения, которые необходимо произвести для элементов строки , составляет

O(0,5(b-1)(2n-b-4)(n-b)).

В соответствие с правилами преобразования O-функций последнее выражение можно преобразовать к следующему виду

O(b(2n-b)(n-b)).

Теперь, при b, стремящемся к n , O(0,5(b-1)(2n-b-4)(n-b)) ®O(n),

а при b, стремящемся к 0,5n , O(0,5(b-1)(2n-b-4)(n-b)) ®O(n).

Таким образом, эффективность модифицированного алгоритма возрастает с увеличением b -средней мощности клик в графе, т.е. аналитичеки подтверждается предположение, положенное в основу модификации базового алгоритма.

5. Реализация модифицированного алгоритма

Разработана программа на Borland C++ Builder для Windows`95 и проведено исследование эффективности предложенного модифицированного алгоритма на графах размерности до 500 вершин, а также на графах Муна-Мозера, которые являются критическими для задачи определения клик графа, так как содержат набольшее количество клик для графов с одинаковым числом вершин.

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

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

Список литературы

Мелихов А.Н., Берштеин Л.С., Курейчик В.М. Применение теории графов для проектирования дискретных устройств.М.:Сов.радио,1975.224с.

Литвиненко В.А. Методы определения семейств клик графа. В кн.: Методы и программы решения оптимизационных задач на графах и сетях. Часть 2. Теория, Алгоритмы. Новосибирск:1982,с.90-92.

Калашников В.А., Литвиненко В.А. К вопросу определения семейств клик графа.30. Intern. Wiss. Koll. TH llmenau Vortragsreihe.1985.c.41-44.

Литвиненко В.А. Курейчик В.М. Определение клик симметрического графа //Известия Северо-Кавказского научного центра высшей школы. Технические науки, 1979,№2,с.13-16

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:37:51 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:46:11 24 ноября 2015

Работы, похожие на Доклад: Модификация алгоритма определения клик графа с параметрической адаптацией

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150913)
Комментарии (1842)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru