[Алгоритмы] Выделение бесхордовых циклов из ненаправленного графа

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
14-Ноя-2020 05:31

Цитировать

Несколько лет назад мне пришлось погрузиться в данную тему по работе. Погуглив, я, к удивлению своему, не нашёл каких-то готовых решений. Да и до сих пор, в общем-то, ничего не видно. Поэтому пришлось разрабатывать тему с нуля.
Чтобы было понятно о чем речь, приведу простейший пример.

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

Для каждой вершины графа находим все смежные вершины и начинаем формировать цикл движением в сторону каждой смежной вершины поочередно.
Если число смежных вершин (исключая ту, с которой вошли) =0, то идём обратно, формируя цикл ---> п.5
Если число смежных вершин (исключая ту, с которой вошли) равно 1, то идём по ней, формируя цикл ---> п.5
Если число смежных вершин (исключая ту, с которой вошли) >=2, то ищем самое правое ответвление (путем нормализации векторов и их перемножения), и идём по нему, формируя цикл ---> п.5
Анализируем — вернулись в начальную точку? Если нет, то ---> п.2
Если да, то завершаем формирование цикла и осуществляем проверки.
Ищем в цикле повторяющиеся вершины, если такие есть, то удаляем все вершины между ними, оставляя только одну повторяющуюся.
Ищем в числе уже сформированных циклов совпадающие с данным циклом, и если есть, то прерываем формирование цикла и переходим на ---> п.1 (проверять надо с учетом всех сдвигов и направлений)
Ещё раз проходим по циклу и смотрим на левые ответвления от него. Найдя такие ответвления, для каждого организуем поиск в ширину (или в глубину, неважно). Если при этом мы попадаем в конце концов на вершину сформированного цикла (кроме текущего), то прерываем формирование цикла и переходим на ---> п.1
Записываем цикл, и переходим на поиск нового ---> п.1

Укрупненный псевдокод:

Сначала для проверки алгоритма строились всё более и более изощрённые графы.

или

и, в конце концов, он был протестирован на всех реальных изыскательских графах типа такого:

Не думаю, что он оптимальный, но на данный момент (года 3 уже) он работает без сбоев и нареканий.
Код не привожу, вряд ли кому это будет интересно, да и вырвать кусок будет сложно, так как это всего лишь одна небольшая часть работы.
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_algoritmy (Алгоритмы), #_grafy (графы), #_algoritmy_na_grafah (алгоритмы на графах), #_algoritmy (
Алгоритмы
)

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 23-Ноя 00:47
Часовой пояс: UTC + 5