ブラウザよりも高速アクセス！
26 関係: 力まかせ探索、垂直、不変条件、中央値、平面、平衡二分探索木、座標、区間木、バイナリ空間分割、ユークリッド空間、ランダウの記号、ロボット工学、データ構造、アルゴリズム、オープンソース、ソート、八分木、直方体、選択アルゴリズム、長方形、NP困難、Python、深さ優先探索、木の回転、木構造 (データ構造)、最近傍探索。
力まかせ探索
力まかせ探索（ちからまかせたんさく、Brute-force search）またはしらみつぶし探索（Exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。 バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 64! / 56!.
新しい！!: Kd木と力まかせ探索 · 続きを見る »
垂直
初等幾何学において、垂直（すいちょく、perpendicular）であること、すなわち垂直性 は直角に交わる二つの直線の間の関係性を言う。この性質は関連するほかの幾何学的対象に対しても拡張される。 垂線 に関連して垂線の「足」() という術語がしばしば用いられる。考える図形の向きは如何様にも変えることができるから、足と謂えどもそれが必ずしも図形の下方にあるわけではない。 垂直性はより一般の数学概念である直交性の特別の場合と考えられる。すなわち、垂直性とは古典的な幾何学的対象に関する直交性を言うものである。ゆえに、より進んだ数学において、より複雑な幾何学的直交性（例えば曲面とその法線の関係など）に対して「垂直」あるいは「垂線」のような語を用いることもある。.
不変条件
不変条件（英: invariant）とは、コンピュータプログラムの理論における用語で、ある処理の間、その真理値が真のまま変化しない述語 (predicate) であり、その処理シーケンスに対して不変であるという。.
中央値
中央値（ちゅうおうち、median）とは、代表値の一つで、有限個のデータを小さい順に並べたとき中央に位置する値。たとえば5人の人がいるとき、その5人の年齢の中央値は3番目に年寄りな人の年齢である。ただし、データが偶数個の場合は、中央に近い2つの値の算術平均をとる。中央値の事を、メディアン、メジアン、中間値とも呼ぶ。ただし、「中間値の定理」の中間値はこの意味ではない。.
平面
平面（へいめん、plane）とは、平らな表面のことである広辞苑 第五版、p.2395「平面」。平らな面。 一般的には曲面や立体などと対比されつつ理解されている。.
平衡二分探索木
平衡二分探索木（へいこうにぶんたんさくぎ、self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木）である。平衡二分探索木は連想配列や集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。.
新しい！!: Kd木と平衡二分探索木 · 続きを見る »
座標
幾何学において、座標（ざひょう）とは、点の位置を指定するために与えられる数の組 (coordinates)、あるいはその各数 (coordinate) のことであり、その組から点の位置を定める方法を与えるものが座標系（ざひょうけい、coordinate system）である。座標系と座標が与えられれば、点はただ一つに定まる。 座標は点により定まる関数の組であって、一つの空間に複数の座標系が重複して定義されていることがある。例えば、多様体は各点の近くでユークリッド空間と同様の座標系が貼り付けられているが、ほとんどの場合、一つの座標系の座標だけを考えていたのでは全ての点を特定することができない。このような場合は、たくさんの座標系を貼り付けて、重なる部分での読み替えの方法を記した地図帳（アトラス、atlas）を用意することもある。 地球上の位置を表す地理座標や、天体に対して天球上の位置を表す天球座標がある。.
区間木
区間木またはインターバル木（Interval tree）は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。似たものに区分木（Segment tree, segtree）があるが別物である。.
バイナリ空間分割
バイナリ空間分割（バイナリくうかんぶんかつ、Binary space partitioning, BSP）は、（N次元）空間の（(N-1)次元）超平面での分割を再帰的に繰返し、何らかの目的に適したデータ構造を構築する手法である。3次元コンピュータグラフィックスへの応用では、シーンをBSP木（BSP tree）と呼ばれる木構造による表現に変換する。 元々は、画家のアルゴリズムのために、シーンを前処理しておくことで効率を向上させる手段として提案されたものである。つまり、あらかじめシーン中に存在する全てのポリゴンについて、ある1枚のポリゴンを「根」として、残りのポリゴンについて、そのポリゴンより表側にあるか、裏側にあるかという分類を再帰的に適用して、2分木に構成してしまえば（両側にまたがっている場合には分割してしまう）、描画する時には、画家のアルゴリズムであれば、各ポリゴンについてカメラ（視点）が表と裏のどちらにあるかに応じて、そのポリゴンより奥側にあるものをまず先に描き、後から手前にあるものを描けばよい。 他にも、CADにおける図形処理、ロボット工学や3Dコンピュータゲームでの衝突判定、その他の複雑な形状を扱うコンピュータアプリケーションなどといった応用がある。.
新しい！!: Kd木とバイナリ空間分割 · 続きを見る »
ユークリッド空間
数学におけるユークリッド空間（ユークリッドくうかん、Euclidean space）は、エウクレイデス（ユークリッド）が研究したような幾何学（ユークリッド幾何学）の場となる平面や空間、およびその高次元への一般化である。エウクレイデスが研究した平面や空間はそれぞれ、2次元ユークリッド空間、3次元ユークリッド空間に当たり、これらは通常、ユークリッド平面、ユークリッド空間などとも呼ばれる。「ユークリッド的」という修飾辞は、これらの空間が非ユークリッド幾何やアインシュタインの相対性理論に出てくるような曲がった空間ではないことを示唆している。 古典的なギリシャ数学では、ユークリッド平面や（三次元）ユークリッド空間は所定の公準によって定義され、そこからほかの性質が定理として演繹されるものであった。現代数学では、デカルト座標と解析幾何学の考え方にしたがってユークリッド空間を定義するほうが普通である。そうすれば、幾何学の問題に代数学や解析学の道具を持ち込んで調べることができるようになるし、三次元以上のユークリッド空間への一般化も容易になるといった利点が生まれる。 現代的な観点では、ユークリッド空間は各次元に本質的に一つだけ存在すると考えられる。たとえば一次元なら実数直線、二次元ならデカルト平面、より高次の場合は実数の組を座標にもつ実座標空間である。つまり、ユークリッド空間の「点」は実数からなる組であり、二点間の距離は二点間の距離の公式に従うものとして定まる。n-次元ユークリッド空間は、（標準的なモデルを与えるものという意味で）しばしば とかかれるが、（余分な構造を想起させない）ユークリッド空間固有の性質を備えたものということを強調する意味で と書かれることもある。ふつう、ユークリッド空間といえば有限次元であるものをいう。.
新しい！!: Kd木とユークリッド空間 · 続きを見る »
ランダウの記号
ランダウの記号（ランダウのきごう、Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （オーもしくはオミクロン Ο。数字の0ではない）を用いることから（ランダウの）O-記法、ランダウのオミクロンなどともいう。 記号 O は「程度」の意味のオーダー（Order）から。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。.
新しい！!: Kd木とランダウの記号 · 続きを見る »
ロボット工学
ボット工学（ロボットこうがく、英語：robotics）は、ロボットに関する技術を研究する学問。ロボットの手足などを構成するためのアクチュエータや機構に関する分野、外界の情報を認識・知覚するためのセンサやセンシング手法に関する分野、ロボットの運動や行動ロボットの制御に関する分野、ロボットの知能など人工知能に関する分野などに大別される。 語源としてはアイザック・アシモフが自著の一連のロボットが登場するSF小説のために、robotに物理学（physics）などに使われている語尾「-ics」を付けることで作った造語である。アシモフの小説内に出てくる「ロボット工学三原則」は、以降のロボット物SFに大きな影響を与えたのみならず、現実のロボット工学においても研究上の倫理的指標のひとつとなっている。また、「ロボット工学の父」と呼ばれることもあるジョセフ・F・エンゲルバーガー博士はアシモフの小説に影響されていた。.
新しい！!: Kd木とロボット工学 · 続きを見る »
データ構造
データ構造（データこうぞう、data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: Kd木とアルゴリズム · 続きを見る »
オープンソース
ープンソース (open source) とは、言葉通りのソースコードへのアクセスが開かれている（ソースコードが公開されている）ことを意味するのではなく、ソースコードを商用、非商用の目的を問わず利用、修正、頒布することを許し、それを利用する個人や団体の努力や利益を遮ることがないソフトウェア開発の手法を意味する。オープンソース・イニシアティブ は、「オープンソース」と名乗るための要件として「オープンソースの定義」を掲げている。.
新しい！!: Kd木とオープンソース · 続きを見る »
ソート
ート は、データの集合を一定の規則に従って並べること。日本語では整列（せいれつ）と訳される。（以前はその原義から分類という訳語が充てられていたが、もう使われていない） 主にコンピュータソフトにおけるリストに表示するデータに対し、全順序関係によって一列に並べることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、）という。 対象となるデータのデータ構造や必要な出力によって、使われるアルゴリズムは異なる。.
八分木
左: 立方体の再帰的な8分割、右: それに対応した八分木 八分木（英: Octree）とは、木構造の一種で、各ノードに最大8個の子ノードがある。3次元空間を8つのオクタント（八分空間）に再帰的に分割する場合によく使われる。四分木を3次元に拡張したものと見ることができる。英語の名称は oct + tree に由来するが "octtree" とは書かず "octree" と書く。.
直方体
方体（ちょくほうたい、cuboid）とは、すべての面が長方形（正方形も長方形の一種である）で構成される六面体（面が6つある多面体）である。長方体（ちょうほうたい）、直六面体（ちょくろくめんたい）とも呼ばれる。その特徴から、隣接する面が直角に交わる。 四角柱、特に直四角柱の一種である。 面を構成する長方形がすべて正方形であるような直方体は特に立方体（正六面体）と呼ばれる。 直方体を傾けると、平行六面体が得られる。.
選択アルゴリズム
選択アルゴリズム（selection algorithm）とは、数列から k 番目に小さい（あるいは k 番目に大きい）数を探すアルゴリズムである。最小値、最大値、中央値を探すアルゴリズムは選択アルゴリズムの特殊なものと言える。これらを「順序統計量」とも呼ぶ。比較的単純な最小値、最大値、k 番目に小さい値を求めるアルゴリズムとしては、平均で線形時間のものが知られている。k 番目に小さい値や一度に複数の順序統計量を最悪でも線形時間で探すことも可能である。選択は最近傍探索問題や最短経路問題のようなもっと複雑な問題の部分問題である。.
新しい！!: Kd木と選択アルゴリズム · 続きを見る »
長方形
長方形 長方形（ちょうほうけい、rectangle）とは.
NP困難
NP完全、'''NP困難'''の相関を表すベン図 NP困難（エヌピーこんなん、NP-hard）とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである。正確にいうと問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。NP困難問題を解ける多項式時間の機械がもしあれば、それを利用してNPに属するどの問題も多項式時間で解くことができる。 NP完全問題とは、NP困難であり、かつNPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。NPは決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、探索問題(en)、組合せ最適化問題など様々な問題が属しうる。 上に挙げた定義から、問題 H がNP困難なとき次のことが言える（以下は定義ではなく主張）。.
Python
Python（パイソン）は、汎用のプログラミング言語である。コードがシンプルで扱いやすく設計されており、C言語などに比べて、さまざまなプログラムを分かりやすく、少ないコード行数で書けるといった特徴がある。.
新しい！!: Kd木とPython · 続きを見る »
深さ優先探索
深さ優先探索のイメージ 深さ優先探索（ふかさゆうせんたんさく、depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。.
新しい！!: Kd木と深さ優先探索 · 続きを見る »
木の回転
木の回転（きのかいてん、tree rotation）は、2分探索木の操作の一種で、要素の順序を崩さずに構造を変更するものである。木の回転は木の中の1つのノードを上にし、別のノードを下にする。木の形状を変化させるのに使い、特に大きい部分木を持ち上げて小さい部分木を下げることで全体の木の高さを低くするのに使う。それによって各種操作の性能を向上させる。 なお、回転の方向によって「右回転」、「左回転」と言うが、どちらが右でどちらが左なのかは必ずしも決まっていない。図示したときにノードがずれる方向を回転の方向とする場合もあれば、どちら側の子ノードが根ノードになるかを回転の方向とする場合もある（前者の逆になる）。本項ではノードがずれる方向を回転の方向とする。.
木構造 (データ構造)
親子構造 木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。.
新しい！!: Kd木と木構造 (データ構造) · 続きを見る »
最近傍探索
最近傍探索（Nearest neighbor search, NNS）は、距離空間における最も近い点を探す最適化問題の一種、あるいはその解法。近接探索（proximity search）、類似探索（similarity search）、最近点探索（closest point search）などとも呼ぶ。問題はすなわち、距離空間 M における点の集合 S があり、クエリ点 q ∈ M があるとき、S の中で q に最も近い点を探す、という問題である。多くの場合、M には d次元のユークリッド空間が採用され、距離はユークリッド距離かマンハッタン距離で測定される。低次元の場合と高次元の場合で異なるアルゴズムがとられる。 ドナルド・クヌースは、The Art of Computer Programming Vol.3（1973年）で、これを郵便局の問題で表した。これはすなわち、ある住所に最も近い郵便局を求める問題である。.
