АЛГОРИТМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА В ЗАДАЧЕ ВИЗУАЛИЗАЦИИ ГРАФА

  • Маргарита Алексеевна Костина Институт экологии Волжского бассейна РАН
  • Елена Анатольевна Мельникова Тольяттинский государственный университет
Ключевые слова: граф, визуализация, метод имитации отжига, генетические алгоритмы, критерии качества раскладки графа

Аннотация

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

Биографии авторов

Маргарита Алексеевна Костина, Институт экологии Волжского бассейна РАН
старший лаборант Института экологии Волжского бассейна РАН
Елена Анатольевна Мельникова, Тольяттинский государственный университет
кандидат физико-математических наук, доцент кафедры «Прикладная математика и информатика»

Литература

1. Апанович З. От рисования графов к визуализации информации // Институт систем информатики им. А. П. Ершова СО РАН. Режим доступа: www.iis.nsk.su/files/ (дата обращения 13.10.2014).
2. Коротков М. Разработка и реализация алгоритма укладки диаграмм состояний // Computer technologies department. Режим доступа: www.rain.ifmo.ru (дата обращения 12.10.2014).
3. Иринеев А., Каширин В. Алгоритм плоской укладки графов // Computer technologies department. Режим доступа: www.rain.ifmo.ru (дата обращения 12.10.2014).
4. Касьянов В., Евстигнеев В. Графы в программировании: обработка, визуализация и применение. СПб., 2003. 1104 с.
5. Мельников Б., Эйрих С. Подход к комбинированию незавершенного метода ветвей и границ и алгоритма имитационной нормализации // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. 2010. № 1. С. 35–38.
6. Многокритериальная оптимизация: математические аспекты / Б.А. Березовский [и др.]. М., 1989. 126 с.
7. Мельников Б.Ф. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ. 2006. № 3. С. 32–42.
8. Мельникова Е.А., Сайфуллина Е.Ф. Подход к проверке изоморфизма графов с помощью построения инвариантов // Вектор науки Тольяттинского государственного университета. 2013. № 1. С. 113–120.
Опубликован
2014-09-30
Выпуск
Раздел
Естественные науки

Наиболее читаемые статьи этого автора (авторов)