@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00223194,
 author = {末吉, 璃子 and 有田, 正剛 and Riko, Sueyoshi and Seiko, Arita},
 book = {コンピュータセキュリティシンポジウム2022論文集},
 month = {Oct},
 note = {Knapsack 問題は古くからから考えられてきた NP 完全問題である．近年，深層強化学習を用いて最適化問題へ応用する研究が増えている．2016 年には，Pointer network を用いた TSP の解法も提案され，更に Knapsack 問題の解法も検討．本研究では，深層強化学習ベースの解法がトラップドア付の Knapsack 問題に対してどこまで解く事ができるのか検証する．手法としては Pointer network と強化学習を使用して Knapsack 問題の最適解を近似する．トラップドアは村上らの研究による超増加性と偶奇性を組み合わせた複合トラップドア，さらにそれらにモジュラ変換を施したものそしてランダム性と超増加性と偶奇性単体でも比較した．本論文では，その提案手法アーキテクチャ及び実験結果を示し，今後の展望について考察する．, The Knapsack problem is an NP-complete problem that has been considered for a long time. In 2016, a method for solving the TSP using a pointer network was proposed, and a method for solving the Knapsack problem was also studied. In this study, we verify to what extent deep reinforcement learning-based solution methods can solve the Knapsack problem with trapdoors. The method uses a pointer network and reinforcement learning to approximate the optimal solution of the Knapsack problem. The trapdoor is a composite trapdoor combining hyper-increasing and even-oddness, which was studied by Murakami et al. and then modulo transformed, and randomness, hyper-increasing, and even-oddness alone. In this paper, we present the proposed method architecture and experimental results, and discuss future prospects.},
 pages = {1012--1019},
 publisher = {情報処理学会},
 title = {Pointer networkを用いたトラップドア付きKnapsack問題の解法},
 year = {2022}
}