矩形密鋪及其應用
「在格狀平面中用矩形以互不重疊的方式鋪滿(2D rectangle tiling problem)」為一NP-complete問題(Dani`ele Beauquier et al ,1995),目前多項式時間只能求出盡可能覆蓋最大面積的近似解。本研究所創的階梯演算法 stair algorithm 透過改變動態規劃紀錄狀態的方式,使狀態數大幅減少,進而改善求準確解的時間複雜度,也成功證明此演算法的正確性。本研究的演算法可被應用於平行計算中的負載平衡、積體電路設計等方面。隨後,本研究寫了一個互動展示品清楚呈現此演算法的功能。且以階梯演算法成功檢驗並比較 RTILE PROBLEM 的 7/3-approximation algorithm (Krzysztof Lorys and Katarzyna E. Paluch,2000 [4]) 與 11/5-approximation algorithm (Piotr Berman et al,2001[7])進行比較與分析。