N车探险问题的一种Rollout算法  

A Kind of Rollout Algorithm for N Vehicles Exploration Problem

作　　者：李晓亚[1] 

机构地区：[1]中国科学院数学与系统科学研究院应用数学研究所,北京100190

出　　处：《应用数学学报》2014年第1期99-108,共10页Acta Mathematicae Applicatae Sinica

基　　金：中国科学院管理;决策与信息系统重点实验室支持项目

摘　　要：本文主要对N车探险问题进行研究,通过建模将该问题转化为一个复杂度为O(n!)的排序问题.将N车探险问题引入动态规划的框架中,继而对该问题进行模型改建,将其转化为一个动态规划模型.引入两个基本启发式算法对其进行求解,在此基础上,提出并构建了一种rollout算法.这种rollout算法的设计源于动态规划中的策略迭代思想,花费较少的计算时间的代价,可以大大改善基础启发式算法的计算效果。文章最后给出计算实例.This paper studies a kind of exploration problem with N vehicles, by modeling, the author transforms the N vehicles exploration problem to a sequential decision problem with an exponential computational time complexity of O（n!）. In particular, the author embeds the problem within a dynamic programming framework, and introduces two types of heuristic algorithms. Based on which, the author proposes a kind of rollout algorithm which is related to notions of policy iteration, and improves the performance of the base heuristic algorithm by costing a reasonable time complexity. Numerical examples are stated at last.

关 键 词：N车探险问题 基本启发式算法 ROLLOUT算法 动态规划 

分 类 号：O221.3[理学—运筹学与控制论]