スモモンガーのページ
ゲームとか将棋とかのページ
TOP
ウェブゲーム
研究
ブログ
将棋
作曲
カンガルー法の探索への応用
カンガルー法は多角形と直線との交点を求めるために作られたアルゴリズムですが、データのキーが"整った"データであれば探索への応用が可能です。カンガルー法を適用するにはまず隣接するデータのキーの値の差の最大値を求めます(これをlとおきます)。そして現在の要素のキー(これをaとします)と探査したいキー(これをbとおきます)との差をとります。あとは進む要素の数をmax((a-b)/l,1)をとればよいです。カンガルー法は配列がキーでソートさせていて、配列間のキーの差が一様分布に従うときにはバイナリーサーチとほぼ同等の性能を示します。しかし、例えキーの値がソートしていても、その分布が"整っていない"場合バイナリーサーチより効率が悪くなります。また隣接するデータのキーの値の最大値を求める必要があるのも難点です。ただ、データが完全にソートされていなくてもキーの分布が"整ってさえいれば"カンガルー法は適用可能です。
カンガルー法を方程式の解を求める手法への応用をする方法
カンガルー法は方程式の解を求めるのにも使うことができます。あらかじめことわっておくと例えばニュートン法などに比べると収束速度は非常に遅いです。なので話半分で読んでください。まず、求めたい方程式を0=f(x)とおきます。次に解が存在する範囲を求めます(例えば[a,b])など。その範囲ないでの|f'(x)|の最大値を求めkとします。まず、x=aとおきx= x+|f(x)|/kとして計算していきます。(これを見て分かった方もいるかと思いますがこの手法はニュートン法に似ています。ニュートン法ではf(x)を割る数が変化するなのに対し、カンガルー法では固定となっています。)これを繰り返せば解が得られます。