bucket methodとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > bucket methodの意味・解説 

バケット法

読み方ばけっとほう
【英】:bucket method

概要

幾何的問題をより単純に高速処理するための実際的方法である. 対象物2次元n\,からなる図形のときは, 対象物座標軸に平行な辺からなる長方形覆い, それを縦横\lceil\sqrt{n}\ \rceil\,等分し全部\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil\,個のバケット呼ばれる長方形領域分割して図形を各バケット切り出し管理する. すると問題を各バケット内での極めて単純な問題帰着できることもしばしばあり, 高速処理できることになる.

詳説

 計算幾何実用的なアルゴリズム代表的設計法一つであり, 平面最小重み完全マッチング (matching), 点位置決定 (point location) などがバケット法 (bucket method) に基づいて効率的に解かれている. 簡単のため2次元説明するが, 高次元にも容易に一般化できる. 平面上にサイズn\, 解きたい問題与えられたとする. 問題を含む領域を軸に平行な辺からなる長方形覆い, 軸に垂直な直線引いて\Theta(n)\, 個のバケット呼ばれる合同な小長方形分割する. そして全体問題それぞれのバケット内の問題として分割して記憶する. すると通常バケット内での問題だけで全体の解が得られるので高速になる. バケット間にまたがる情報必要に応じて利用しなければならない場合もあるがこの場合高速手法があることが多い.

 具体例より詳しく説明する. 与えられ平面上のn=2m\, 個の点集合に対して, 2\, 点ずペアにしてm\, \, 個のペア集合M\, をつくるという問題考える. このようなM\, は, 完全マッチング呼ばれている. その際, ペア重みをそのペア含まれる2\, 点間の距離(2\, 点を結ぶ線分長さ)とする. 完全マッチングM\, 重みM\, 含まれるm\, 個のペア重み総和見なし, 重み最小にする完全マッチング求め問題平面最小重み完全マッチングというが, この問題をバケット法に基づいて解決しその実用性を実証した研究 [2] が, 計算幾何学問題対するバケット法の最初の適用例といわれている. できるだけ小さ重み完全マッチングをつくるわけであるので, 遠く離れた2\, 点がペアになる可能性は低い. そこで, 対象領域(長方形領域)を縦横\lceil \sqrt{n}\ \rceil\, 等分し全部\lceil \sqrt{n} \ \rceil \times \lceil \sqrt{n} \ \rceil=\Theta(n)\, 個のバケット分割して, 同一バケット含まれる点でまずペアをつくる. 最小重み完全マッチングには距離の小さ2\, 点がペアとして含まれることが多いので, 同一バケット含まれるもの同士ペアにするということは, 同一バケット含まれる2点極めて近い点である可能性高く, 異なバケット属す2点遠くにある可能性が高いという, 自然な仮定基づいている.

 このように, バケット法では問題局所領域限定できるという特徴がある. さらに, 与えられる点の集合対象領域において一様に分布するときは, n=2m\, 個の点に対してほぼ同数個のバケット分割しているので, 各バケット平均的に一定数(\mbox{O}(1)\, )個の点し含まないといえる. したがって, 各バケット内での最小重み完全マッチング\mbox{O}(1)\, の手間で見つけることができる. このように, バケット法では, バケット内の問題極めて単純であるという特徴併せもっている. さらに, バケット合同長方形であるため, バケット含まれる点も簡単に求められるという特徴もある. このような特徴から, バケット法に基づく手法は, 一般に極めて高速となる [1].

 上の平面最小重み完全マッチング問題では, バケット内での完全マッチングだけでは, 全体完全マッチングはならずに, ペアにされていない点が残るのが普通で, 最終的には, バケット間にまたがる点同士でさらにペアつくっていかなければならないが, これは, 2\, 次元バケット間の距離を, ある程度忠実に保存するようにして, 一列並べ, その順番次々とペアにしていけばよい. このようにして求められ完全マッチングは, 最小重み完全マッチングでないことが多いが, 詳細な解析により, かなり精度の高い解となることが保証されている [2]. 最適解ネットワークアルゴリズム用いて\mbox{O}(n^3)\, の手間で解けるが, 上記のバケット法に基づく方法\mbox{O}(n)\, の手間であり, 実際応用では極めて有効である.

 平面最小重み完全マッチングプロッターペン用いて地図を描く際の筆順最適化 (optimal drawing (of map) ) に応用する. 地図きれいに描くため, 同じ線を2\, 度描くことはしないものとする. ペンおろして線を描いているときもあるし, ペン上げて次に描くべき線始まりまで移動しているときもある. 地図を描くという観点からすると, ペンおろして線を描くという動作必要不可欠なものである. これに対して, ペン上げて次に描くべき線始まりまで移動する動作は, 空送り呼ばれ無駄な動作であるので, できるだけ少なくするのがよい. さて, 地図一筆書き可能なら空送りをすることなく描けることになる. 地図一筆書き不可能ならば空送り部分対応する線を付け加えた図で一筆書きできるように変形して描くことになる. プロッターでの描画要する時間は, ほぼ, この2\, つの動作要する時間総和になるので, 描画時間を減らすには, 空送り全体要する時間減らせばよい. これらの動作要する時間移動量に比例するものとすれば, 空送り全体移動量(移動距離)を最小にすれば, 描画要する時間最小ということになる. これは平面最小重み完全マッチング帰着できる. 地図一筆書き不可能ならば奇数本の線が接続する点を全部拾ってきて(すると点は偶数個になる), 2\, 個ずつペアにして完全マッチング求め, 完全マッチング含まれる線を空送りに対応させて付け加えれば一筆書きできることになる. 完全マッチング選び方により付け加えた線の総長異なるので, 総長最小完全マッチング求め問題となる.

 その他の計算幾何様々な探索問題対するバケット法の応用については文献 [1, 3] を参照のこと.




参考文献

[1] T. Asano, M. Edahiro, H. Imai, M. Iri and K. Murota, "Practical Use of Bucketing Techniques in Computational Geometry," in Computational Geometry, G.T. Toussaint, ed., North-Holland, 1985.

[2] M. Iri, K. Murota and S. Matsui, "Heurisitics for Planar Minimum Weight Perfect Matchings," Networks, 13 (1983), 67-92.

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


「bucket method」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


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

辞書ショートカット

すべての辞書の索引

「bucket method」の関連用語

bucket methodのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



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

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS