Перебирайте все деревья заданного размера
Я часто сталкиваюсь с проблемой проверки некоторых свойств деревьев (графовых) заданного размера грубой силой. У вас есть какие-нибудь хорошие трюки для этого? В идеале я хотел бы изучить каждый класс изоморфизма только один раз (но в конце концов, скорость-это все, что имеет значение).
Трюки с битами наиболее приветствуются, так как n обычно меньше 32 :)
Я прошу немного более совершенные алгоритмы, чем такие, как " цикл через все (n-1)-реберные подмножества и проверить, образуют ли они дерево " для деревьев на n узлах.
2 ответа:
Это в книге кнута "искусство компьютерного программирования", посвященной комбинаторным алгоритмам. Если я правильно помню, это упражнение там. Поскольку у него есть решения для этого, я указываю вам туда.
В некоторых гуглах появилось следующее описание алгоритма: http://www.cs.auckland.ac.nz/compsci720s1c/lectures/mjd/treenotes.pdf они адаптируют алгоритм для перечисления корневых деревьев к перечислению некорневых деревьев.
Очевидно, другие доказали, что для этого требуется только амортизированное постоянное время на дерево, и PDF показывает некоторые измерения производительности, демонстрирующие это.