对不确定规划中观测约简的进一步研究

从3个方面改进了不确定规划(non-deterministicplanning,简称ndp)中的观测约简:一是如何找最小观测集合(minimalobservationset,简称mos),二是如何在观测代价不均等时找最优观测集合(optimalobservationset,简称oos),三是如何找到容错的oos.通过mos问题和图论中的最小覆盖集问题(minimalsetcover,简称msc)的类似性,可证mos是np难的问题,还可参考msc算法得出时间复杂性不超过o(2mm2)且不低于ω(2m?1)的算法,其中m是观测的个数.通过使用整数规划(integerprogramming,简称ip)技术,可找到oos以及容错的oos.可以证明,上述算法能够保证找到解,并且能够保证解的最优性.