大规模机组组合问题的量子近似动态规划

该文用量子近似动态规划解大规模机组组合问题。利用量子叠加态可表示海量信息的特性,把大规模的0-1机组组合状态用量子叠加态表示,将量子旋转门作为量子叠加态的搜索策略,实现了近似动态规划对海量机组组合状态空间的全局搜索。使用量子测量塌缩原理解Bellman方程,提高了方程的求解效率。用量子平均收敛概率改进迭代中断条件,避免了算法的过度迭代。10~1000机系统的计算结果表明:该文算法能有效地搜索大规模状态空间,产生解Bellman方程所必须的预决策状态;可在多项式时间内获取高质量的解,与外–内逼近法相比最优值的平均偏差小于1/100;所解系统的规模较传统动态规划法增加10倍以上,克服了"维数灾"问题。用量子计算理论克服近似动态规划遇到的状态空间搜索难等问题是可行的,算法具有广阔的应用前景。