优化问题,我需要为平面图构建所有切片树。我的主要问题是,我没有被告知如何创建这样的平面图。
感谢您的帮助。
最佳答案
http://cas.ee.ic.ac.uk/people/gac1/Synthesis/Lecture16.pdf
提供了我理解问题所需的一切。
从一组起始矩形创建一个随机平面图。本质上是您的切片树或带有随机运算符的波兰表达式(V 表示垂直切割,H 表示水平切割)和矩形(用字母表示)。内部节点的数量为 L-1,其中 L 是外部叶子的数量。
让我们说这个波兰语表达式:712H3H645HVHV
要优化平面图,请尝试从允许的移动中改进它:
Swap two adjacent operands (leaf nodes) in the Polish expression.
Take a chain of consecutive operators, e.g. “HVHV”, and complement it, e.g. “VHVH”.
- Swap an adjacent operator and operand. (But make sure still a skewed tree!)
要知道解决方案是否有所改进,您需要计算面积:
- Height( XYH ) = max( Height( X ), Height( Y ) )
- Width( XYH ) = Width( X ) + Width( Y )
- Height( XYV ) = Height( X ) + Height( Y )
- Width( XYV ) = max( Width( X ), Width( Y ) )
关于algorithm - 构建切片树的算法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22213458/