Исследование задачи о ширине графа и ее обобщений тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Иванова, Светлана Диадоровна

• Иванова, Светлана Диадоровна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Иванова, Светлана Диадоровна

Введение

1. Задача о ширине графа и ее обобщения

1.1. Постановки задач.

Введение диссертации (часть автореферата) на тему «Исследование задачи о ширине графа и ее обобщений»

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

Графы традиционно и успешно применяются для моделирования и анализа различных систем, имеющих сложную сетевую структуру, например, транспортных, информационно-вычислительных сетей, систем взаимоотношений в коллективе и т.д. [6,27].

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

В задаче о ширине графа требуется пронумеровать вершины графа последовательными натуральными числами так, чтобы минимизировать максимальное значение модуля разности номеров смежных вершин. Она интересна как с теоретической, так и с практической точки зрения, поскольку имеет ряд важных приложений в различных областях, таких как решение систем линейных уравнений, проектирование интегральных схем и других объектов. Задача о ширине графа относится к задачам оптимальной нумерации. Общим для всех задач данного класса является вид допустимого решения - нумерация вершин, а отличаются они друг от друга лишь оптимизируемой функцией. Этот класс включает, в частности, задачу оптимального линейного упорядочения, которой посвящено значительное число работ [28,66,68,77], а также ряд других задач [3,30,60,78]. Обзор результатов по задачам нумерации можно найти в [39,63].

Задачи оптимальной нумерации, в свою очередь, можно отнести к более широкому классу задач размещения графа на линии. Они изучаются в работах [9,10,19,79].

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

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

Задача о ширине графа, а следовательно, и более общая задача проектирования, являются TVP-трудными [71], поэтому особый интерес представляет выделение полиномиально разрешимых частных случаев и разработка алгоритмов приближенного решения этих задач. Исследованиям в области алгоритмов для задачи о ширине графа посвящены работы [30,34,36,40,44,45,51-53,67,72,73,76]. В работах [29,32,33,41,54,56, 62,70,74,75] описываются некоторые классы графов, для которых задача о ширине может быть решена за полиномиальное время. Заметим, что задача о ширине остается TVP-трудной даже для графов достаточно простой структуры - деревьев с максимальной степенью вершины 3 [45], а также для решеточных графов [38]. Граф называется решеточным, если множество его вершин - это подмножество множества Z2, и две вершины смежны тогда и только тогда, когда евклидово расстояние между ними равно единице.

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

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

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

Диссертация состоит из введения, трех глав, заключения и списка литературы.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Иванова, Светлана Диадоровна

Основные результаты работы заключаются в следующем.

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

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

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

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

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Иванова, Светлана Диадоровна, 2006 год

1. Архипенко М.Ю., Иванова С.Д., Колоколов АА., Нагорная З.Е. Автоматизация процесса размещения меховых полуфабрикатов в скрое изделия // Естественные и технические науки. - 2004. - N 4(13). -С. 269-274.

2. Батищев Д.И. Генетические алгоритмы решения экстремальных задач Учебное пособие. - Воронеж: Воронеж, гос. техн. ун-т, 1995. -69 с.

3. Головач П.А., Фомин Ф.В. Суммарная величина вершинного разделения и профиль графов // Дискретная математика. 1998. - Т. 10, N 1. - С. 87-94.

4. Гольдберг М.К., Клипкер И.А. Алгоритмы минимальной нумерации вершин дерева // Сообщения АН ГрССР. 1976. - Т. 81, N 3. - С. 553-558.

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

6. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. Новосибирск: Изд-во Ново-сиб. ун-та, 1996. - 167 с.

7. Еремеев А.В. Генетический алгоритм для задачи о покрытии // Дискрет. анализ и исслед. операций. 2000. - Сер. 2. - Т. 7, N 1. - С. 47-60.

8. Заблоцкая О. А., Колоколов А А. Вполне регулярные отсечения в булевом программировании // Управляемые системы. Новосибирск: Наука, 1983. - Вып. 23. - С. 55-63.

9. Забудский Г. Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы Новосибирск: Наука, 1990,- Вып. 30. - С. 35-45.

10. Забудский Г.Г. Задачи оптимального размещения объектов на линии с минимально допустимыми расстояниями Препринт АН СССР. Сиб. отд-ние ВЦ: Новосибирск. 1990. - 32 с.

11. Заозерская JI.A. Об одном алгоритме перебора//-классов для решения задачи о покрытии множества // Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск, 1998. - N.1. - С. 139-142.

12. Иванова С.Д. Некоторые полиномиально разрешимые случаи задачи о ширине графа Препринт. - Омск: "Полиграфический центр КАН", 2006. - 32 с.

13. Иванова С.Д. О задаче оптимальной нумерации вершин графа // Материалы Российской конф. "Дискретный анализ и исследование операций". Новосибирск, 2004. - С. 106.

14. Иванова С.Д. О сложности некоторых задач нумерации вершин графа // Материалы Всероссийской конф. "Проблемы оптимизации и экономические приложения". Омск, 2003.- С. 92.

15. Иванова С.Д. Об одном полиномиально разрешимом случае задачи о ширине графа // Материалы Всероссийской конф. "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 97.

16. Иванова С.Д. О ширине Т-образного наложения прямоугольных решеток // Прикладная математика и информационные технологии: Сб. науч. и метод, трудов. Омск: Изд-во ОмГТУ, 2005. - С. 38-51.

17. Иванова С.Д. Ширина решеточных графов специальной структуры // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск, 2005. - Т. 1. -С. 485-490.

18. Иванова С.Д., Колоколов А.А. Оценки мощности L-накрытий для задачи о ширине графа // Омский научный вестник. 2006. -N 4(38). - С. 68-71.

19. Иорданский М.А. Оптимальные нумерации вершин графов // Мат. вопросы кибернетики. 2001. - Вып. 10. - С. 83-102.

20. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании j j Сиб. журн. исслед. операций. 1994. - T.l, N 2. - С.18-39.

21. Колоколов А.А., Девятерикова М.В. Анализ устойчивости L-разбиения в конечномерном пространстве // Дискретный анализ и исследование операций. Новосибирск: ИМ СО РАН, 2000. - Сер.2.- N 2.- С. 47-53.

22. Колоколов А.А., Нагорная З.Е., Иванова С.Д. О некоторых задачах проектирования изделий сложной структуры // Материалы Российской конф. "Дискретный анализ и исследование операций". Новосибирск, 2002. - С. 243.

23. Лепин В.В., Задача о профиле матриц и графов Препринт АН БССР. - Минск: Изд-во ин-та математики, 1986 - N 33(269).

24. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа. -Томск: НТЛ, 1997. 396 с.

25. Попков В.К. Математические модели связности. 4.2. Гиперграфы и гиперсети. Новосибирск: Изд-во ИВМиМГ СО РАН, 2001. - 180 с.

26. Adolfson D., Ни Т.С. Optimal linear ordering // SIAM J. Appl. Math.- 1973. V. 25, N 3. - P. 403-423.

27. Assman S.F., Peck G.W., Syslo M.M., and Zak J. The bandwidth of caterpillars with hair of lengths 1 and 2 // SIAM J. on Algebraic and Discrete Meth. 1981. - V. 2. - P. 387-393.

28. Blum A., Konjevod G., Ravi R., and Vempala S. Semi-definite relaxations for minimum bandwidth and other vertex-orderind problems // Theoretical Computer Science. 2000. - V.235, N 1. - P. 25-42.3137

29. Chinn P.Z., Chvatalova J., Dewdney A.K., Gibbs N.E. The bandwidth problem for graphs and matrices a survey // J. Graph Theory. - 1982. - V. 6. - P. 223-254.

30. Chinn P.Z., Lin Y., Yuan J., Williams K. Bandwidth of the composition of certain graph powers // Ars Combinatoria. 1995. - V. 39. - P. 167-173.

31. Chvatalova J. Optimal labelling of a product of two paths // Discrete mathematics. 1975. - 11. - P. 249-253.

32. Cuthill E., McKee J. Reduction the bandwidth of sparse symmetric matrices // Proc. of 24th Nat. Conf. ACM, 1969. P. 157-172.

33. Davis L. Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, 1991. - 371 p.

34. Dueck G.H., Jeffs J. A heuristic bandwidth reduction algorithm // J. Combinatorial Mathematics and Combinatorial Computing. 1995. -V. 18. - P. 97-108.

35. Dfaz J., Gibbons A.M., Paterson M.S., Toran J. The Minsumcut problem //In Algorithms and Data Structures, F. Dehen, R. J. Sack, and N. Santoro, Eds. Lecture Notes in Computer Science, 1991. V. 519. - P. 65-79.

36. Dfaz J., Penrose M.D., Petit J., Serna M.J. Approximating layout problems on random geometric graphs // J. Algorithms. 2001. - V. 39, N 1, P. 78-116.

37. Diaz J., Penrose M.D., Petit J., Serna M.J. A survey on graph layout problems // ACM Computing Surveys. 2002. - V.34, N 3. - P. 313-356.

38. Dunagan J., and Vempala S. On Euclidian embedclings and bandwidth minimization //In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Lecture Notes in Computer Science. 2001. - V. 2129. - P. 229-240.

39. Eitner P.G. The bandwidth of the complete multipartite graph // Presented at the Toledo Symposium on Applications of Graph Theory, 1979.

40. Ellis J., Sudborough I. H., and Turner J. The vertex separation and search number of a graph // Information and Computation. 1979. -V. 113. - P.50-79.

41. Eremeev A.V. A Genetic Algorithm with a Non-Binary Representation for the Set Covering Problem // Proc. of Operations Research: Springer Verlag, 1999. P. 175-181.

42. Feige U. Approximating the bandwidth via volume respecting embeddings // J. Comput. Syst. Sci. 2000. - V. 60, N 3. - P. 510539.

43. Garey M.R., Graham R.L., Johnson D.S., Knuth D.E. Complexity results for bandwidth minimization // SIAM J. Appl. Math. 1978. - V. 2. - P. 477-495.

44. Garey M.R., Johnson D.S., Stockmeyer L. Some simplified NP-complete graph problems // Theoretical Computer Science. 1976. - V. 1. - P. 237-267.

45. Gavril F. Some NP-complete problems on graphs //In Proc. of 11th Conf. on Information Sciences and Systems: Johns Hopkins University, Baltimore, 1977. P. 91-95.

46. Gibbs N.E., Poole W.G., and Stockmeyer P.K. An algorithm for reducing the bandwidth and profile of a sparse matrix // SIAM J. Num. Anal. -1976. V. 13, N 2. - P. 236-250.

47. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning Reading: Addison Wesley, 1989. - 412 p.

48. Goldberg D.E. and Lingle R. Alleles, Loci and the Travelling Salesman Problem // Proc. of an International Conference on Genetic Algorithms, Lawrence Erlbaum Associates (Hillsdale), 1985.

49. Gupta A.: Improved bandwidth approximation for trees and chordal graphs // J. Algor. 2001. - V. 40, N 1. - P. 24-36.53.54