Построение алгоритмов ортогонального представления графа с указанными портами рёбер

• Автор: Ворожцов, Артём Викторович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 129 с. : ил.

Оглавление
Введение

1 Обзор задач и алгоритмов теории представления графов

1.1 Ссылки на базовые алгоритмы и ключевые работы

1.2 Компьютерные системы.

Система vi.

Библиотека алгоритмов и системы у , .

1.3 Задача поиска оптимального линейного порядка.

Основные понятия и формулировка ключевых задач.

Обзор приближенных алгоритмов решения задач .

2 Человеческие методы решения сложных задач

2.1 Базовые составляющие алгоритмов решения сложных задач . .
Метод ivi разделяй и властвуй
Метод распараллеливание
Метод ii отбор лучших
Метод локальные улучшения, жадные алгоритм,
Метод огрубление
Метод введение макрообъектов.
Метод метасистемные переходы в программировании .
2.2 Инструментарий для ЛРпрограммировапия.
3 Задача ортогонального представления графа с портами
3.1 Общая задача плоского ортогонального представления графа .
3.2 Задача представления графа с заданными портами рбер
3.3 Сводимость к .
4 Эвристические алгоритмы решения задачи
4.1 Идеи решения.
4.2 Схема основного алгоритма
4.3 Метод ранжирования последовательными улучшениями
4.4 Метод ранжирования на основе физической модели.
4.5 Метод выделения каркаса графа
4.6 Спектральные методы ранжирования.
4.7 Задача проведения рбер
4.8 Задача выпрямления рбер
4.9 Примеры работы алгоритма .
4. Реализация алгоритмов.
5 Методы анализа приближнных алгоритмов
5.1 Сила алгоритма и мера зависимости сил двух алгоритмов .
5.2 Понятия наджности и полезности алгоритмов
5.3 Результаты сравнительного анализа.
6 Задача и вычислительная сложность
6.1 Задача о лидере два метода ранжирования.
6.2 Модель Естественный отбор.
6.3 Модель Обмен товаровI
6.4 Ранжирование по вычислительной сложности .
Заключение
Список литературы


Глава 5 посвящена тонким моментам, возникающим при этом переходе, методам сравнения приближенных алгоритмов и методам оценки сложности приближенного решения JfV-сложных оптимизационных задач. В частности, в этой главе введены понятия надёжности и полезности алгоритма, и приведены качественные результаты, демонстрирующие эффективность “сложения” различных алгоритмов решения задачи OOGLP. Приведены диаграммы сложения алгоритмов на плоскости с координатами (надёжность, полезность). В главе G исследуется проблема определения понятия сложности вычислений. Есть два важных момента, которые связывают эту фундаментальную проблему с темой диссертации. Вопрос построения сложностного порядка на множестве вычислимых функций можно сформулировать в терминах задачи OLA — задачи поиска оптимального линейного порядка вершин графа с взвешенными ребрами, где веса ребер характеризуют меру доминирования одной вершины над другой. В работе дан абстрактный подход к определению этой меры (действительного положительного числа), который имеет довольно большую область применения (сравнение сложности функций, сравнение пропускных способностей информационных каналов, ёмкость Шеннона графов и др. Один из важнейших результатов состоит в том, что неоднозначность понятия сложности вычислений (зависимость от выбора исполнителя и сложностной характеристики требуемой памяти, времени вычисления, размера “программы” для исполнится и др. Эта тема впервые была рассмотрена в магистерской работе автора []. Глава 1. Важнейшие области приложения теории представления графов — это проектирование интегральных схем (БИС), разводка печатных плат и визуализация сложных структур [, , , , , ]. К последней области относится рассматриваемая в работе задача. Она охватывает такие случаи как, визуализация структуры компьютерных систем, визуализация бизнес процессов в виде IDEF-диаграмм [], создание наглядных организационных схем. Разработано много алгоритмов, которые находят оптимальные представления графов (Graph Drawing, GD) для различных частных случаев. Большая часть из них решают задачу приближенно, то есть находят представления, на которых функция качества не достигает максимума, но достаточно близка к нему. В качестве функции штрафа за представление рассматривались площадь представления, число пересечений рёбер, число изгибов рёбер (для ортогональных представлений), сумма длин рёбер и др. Большой вклад в теорию представления графов на плоскости внёс Роберто Тамассия [] в конце -х годов. Тогда же был выделен круг полиномиально-разрешимых задач в области GD. Есть много работ, посвященных указанным задачам. Одна из этих задач близка к рассматриваемой в диссертации задаче и подробно рассмотрена в главе 3 (утверждение 3. Это задача о минимизации числа изгибов в ортогональном представлении графа без указанных портов рёбер. Она сводится к задаче поиска максимального потока в сети, которая решается за полиномиальное время. Есть аннотированная библиография работ по теме представления графов [7], написанная Тамассия совместно с Баттиста, Идесом и Толлисом. Её можно найти на домашней странице Тамассия (]. Там же можно найти библиотеку работ по ОВ. Многие задачи теории представления графов являются ЛЛР-сложными или имеют слишком сложный полиномиальный алгоритм (с полиномом высокой степени и множеством сложных технически моментов). Например, для задачи проверки графа на планарность найден сложный полиномиальный алгоритм, но при этом программисты не решаются его реализовывать и предпочитают пользоваться простыми эвристическими алгоритмами, корректность которых еще не доказана. Практика использования эвристических алгоритмов, для которых не получено точных математических оценок качества (надёжности) становится типичной в индустрии программирования. Это связано с попытками решать сложные задачи, и сложностью разрабатываемых для них алгоритмов, которые трудно анализировать математическими методами. Единственный обек-тивный метод анализа таких алгортмов — это сравнительный анализ на основе экспериментальных результатов.