14.09.2024 12:21
interesting-cs-math 1 1100 Источник

Аннотация

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

Вычислительная сложность алгоритма определяется как I \cdot O(S \cdot ???(?) \cdot M^2), где I – количество итераций алгоритма, S – размер популяции (задаётся пользователем), M – количество рёбер графа.[1]

Введение

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

Эволюционный алгоритм проще в реализации, чем любой другой классический алгоритм проверки планарности графа.

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

Определение. Неориентированным графом G называется пара G = (?, ?), где V – множество вершин, а E ⊂{{v, u}: v, u ∈ V} – множество рёбер.

Определение. Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра геометрически не пересекаются. Граф, изоморфный плоскому графу, называется планарным.[2]

Эволюционный алгоритм

Эволюционный алгоритм строит изображение графа с минимальным числом пересечений рёбер.

К недостаткам алгоритма можно отнести его асимптотическую сложность. Однако, на практике алгоритм находит оптимальное решение достаточно быстро.

К преимуществам данного алгоритма относятся простота реализации и возможность построения изображения планарного графа.

Описание эволюционного алгоритма

Кодирование решения

Каждая особь популяции представляет собой изображение (список координат вершин) графа на плоскости.

Инициализация

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

Fitness-функция

Fitness-функция определяется как количество пересечений рёбер графа на изображении.

Стратегия отбора

Выполним сортировку особей текущей и предыдущей популяций. Выберем 50% лучших особей из каждой.

Оператор скрещивания

Случайным образом выбираем два рисунка G1, G2 из популяции. Для каждой пары соответствующих вершин G1[i], G2[i] выполняем процесс скрещивания координат. Формула скрещивания координат:

x=x_1 \cdot \lambda + x_2 \cdot (1- \lambda),

y=y_1 \cdot \lambda + y_2 \cdot (1- \lambda),

где \lambda = \frac{1}{e}.

В процессе скрещивания координат случайным образом выбирается одно из 3-х направлений скрещивания:

1) ? = -?;

2) ? = 1 - ?;

3) ? = -?; ? = 1 - ? .

Оператор мутации

Случайно выбираем любую вершину графа и изменяем её координаты случайным образом (в пределах заданной области).

Результат работы программы
Результат работы программы
Результат работы программы
Результат работы программы

Заключение

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

Список литературы:

1. Проверка планарности графа. – Текст : электронный // Справочник от Автор 24 : [сайт]. – URL:https://spravochnick.ru/informatika/proverka_planarnosti_grafa/ (дата обращения: 20.06.2023).https://ru.wikipedia.org/wiki/Планарный_граф

2. Нина, Костюкова Проверка планарности графа / Костюкова Нина. – Текст : электронный // Курс: "Графы иих применение". Лекция 3: Представления о планарном графе : [сайт]. – URL:https://intuit.ru/studies/courses/58/58/info (дата обращения: 20.06.2023).

Комментарии (1)


  1. Asker1987
    15.09.2024 11:43
    #27294824

    1. Грубейшая ошибка - отсутствие ссылок. Ссылка на лекцию и статью в вики - не считается.

    2. Есть мастодонты в этой области, которые решали 100 и планарность графа и применяли генетические алгоритмы ко всевозможным графовым задачам - Курейчик, Гладков, Лебедев и т.д. У кого-то из них даже диссертация ровно по этой теме.

    3. Почему в определении сложности алгоритма число итераций вынесено за скобки из O-функции?

    4. Судя по расчетам есть неправильное понимание, что такое O-функция. Это зависимость числа операций от размера ВХОДНЫХ данных задачи. Настройки алгоритма не являются входными данными задачи.

    5. "Случайным образом выбираем два рисунка" - какие еще вдруг рисунки? вроде же точки кодировали.

    6. Нет графиков, таблиц, аналитики. Хотя бы график зависимости ЦФ от времени выполнения..

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

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

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

    По сути, невыполнение первого или даже 1-2 пунктов вызвало каскад проблем. Не нужно полагаться на вики и одну поверхностную лекцию.