CAJ | 학술논문

在不确定规划中，可通过观察周围的信息来区分多个状态，但周围的观察信息较多，因此如何从大量的观察信息中筛选必须的信息非常重要。以往算法是在直接搜索过程中增加一些剪枝条件来达到优化的目的，存在一定的局限性。在对观察信息约简研究中，为提高搜索效率，设计一种高效的不确定规划中观察信息约简算法。该算法将规划问题转化为求解0-1矩阵的覆盖问题，使用数据结构十字链表来表示0-1矩阵，通过维护十字链表并采用启发式函数来加速求解一个最小观察变量集。实验结果表明，该算法不仅能够找最小观察变量集，而且运行速度超过同类算法。
재불학정규화중，가통과관찰주위적신식래구분다개상태，단주위적관찰신식교다，인차여하종대량적관찰신식중사선필수적신식비상중요。이왕산법시재직접수색과정중증가일사전지조건래체도우화적목적，존재일정적국한성。재대관찰신식약간연구중，위제고수색효솔，설계일충고효적불학정규화중관찰신식약간산법。해산법장규화문제전화위구해0-1구진적복개문제，사용수거결구십자련표래표시0-1구진，통과유호십자련표병채용계발식함수래가속구해일개최소관찰변량집。실험결과표명，해산법불부능구조최소관찰변량집，이차운행속도초과동류산법。
In nondeterministic planning, it is feasible to distinguish some states through observation information, however, observation information is so much that it is significant how to select useful information from plenty of observation information. The previous algorithms use direct search algorithm that adds some cutting condition to achieve optimized objective, however, these methods have certain limitations. In research to observation information reduction, this paper designs a new algorithm which improves search efficiency. It converts the problem into cover problem in 0-1 matrix through abstract problem model, and replaces the 0-1 matrix using orthogonal list data structure and can get a minimal set of observation variable through maintaining the orthogonal list and using heuristic function. Experimental result shows that this algorithm not only finds a minimal set of observation variable, but also runs more quickly than similar algorithm.