多維度背包問題之線性搜尋演算法

Abstract

背包問題(Knapsack Problem：KP)是作業研究領域中相當著名的問題 。然而，背包問題最佳解之獲得是NP-hard的問題，如果以窮舉法( Exhaustive Enumerations)來求解，一個有n個項目的背包問題，將需要 計算O(2^n)次; 尤其當項目甚大時（例如n=60， ），欲求得背包問題之 最佳解，是相當耗時的。 Yang於1992提出線性搜尋演算法（Linear Search Algorithm），求解一維度背包問題;其原理是依據，若有一個項 目所使用的成本較低(Cj)，或者是它所帶來的利益(Pj)較高，或者是每單 位成本所帶來的利益(Pj/Cj)較高，則此項目進入最佳解集合的機率也就 較高。 本研究加入準則Pj-Cj於Yang的線性演算法中，以改良線性搜 尋演算法之績效。並進一步將線性搜尋演算法運用在多維度背包問題之求 解上。經由電腦大量的模擬驗證，本研究獲致以下結論：(1)準則Pj-Cj的 加入，對於線性搜尋演算法的績效，並無顯著的提昇。(2)對於一維度背 包問題，本研究的模擬結果顯示，線性搜尋演算法有93%以上 的機率可 以找到最佳解。(3)對於多維度背包問題，線性搜尋演算法的績效雖然沒 有一維度背包問題來得 好，但模擬結果顯示，仍有82%以上的機率可以 找到最佳解。(4)無論一維度或多維度背包問題，線性搜尋演算法即使無 法找到最佳解，其遺 漏最佳解項目的平均個數亦不超過兩個。 Knapsack Problem is a well-known problem in Operation Research. However, Knapsack Problem is a NP-hard problem . If we solve Knapsack Problem by Exhaustive Enumeration , a problem with 60 items will need O(2^n) computation time. It is time- consuming to solve a Knapsack Problem,especially when n is large . Yang proposed Linear Search Algorithm to solve One- dimensional Knapsack Problem in 1992. The philosophy behind Linear Search Algorithm is that if an item with lower cost ( Cj ) or with higher profit ( Pj ) or with higher profit per cost ( Pj / Cj ), it will have a higher probability to get into the optimal solution set.This thesis adds a new criteria Pj-Cj into Yang's Linear Search Algorithm in order to improve the performance of Linear Search Algorithm . Furthermore, this thesis try to solve Multi-dimensional Knapsack Problem by Linear Search Algorithm. By verifying a large amount of cases , this research gets some conclusions listed below:1. It is no obvious improvement for the performance of Linear Search Algorithm by adding the criteria Pj-Cj.2. The results of computer simulation in this research show that the probability to find the optimal solution of One-dimensional Knapsack Problem is more than 93% by Linear Search Algorithm.3. For Multi-dimensional Knapsack Problem , the performance of Linear Search Algorithm is not as goos as that of One-dimensional Knapsack Problem; however, by using Linear Search Algorithm , the probability to find the optimal solution is still more than 82%.4. For either One- dimensional or Multi-dimensional Knapsack Problem , even if Linear Search Algorithm can't find the optimal solution , it won't loss more than two optimal solution items in average.