線性多重選擇性背包問題在網頁內容決選之應用

Abstract

隨著個人通訊的設備不斷的進步以及Internet的蓬勃發展，WWW的服務漸漸在日常生活中變得重要，透過WWW的服務，人們能夠獲取豐富的全球資訊。因為通訊設備的多樣化(如：個人電腦、掌上型電腦、個人數位助理、手機)，如何透過各種不同的通訊設備，有效率地來瀏覽網頁內容；且滿足不同使用者的偏好（Preference），這些就成為Internet的一個新議題。W3C近年提出了設備性能與偏好描述(Composite Capability/Preference Profiles, CC/PP)的標準，用以描述通訊時設備的性能與環境。透過這CC/PP的通訊協定，WWW使用者得以將通訊的配備、環境及個人偏好設定，傳送給網頁伺服器，網頁伺服器藉此得以挑選出適當的網頁內容傳回給瀏覽設備。在本論文中，我們架設一個能夠有效利用網路頻寬及使用者配備性能與偏好設定的Internet存取架構。本論文將網頁內容挑選的問題化成一個多重選擇背包問題，並利用動態規劃方法去挑選適合設備端瀏覽及網路頻寬的網頁內容，以減低網頁伺服器挑選網頁的運算處理時間，提供WWW資訊服務一個有效的解決方案。

In the recent year, Internet becomes very popular and everyone needs it to get the global information from the WWW. WWW client devices vary from low capacity wireless PDA to high performance desktop PC and networks rang from low speed modem links to high speed ATM backbones. This heterogeneity makes user to know the network constraints of different users. Composite Capabilities and Preference Profiles (CC/PP), proposed by W3C recently, is a standard of describing user agent’s capabilities and preferences, and in our early work, we designed a web content adaptation system, which can detect bandwidth dynamically and adapt various capabilities and preferences of clients based on CC/PP. In this thesis, we formulate the web content selection problem as a linear multi-choice knapsack problem (LMCKP). A dynamic programming is proposed to solve it. Then, the optimal solution of LMCKP is used to reduce the processing time of adaptive web server.