二段式演算法在電腦通訊網路中資料庫佈設問題上之運用

Abstract

近年來電腦通訊網路的大幅成長有目共睹，藉由電腦通訊網路使得軟體、硬體及資 料庫等資源得以共享。在電腦通訊網路的設計與管理中，一項重要的課題就是如何 佈設資料庫以及資料處理中心，在一定的服務水準前題下，期望以最低的成本提供 正常的資料處理服務。所考慮的成本包括硬體設備的成本、資料傳輸成本以及資料 存取、處理成本等。為節省資料傳輸的成本，系統的設計將增加資料處理中心及資 料庫的設立，但此時硬體的設備成本亦相對增加。所以基本上電腦通訊網路中資料 庫佈設問題是各類成本間取捨的問題，此問題以數學模式表示為NP-complete 的整 數規劃的問題，沒有多項式時間內的求解方式。針對此類問題，Fisher及Hochbaum 曾在Database Location in Computer Network 一文中以Lagrangian Relaxation 及Subgradient Optimization的方式求解，但其解之上、下限之差距仍在百分之二 十至三十間。本研究以〝二段式〞演算法在較快的運算速度下求得較佳的結果，實 驗測試的網路多達100 個節點，而所有結果顯示，上、下限之差距皆在百分之三之 內。