WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«научный руководитель: Ладыженский Юрий Валентинович «Параллельные алгоритмы для решения задач на графах» Введение Графы являются широко распространенной структурой данных, и ...»

Куркчи В.А

Магистрант группы ПО-99, ФВТИ, ДонНТУ

научный руководитель: Ладыженский Юрий Валентинович

«Параллельные алгоритмы для решения задач на графах»

Введение

Графы являются широко распространенной структурой данных, и

задачи, связанные с ними, находят свое применение в различных областях

науки и техники: эти задачи решаются при проектировании БИС, при

распараллеливании вычислительных и других процессов, при организации

ассоциативной памяти, в теории конечных автоматов, потоков в сетях и др .

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

К сожалению, большая часть задач на графах – NP-полные, что в значительной степени затрудняет поиск решений. Примером такой задачи может послужить задача о развозке: поставщику необходимо доставить товары потребителям, при этом существует множество используемых маршрутов, каждый из которых требует затрат времени и средств; требуется определить, какие маршруты следует использовать, чтобы обслужить всех потребителей при минимальных транспортных расходах (эта задача сводится к задаче о наименьшем покрытии). Если у поставщика несколько клиентов в пределах города, эту задачу можно решить устно, но если клиентов несколько тысяч, и они разбросаны по всей стране, – поиск решения даже с помощью ЭВМ может затянуться. Ну а если поставщиком является транснациональная компания, то эта задача не может практически быть решена .



Однако задачи этого класса часто просто необходимо решить. Это обусловило появление направления, изучающего приближенные, или эвристические, алгоритмы. Большая часть NP-полных задач сводится к ЗЦЛП, что позволяет использовать в качестве решение любые локальные максимумы (минимумы). Такое решение, конечно же, не является оптимальным, но допустимо. То есть, применительно к описанной выше задаче, транспортные расходы не будут минимальными, но будут гораздо меньше, чем при доставке «наугад» .

Но процесс решения задачи большой размерности, даже приближенным алгоритмом может быть весьма длительным, что справедливо для всех задач и любых алгоритмов. Для ускорения поиска решений, используют параллельные алгоритмы. Временная сложность параллельных алгоритмов обычно, как минимум на порядок ниже, чем у аналогичных последовательных, а иногда и относится к другому классу. Например, простая сортировка в последовательной реализации имеет временную сложность от O(n 2 ) до O(n log n), то есть полиномиальную, а сортировку n элементов на n процессорах можно выполнить за O(log n), то есть логарифмическое время. А решение задач на графах, при использовании алгоритмических методов, часто сводится к сортировкам. Так, в [5] описан приближенный параллельный алгоритм для поиска наибольшего независимого множества, использующий исключительно сортировки .

В настоящий момент существует достаточно большое количество параллельных вычислительных моделей: от гипотетических – EREW PRAM, CRCW PRAM, – до реально используемых – MIMD, вычислительные сети .

1 Обозначения и определения

–  –  –

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



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

Рассмотрим наиболее часто встречающиеся в литературе. При этом следует сразу отметить, что задача о наибольшем независимом множестве неразрывно связана с задачей о наибольшей клике. Множество S является кликой G тогда и только тогда, когда S – независимое множество G. Любой результат, полученный для одной из этих задач имеет эквивалентную форму для другой задачи. Следовательно, (G ) = (G ), и, в общем случае, (G, w) = (G, w) .

–  –  –

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

Здесь же приведем другую формулировку задачи .

Найти S : ( xi, x j ) S 2 ( xi, x j ) E & ¬S ': S S ' .

–  –  –

В 1975г Немхаузер и Троттер доказали, что если переменная xi принимает целое значение 1 в решении релаксации, то она принимает значение 1 по крайней мере в одном из оптимальных решений. Это предполагает неявный переборный алгоритм для решения задачи посредством решения ее линейной релаксации. Однако, в большинстве случаев, лишь несколько переменных имеют целое значение в оптимальном решении линейной релаксации, и зазор между оптимальными решениями задачи и ее линейной релаксации слишком велик, что значительно ограничивает использование этого подхода [1] .

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

Очевидно, что для двоичных xi и x j xi + x j 1 тогда и только тогда, когда xi x j = 0 [1]. Также можно записать ограничение на количество значений уравнением, корни которого есть допустимые значения, то есть ( xi 0) * ( xi 1) = 0 xi2 xi = 0 .

–  –  –

добавление остальных ограничений не позволит записать функцию в матричной форме. Впрочем, такой формулировкой для данной задачи обычно подразумевают целочисленные переменные, то есть X {0,1} N .

–  –  –

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





3 Связь с другими задачами Эквивалентность рассматриваемой задачи задаче о наибольшей клике была описана ранее. Рассмотрим связь с другими задачами .

3.1 Задача о совершенном паросочетании Паросочетанием, или независимым множеством ребер, называется множество ребер, в котором никакие два ребра несмежны. Совершенное паросочетание – паросочетание наибольшей мощности .

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

Вершины нового графа смежны, если смежны соответствующие ребра .

Решение задачи о наибольшем независимом множестве графа и есть совершенное паросочетание .

3.2 Задача о наименьшем доминирующем множестве вершин Доминирующее множество вершин – множество, смежное с любой вершиной графа, не входящей в это множество. Найти доминирующее множество наименьшей мощности .

I является наибольшим независимым множеством G тогда и только тогда, когда I является наибольшей кликой G, и тогда и только тогда, когда V \ I является минимальным вершинным покрытием G. Последнее следует из тождества Галлаи (Gallai)[6] .

3.3 Задача о минимальной раскраске Раскраской графа называют такое приписывание цветов (натуральных чисел) его вершинам, что никакие две смежные вершины не получают одинаковый цвет. Минимальная раскраска – раскраска минимальной мощности [4] .

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

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

Начнем с простейшего переборного алгоритма – рекурсивного поиска с возвратами [4] .

Алгоритм 3.1 – ПВ .

Вход: S – текущее независимое множество, V – множество вершин .

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

e := false;

m := 0;

for v V do if S {v} then e := true;

ПВ( S {v}, V \ N (v))

–  –  –

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

Это сделано для сохранения контекста, но на практике выполняется следующим циклом:

f := true { множество считается независимым} for u S do if (u, v) E then f := false; exit for ;

end if end for Этот алгоритм работает следующим образом, строится независимое множество, при этом при добавлении каждой вершины проверяется на независимость. Если расширить множество нельзя – оно максимально, то есть может претендовать на то, чтобы считаться наибольшим. Оно сравнивается с найденным ранее (или пустым, если найдено первое множество) и еcли оказывается больше, принимается за новое текущее множество. Далее алгоритм строит новое максимальное независимое множество .

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

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

Рассмотрим теперь другой алгоритм, алгоритм Брона-Кербоша [4], его нельзя распараллелить, но он использует сокращенный перебор, учитывая особенности задачи, что делает его рассмотрение очень полезным .

Идея алгоритма аналогична предыдущему, то есть, начиная с пустого, строится множество вершин с сохранением независимости. Пусть S k, уже полученное множество из k вершин, Qk - множество вершин, которое можно добавить к S k, то есть S k N (Qk ) = 0. Среди вершин Qk будем различать те, которые уже использовались для расширения S k (обозначим Qk ), и те, которые еще не использовались ( Qk+ ). Тогда общая схема алгоритма будет состоять из следующих шагов .

Шаг вперед от k к k+1 состоит в выборе вершины x Qk+ :

S k +1 = S k {x}, Qk+1 = Qk N ( x), Qk++1 = Qk+ ( N ( x) {x}) .

Шаг назад от k+1 к k:

S k = S k +1 {x}, Qk+ = Qk++1 {x}, Qk = Qk+1 {x} .

–  –  –

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

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

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

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

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

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

Список литературы 1 Bomze I.M, Budinich M, Pardalos P.M, Pelillo M. The maximum clique problem. Handbook of combinatorial optimization. – Adison-Wesley: 1999 .

2 T.S. Motzkin and E.G. Straus, Maxima for graphs and a new proof of a theorem of Turan, Canad. J. Math., Vol. 17: 533-540, 1965 .

3 http: // dimacs.rutgers.edu/Challenges/index.html 4 Новиков Ф.А, Дискретная математика для программистов: Спб: Питер, 2001. – 304с .

5 Goldberg M., Spenser T. Constructing a maximum independent set in parallel. //SIAM J. Discr. Math. Vol. 2. – 1989, p. 322-328 .

6 Abello J, Butenko S, Pardalos P.M, Resende M.G.C. Finding independent set in a graph using continious multivariable formulations//AT&T labs research technical report .






Похожие работы:

«Московский государственный университет имени М. В. Ломоносова Факультет Вычислительной Математики и Кибернетики Кафедра Математических Методов Прогнозирования ШАДРИКОВ Андрей Алексеевич Алгоритмы неотрицательных матричных р...»

«ГЕОФИЗИЧЕСКИЕ ИССЛЕДОВАНИЯ, 2017, том 18, № 2, с.27-54. DOI: 10.21455/gr2017.2-2 УДК 550.837.211 ОПЫТ И ПЕРСПЕКТИВЫ ИСПОЛЬЗОВАНИЯ МАГНИТОТЕЛЛУРИЧЕСКИХ ЗОНДИРОВАНИЙ В ОСАДОЧНЫХ БАССЕЙНАХ 2017 г. Н.А. Пальшин1, Е....»

«Лабораторная работа №07 по дисциплине Высокоуровневые методы информатики и программирования ТЕМА: ИСПОЛЬЗОВАНИЕ СПИСКА. СОЗДАНИЕ И ИСПОЛЬЗОВАНИЕ ПАПОК 1. В Вашей папке создайте папку с именем В_лр07, совпадающим с именем файла с этим заданием, и затем скопируйте файл с з...»

«Региональное содружество в области связи (РСС) 12-е заседание Комиссии по информационной безопасности при Координационном совете государств – участников СНГ по информатизации при РСС г.Москва, 25 ноября 2010 года Протокол № 12 заседания Комиссии по информационной безо...»

«Тема 16 Методы и технологии моделирования. Информационная модель объекта Методы и технологии моделирования Все многообразие способов моделирования, рассматриваемого теорией моделирования, можно условно разделить группы. Аналитическое модел...»

«Трехмерная численная модель релаксации электронного пучка в плазме Е. А. Месяц, А. В. Снытников Институт вычислительной математики и математической геофизики СО РАН, Новосибирск, Россия e-mail: mesyats@gmail.com Аннотация. На основе метода частиц в яче...»

«СЕРИЯ 10 ВЕСТНИК ВЫПУСК 4 ПРИКЛАДНАЯ МАТЕМАТИКА САНКТ-ПЕТЕРБУРГСКОГО ДЕКАБРЬ ИНФОРМАТИКА УНИВЕРСИТЕТА ПРОЦЕССЫ УПРАВЛЕНИЯ Научно-теоретический журнал Издается с августа 1946 года СОДЕРЖАНИЕ Прикладная математика Ампилова Н. Б., Терентьев С. В. О применении интервальной арифметики пр...»

«Министерство образования Республики Беларусь Учреждение образования "Белорусский государственный университет информатики и радиоэлектроники" УТВЕРЖДАЮ проректор С.К. Дик 2018 г. ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА для магистерской подготовки по специальности 1-40 80 01 Элементы...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.