文章基本信息

标题：Analysing and Combining Partial Problem Solutions for Properly Informed Heuristic Generations
本地全文：下载
作者：Kee-cheol Lee ; Han-gyoo Kim
期刊名称：Computer Engineering and Intelligent Systems
印刷版ISSN：2222-1727
电子版ISSN：2222-2863
出版年度：2012
卷号：3
期号：11
页码：1-8
语种：English
出版社：International Institute for Science, Technology Education
摘要：Finding an optimal path to the fixed goal state of a problem instance lying in an enormous search space may be described in the framework of the conventional A * algorithm. However, the estimated distance to the goal state, so called h _ value , must be generated by an admissible heuristic such that it is not larger than but still as close as the unknown real distance to the goal. In this paper, we suggest a method of generating a heuristic with that property. After analyzing a number of devised partial problems, some are selected to be combined to produce a properly informed heuristic. In solving a complex problem with a fixed goal, some depth of fixed backward states is pre-stored. Those static backward states are also used for partial problem backward searches. For a given problem instance, the forward search is first performed for each of its partial problem. The dynamically generated space is combined with the static search space to produce the temporary search space, which is used to aid in the generation of each state heuristic for the course of problem solving. A novel method of constructing the temporary search space for each partial problem is suggested, in which each forward state found in the static backward space is back-propagated and propagated in the forward space. To show the effectiveness of our method, it has been massively experimented for instances of Rubik’s cube problem of some difficulty whose search space of states reachable from any given start state is known to cover 43*10 18 states, the number of which even an 64-bit unsigned integer cannot hold.
关键词：A * ; admissible heuristic; partial problems; dynamic forward search; static backward search; Rubik’s cube