Вот небольшая программа, которая сначала обеспечивает базовую глубину, ациклический переход от любого узла к любому узлу, который можно изменить, поместить в цикл или распределить. Список можно поместить в статический собственный массив, используя шаблон с размером в качестве одного параметра, если известен максимальный размер набора данных, что сокращает время итерации и индексации.
е мне нуженбыстрый алгоритм подсчета количества ациклических путей в простом ориентированном графе.
Попросто Под графиком я имею в виду один без самоконтроля или нескольких ребер.дорожка может начинаться с любого узла и должен заканчиваться на узле, который не имеет исходящих ребер. Путьациклический если в нем дважды нет ребра
Мои графики (эмпирические наборы данных) имеют только от 20 до 160 узлов, однако некоторые из них содержат много циклов, поэтому будет очень много путей, и мой наивный подход просто не достаточно быстр для некоторых графиков. У меня есть.
В настоящее время я делаю «спуск» по всем возможным ребрам с помощью рекурсивной функции, отслеживая, какие узлы я уже посетил (и избегая их). Самое быстрое решение, которое у меня было до сих пор, было написано на C ++ и использует аргумент std :: bitset в рекурсивной функции, чтобы отслеживать, какие узлы уже были посещены (посещенные узлы отмечены битом 1). Эта программа запускается на образце набора данных за 1-2 минуты (в зависимости от скорости компьютера). С другими наборами данных это занимает больше дня, или, очевидно, намного дольше.
Образец набора данных:http://pastie.org/1763781 (каждая строка является парой ребер)
Решение для примера набора данных (первое число - это узел, с которого я начинаю, второе число - это число путей, начинающееся с этого узла, последнее число - это общее количество путей):http://pastie.org/1763790
Пожалуйста, дайте мне знать, если у вас есть идеи об алгоритмах с большей сложностью. Я также заинтересован в приближенных решениях (оценка числа путей с некоторым подходом Монте-Карло). В конце концов, я также хочу измерить среднюю длину пути.
Изменить: также опубликовано в MathOverflow под тем же заголовком, поскольку это может быть более уместным там. Надеюсь, это не противоречит правилам. Невозможно дать ссылку, так как сайт не разрешит более 2 ссылок ...