- PVSM.RU - https://www.pvsm.ru -
Несколько лет назад мне пришлось погрузиться в данную тему по работе. Погуглив, я, к удивлению своему, не нашёл каких-то готовых решений. Да и до сих пор, в общем-то, ничего не видно. Поэтому пришлось разрабатывать тему с нуля.
Чтобы было понятно о чем речь, приведу простейший пример.
Граф очень простой, и для такого рода графов несложно придумать алгоритм, выделяющий бесхордовые циклы (т.е. циклы, которые не имеют самопересечений, и которые нельзя разбить на более мелкие). Проблема в том, что графы могут быть гораздо более хитрыми, и все случаи надо предусмотреть. Путём обдумывания, написания кода, проб и ошибок, в конце концов и родился алгоритм, которые сейчас работает на благо инженерных изыскателей.
Текстовое описание:
Укрупненный псевдокод:
Сначала для проверки алгоритма строились всё более и более изощрённые графы.
или
и, в конце концов, он был протестирован на всех реальных изыскательских графах типа такого:
Не думаю, что он оптимальный, но на данный момент (года 3 уже) он работает без сбоев и нареканий.
Код не привожу, вряд ли кому это будет интересно, да и вырвать кусок будет сложно, так как это всего лишь одна небольшая часть работы.
Автор: Владимир
Источник [1]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/358816
Ссылки в тексте:
[1] Источник: https://habr.com/ru/post/528002/?utm_source=habrahabr&utm_medium=rss&utm_campaign=528002
Нажмите здесь для печати.