仮説生成に基づく分散型問題解決
スポンサーリンク
概要
- 論文の詳細を見る
The critical problem of search is the amount of time and space necessary to find a solution. For example, exhaustive search is not feasible for Rubik's Cube, because examining all sequences of means would require operation in a search space in which the number of nodes grows exponentially with the number of means. Such a phenomenon is called a combinatorial explosion. To prevent it from happening, one must reduce the size of the search space. The reduction of the search space, in this paper, is accomplished by generating hypotheses for a solution. At first, hypothesis is generated to limit the search space. Then the process is followed by the verification of hypotheses, namely, a solution is found if the hypothesis is true. It has a possibility, however, that the number of hypotheses grows too large, since a hypothesis is generated from a necessary condition for a solution. If that happens it results that the amount of time and space necessary to find a solution would reach to the same level as the exhaustive search. In this paper, we introduce a distributed system that has no restrictions on the number of processes and we assign the verifications to the processes of the system in order for all of the verifications to be done concurrently. As a result, the efficiency of problem solving is greatly improved. In order to examine the improvement acquired in the present system, the paper describes the results of simulation how the system solves 2×2×2 Rubik's Cube.
- 社団法人人工知能学会の論文
- 1989-05-20
著者
関連論文
- 仮説生成に基づく分散型問題解決
- 俯瞰可能迷路の代数的構造(Semi-Ring)による数学的モデル化と成功経路導出アルゴリズム
- 初期視覚モデルと眼球運動
- 初期視覚モデルと錯視 : ラプラシアン・ガウシアンに関する一考察
- 超多重解像度に基づく錯視の情報処理モデル
- 網膜における多重解像度と錯視 : ミューラー・リヤー錯視の場合
- 複雑さの制御による問題解決 : 大規模巡回セールスマン問題の求解
- 2000-HPC-82-27 クラスタリングによる抽象化を用いた巡回セールスマン問題の分散処理解法
- マルチプロセッサシステムによる並行探索 : 仮説検証法の場合
- エッジ検出に基づく曲率計算
- 帰納的アルゴリズムに基づく巡回セールスマン問題の解法
- 並列処理に適した縦続的問題分解