サクサク読めて、アプリ限定の機能も多数！
トップへ戻る
猛暑に注意を
www.ics.kagoshima-u.ac.jp/~fuchida
離散ボロノイ図を作成する素朴で簡単な方法は、すべての離散点について、どの母点に最も近いかを１つ１つ計算していく方法である。この方法は、離散点の数 M (=WxH) と母点数 N に比例した時間がかかるのが欠点だが、アルゴリズムは簡単である。そこで、まず手始めに全探索法のアルゴリズムを考え、これをプログラム化して離散ボロノイ図の作成実験をしてみよう。 全探索法のアルゴリズム 全探索法のアルゴリズムを、なるべく簡単な言葉で述べると、次のようになる。 N 個の母点からなる母点集合 S と、離散ボロノイ図を作成するための離散平面を準備する。 母点集合と離散平面を初期化する。 すべての離散点について、4. の処理を繰り返して 5. へ すべての母点との距離を計算し、最も距離が小さい母点の番号を、その離散点の位置に書きこむ。 結果を出力して終了 このアルゴリズムをフローチャートの形に表すと図4.1のよ
平面上に、いくつかの点が配置されている。このとき、その平面ないの点を、どの点に最も近いかによって分割してできる図を、ボロノイ (Voronoi) 図という。また、その分割のことをボロノイ分割という。図1.1にボロノイ図の例を示す。 配置された点のことを母点と呼ぶ。この図での母点数は5であり、ボロノイ領域は5つに分かれている。一般的なボロノイ図では、母点数とボロノイ領域数は一致する。ボロノイ領域の境目の線をボロノイ境界と呼ぶ。また、ボロノイ境界の交点をボロノイ点と呼ぶ。 ボロノイ図の応用例 ボロノイ図の応用範囲は広く、情報処理のさまざまな分野で利用されている。 最も近い PHS の基地局を探す 新しい基地局をどこに作ればよいかの指標を得る 散らばったデータを、いくつかの代表データにまとめる キタキツネの勢力範囲 有限要素法の領域分割 画像のデータ圧縮 など。他にもいろいろある。 ドロネー図
ヒープ構造とは、簡単に言うと、2分木の各節点にデータを保持し、親のデータが2つの子のデータよりも小さくなるように作られたデータ構造です。すべてのデータの中で、木の根のデータがもっとも小さいことが保障されますから、最小値データを取り出すことや、データの追加が最悪でも log(N) 時間で行えるという、優れた特徴があります。 ヒープソートの基本的な考え方は、与えられたデータを順にヒープ構造に追加して行き、すべてのデータを追加し終わったら根から取り出すと言うものです。 ヒープ構造は、もっとも小さいデータが常に根にあることが特徴です。したがって、すべてのデータをヒープに追加してから、根から順に取り出せば、小さい順にデータを取り出すことが可能です。ただし、データの追加や取り出しのときは、ヒープ構造が壊れないように注意しなければなりません。 ヒープにデータを追加するときは、まず木構造の最後に追加します
ソートアルゴリズムの最後を飾るのは、やはりクリックソートです。 クイックソートは、データの比較と交換回数が非常に少ないのが特徴で、一般的なばらばらデータ（ランダムに散らばっているデータ）に対して、最も効率良く並べ替えを実行します。 クイックソートは、実用上もっとも高速であるとされている並べ替えアルゴリズムで、多くのプログラムで利用されています。 ばらばらなデータが格納された配列 a[ ] が与えられた場合に、それらをクイックソートで並べ替える手順を、下の図に示します。 まず始めに、「軸要素」と呼ばれるデータ値を決定します。この値は、データ全体を2つに分割するときのしきい値として使われます。軸要素は、分割が均等に行われるように選ぶのが望ましいのですが、その選択に時間をかけると、かえって並べ替えの時間を大きくしてしまいます。一般には、次のような方法がよく用いられているようです。 データの先頭の
下のアプレットは、6種類すべてのソートアルゴリズムを同時に実行するものです。 左上から右へ、バブルソート、バケットソート、基数ソート、ヒープソート、マージソート、クイックソートです。 "Start" ボタンを押すと、すべてのソートが同時開始されます。クイックソートがもっとも速く並べ終わり、次にバケットソート、基数ソートの順で並べ終わるのがわかります。 データ数や初期並びを変えて、いろいろなデータで試してみましょう。 アプレットの並べ替えプログラムは、人間の眼で見て並べ替えの様子がわかりやすいように、データの交換が起こるたびに wait を入れて速度を遅くして表示しています。しかし、この方法では、データの交換以外に要する時間はほとんど無視されることになり、正確な意味で正しい比較をしていることにはなりません。 そこで、wait を入れずに並べ替えを行うプログラムを作成し、いろいろな個数のデータ
いろいろなソートアルゴリズム 大小関係が定められたたくさんのデータを、小さい順（昇順）あるいは大きい順（降順）に並べ替える作業をソート（整列）と言います。この処理は、さまざまなプログラムの中で頻繁に使われ、そのゆえ、古くからいろいろなアルゴリズムが考案されてきました。 並べ替えは、主にデータベースなどの大量のデータを処理する必要のあるプログラムで有用です。試験の点数の高い順番に並べ替えて、上位1000人を合格にするなどの場合は、点数による並べ替えが行われます。また、住所録のデータを住所毎にまとめて参照したい場合は、住所（文字列）による並べ替えが行われます。 このページでは、多くあるソートアルゴリズムのうち、以下の6通りのアルゴリズムについて説明し、Javaアプレットで実際の並べ替えの様子を見て、その特徴を理解することにします。 バブルソート バケットソート（ビンソート） 基数ソート ヒープ
あらかじめ整列してある2つの配列を合体させて、新しい、整列された配列を得るのは容易です。マージソートはこれに着目して、並べ替えたい配列を再帰的に分割していき、再び併合（マージ）していくことで、並び替えを実現しようとする、ソートアルゴリズムです。 次の図は、マージソートが行われる過程を表しています。 ばらばらな順番で与えられた配列データは、まず始めに小さい配列へと分解されます。このとき、マージソートでは各配列がほぼ2分割されるように分解していきます。 もっとも小さい配列（要素数1）まで分解されたら、それを順序良く併合していきます。このとき、2つの配列の先頭から小さい方を取り出して新しい配列を作成するようにすれば、取り出すだけで整列された配列を作成することができます。 /* * マージ * 2つの配列a1[]とa2[]を併合してa[]を作ります。 */ void merge(int[] a1,
public void sort(int[] a){ // バケツに入っているデータ数を覚えるための配列です int[] bn=new int[bucket.length]; // 最下位桁の数字を見て、対応するバケツにデータを入れます。 for(int i=0;i<a.length;i++){ bucket[a[i]%m].add(new Integer(a[i])); notifier.notify(i,-1); } // 最初のバケツから順番にデータを取りだし、データの指定桁の値を見て、 // 対応するバケツにデータを追加します。 for(int j=1;j<k;j++){ // 現在、それぞれのバケツに何個のデータが入っているかを // 覚えておきます。 for(int b=0;b<bucket.length;b++) bn[b]=bucket[b].num; // 各バケツの先頭
計算幾何学とは、計算機上で幾何的な図形データを取り扱う方法について研究する学問の総称である。このページでは、計算幾何学の代表的な問題であるボロノイ図を例に挙げて、波面法アルゴリズムとそれを実現するプログラムを対比して説明する。プログラム言語として、WWW ページ上で実行可能な Java を使用した。 ボロノイ図とは 離散ボロノイ図とは 問題の定義 素朴な方法 ～全探索法～ 波面法アルゴリズム 非ユークリッド距離に基づく離散ボロノイ図への適用 高位の離散ボロノイ図への適用 重み付き離散ボロノイ図への適用 教育関連のページへ 1999.4.28 Takayasu Fuchida
<body> <p>このページにはフレームが使用されていますが、お使いのブラウザではサポートされていません。</p> </body>
バブルソートアルゴリズムを使ってこの数字を並べ替えるための、基本的な方針は次の通りです。 上の要素と比較し、上のほうが大きければ互いに交換する これを、下から順番にやっていきます。そうすると、小さい数字は交換されて上に順々に上がってきます。一番下から一番上まで1回通ると、一番小さい数字が一番上に上がってきているはずです。 次に、一番上を除いて、もう1回同じことを繰り返します。そうすると、今度は2番目に小さい数字が2番目まで上がって来ます。（一番上は、操作から外れているので変化しません） もう1回やると、3番目が上がってきます。 もう1回やると、4番目も上がってきます。以下、同様です。 最後までやれば、並べ替えは終了です。簡単ですね。
バケットソートとは、別名バケツソートとも呼ばれ、あらかじめ順番通り並べて準備されたバケツに、データを放り込むことで並べ替えを行おうという、いささか乱暴なソートアルゴリズムです。 この方法は、データの存在する範囲が有限個に限定されていないと使えませんが、使える場合は非常に高速に並べ替えを実行できる、きわめて有用なアルゴリズムです。 1～100までの数字が書かれたたくさんのカードがあるとします。カードに書かれている数字には重複があっても構いません。また、最初、カードはばらばらに混ざっています。 これらのカードを、数字が小さい順に並べ替えるのに、バケットソートでは、1～100までの数字が横に書かれている100個のバケツを準備します。 そして、カードを適当に取り出して、その番号と一致するバケツに放り込みます。また、別なカードを取り出しては、対応するバケツに放り込みます。 これをカードがなくなるまで
このページを最初にブックマークしてみませんか？
『www.ics.kagoshima-u.ac.jp』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
