У меня есть алгоритмическая проблема, в которой я вывел матрицу передачи между многими состояниями. Следующим шагом является его возведение в степень, но оно очень большое, поэтому мне нужно сделать некоторые сокращения. В частности, он содержит много симметрии. Ниже приведены некоторые примеры того, сколько узлов можно устранить с помощью простых наблюдений.
Мой вопрос заключается в том, существует ли алгоритм для эффективного устранения симметрии в орграфах, аналогично тому, как я делал это вручную ниже.
Во всех случаях исходный вектор имеет одинаковое значение для всех узлов.
В первом примере мы видим, что b, c, d и e все получают значения от a и друг от друга. Следовательно, они всегда будут содержать одинаковое значение, и мы можем объединить их.
В этом примере мы быстро обнаружим, что график идентичен с точки зрения a, b, c и d. Также для их соответствующих sidenodes не имеет значения, к какому внутреннему узлу он присоединен. Следовательно, мы можем уменьшить график до двух состояний.
Обновление: Некоторые люди были достаточно разумны, не вполне понимая, что подразумевается под "матрицей передачи государства". Идея заключается в том, что вы можете разбить комбинаторную задачу на несколько типов состояний для каждого n в вашем повторении. Затем матрица расскажет вам, как получить от n-1 до n.
Обычно вас интересует только значение одного из ваших состояний, но вам также необходимо рассчитать остальные, чтобы вы всегда могли перейти на следующий уровень. Однако в некоторых случаях несколько состояний симметричны, то есть они всегда будут иметь одинаковое значение. Очевидно, что вычислять все это довольно бесполезно, поэтому мы хотим уменьшить граф, пока все узлы не станут «уникальными».
Ниже приведен пример матрицы переноса для приведенного графа в примере 1.
[S_a(n)] [1 1 1] [S_a(n-1)]
[S_f(n)] = [1 0 0]*[S_f(n-1)]
[S_B(n)] [4 0 1] [S_B(n-1)]
Любые предложения или ссылки на документы приветствуются.