ブラウザよりも高速アクセス！
26 関係: 双方向探索、均一コスト探索、天体、主記憶装置、マンハッタン距離、ヒューリスティクス、ダイクストラ法、ベルマン–フォード法、分割統治法、アルゴリズム、グラフ、シェーキー、優先度付きキュー、CPU、閉路、集合、連結リスト、STRIPS、探索、最適性、最良優先探索、文脈自由文法、15パズル、1968年、1976年、1980年。
双方向探索
双方向探索（英: bidirectional search）とは、グラフ探索アルゴリズムの一種で、同時に2つの方向から探索を行う。一方は初期状態から順方向に探索し、もう一方は最終状態から逆方向に探索して、その中間でぶつかった時点で終了する。それぞれの探索の計算量は O(b^)（ランダウの記号）であり、両方を合わせても O(b^+b^) となり、一方向から全部の探索を行った場合の O(b^) よりも効率がよい。 しかし、よいことばかりではない。並列に2つの探索を行う複雑さは別として、探索木をどう拡張していくかを各ステップで決定する必要がある。また、最終状態から逆方向に探索できる状況は限られているし、事前に用意が必要になる場合もある。また、2つの探索木の交差を見つける効率的方法も必要になる。このような問題があるため、うまいヒューリスティックがあるならA*の方がよい選択となることが多い。 双方向探索でもヒューリスティックを使うことができる。A*について証明されているように、許容的ヒューリスティックによって最短解が得られる場合がある。 拡張されるノードは、オープンなノード数が最も少なく最も見込みがある最先端から選ばれる。そのようなノードがもう一方の最先端にもある時に、アルゴリズムは終了する。子ノードのf値の計算に当たっては、もう一方の最先端の全てのオープンなノードのg値を考慮しなければならない。そのため、ノードの拡張はA*よりも計算量が多くなる。訪れるノードの数は上で概説したように少なくなることが期待できる。従って、個々の計算量が多くても調べるノード数が少なくなる。参考文献に示した1977年の文献では、A*では解けなかった問題を双方向探索で解いた例が示されている。許容的でないヒューリスティックを使った場合でもより短い経路が見つかっている。これらの検証は Ira Pohl が15パズルで行った。 Ira Pohl は、世界で初めて双方向ヒューリスティック探索アルゴリズムを設計・実装した。最先端の子ノードは、もう一方の側のターゲットについてだけ評価していた。彼の報告によれば、2つの探索木は相手と交差したことを検出できなかったという。.
均一コスト探索
均一コスト探索（きんいつこすとたんさく、uniform-cost search）は、重み付きの木や木構造やグラフを辿ったり探索するための探索アルゴリズムである。最良優先探索において、評価関数を根ノードから探索ノードまでのコストの総和とした物。直観的には、探索は根ノードで始まり根ノードからの合計コストが最小になるようにノードを訪れ、ゴールに到達するまで続く。均一探索は探索方法としては幅優先探索に似ている。 普通、探索アルゴリズムには隣接する未訪のノードを優先度付きキューに追加する操作が含まれる。キューにはそれぞれのノードが根ノードからの合計コスト順に格納されていて、最小コストのパスを持つノードが最も高い優先度を持っている。キューの先頭にあるノードから直接つながった次のノードをたどり、根ノードからのコストを計算してキューに追加する。 均一コスト探索は一般のグラフ探索を行うダイクストラ法の特殊なケースである。ダイクストラ法はA*アルゴリズムの特殊なケースでヒューリスティクスを定数関数にした場合と同じである。幅優先探索は均一コスト探索の特殊なケースであり、辺のコストが全て同じ場合と同じである。 辺のコストが非負値の場合、最小の評価値の物が必ず見つかる。.
新しい！!: A*と均一コスト探索 · 続きを見る »
天体
天体（てんたい、、）とは、宇宙空間にある物体のことである。宇宙に存在する岩石、ガス、塵などの様々な物質が、重力的に束縛されて凝縮状態になっているものを指す呼称として用いられる。.
主記憶装置
主記憶装置（しゅきおくそうち）は、記憶装置の分類で、「補助記憶装置」が一般に外部バスなど比較的CPUから離れていて大容量だが遅い記憶装置を指すのに対し、コンピュータのメインバスなどに直接接続されている記憶装置で、レイテンシやスループットは速いが比較すると小容量である。特に、CPUが入出力命令によって外部のインタフェースを操作するのではなく、「ロード・ストア命令」や、さらには通常の加算などの命令において直接読み書きできる対象であるものを指す。メインメモリ、一次記憶装置とも。.
マンハッタン距離
マンハッタン距離（マンハッタンきょり、Manhattan distance）またはL1-距離は、幾何学における距離概念のひとつ。各座標の差（の絶対値）の総和を2点間の距離とする。 ユークリッド幾何学における通常の距離（ユークリッド距離）に代わり、この距離概念を用いた幾何学はタクシーの幾何 (taxicab geometry) と呼ばれる。19世紀にヘルマン・ミンコフスキーによって考案された。.
新しい！!: A*とマンハッタン距離 · 続きを見る »
ヒューリスティクス
ヒューリスティック（heuristic, Heuristik）とは、必ず正しい答えを導けるわけではないが、ある程度のレベルで正解に近い解を得ることができる方法である。ヒューリスティックスでは、答えの精度が保証されない代わりに、回答に至るまでの時間が少ないという特徴がある。主に計算機科学と心理学の分野で使用される言葉であり、どちらの分野での用法も根本的な意味は同じであるが、指示対象が異なる。すなわち、計算機科学ではプログラミングの方法を指すが、心理学では人間の思考方法を指すものとして使われる。なお、論理学では仮説形成法と呼ばれている。.
新しい！!: A*とヒューリスティクス · 続きを見る »
ダイクストラ法
ダイクストラ法の動作のアニメーション ダイクストラ法（だいくすとらほう、Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが、実用性はあまり高くない。.
新しい！!: A*とダイクストラ法 · 続きを見る »
ベルマン–フォード法
ベルマン–フォード法 (Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。 グラフに「負閉路」(negative cycle) が含まれるとき、すなわち辺の重みの総和が負になるような閉路が存在するとき、好きなだけ小さな重みを持つ歩道を取れるので、「最短」経路は定まらない。このためベルマン-フォード法も負閉路が始点から到達可能である場合は正しい答を出せないが、負閉路を検出してその存在を報告することはできる。 ロバート・セジウィックによれば、「負の重みは単なる数学的な好奇心の対象というだけではない。（中略）他の問題を最短経路問題に還元すると、自然に負の重みが現れる」。G を負閉路を含むグラフとしよう。最短経路問題のとあるNP完全な変種で、G における辺の重複を許さない（負閉路を含む）最短経路を求めよという問題がある。セジウィックはハミルトン閉路問題をこの問題に還元する方法を示している。.
新しい！!: A*とベルマン–フォード法 · 続きを見る »
分割統治法
分割統治法（ぶんかつとうちほう、divide-and-conquer method）は、そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という問題解決の手法である。.
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
グラフ
ラフ; graph.
シェーキー
ェーキー（）は、スタンフォード研究所が1966年から1972年にかけて研究開発したロボットである。移動能力のある世界初の汎用ロボットであり、自身の動作を推論することができた。当時、他のロボットが大きな仕事をするのに各段階をいちいち命令されなければならなかったのに対し、シェーキーは指令を分析し、基本的動作の列へと分解して実行できた。 その性質から、プロジェクトはロボット工学だけでなく、コンピュータビジョンや自然言語処理も含めた研究であった。そのため、論理的推論と物理的動作を統合した初のプロジェクトとなった。シェーキーはスタンフォード研究所（現SRIインターナショナル）の人工知能センターが開発した。 主な成果として、A*探索アルゴリズム、ハフ変換、法などがある。.
優先度付きキュー
優先度付きキュー（ゆうせんどつき -、priority queue）は、以下の4つの操作をサポートする抽象データ型である。.
新しい！!: A*と優先度付きキュー · 続きを見る »
CPU
Intel Core 2 Duo E6600) CPU（シーピーユー、Central Processing Unit）、中央処理装置（ちゅうおうしょりそうち）は、コンピュータにおける中心的な処理装置（プロセッサ）。 「CPU」と「プロセッサ」と「マイクロプロセッサ」という語は、ほぼ同義語として使われる場合も多いが、厳密には以下に述べるように若干の範囲の違いがある。大規模集積回路（LSI）の発達により1個ないしごく少数のチップに全機能が集積されたマイクロプロセッサが誕生する以前は、多数の（小規模）集積回路（さらにそれ以前はディスクリート）から成る巨大な電子回路がプロセッサであり、CPUであった。大型汎用機を指す「メインフレーム」という語は、もともとは多数の架（フレーム）から成る大型汎用機システムにおいてCPUの収まる主要部（メイン）、という所から来ている。また、パーソナルコンピュータ全体をシステムとして見た時、例えば電源部が制御用に内蔵するワンチップマイコン（マイクロコントローラ）は、システム全体として見た場合には「CPU」ではない。.
閉路
有向閉路の例。青い頂点を2度通るので単純閉路ではない。 閉路（へいろ、cycle, circuit, closed walk）あるいは閉道（へいどう、closed path）とは、始点と終点が同じ路のこと。すなわち、出発点に戻るような辿り方のことである。グラフ理論や位相幾何学において用いられる。 単純閉路（たんじゅんへいろ、simple cycle）とは、自分自身と交差していない閉路のこと。グラフの単純閉路であればいかなる頂点も一度しか現れない。 閉路ならば同じところを行ったり来たりして辿ってもよく、同じところを繰り返し通らない閉路のことを閉道という。 n個の相異なる頂点vi（i.
集合
数学における集合 (しゅうごう、set, ensemble, Menge) とは、大雑把に言えばいくつかの「もの」からなる「集まり」である。集合を構成する個々の「もの」のことを元 (げん、; 要素) という。 集合は、集合論のみならず現代数学全体における最も基本的な概念の一つであり、現代数学のほとんどが集合と写像の言葉で書かれていると言ってよい。 慣例的に、ある種の集合が系 (けい、) や族 (ぞく、) などと呼ばれることもある。実際には、これらの呼び名に本質的な違いはないが細かなニュアンスの違いを含むと考えられている。たとえば、方程式系（「相互に連立する」方程式の集合）、集合族（「一定の規則に基づく」集合の集合）、加法族（「加法的な性質を持つ」集合族）など。.
連結リスト
連結リスト（れんけつリスト、Linked list）は、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。 一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク（またはポインタ）を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる（場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する）。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。 連結リストは多くのプログラミング言語で実装可能である。LISP や Scheme 、Prologといった言語は組み込みでこのデータ構造を持っていて、連結リストにアクセスするための操作も組み込まれている。手続き型やオブジェクト指向型の言語（C言語、C++、Java）では、連結リストを作るには mutable（更新可能）な参照を必要とする。.
STRIPS
STRIPS（Stanford Research Institute Problem Solver）とは、1971年、Richard Fikes と Nils Nilsson が開発した自動計画に関する人工知能の一種。後にそのシステムの入力に使う形式言語も同じ名前で呼ばれるようになった。自動計画用の言語としては最も広く利用されている。本項目では、システムではなく言語に関して解説する。.
探索
探索（たんさく、search）とは、特定の制約条件を満たす物を見つけ出す行動のこと。何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索（search）も参照。.
最適性
最適性（:en:Optimality）とは.
最良優先探索
最良優先探索（さいりょうゆうせんたんさく、best-first search）は、幅優先探索（breadth-first search）を何らかの規則（評価関数）に従って次に探索する最も望ましいノードを選択するように拡張した探索アルゴリズムである。 探索ノードを効率的に選択するには優先度付きキュー（priority queue）を用いて実装するのが一般的である。キューに貯めずに最良のノードだけを扱うと山登り法になる。キューを評価関数でソートしないと幅優先探索になる。 最良優先探索の例としてはダイクストラ法（Dijkstra's algorithm）やA*アルゴリズム（A* search algorithm）や均一コスト探索を挙げることができる。最良優先探索は経路探索においてしばしば使われるアルゴリズムである。コンピュータ将棋・コンピュータチェスなどでも最良優先探索を拡張した物が使われている。.
文脈自由文法
文脈自由文法（ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG）は、形式言語の理論（特に、生成文法）において全生成規則が以下のようである形式文法である。 ここで V は非終端記号であり、w は終端記号と非終端記号の（0個を含む）任意個の並びである。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できる、という所から来ている（「文脈無用」という訳の提案もある）。文脈自由文法によって生成される形式言語を文脈自由言語という。.
15パズル
15パズルの目的の配置、ないし初期配置 15パズルは、スライディングブロックパズル（Sliding puzzle）のひとつである。4×4のボードの上に4×4-1すなわち15枚の駒があり、1駒ぶんの空きを利用して駒をスライドし、駒を目的の配置にする。3×3のボード上で8枚の駒で同様に遊ぶものは8パズルと呼ばれる。m×nのボードとm×n-1個の駒（m, n ≧ 2）に一般化できる。右下の隅または左上の隅を空きとした配置を最終目標とするものが多い。.
1968年
記載なし。
1976年
記載なし。
1980年
この項目では、国際的な視点に基づいた1980年について記載する。.
