У меня есть алгоритмическая проблема, в которой я получил передаточную матрицу между множеством состояний. Следующий шаг — возвести его в степень, но он очень большой, поэтому мне нужно сделать для него некоторые сокращения. В частности, он содержит много симметрии. Ниже приведены несколько примеров того, сколько узлов можно исключить с помощью простых наблюдений.
Мой вопрос заключается в том, существует ли алгоритм для эффективного устранения симметрии в орграфах, подобно тому, как я сделал это вручную ниже.
Во всех случаях начальный вектор имеет одинаковое значение для всех узлов.
В первом примере мы видим, что b, c, d и e получают значения от a и друг от друга. Следовательно, они всегда будут содержать одинаковое значение, и мы можем их объединить.
В этом примере мы быстро замечаем, что график идентичен с точки зрения a, b, c и d. Также для соответствующих боковых узлов не имеет значения, к какому внутреннему узлу он подключен. Следовательно, мы можем свести граф только к двум состояниям.
Обновление: некоторые люди были достаточно разумны, не совсем понимая, что имелось в виду под "матрицей передачи состояний". Идея здесь в том, что вы можете разделить комбинаторную задачу на несколько типов состояний для каждого 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)]
Любые предложения или ссылки на документы приветствуются.
