| 講演名 | 1994/11/18 8パズルの高速解法 飯田 栄治, 下平 博, 木村 正行, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 8パズル及び一回り大きくした15パズルについて、探索に基づいた解法がこれまでいくつか研究されている。通常、これらのパズルの探索による解法では、ゴール状態までの手数が少し長くなると容易には解けない。また、効率良い探索を行なうためにヒューリスティック関数を考案することも一般に難しい。そこで、今回は8パズルに対し、探索ではなく問題をいくつかの小問題に分割しそれらの各サブゴールに到達するための整列戦略に従って、状態遷移オペレータを次々に適用することにより高速に問題を解決する手法を提案する。また、いくつか例題に対し代表的な探索方法と比較実験を行なったのでその結果を報告する。 |
| 抄録(英) | Several authors studied solving technique for solving 8-puzzle and 15-puzzle by the search. In many cases we can't easily solve the problem which has a long solution in 8-puzzles etc and it is generally difficult to devise hi-performance heuristic function to search efficiently. Here we propose new fast method for solving 8-puzzle without using the search.In this approach,first the problem is decomposed into simpler subproblems and then the subproblems are solved sequencially using the state transition operators under suitable sorting strategies. And we report the result of the comparative experiments for both the typical solution by the search and the fast-solution we proposed this time. |
| キーワード(和) | 8パズル / 15パズル / グラフ探索 / ヒューリスティック関数 / 整列戦略 / 高速解 法 |
| キーワード(英) | 8-puzzle / 15-puzzle / graphsearch / neuristic function / sorting strategy / fast solution |
| 資料番号 | COMP94-59 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1994/11/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 8パズルの高速解法 |
| サブタイトル（和） | |
| タイトル（英） | Fast solution of 8-puzzle |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 8パズル / 8-puzzle |
| キーワード(2)（和/英） | 15パズル / 15-puzzle |
| キーワード(3)（和/英） | グラフ探索 / graphsearch |
| キーワード(4)（和/英） | ヒューリスティック関数 / neuristic function |
| キーワード(5)（和/英） | 整列戦略 / sorting strategy |
| キーワード(6)（和/英） | 高速解 法 / fast solution |
| 第 1 著者 氏名（和/英） | 飯田 栄治 / Eiji Iida |
| 第 1 著者 所属（和/英） | 三菱プレシジョン Mitsubishi precision |
| 第 2 著者 氏名（和/英） | 下平 博 / Hiroshi Shimodaira |
| 第 2 著者 所属（和/英） | 北陸先端科学技術大学院大学 Jpan Advanced Institute of Science and Technology,Hokuriku |
| 第 3 著者 氏名（和/英） | 木村 正行 / Masayuki Kimura |
| 第 3 著者 所属（和/英） | 北陸先端科学技術大学院大学 Japan Advanced Institute of Science and Technology,Hokuriku |
| 発表年月日 | 1994/11/18 |
| 資料番号 | COMP94-59 |
| 巻番号（vol） | vol.94 |
| 号番号（no） | 354 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |