让神经网络学会解背包问题，提升对更大规模实例的泛化能力
KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems
- 模仿动态规划两阶段流程，分步构建状态表并回溯解
- 在更大规模实例上表现优于直接预测最优子集的基线方法
- 适合研究神经算法推理与组合优化结合的学者参考
神经算法推理（NAR）旨在通过模仿经典算法，将算法逻辑嵌入神经网络。本文介绍我们构建神经算法推理模型以求解背包问题——一种连接经典算法与组合优化的伪多项式问题，该问题未被标准NAR基准覆盖。所提模型遵循背包问题的两阶段范式：先构建动态规划表，再从中重构解。通过动态规划监督中间状态，该方法在更大规模实例上展现出比直接从输入预测最优子集的基线模型更强的泛化能力。
原文摘要 · Abstract (English)
Neural algorithmic reasoning (NAR) is a growing field that aims to embed algorithmic logic into neural networks by imitating classical algorithms. In this extended abstract, we detail our attempt to build a neural algorithmic reasoner that can solve Knapsack, a pseudo-polynomial problem bridging classical algorithms and combinatorial optimisation, but omitted in standard NAR benchmarks. Our neural algorithmic reasoner is designed to closely follow the two-phase pipeline for the Knapsack problem, which involves first constructing the dynamic programming table and then reconstructing the solution from it. The approach, which models intermediate states through dynamic programming supervision, achieves better generalization to larger problem instances than a direct-prediction baseline that attempts to select the optimal subset only from the problem inputs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。