並列処理に適した縦続的問題分解

概要

論文の詳細を見る
The progress of VLSI technology has made it possible to combine problem-decomposition methods and the parallel processing technology that runs concurrently a large number of processors. If a problem is decomposed into intermediate problems and they are all solved with processors, concurrently, then the efficiency of problem-solving will be improved remarkably. However, the traditional problem-decomposition methods are not fit for the parallel processing, because the initial state of each intermediate problems is determined by the solution of the one that precedes. In this paper, we propose a serial decomposition method and extend it to the one that is fit for parallel processing. In general, a serial decomposition method decomposes a given problem into the sequence of intermediate problems by setting subgoals. For this method to be of interest, it is necessary that the intermediate problems be solvable and be simpler than original one. To simplify them, we introduce equivalence relations on their state spaces and get quotient problems. We show a condition for the composition of solutions of these quotient problems to be a solution of the original problem. Furthermore we extend the method to the one that is fit for parallel processing. Since the initial state of an intermediate problem is contained in the goal of the preceding intermediate problem, if one regards all elements of the goal as candidates for the initial state and define intermediate problems for the candidates, respectively, the set of all intermediate problems surely contains the desired one. As a result, the number of intermediate problems to be solved is increased. The total processing time, however, will be improved, since they can be solved concurrently.
社団法人人工知能学会の論文
1988-11-20

著者

新妻清三郎
静岡大学工業短期大学部

並列処理に適した縦続的問題分解

スポンサーリンク

概要

著者

関連論文

スポンサーリンク