ランダマイゼーションとは何？わかりやすく解説 Weblio辞書

ランダマイゼーション

　本項では, 計算幾何の問題に対するランダマイゼーションの代表的手法についてまとめる. 代表的手法としては次の 2つのものがあり, 以下その説明をする.

　代表的な例で, 平面上の $n\,$ 個の点の集合 $S\,$ の $\epsilon\,$ -近似 $T\,$ を考える. 任意の $\epsilon\ge0\,$ に対して, $S\,$ の部分集合 $T\,$ が $\epsilon\,$ 近似である}とは, 任意の半平面 $h\,$ に対して次式が成り立つことをいう.

$\left| {|S\cap h|\over|S|}-{|T\cap h|\over |T|}\right| \le\epsilon\,$

定理. 任意の $\epsilon,\ \delta>0\,$ に対して, 点集合 $S\,$ から少なくとも

$m\ge{16\over\epsilon^2}\left(3\ln{48\over\epsilon^2}+\ln{4\over\delta}\right)\,$

なる $m\,$ 点をランダムかつ独立に選んで得られる集合 $T\,$ は, 少なくとも $1-\delta\,$ の確率で $S\,$ の $\epsilon\,$ -近似である.

(b) ランダム順添加法　ランダム順添加法も有用な方法である. これは, アルゴリズム設計のパラダイムの1つである逐次添加法 (incremental method)をもとにするものである. 従来の逐次添加法は, $n\,$ 要素の問題を解くときに, 最初は定数個(例えば2,3)の要素の部分問題に対する解から始めて, $i\,$ 個の要素の部分問題の解があるとき, $i+1\,$ 番目の要素をそこに加えて $i+1\,$ 個の要素の部分問題に対する解をつくり, これを $n\,$ 個全体に対する解が得られるまで繰り返す方法である. このとき, $i\,$ 個の要素の部分問題に対する解がわかっていれば, 通常それに1個加えた $i+1\,$ 個の部分問題に対する解は, ゼロからその $i+1\,$ 個の問題を解くのに比べて, はるかに効率よく求めることができるということが, 高速アルゴリズムを得るために役立つ. たとえば, 挿入ソートなどは, この典型例である.

　ランダム順添加法では, ランダマイゼーションにより要素をランダム順に並べ, その順に逐次添加を行なっていく. それによって, 最悪の場合を考えたとき, 単に与えられた順で添加していくと, たいてい逐次添加法にとっては都合の悪い順番が存在し, その場合の計算量が最悪計算時間となってしまうことが多いのに対し, ランダマイゼーションによってそれを避けることができる. これは, 入力になんらかの分布を仮定して平均計算時間を評価するのと近く, ただ複雑な問題では入力の分布として妥当なものを考えることが難しいので, 作為的な入力分布を仮定するより, アルゴリズムの中でランダマイゼーションした方がより汎用的な成果が得られる. また, ランダマイゼーションアルゴリズムといっても, もし, 入力の分布に関して, そう悪い例が出てこなさそうであれば, 実際には単に与えられた順で添加をしていけばよいのである. このランダム順添加法は, 低次元線形計画や凸包構成など幅広く適用されている.

[2] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

[3] K. Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, Prentice-Hall, 1994.

「OR事典」の他の用語

計算幾何：


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.