Приближенная реализация набора минимальных обратных связей в Java

Question

Приближенная реализация набора минимальных обратных связей в Java

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

1

java graph implementation approximation

Источник

user81574 30 ноя '12 в 11:28

1 ответ

Решение

Другие вопросы по тегам java graph implementation approximation

user81574 25 фев '13 в 00:16 2013-02-25 00:16 · Accepted Answer · 2013-02-25 00:16

Похоже, что простейший приближенный алгоритм, который можно реализовать (но без гарантий минимальности), описан в этой статье:

Быстрая и эффективная эвристика для задачи о множестве дуг обратной связи, П. Идс, Х. Лин, У. Ф. Смит.

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