翻訳と辞書
Words near each other
・ A☆Lucky
・ A♥K
・ A♭
・ A♯
・ Aさんの庭
・ Aちゃんねる
・ AとR
・ Aの嵐
・ Aの悲劇
・ Aの魔法陣
Aアルゴリズム
・ AアンドP・ロバーツ
・ Aウィング
・ Aウムラウト
・ Aカットごはん
・ Aカップ
・ AカップCカップ
・ Aカード
・ Aクラス
・ Aクラス・Bクラス


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Aアルゴリズム : ミニ英和和英辞書
Aアルゴリズム
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。


Aアルゴリズム ( リダイレクト:A* ) : ウィキペディア日本語版
A*[えい]

A
*(A-star, エースター)探索アルゴリズム
は、グラフ探索アルゴリズムの一つ。
最良優先探索を拡張したZ
*
に、さらにf値として「現時点までの距離」gと「ゴールまでの推定値」hの和を採用したもの。〔Pearl,Judea. "Heuristics: intelligent search strategies for computer problem solving." (1984).〕 h は ヒューリスティック関数と呼ばれる。
== 概要 ==
A
* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 ''h(n)'' という探索の道標となる関数を用いて探索を行うアルゴリズムである。hは各頂点nからゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまなhを設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、hとしてユークリッド距離 \sqrt を使うことができ、この値は道に沿った実際の距離のおおまかな予測になっている。しかし、高次元空間でのグラフ探索を効率的に行うためには、より高度に設計された関数を用いる必要がある。例えば、15パズルにおいてはマンハッタン距離パターンデータベースSTRIPSプランニングにおいてはFFヒューリスティック〔Hoffmann, Jörg, and Bernhard Nebel. "The FF planning system: Fast plan generation through heuristic search." Journal of Artificial Intelligence Research (2001): 253-302.〕,Merge-and-Shrink〔Hoffmann, Jörg, and Bernhard Nebel. "The FF planning system: Fast plan generation through heuristic search." Journal of Artificial Intelligence Research (2001): 253-302.〕,Landmark-Cut〔Helmert, Malte, and Carmel Domshlak. "Landmarks, critical paths and abstractions: what's the difference anyway?." ICAPS. 2009.〕 などがある。
A
* アルゴリズムは、ダイクストラ法を推定値つきの場合に一般化したもので、h が恒等的に0である場合はもとのダイクストラ法に一致する。
A
*の探索効率はhの正確さに左右される。
もしもhがまったくでたらめな値を返すならば、探索はゴールとはあさっての方向に進んでしまい、現実的な時間内 --- 一時間、一週間、一年 --- では解を発見できない場合がある。しかし、いくらおかしな方向に探索が進んだとしても、いつかは必ず解を発見できる保証がある(完全性)。
一方、hが常に正しい値''h
*''を返す場合、計算機は「迷うこと無く=分岐をすること無く」グラフ上の最短経路を発見することができる。そのようなhのことを、パーフェクト・ヒューリスティクスとよぶ〔How Good is Almost Perfect?. M Helmert, G Röger - AAAI, 2008〕。
現実に用いられる有用なhは、これらの中間の位置にある。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「A*」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 A* search algorithm 」があります。




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.