动态规划算法在基于子区间消除的随机点定位问题中的应用

• 作者: 江文 王伊凡 葛昊
• 来源期刊: 计算机应用研究
• 关键词: 随机点定位 子区间消除 动态规划 判决方程法 时间复杂度
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 339-342
• 页数: 4页
• 分类号: TP301.5
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2016.02.004

摘要

针对原有基于判决方程的子区间消除算法中所存在的判决结果与决策表不相符,以及当子区间划分规模增大时运行时间呈平方次增长的问题,提出了一种全新的基于动态规划的子区间消除算法.新算法充分利用动态规划在多阶段决策问题中的卓越性能,将子区间的消除问题划分为合理性判断和新区间生成两部分,这两个部分均可以利用动态规划中子问题分割的思想来解决;证明了通过解决这些子问题可以构造得到原问题的最优解,分析了算法的时间复杂度和空间复杂度.为了检验新算法的性能,从理论和实验两种维度进行了新旧两种算法的对比,实验结果表明,该方法大大降低了算法的时间复杂度,有效克服了子区间规模增大所导致的问题,提高了算法的灵活性和运行速度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王伊凡	上海交通大学电子信息与电气工程学院	3	9	1.0	3.0
2	葛昊	上海交通大学电子信息与电气工程学院	2	8	1.0	2.0
3	江文	上海交通大学电子信息与电气工程学院	3	82	2.0	3.0