treeとは?

読み方:き
【英】:tree

概要

閉路含まない連結グラフを木という. 連結グラフ G=(V,A) \,に対して, G \,部分グラフであって集合 V \,をもつ木を, グラフ G \,張る木(spanning tree)といったり, グラフ G \,全域木, 極大木, 全張木あるいは, 単にグラフ G \,の木などという. 根と呼ばれる1点が指定された木を根付き木(rooted tree)という. さらに, 根付き木は, (有向グラフとして)向き沿って根からすべての点に行くことができるとき, 有向木(directed tree)と呼ばれる.

詳説

 平面上 (空間内) の幾何的問題を解く際に対象領域分割しながら部分領域に対応する木のノード考え分割階層構造を木 (構造データ構造) を用いて表現する. 分割のしかたにより様々な木が得られそれぞれ特別な名前がつけられている. 計算幾何代表的問題である点位置決定 (point location) 問題(与えられた平面上のn点からなる直線分の平面グラフS\, に対して, 質問Q\, 与えられたとき, Q\, を含む面 (領域) を求め問題) および領域探索 (range search) 問題(与えられた平面上のn\, 点の集合S\, に対して, 質問多角形Q\, 与えられたとき, Q\, 含まれるS\, の点を列挙する問題)を例にとり説明する.

 これらの問題は, いずれも, 与えられた対象物集合S\, (以下台集合と呼ぶ)に対して, 質問Q\, 与えられたとき, Q\, ある種条件をみたすS\, 要素列挙する問題であり, その意味で探索問題呼ばれている. 同一台集合S\, に対して, 質問(問い合わせ)が繰り返し行われることも多いので, 台集合に前処理を施し質問高速応答できるように工夫する. すなわち, 質問高速応答できるようにS\, 計算機内で違った形(データ構造)で表現する. 実際データベースでもこのような工夫がなされている.

 このような状況下では, S\, 表現するデータ構造D(S)\, のための記憶領域, D(S)\, 構成するための手間(および作業領域), および質問応答している時間 (探索時間) の3\, つの基準基づいて性能総合的評価なければならない.

 点位置決定問題に対応する1次元問題は, 一直線上に与えられたn\, 個の点の集合P\, 分割された区間集合S\, に対して質問Q\, 与えられたときQ\, を含むS\, 区間求め問題となる. これは, P\, およびS\, 平衡探索木D(S)\, 表現しておけば, \mbox{O}(\log n)\, の手間で応答できる. D(S)\, 構成するための手間および記憶領域いずれも\mbox{O}(n)\, である. さらに点集合新しい点が付加されたり古い点が除去されたりして台集合P\, S\, 変化するのが普通である. このときにはそれに応じてD(S)\, 更新なければならないが, この更新操作ダイナマイゼーション (dynamization) という. 1回の更新要する手間\mbox{O}(\log n)\, ダイナマイゼーション技術多数知られている.

 領域探索問題に対応する1次元問題は, 一直線上に与えられたn\, 個の点の集合S\, に対して質問区間Q\, 与えられたときQ\, 含まれるS\, の点をすべて列挙する問題となる. これもS\, 平衡探索木D(S)\, 表現しておけば, \mbox{O}(k+\log n)\, の手間で応答できる. ここでk\, 列挙される点の個数である. 更新の手間も\mbox{O}(\log n)\, である.

 2\, 次元点位置決定問題領域探索問題は1次元このような探索問題(の系列)に帰着して解かれている. たとえば, 点位置決定問題に対して有名な手法であるスラブ法 (slab method) では, グラフ頂点を通る (x\, 軸に) 垂直な直線を引いて平面を垂直な帯に分割する. この垂直な帯がスラブ (slab) と呼ばれる. 一つスラブ内では, 横切るグラフ線分上下関係一列に並べることができるのでそれを平衡探索木表現しておく. すると, 点位置決定問題は, 質問Q\, に対して, Q\, を含むスラブ二分探索で見つける. 次にそのスラブ内で平衡探索木利用してQ\, のすぐ上にある線分求め, その線分境界にもつ下の面をQ\, を含む領域として求めればよい. これは2次元問題n+1\, 個のスラブでの問題(1次元問題)に帰着していると見なせる. 応答の手間は\mbox{O}(\log n)\, となるが, 必要とするデータ構造構築するための手間と記憶領域\mbox{O}(n^2)\, となる. これに対して, サーナクとタージャン (Sarnak-Tarjan) の残存スラブ法 [2] では, x\, 座標の値を時刻考えて, 連続する2つのスラブ構造変化定数であることに注目して, 過去に遡っても探索が可能になるようにデータ構造工夫をしている. これは点位置決定問題に対して, 理論的最適アルゴリズム (前処理時間\mbox{O}(n\log n)\, , 記憶領域\mbox{O}(n)\, , 応答時間\mbox{O}(\log n)\, ) の一つである.

 領域探索に対して多角形は軸に平行な辺からなる長方形場合多く, そのときにはk-d木 (k\, -d\, tree), 四分木 (quadtree), 領域木 (range tree) などのデータ構造が有効である.

 領域木平面上の集合領域x\, 座標中央値基づいて二分割を繰り返してできる分割に対応する二分木で, 各ノードには対応する対象領域内にある点をすべて記憶しておく. すなわち区間木 (interval tree) の各ノードに対応するx\, 区間に入る点を平衡探索木などで記憶しているものである. するとx,y\, 軸に平行な質問長方形Q\, 与えられたとき, Q\, x\, 区間区間木分割に対応して互いに共通部分をもたない区間和集合として表現されるが, そのような区間に対応するノード一次元領域探索をすることでQ\, 含まれるSの点を効率的列挙できる.

 k\, -d\, 木はk\, 次元空間領域分割表現するデータ構造一つであり, 2次元場合では, 根に全体領域が対応し, その左右の子にはx\, 座標注目して左右二等分された点集合領域が対応する. 次に分割された左(右)点集合領域y\, 座標基づいて上下二等分それぞれ左(右)の子左右の子に対応させる. 以下交互繰り返して対応する領域に点が1個になったら分割終了する. この分割法を表現したものが2-d\, 木である. k\, 次元のときは, x_1\, 座標, x_2\, 座標, \cdots\, , x_k\, 座標といってまた, x_1\, 座標戻り循環しながら分割ていったものを表現する. これに対して, 四分木2\, 次元平面領域分割表現するデータ構造で, 根に全体領域が対応し, 根の4\, の子にはx\, 座標中央値およびy\, 座標中央値を通る水平線および垂直線をひいて四分割された部分領域が対応する. さらにそれぞれのv\, に対応する部分領域同様に水平線および垂直線四等分してv\, の4つの子に対応させる. このようにして得られる分割表現するデータ構造四分木である. 分割された領域対象物がなくなると分割停止する.

 k\, -d\, 木も四分木探索は同様で, x,y\, 軸に平行な質問長方形Q\, 与えられたとき, Q\, 共通部分をもつ領域に対応するノード1次元領域探索をすることでQ\, 含まれるS\, の点を効率的列挙できる.

 八分木 (octree)は3次元空間の点の集合の分割表現するデータ構造で, 3次元領域探索などに用いら, 2次元平面における四分木に対応する. 計算幾何様々な探索問題対すアルゴリズムとその詳細については文献 [1] を参照のこと.



参考文献

[1] 伊理正夫監修, 腰塚武志編集, 『計算幾何学地理情報処理(第2版)』, 共立出版, 1993.

[2] N. Sarnak and R.E. Tarjan, "Planar Point Location Using Persistent-Search Trees," Communications of the ACM, 29 (1986), 669-679.


Tree


ツリー

(tree から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/04/20 17:11 UTC 版)

ツリー (tree)




「ツリー」の続きの解説一覧





固有名詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「tree」の関連用語

treeのお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング

画像から探す

Sストローク

水木海水浴場

伊良湖岬恋路ヶ浜の潮騒

OASYS 48VA112

中部山岳国立公園

ケ200

広帯域移動無線アクセスシステム

掛矢





treeのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
三省堂三省堂
Copyright (C) 2001-2017 Sanseido Co.,Ltd. All rights reserved.
株式会社 三省堂三省堂 Web Dictionary
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2017 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのツリー (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2017 Weblio RSS