| 对不确定规划中观测约简的进一步研究 |
| |
| 引用本文： | 饶东宁,蒋志华,姜云飞,朱慧泉.对不确定规划中观测约简的进一步研究[J].软件学报,2009(5). |
| |
| 作者姓名： | 饶东宁 蒋志华 姜云飞 朱慧泉 |
| |
| 作者单位： | [1]中山大学信息科学与技术学院软件研究所,广东广州510275 [2]暨南大学计算机系,广东广州510632 [3]School of Computingl National University of Singapore, Singapore |
| |
| 基金项目： | 国家自然科学基金No.60773201~~ |
| |
| 摘 要： | 从3个方面改进了不确定规划（non—deterministic planning，简称NOP）中的观测约简：一是如何找最小观测集合（minimal observation set，简称MOS），二是如何在观测代价不均等时找最优观测集合（iptimal observation set，简称OOS），三是如何找到容错的OOS．通过MOS问题和图论中的最小覆盖集问题（minimal set cover,简称MSC）的类似性，可证MOS是NP难的问题，还可参考MSC算法得出时间复杂性不超过O（2^mm^2）且不低于Ω（2^m-1）的算法，其中m是观测的个数．通过使用整数规划（integer programming，简称IP）技术，可找到OOS以及容错的OOS．可以证明，上述算法能够保证找到解，并且能够保证解的最优性．
|
| 关 键 词： | 智能规划 不确定规划 观测约简 最小观测集 最优观测集 容错 |
Further Research on Observation Reduction in Non-Deterministic Planning |
| |
| RAO Dong-Ning,JIANG Zhi-Hua,JIANG Yun-Fei,ZHU Hui-Quan.Further Research on Observation Reduction in Non-Deterministic Planning[J].Journal of Software,2009(5). |
| |
| Authors: | RAO Dong-Ning JIANG Zhi-Hua JIANG Yun-Fei ZHU Hui-Quan |
| |
| Affiliation: | Software Research Institute;School of Information Science and Technology;Sun Yat-Sen University;Guangzhou 510275;China;Department of Computer Science;Jinan University;Guangzhou 510632;China;School of Computing;National University of Singapore;Singapore |
| |
| Abstract: | This paper improves the methods of observation reduction in non-deterministic planning(NDP) in three aspects:in finding MOS(minimal observation set);in finding out the optimal observation set(OOS) when observations have different costs;and in finding fault-tolerant OOS.A MOS problem is similar to a minimal set cover(MSC) problem,so it can be proved that finding MOS is NP-hard.Inspired by MSC methods,an O(2mm2) but ?(2m?1) algorithm for MOS is presented,where m is the number of observations.By using integer ... |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 等数据库收录！ |
