文献

J-GLOBAL ID：201802269251356371   整理番号：18A1669691

0-1ナップサック問題のための期待効率に基づく発見的アルゴリズム

A HEURISTIC ALGORITHM BASED ON EXPECTATION EFFICIENCY FOR 0-1 KNAPSACK PROBLEM

著者 (2件)： ZHANG Lingling (Beihua Univ., Jilin, CHN) ,  LV Jianhui (Northeastern Univ., Shenyang, CHN)
資料名： International Journal of Innovative Computing, Information and Control  (International Journal of Innovative Computing, Information and Control)
巻： 14  号： 5  ページ： 1833-1854  発行年： 2018年10月 
JST資料番号： F1199A  ISSN： 1349-4198  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 0-1ナップサック問題(KP01)は古典的NP困難問題であり,それは実応用において重要な役割を果たす。本論文において,著者らは,KP01の近似解を得るために,期待効率,利益の増加率および改良貪法(EEII)に基づく発見的アルゴリズムを提案した。(i)貪欲法を用いていくつかの項目を選択し,ナップサックに入れる。(ii)残りの項目からどの項目をナップサックにいれるかを,期待効率戦略と利益戦略の増加率から決定する。(iii)期待効率の計算効率を向上させ,利益率を増加させるために,各項目の大きさを制限する。(iv)改良貪欲法を考案し,変動係数の観点から特別なKP01を解いた。計算実験は,(i)貪欲法近似アルゴリズム(GAA)と(ii)貪欲法と期待効率(GDEE)アルゴリズムによってEEIIを比較することによって行い,EEIIがKP01を解明するために良い性能を持つことを示した。(翻訳著者抄録)

シソーラス用語： *ナップサック問題 ,  *問題 ,  *計算機アルゴリズム ,  最適化問題 ,  アルゴリズム ,  最適化手法 ,  解
準シソーラス用語： *NP困難問題 ,  近似解 ,  発見的アルゴリズム ,  *貪欲法

分類 (1件)： 計算理論  (JB02000A)

引用文献 (32件)：

• H. Buhrman, B. Loff and L. Torenvliet, Hardness of approximation for knapsack problems, Theory of Computing Systems, vol.56, pp.372-393, 2015.
• G. Dantzig, Discrete variable extremum problem, Operations Research, vol.5, pp.266-277, 1957.
• S. Sahni, Approximate algorithms for the 0/1 knapsack problem, Journal of ACM, vol.22, pp.115-124, 1975.
• P. Toth, Dynamic programming algorithms for the zero-one knapsack problem, Computing, vol.25, pp.29-45, 1980.
• C. Bazgan, H. Hugot and D. Vanderpooten, Implementing an efficient fptas for the 0-1 multi-objective knapsack problem, European Journal of Operational Research, vol.198, pp.47-56, 2009.

タイトルに関連する用語 (3件)： ナップサック問題 ,  期待 ,  発見的アルゴリズム