|
本文的研究主旨在於探討一維空間中的不定長線段或多維空間中一組大小
相同且各邊平行於一座標軸的正方体,我們稱之為一致性的定向正方体
(congruent homothetic cubes ), 從中選取一組互不相交之線段或正方
体子集, 使其体積為最大的最佳化演算法( optimal algorithm), 以及求
取最大下界的演算法. 1947年R. Rado.曾經提出在n 維的空間中, 若有
m 個大小相同的定向正方体所組成的有限非空集合S, 可以從集合S中選出
子集合S', 其中S'中的正方体均互不相交. 此時,S'的体積總合至少可為
S 的(1/2)^n. 當時R. Rado. 並未討論如何選取 S' 使得S'之體積為最大
的 最佳化問題.本論文中我們將討論其最佳化的問題及其相關問題. 首
先, 我們定義一些本文中所談論之名詞, 如覆蓋問題, 下界等等, 再介紹
一維空間中線段的覆蓋問題並利用一時間複雜度為O(m^2)之演算法
OPTIMAL LINECOVER解決其最佳化問題. 進而, 利用演算法OPTIMAL COVER
解決多維空間中的正方体覆蓋最 佳化問題. 本論文中亦介紹求覆蓋總面
積的方法和一含最大下界之可行解求法.一般來說 TSP 問 題(Traveling-
Salesman Problem ) 是屬於 NP-complete 的問題, 若將TSP 問題加上座
標即為ETSP 問題, 該問題亦仍是 NP-Complete 問題. 但 Cormen,
Leiserson 和Rivest[2]中曾指出若利用J. L. Bentley所提的方式將
ETSP 的問題限制為 bitonic tours (即整個 tours 強制起於最左邊的點
並由左往右到達最右邊的點再往左回到最左邊的點) 則TSP便成為 O(
m^2) 的問題.我們試圖將覆蓋問題歸納為 P class, 但僅知一維空間中之
覆蓋問題屬於P class. 對於其延申的 0/1 Knapsack 問題, 如 3.3 所
述,若$0/1$ Knapsack 問題有了座標的限制則使0/1 Knapsack 問題由NP-
complete變為 O(m^2) 的問題.
|