A problem-decomposition method using differences or equivalence relations between states

摘要

This paper describes a method for decomposing a problem into some intermediate problems using a solution of the quotient problem constructed through certain information about a relationship between differences and means. The intermediate problems are not necessarily simpler than the original one. We restrict the state set and means set of the intermediate problem in order to reduce it to a simpler one. But, the problems gained by restrictions which are called subproblems may not be solvable in general. We show a condition for the subproblems to be solvable. Next, a method for decomposing a problem into the simplest subproblems is presented. The simplest subproblem is the one in which only one difference exists between the initial state and the goal. A sufficient condition for the success of the method is investigated. For a difference sequence D, we give the procedure of the decomposition by the AND/OR-type subproblem tree T(D). A sufficient condition for T(D) to include a solvable tree (whose leaves are eventually the simplest subproblems) is given.