У меня есть алгоритмическая проблема, в которой я получил матрицу переноса между множеством состояний. Следующий шаг состоит в том, чтобы показать его, но он очень большой, поэтому мне нужно сделать некоторые сокращения на нем. В частности, он содержит много симметрии. Ниже приведены некоторые примеры того, сколько узлов можно устранить с помощью простых наблюдений.
Мой вопрос заключается в том, есть ли алгоритм для эффективного устранения симметрии в орграфах, подобно тому, как я сделал это вручную ниже.
Во всех случаях исходный вектор имеет одинаковое значение для всех узлов.
В первом примере мы видим, что 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)]
Приветствуются любые предложения или ссылки на документы.
