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

Dynamic programming method for sub-interval elimination-based stochastic point location problem

作　　者：王伊凡[1] 葛昊[1] 江文[1] 

机构地区：[1]上海交通大学电子信息与电气工程学院,上海200240

出　　处：《计算机应用研究》2016年第2期339-342,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(61271316)

摘　　要：针对原有基于判决方程的子区间消除算法中所存在的判决结果与决策表不相符,以及当子区间划分规模增大时运行时间呈平方次增长的问题,提出了一种全新的基于动态规划的子区间消除算法。新算法充分利用动态规划在多阶段决策问题中的卓越性能,将子区间的消除问题划分为合理性判断和新区间生成两部分,这两个部分均可以利用动态规划中子问题分割的思想来解决;证明了通过解决这些子问题可以构造得到原问题的最优解,分析了算法的时间复杂度和空间复杂度。为了检验新算法的性能,从理论和实验两种维度进行了新旧两种算法的对比,实验结果表明,该方法大大降低了算法的时间复杂度,有效克服了子区间规模增大所导致的问题,提高了算法的灵活性和运行速度。The decision formula based sub-interval elimination algorithm has two major problems to be solved. One is the in- consistency with the decision table results, the other is its difficulty in dealing with the massive sub-interval problems. To solve these problems, this paper proposed a new sub-interval elimination algorithm based on dynamic programming. This algorithm took advantage of dynamic programming superior property in multi-stage decision problem. Based on dynamic programming, it divided the sub-interval elimination problem into two parts ： reasonable judgment and new interval generation, which could use dynamic programming to solve. This paper also proved the reasonableness of this sub-problem division, and analyzed the time and space complexity. Meanwhile, in order to test the performance of this new algorithm, this paper made comparisons in both theoretical and experimental aspects. The simulation results show that the proposed method is able to reduce the algorithm＇ s time complexity, overcome the problem of increasing the size of the sub-interval, and improve the flexibility and speed of the algorithm.

关 键 词：随机点定位 子区间消除 动态规划 判决方程法 时间复杂度 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]