Блог

Существует ли алгоритм, который принимает ориентированный граф в качестве входных данных, а на выходе дает минимальное количество ребер для «разрыва», чтобы предотвратить циклы?

В качестве примера, циклы на приведенном выше графике:

• A, B, C, D
• A, B, E
• E, G, H, F

И минимальное количество ребер для разрыва всех из них:

• 1. A — B, разрывает 2 цикла
• 2. Например, разрывает 1 цикл

Это становится более сложным, когда циклы вложены друг в друга и имеют общие ребра.

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

Я попробовал несколько методов, и все они различаются количеством ребер, которые они ломают — я ищу минимально теоретически возможный.

Существует ли установленный алгоритм, который делает это?

Это задача NP-жесткого минимального набора дуг обратной связи. Википедия не указывает на точный алгоритм для графов малого и среднего размера, поэтому позвольте мне предложить его.

Используя библиотеку решателей целочисленного программирования, такую как OR-Tools, мы формулируем целочисленную программу с переменной 0-1 для каждой дуги, где 0 означает сохранение дуги, а 1 означает удаление дуги. Цель состоит в том, чтобы минимизировать сумму этих переменных.

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

1. Решите целочисленную программу (изначально, без ограничений).
2. Используйте поиск по ширине, чтобы найти кратчайший цикл в сохраненных ребрах, если он есть.
3. Если цикл существует, добавьте ограничение, что сумма соответствующих переменных должна быть больше или равна единице, затем вернитесь к шагу 1. В противном случае текущее решение является оптимальным.