автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Эффективные алгоритмы на кодированных графах и их применение

Введение.

1. Вычислительная сложность алгоритмов поиска при различных формах представления графов.

1.1. Вычислительная сложность.

1.2. Алгоритмы поиска.

1.3. Вычислительная сложность алгоритмов поиска при различных формах представления графов.

2. Алгоритмы поиска на кодированных графах.

2.1. Кодирование графов.

2.2. Операции на кодированных графах.

2.3. Алгоритм "поиска в глубину".

2.4. Алгоритм "поиска в ширину".

2.5. Вычислительная сложность алгоритмов поиска на кодированных графах.

3. Эффективные алгоритмы на кодированных графах.

3.1. Алгоритм выделения связных компонент графа.

3.2. Алгоритм выделения двусвязных компонент.

3.3. Алгоритм построения кратчайшей цепи.

3.4. Алгоритм построения максимального паросочетания на двудольном графе.

3.5. Алгоритм построения максимального паросочетания на произвольном графе.

Актуальность темы.

Математическое обеспечение большинства систем автоматизированного проектирования и управления в качестве составной части содержит методы и алгоритмы теории графов, что обусловлено, в частности, эффективностью моделирования сложных систем с использованием математического аппарата теории анализа и синтеза сетей. Сетевые модели широко применяются в исследовании операций и используются на практике, например, при проектировании систем энергоснабжения, вычислительных комплексов, транспортных сетей, телетрансляционных сетей, систем космической связи и др.[1]. Для решения практических задач, связанных со складированием и продвижением товаров, календарным планированием, графиком капремонта и замены оборудования, контролем за уровнем издержек, обеспечением ритмичности производственного процесса, управлением запасами, распределением ресурсов, а также многих других задач разработаны эффективные алгоритмы, основанные на методах сетевого анализа, в значительной степени опирающихся на методы и алгоритмы теории графов [1,2].

Методы и алгоритмы теории графов успешно применяются и при моделировании поведения сложных систем в окрестности критических точек, в частности, при исследовании электрических свойств неоднородных материалов дискретной структуры таких, как аморфные полупроводники, кристаллические полупроводники с примесями, композитные материалы типа металл - диэлектрик [3]. Алгоритмы выделения связных компонент графа, построения широтного дерева и кратчайшей цепи на графе являются существенной частью математического обеспе5 чения вычислительных экспериментов в теории протекания для исследования взаимообусловленности геометрических и физических свойств объектов различной природы [4], например, при исследовании и создании новых материалов с заданными свойствами. Необходимость увеличения количества учитываемых факторов при моделировании естественных и искусственных больших систем с целью более полного отражения в модели их особенностей ведёт к постоянному росту размерности графов, отражающих структуру и связи исследуемых систем. В связи с этим, несмотря на высокую скорость роста быстродействия и объёма оперативной памяти современных ЭВМ, остаётся актуальной проблема повышения эффективности известных и широко используемых алгоритмов на графах. Составной частью большинства эффективных алгоритмов на графах являются алгоритмы поиска, поэтому снижение трудоёмкости алгоритмов поиска является одним из возможных путей повышения эффективности многих других алгоритмов.

Цель исследования.

Целью данной работы является повышение эффективности (снижение вычислительной сложности) алгоритмов поиска и основанных на них алгоритмов на графах:

- алгоритм построения дерева методом «поиска в глубину»;

- алгоритм построение дерева методом «поиска в ширину»;

- алгоритм выделения связных компонент;

- алгоритм построения кратчайшей цепи;

- алгоритм выделения двусвязных компонент графа;

- алгоритм построения максимального паросочетания на двудольном графе; 6

- алгоритм построения максимального паросочетания на произвольном графе.

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

Методы исследования.

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

Научная новизна.

Разработанные автором форма представления графов в памяти ЭВМ в виде списка двоичных чисел (кодов вершин) и определение элементарных операций на кодированных графах позволили построить ал7 горитмы поиска и некоторые другие, основанные на них алгоритмы на графах, вычислительная сложность которых в общем случае существенно (не менее чем в 0(^2п) раз, п - мощность множества вершин графа) меньше вычислительной сложности лучших из известных в литературе аналогичных алгоритмов.

Практическая ценность.

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

Апробация работы.

Основные результаты работы докладывались и обсуждались на 1,2 и 3-й научно-практических конференциях преподавателей и аспирантов К ЧТИ (Черкесск, 1995, 1996 и 1997 гг.), на Международном научном симпозиуме «Экономика и право - стратегия 2000» (Кисловодск, 1996 г.), на Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск,!997 г.), на международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики" (Нальчик, 1996 г.) и Др. 8

Публикации.

Результаты работы отражены в 15 публикациях (список прилагается).

На защиту выносятся:

1. Форма представления графов в виде списка двоичных чисел (кодов вершин) и элементарные операции на кодированных графах.

2. Алгоритм построения дерева методом «поиска в глубину» на кодированном графе;

3. Алгоритм построения дерева методом «поиска в ширину» на кодированном графе;

4. Алгоритм выделения связных компонент кодированного графа;

5. Алгоритм построения кратчайшей цепи на кодированном графе;

6. Алгоритм выделения двусвязных компонент графа кодированного графа.

7. Алгоритм построения максимального паросочетания на двудольном кодированном графе.

8. Алгоритм построения максимального паросочетания на произвольном кодированном графе.

Структура диссертационной работы.

Диссертация состоит из введения, трёх основных глав и приложения, изложенных на 130 страницах машинописного текста, 25 иллюстраций и библиографического списка, включающего 50 наименований.

Заключение

В первой главе диссертации рассматривается современное состояние вопроса о вычислительной сложности алгоритмов «поиска в глубину» а[ (по [5-12]) и «поиска в ширину» а'2 (по [5,11-16]) на невзвешен-ных графах. При этом вычислительная сложность оценивается некоторой функцией, которая каждой входной длине п ставит в соответствие максимальное (по всем индивидуальным задачам длины п) время, затрачиваемое алгоритмом на получение и представление решения индивидуальных задач этой длины [11,13]. Под входной длиной п при таком подходе понимается количество символов некоторого алфавита, достаточное для однозначного представления описания и исходных данных индивидуальной задачи [13-15]. При использовании двоичного алфавита {0; 1}, являющегося основой машинного языка практически всех современных ЭВМ, под длиной входа понимается информационная длина, т.е. количество двоичных разрядов, достаточных для представления описания и исходных данных индивидуальной задачи [15].

Учитывая, что оценки вычислительной сложности задач и алгоритмов в работах [4-9,13-19 и др.] получены относительно символьной длины входа (т.е. в предположении, что любое число, независимо от величины, может быть представлено во входном слове одним символом некоторого универсального алфавита [11,13]), а предлагаемые в данной работе форма представления графов и операции на них существенным образом используют двоичный алфавит {0;1}, оценки вычислительной сложности в гл. 1 и 2 даются в двух вариантах - относительно символьной длины входа (обозначается через х) и относительно информационной длины входа, измеряемой количеством символов двоичного алфавита в описании задачи (х').

112

Сравнительный анализ рассматриваемых алгоритмов при использовании различных известных способов представления графа в памяти ЭВМ показывает, что вычислительная сложность алгоритмов поиска зависит от выбранной формы представления графа. Вычислительная сложность алгоритмов поиска на графах, представленных матрицей смежности или списками смежности, составляет о(п2) относительно длины входа п, выраженной в количестве символов некоторого универсального (по [13]) алфавита и о(п2 п) относительно длины входа в алфавите {О; 1).

Во второй главе данной работы подробно излагается форма представления графов в памяти ЭВМ в виде списка из п целых чисел - кодов вершин, впервые предложенная автором в [50]. Показано, что для хранения информации о графе, представленном в указанном виде, в памяти

ЭВМ достаточно о(п2) символов алфавита {0;1} или 0(п) символов некоторого универсального алфавита (по [13]), т.е. список кодов вершин является более компактной формой представления графа. Для построения каких - либо конструктивных алгоритмов на кодированных графах необходимо создать математический механизм анализа информации о графах, представленных в такой форме в памяти ЭВМ - сформулированные и доказанные в гл.2 теоремы 1-6 являются достаточной теоретической базой для создания такого механизма в виде списка допустимых операций с кодами вершин.

Таким образом, определённые и достаточно подробно рассмотренные в разделе 2.2 операции на кодированных графах, представляющие собой механизм анализа информации о графе по списку кодов его вершин, позволили перейти к построению конкретных алгоритмов на кодированных графах и прежде всего алгоритмов «поиска в глубину» оц (раздел 2.3) и «поиска в ширину» а2 (раздел 2.4).

113

Сравнительный анализ вычислительной сложности алгоритмов поиска на графах, представленных матрицей смежности и списками кодов вершин (раздел 2.5, теоремы 7 , 8) показывает, что предлагаемая автором форма представления графов и разработанный в разделе 2.2 математический механизм анализа кодированных графов позволили существенно снизить (не менее чем в 0(log2 п) раз) вычислительную сложность классических алгоритмов «поиска в глубину» и «поиска в ширину».

Алгоритмы поиска являются составной частью большинства эффективных алгоритмов на графах, поэтому представление графов в кодированном виде и использование алгоритмов а1?а2 позволяет существенно снизить вычислительную сложность многих алгоритмов на графах. В третьей главе данной работы рассмотрены некоторые из таких алгоритмов, причём при оценке вычислительной сложности алгоритмов остаёмся в рамках традиционного подхода [5-16,19-26], т.е. принимая допущение о представимости чисел (в том числе и больших) в памяти ЭВМ одним символом некоторого универсального алфавита (см. гл. 1,2).

Одной из задач, возникающих во многих приложениях при анализе графов, является проверка графа на связность или выделение связных компонент графа. В [11] показано, как методом поиска в глубину решается задача выделения к-связных компонент графа при к<3. Предлагаемая в данной работе форма представления графов и реализация "поиска в глубину" алгоритмом а1 позволяет существенно снизить трудоёмкость решения этих задач. Вычислительная сложность приводимых в разделах 3.1-3.2 алгоритмов а4 и а5 (выделения соответственно связных и двусвязных компонент) составляет 0(п), т.к. алгоритмы а 4, а 5 отличаются от 0ц только наличием линейных по сложности процедур выделения связных и двусвязных компонент.

114

Задача построения кратчайшей цепи между двумя заданными вершинами невзвешенного графа, рассматриваемая в разделе 3.3, возникает как подзадача во многих приложениях теории графов, например, в задаче определения максимального потока в сети с ограниченной пропускной способностью. В [1] показано, что алгоритм построения дерева методом "поиска в ширину" может быть применён для построения кратчайшей цепи Ь(у0,у8) между двумя заданными вершинами графа у0 и . В главе 2 доказано (теорема 8) что вычислительная сложность алгоритма "поиска в ширину" а2 на кодированном графе равна 0(п), трудоёмкость построения цепи рассматриваемым в разделе 3.3 способом тоже не превышает О(п), таким образом, вычислительная сложность алгоритма а6 построения кратчайшей цепи на графе, представленном списком кодов своих вершин, составляет 0(п).

В разделах 3.4 и 3.5 рассматриваются широко распространённые в приложениях задачи построения максимального паросочетания соответственно на двудольном и произвольном графах. Показано, что представление графа в виде списка кодов и использование предложенного в гл.2 данной работы математического механизма анализа кодированных графов позволяет разработать алгоритмы, реализующие известные [11,21 и др.] методы решения указанных задач, но обладающие вычислительной сложностью о(п2), что существенно меньше вычислительной сложности «классических» алгоритмов Хопкрофта-Карпа (о(п5 2) ) и Габова (0(п3)).

Таким образом, в работе «Эффективные алгоритмы на кодированных графах» получены следующие новые результаты:

1. Разработана новая форма (кодированная) представления графов в памяти ЭВМ.

2. Определены элементарные операции на графах, представленных в ко

115 дарованной форме.

3. Разработаны алгоритмы поиска на графах, представленных в кодированной форме.

4. Построены некоторые другие эффективные алгоритмы, основанные на алгоритмах поиска на кодированных графах.

5. Получены оценки вычислительной сложности для всех построенных алгоритмов.

116

1. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: МирД984.

2. Берж К. Теория графов и её применение. М.: ИЛ, 1962.

3. Шкловский Б.И., Эфрос А.Л. Электронная теория неупорядоченных полупроводников. ~М.: Наука, 1978.

4. Эфрос А.Л. Физика и геометрия беспорядка.-М.: Наука, 1982.

5. Ope О. Теория графов. М.:Наука, Главная редакция физико-математической литературы, 1980.

6. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. М.:Высш. школа, 1976.

7. Емеличев В.А., Ковалёв М.М., Кравцов М.К. Многогранники, графы, оптимизация (комбинаторная теория многогранников).- М. :Наука, Главная редакция физико-математической литературы, 1981.

8. ХарариФ. Теория графов.-М.:Мир, 1973.

9. Стенли Р. Перечислительная комбинаторика. М.:Мир, 1990.

10. Ю.Харари Ф., Палмер Э. Перечисление графов. - М.:Мир, 1977.

11. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

12. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

13. Гер и М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

14. Нефёдов В.Н., Осипова В.А. Курс дискретной математики. М.: Изд-во МАИ,1992.

15. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. -М.: Энергоатомиздат,1988.132

16. Ахо А., Хопкрофт Дж.,Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

17. Семененко В.А.,Айдинян В.М.,Липовой А. Д. Электронные вычислительные машины. М.: Высшая школа, 1991.

18. Гилмор Ч. Введение в микропроцессорную технику. М.: Мир, 1984.

19. Коршунов Ю.М. Математические основы кибернетики. М.: Энергоатомиздат, 1987.

20. Edmonds J., Paths, Trees and Flowers, Canad.J.Math., Vol. 17,1965.

21. Hopcroft J.E. and Karp R.M., An n5/2 Algorithm for Maximum Matching in Bipartite Graphs, SIAM J. Comput., Vol. 2, 1973.

22. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М: Наука, 1969.

23. Gabow H.N., An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs, J. ACM, Vol. 23,1976.

24. Balinski M.I., Labelling to Obtain a Maximum Matching, in Combinatorial Mathematics and Its Applications (R.C. Bose and T.A. Dowling, Eds.), Univ. North Carolina Press Chappel Hill, N.C., 1967.

25. Kameda T. and Munro I., A 0(|V| |E|) Algorithm for Maximum Matching of Graphs, Computing, Vol. 12, 1974.

26. Even S., Kariv O., An Algorthm for Maximum Matching in General Graphs, Proc. 16th Annual Symp. on Foundations of Сотр. Science, IEEE, 1975, pp. 100-112.

27. Торопцев Н.Д. Асинхронно-синхронные генераторные установки для малых ГЭС. Материалы 1 научно-практической конференции преподавателей и аспирантов. - Черкесск, РИО КЧТИ, 1995.

28. Твайделл Дж., Уэйр А. Возобновляемые источники энергии. М.: Энергоатомиздат, 1990.

29. Ахметов Р.Б. Перспективы использования нетрадиционных источников энергии. М.: Информэнерго,1985.133

30. Лидоренко Н.С., Стребков Д.С. Нетрадиционная энергетика. -М. :3нание, 1986.

31. Шефтер Я.И. Использование энергии ветра. М.: Энергоатомиздат, 1983.

32. Беспалов В.Я., Алиев И.И., Клоков Ю.Б. Асинхронный генератор с гарантированным самовозбуждением. Электричество,№7,1997.

33. Джендубаев А-З.Р. К определению границ области устойчивого самовозбуждения асинхронного генератора с двумя обмотками статора. Электричество,№10,1993.

34. Алиев И.И. Асинхронный генератор с "провоцируемым" возбуждением. Тезисы докладов 6-й Всесоюзной научно-технич. конф. "Динамические режимы работы электрических машин и электроприводов". - Бишкек, 1991.

35. Зб.Джендубаев А-3. Р. Асинхронный сварочный генератор. -Автоматическая сварка, №1,1992.

36. Джендубаев А-З.Р. Жёсткое самовозбуждение асинхронного генератора с ферромагнитным короткозамкнутым ротором. -Электричество,№9,1997.

37. Окороков В.Р. Управление электроэнергетическими системами.Технико экономические принципы и методы. - Л.: Изд-во ЛГУ,1976.

38. Мелентьев Л.А. Системные исследования в энергетике: элементы теории, направления развития. М.: Наука, 1979.

39. Мелентьев Л.А. Оптимизация развития и управления больших систем энергетики. М.: Высшая школа, 1982.

40. Гук Ю.Б., Долгов П.П., Окороков В.Р. Комплексный анализ эффективности технических решений в энергетике. Л.: Энергоатомиздат, 1985.

41. Клима И. Оптимизация энергетических систем. М.: Высшая школа, 1991.

42. Кобринский Н.Е., Майминас Е.В., Смирнов А.Д. Экономическая кибернетика. -М.: Экономика, 1982.

43. Веников В.А., Зуев Э.Н., Литкенс И.В., Маркович И.М., Мельников H.A., Солдаткина JI.A., Строев В.А. Электрические системы. Математические задачи электроэнергетики. М.: Высшая школа, 1981.

44. Фёдоров A.A., Каменева В.В. Основы электроснабжения промышленных предприятий. -М.: Энергоатомиздат, 1984.

45. Ристхейн Э.М. Электроснабжение промышленных установок. М.: Энергоатомиздат, 1982.

46. Фёдоров A.A., Садчиков C.B. Характеристики и алгоритмы формирования и отбора вариантов систем промышленного электроснабжения. Электричество, №2,1982.

47. Дудов М.Х. Транспортная модель в некоторых задачах оптимизации систем электроснабжения. Материалы 1 научно-практической конференции преподователей и аспирантов. - Черкесск, РИО КЧТИ, 1995.

48. Дудов М.Х., Мамедов A.A. Экономико-математическая модель структуры электросети. Материалы Всероссийского симпозиума "Математическое моделирование и компьютерные технологии", Кисловодск, 1997.

49. Щукин Б.Д., Лыков Ю.Ф. Применение ЭВМ для проектирования систем электроснабжения. М.: Энергоиздат,1982.

50. Дудов М.Х. Алгоритм «поиска в глубину» на кодированных графах. -М. : ВИНИТИ, 1997, деп. рукоп. №3480-В97.