構建切片樹的算法是什麼？

Question

優化問題，我需要爲平面佈局構建所有切片樹。我的主要問題是，我沒有指示如何創建這樣的平面佈局。

感謝您的幫助。

Answer 1

http://cas.ee.ic.ac.uk/people/gac1/Synthesis/Lecture16.pdf

提供了所有我需要了解的問題。

從矩形的起始集創建隨機平面佈置圖。基本上你的切片樹或波蘭語表達式用你的矩形（用一個字母來表示）用隨機運算符（V代表垂直切割，H代表水平切割）。內部節點的數量是L-1，其中L是外部葉子的數量。

比方說，這個波蘭表達式：712H3H645HVHV

要優化佈局規劃嘗試從允許的動作改進：

• 交換波蘭表達兩個相鄰的操作數（葉節點）。

• 取一連串連續的操作符，例如「HVHV」，並對其進行補充，例如「VHVH」。

• 交換相鄰的運算符和操作數。 （但要確保仍然是一個歪斜的樹！）

要知道，如果解決方案有所提高，你需要計算面積：

• 高度（XYH）= MAX（身高（ X），高度（Y））
• 寬度（XYH）=寬度（X）+寬度（Y）
• 高度（XYV）=高度（X）+高度（Y）
• 寬度（XYV）=最大（寬度（X），Wid th（Y））