Tbpgr Blog

Employee Experience Engineer tbpgr(てぃーびー) のブログ

アルゴリズム

アルゴリズム | A*探索(A-Star探索)

概要 A*探索(A-Star探索) 内容 ゴールが分かっている場合にゴールまでの推定値を利用して最短経路を解く。 推定距離は実際の値と同じかそれより小さい必要がある。 典型的な例としてはゴールまで何も障害物が無いと想定して、直線距離を推定値にする。 ア…

アルゴリズム | 幅優先探索(breadth first search=BFS)

概要 幅優先探索(breadth first search) 内容 幅優先探索は木やグラフを探索するためのアルゴリズム。 アルゴリズムは根から始まり、隣接ノードから探索する。 全ての隣接ノードを探索し終わったら次の深さのノードを探索する。 別名「横型探索」。 特徴 空…

アルゴリズム | 深さ優先探索(depth first search=DFS)

概要 深さ優先探索(depth first search) 内容 深さ優先探索は木やグラフを探索するためのアルゴリズム。 別名「縦型探索」。以下、処理フロー。 ・開始点を決める ・隣接するノードへ移動 ・ノードがなくなるまで進む ・ノードがなくなったら一つ戻り、未訪…

アルゴリズム | クイックソート

概要 クイックソート 内容 最良計算量および平均計算量はO( n\log n )。 ソート仕様 ・適当な数(ピボットという)を選択する ・ピボットより小さい数を前方、大きい数を後方に移動 ・二分割された各々のデータを、それぞれソートする(再帰) コード quick_…

アルゴリズム | マージソート

概要 マージソート 内容 データを分割し、それぞれをソート後、結果をマージする。 分割統治法。最悪計算量O(n log n) コード merge_sort.rb # encoding: utf-8 class Array def merge_sort s = self.size return self if s == 1 lesses = self.pop(s >> 1) …

アルゴリズム | 挿入ソート

概要 挿入ソート 内容 整列してある配列に追加要素を適切な場所に挿入すること。 平均計算時間・最悪計算時間がともにO(n2)。 ソート仕様 ・左端から順にN番目の要素をN-1番目までの要素と比較して、自分より小さい値と大きい値の間に挿入する。 コード inse…

アルゴリズム | 選択ソート

概要 選択ソート 内容 最小値を探し、先頭から順に並べていくソート。 O(n2)と低速だが実装が容易。 コード selection_sort.rb class Array def selection_sort max = self.size - 1 (0..max).each do |i| min = i ((i + 1)..max).each do |j| min = j if se…

アルゴリズム | データ構造

概要 データ構造 内容 データ構造について 構造名 概要 リスト・ベクター 追加・削除・検索時のコストが高い。一定容量で領域確保するため任意の要素へのアクセスは早い 連結リスト 前後へのリンク構造を持つため追加・削除時のコストはその前後の要素しか影…

アルゴリズム | バブルソート

概要 バブルソート 内容 基本交換法、隣接交換法ともいう。 最悪計算時間はO(N2)。 ソート仕様 ・左端から順に隣り合う要素を比較し、左の方が大きければ右の要素と入れ替える。 ・右端まで到達したら再度左端から比較を行う。 ・要素数=Nとして、N回の比較…

アルゴリズム

概要 アルゴリズム 内容 探索 項目 URL バイナリサーチ http://d.hatena.ne.jp/tbpg/20130831/1377968008 深さ優先探索 http://d.hatena.ne.jp/tbpg/20130909/1378735858 幅優先探索 http://d.hatena.ne.jp/tbpg/20130910/1378820207 A*探索 http://d.hatena…

アルゴリズム | 冪剰余の計算

概要 冪剰余の計算 内容 冪乗の剰余を計算。 書籍「アルゴリズムを学ぼう」より。 書籍のサンプルはJavaのコードだったが、Rubyで書いてみた。1.オーソドックスに計算 2.a*b mod c = (a mod c) * (a mod c) mod c を利用 3.2の計算中の個別の結果を再利用…