以B*樹處理邊界條件限制下的擺置問題之研究

Abstract

在這篇論文中，我們研究了在邊界條件限制下的擺置問題，並利用B*樹的表示方法，針對非切割平面結構（non-slicing structure）的結構發展出一simulated annealing演算法。B*樹的表示方法已經被證明是一有彈性且有效率的表示方法，它利用二元樹的結構有效地表達出幾何位置的資訊。利用限定那些有邊界條件限制的模組維持在B*樹中特定的位置，就可以產生一棵適當的B*樹來得到一合理的擺置方式（feasible placement），以使有邊界條件限制的模組都被放置在邊界旁。實驗結果顯示，和利用sequence-pair表示法的方式比較，我們的演算法可以得出比較好的結果。

In this thesis, we study the placement problem with boundary constraints and develop a simulated annealing based algorithm using the B*-tree representation for non-slicing structure. The B*-tree has been shown a flexible and efficient representation conveying geometric information well in the binary tree structure. By restricting boundary-constrained modules in some particular positions in a B*-tree, an appropriate B*-tree is generated to get a feasible placement with all its boundary-constrained modules being placed along the boundaries. The experimental results show that our algorithm can obtain superior outcomes in contrast to the method using the sequence-pair representation.