LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@royal_straight_flush

アルゴリズム（一部Rubyの実装例記載）

Last updated at Posted at 2024-12-25

アルゴリズムとは

計算や作業を遂行するための手順のこと。
つまり、「問題を解決するための『やり方』や『考え方』を手順化したもの」

  • 例
    • ランダムに並んだ数列を大きい順に並び替える
    • 経路で最短のものを発見する

問題を解決するための「やり方」や「考え方」を変えるだけで効率が変わる

計算量の表し方＜例＞

  • $O$：オーダー（計算量）
  • $n$：データの数

例）$O(n)$の計算時間がかかる

  • $O(\log n)$
    • これは対数時間を示し、典型的にはデータサイズ（$n$）が大きくなっても、比較的少ない操作回数（対数的に増加）で処理が完了するアルゴリズム
      • 例）バイナリサーチ（二分探索）
  • $O(n)$
    • これは線形時間を示し、データサイズに比例して処理時間が増加する
      • 例）線形探索、単純なループ処理

→$n$が大きくなるほど、$O(\log n)$は$O(n)$よりも圧倒的に少ない操作回数で済むため速い

アルゴリズムの計算量において、$O(\log n)$の方が$O(n)$よりも高速

データ構造

🔶 リスト

⭕️データの追加・削除：$O(1)$
❌アクセスにかかる時間：$O(n)$ ※アクセスしたいデータが後ろの場合

  • データを一直線に並べた構造
  • ポインタが、次のデータのメモリ上を指す
  • リストの先頭から辿ることでしかアクセスできない（線形探索になる）

データの追加や削除はしやすいが、アクセスには時間がかかる

アクセスしたいデータが後ろの場合は $O(n)$

🔶 配列

⭕️データへのアクセス：$O(1)$
❌ データの追加・削除：$O(n)$

  • ランダムアクセス（メモリアドレスを添字から計算）できる
  • 要素を任意の場所に追加・削除する場合は、一つずつデータをずらす必要がある

リストとは対象的。アクセスは簡単だが、追加・削除にはコストがかかる

🔶 スタック

後入れ先だし（Last In First Out） ※略してLIFO

  • ※ 書類を積み上げた時のイメージ
    • データを追加する時：1番上に置く
    • データを取り出す時：1番上から取り出す

途中のデータが必要な場合、そこが1番上になるまでデータをポップする（取り出す）必要がある。

常に最新のデータへしかアクセスしないような使い方をする場合に便利

🔶 キュー

先入れ先だし（First In First Out） ※略してFIFO

  • 追加する側と削除する側が反対
    • 古いデータから順に処理していくという、極めて自然な考え方
  • キューは「待ち行列」とも呼ばれる
  • 途中のデータにアクセスするには、スタックと同様に必要なデータが出てくるまでデキューしなければならない

🔶 ハッシュテーブル

⭕️データへのアクセス

①「ハッシュ関数」を用いて、該当キーのハッシュ値を計算
② i = ①で求めたキーのハッシュ値 mod 配列の箱の数
③ i 番目の箱（配列）にデータを格納
④余りが衝突（データの格納位置が重複）した場合は、同じ要素にリストとして接続する

ハッシュテーブルに利用する配列のサイズについて

小さすぎると衝突が増え、線形探索が発生しやすくなる

大きすぎるとデータの格納されない箱が多く、メモリの無駄遣いとなる

配列のサイズを適正に設定することが重要

🔶 ヒープ

⭕️最小値の取り出し：$O(1)$
⭕️取り出した後のヒープの再構築：$O(\log n)$
⭕️データの追加：$O(\log n)$

  • 木構造の１つで、プライオリティキュー（データを自由に追加でき、小さいものから取り出す） を実現する時に使う
  • ヒープを表す木構造では、各頂点を「ノード」と呼ぶ
  • 各ノードにデータが格納される

ヒープは、常に一番上に最小のデータがあるため、データ数に関係なく$O(1)$時間で最小値を取り出すことが出来る

データの中から最小値を頻繁に取り出す場合に便利

🔶 2分探索木

⭕️ノードが$n$個＆木の形のバランス取れている場合：$O(\log n)$
❌木が偏って縦へ一直線に並んだ形：$O(n)$

性質

  • 全てのノードは、そのノードの左部分木に含まれるどの数よりも大きくなる
  • 全てのノードは、そのノードの右部分木に含まれるどの数よりも小さくなる

最上部ノードから左部分木のみ辿った末端が最小ノード。
逆に最大ノードは右。

ソート

🔷 バブルソート

右の方が小さければデータを入れ替えていき、整列させる方法。

一番右を基準にして小さい順にデータの並べ替えを行い、整列させていく。
隣同士のデータを右から順番に比較。

  • 計算時間：入力データに依存する
    • 入力データが小さい順である場合：数字の入れ替えが発生しない or 少ない
    • 入力データが大きい順である場合：$O(n^2)$ （毎回比較＆数字の入れ替えが発生）

最悪となる入力は、入力データが大きい順であるケース

🔷 選択ソート

「数列の中から最小値を検索し、左端の数字と入れ替える」という操作を繰り返し行う。

数列の中から最小値を探す際は、線形探索を行っている。

  • 計算時間：入力データに依存する
    • 入力データが小さい順である場合：数字の入れ替えが発生しない or 少ない
    • 入力データが大きい順である場合：$O(n^2)$ （毎回比較＆数字の入れ替えが発生）

最悪となる入力は、入力データが大きい順であるケース

🔷 挿入ソート

未整列データの先頭の要素を正しい場所に挿入していくことで整列済みにしていく方法。

初めに整列済みにしたデータを基準にし、小さい順にデータの並べ替えを行い整列させていく。データを整列済みと未整列の2つに分類する。

数列の左から順番にソートしていくイメージ。

  • 計算時間：入力データに依存する
    • 入力データが小さい順である場合：数字の入れ替えが発生しない or 少ない
    • 取り出した数字がソート済み領域の全ての数字よりも小さい場合：$O(n^2)$

最悪となる入力は、入力データが大きい順であるケース

🔷 ヒープソート

データ構造のヒープを利用する。
ヒープは、降順になるように構築する。取り出した数字は右から順に置いていく。

  • 計算時間：$O(n \log n)$
    • 最初に$n$個の数字をヒープに格納するための時間：$O(n \log n)$
    • ヒープを再構築するのにかかる時間：$O(\log n)$
    • ヒープができた後にソートしていく時間：$O(n \log n)$

降順ヒープは、大きいものから順にデータが取り出される性質があるため、出てきた数字を逆順に並べればソートが完了する

バブルソートや選択ソート、挿入ソートの $O(n^2)$ よりも高速

🔷 マージソート

ソートしたい数列を、ほぼ同じ長さの二つの数列に分割していく。←計算時間はかからない
これ以上分割出来なくなったところから、グループ同士統合（マージ）していく。
マージの際は二つのソート済み数列を統合し、一つのソート済み数列にする。
これを全体が一つのグループになるまで繰り返す。

  • 計算時間：$O(n \log n)$

🔷 クイックソート

基準となる数（ピボット）を数列の中からランダムに一つ選ぶ。
ピボット以外の数を、「ピボットより小さい数」と「ピボット以上の数」の二つのグループに分ける。そして、以下のように配置する。
[ピボットより小さい数] ピボット [ピボット以上の数]
後はそれぞれ[]の中をソートすればOK。
※[]内をソートするのにも、クイックソートを使用する。

  • 計算時間：$O(n \log n)$

平均的には $O(n \log n)$ の計算時間で終了することが知られている

但し、運悪く毎回最小値がピボットとして選ばれてしまう場合は $O(n^2)$

配列の探索

🟥 線形探索

配列からデータを探索するアルゴリズム。配列の先頭から順に比較を繰り返す。

  • 計算時間：$O(n)$

目的のデータが後方、もしくは目的のデータが存在しない場合に比較回数が多くなり、時間がかかる

配列中のデータはランダムで並んでいても問題ない。配列をメンテナンスするコストはかからない

配列への追加操作が頻繁に行われる場合には有効な探索

実装例（Ruby）

前後で値が同じ要素のペア数を数える

n = 5
arr = [5, 0, 0, 0, -2, 7]

# 隣り合う要素を比較し、一致するペア数をカウント
count = 0
(0...n-1).each do |i|
  count += 1 if arr[i] == arr[i+1]
end

# 結果を出力
p count #=> 2
リファクタver
n = 5
arr = [5, 0, 0, 0, -2, 7]

p arr.each_cons(2).count { |x, y| x == y } #=> 2

① 隣り合う要素を順番に比較
配列の最初から最後まで一つずつ順番に比較している。

② 時間計算量が $O(n)$
配列の長さ $n$ に対して1回ずつ比較を行うため、処理にかかる時間はデータ量に比例する。

線形探索メソッド例（Ruby）

等々

🟥 2分探索

配列からデータを探索するアルゴリズム。データがソートされている場合のみ適用できる。
目的のデータが中央より左にあるか右にあるかを知ることが出来るため、一度の比較で探索すべき範囲を半分に絞ることが可能。
これを、データが見つかる or 存在しないことが分かるまで繰り返す。

  • 計算時間：$O(\log n)$

2分探索の計算時間 $O(\log n)$ は、$O(n)$ に比べて指数的に高速

2分探索を行うためには、常にデータがソートされていなければいけない
→データを追加する際には適正な位置に追加しなければならず、配列をメンテナンスするコストがかかる

配列への追加操作が少なく、探索を頻繁に行う場合に有効

2分探索用メソッド（Ruby）

ary = [0, 4, 7, 10, 12]
ary.bsearch {|x| x >=   4 } # => 4
ary.bsearch {|x| x >=   6 } # => 7
ary.bsearch {|x| x >=  -1 } # => 0
ary.bsearch {|x| x >= 100 } # => nil

グラフアルゴリズム

  • 辺重み付きグラフ
    • 辺に付けられた値のことを、辺の「重み」や「コスト」と呼び、そのようなグラフを「辺重み付きグラフ」という
  • 有向グラフ：辺に向きを付ける
  • 無向グラフ：辺に向きがない
  • 連結で閉路のないグラフを「木」という ※閉路：始点と終点が同じ路のこと

🟨 幅優先探索

グラフを探索するアルゴリズム。

頂点を探索する際、始点に近い頂点から優先的に探索していくもの。
候補の頂点は 「先入れ先出し（FIFO）」 の仕組みで管理する（キューのデータ構造）。

指定された頂点（ゴール）が始点の近くにある場合、探索が早く終了する

実装例（Ruby）

解答コード例 
# 入力の取得
## 入力例1：5, 3, 2
## 入力例2：7, 5, 2
N, X, L = gets.split.map(&:to_i)

# 隣接リストの構築
graph = Array.new(N + 1) { [] }
#=> 入力例1：[[], [], [], [], [], []]
#=> 入力例2：[[], [], [], [], [], [], [], []]

(N - 1).times do
  a, b = gets.split.map(&:to_i)
  graph[a] << b
  graph[b] << a
end
# p graph
#=> 入力例1：[[], [2], [1, 3], [2, 4], [3, 5], [4]]
#=> 入力例2：[[], [5, 4, 2, 3], [1], [1], [1], [7, 6, 1], [5], [5]]

##【補足】
## 木の構成(入力例1のケース)
## 1 - 2 - 3 - 4 - 5
## 頂点1は頂点2と接続されているため、      graph[1] = [2]
## 頂点2は頂点1と頂点3と接続されているため、graph[2] = [1, 3]
## 頂点3は頂点2と頂点4と接続されているため、graph[3] = [2, 4]
## 頂点4は頂点3と頂点5と接続されているため、graph[4] = [3, 5]
## 頂点5は頂点4と接続されているため、      graph[5] = [4]
##
## 木の構成(入力例2のケース)
## 頂点1は頂点5, 4, 2, 3と接続されているため、graph[1] = [5, 4, 2, 3]
## 頂点2は頂点1と接続されているため、         graph[2] = [1, 3]
## 頂点3は頂点1と頂点4と接続されているため、   graph[3] = [2, 4]
## 頂点4は頂点1と頂点5と接続されているため、   graph[4] = [3, 5]
## 頂点5は頂点7, 6, 1と接続されているため、   graph[5] = [7, 6, 1]
## 頂点6は頂点5と接続されているため、         graph[6] = [5]
## 頂点7は頂点5と接続されているため、         graph[7] = [5]


# BFSの実行
queue = [[X, 0]]  # [頂点, 現在の距離]
visited = Array.new(N + 1, false)
visited[X] = true
# p visited
#=> 入力例1：[false, false, false, true, false, false]
#=> 入力例2：[false, false, false, false, false, true, false, false]

result = []

while queue.any?
  current, dist = queue.shift

  # 距離がLに達した頂点を結果に追加
  result << current if dist == L

  # 隣接する頂点を探索
  graph[current].each do |neighbor|
    next if visited[neighbor]

    visited[neighbor] = true
    queue << [neighbor, dist + 1]
  end
end
# p queue
#=> 入力例1：[]
#=> 入力例2：[]
# p visited
#=> 入力例1：[false, true, true, true, true, true]
#=> 入力例2：[false, true, true, true, true, true, true, true]
# p result
#=> 入力例1：[1, 5]
#=> 入力例2：[4, 2, 3]

# 結果を昇順にして出力
puts result.sort

入力例1の木（グラフ）の構造

1 - 2 - 3 - 4 - 5

入力例2の木（グラフ）の構造

   1
 / | \ \
2  3  4  5
        / \
       6   7

🟨 深さ優先探索

グラフを探索するアルゴリズム。

頂点を探索する際、一つの路をいけるところまで進んでいき、これ以上進むことが出来なくなったところで引き返し、次の候補となる路を進んでいく。
候補の頂点は 「後入れ先出し（LIFO）」 の仕組みで管理する（スタックのデータ構造）。

1つの路をより深く掘り下げながら探索を行っていく特徴がある

実装例（Ruby）

解答コード例 
def dfs(now, graph, unvisited)
  unvisited[now] = false # 現在の頂点（now）を訪問済みとする

  puts now + 1

  # 現在の頂点nowに隣接するすべての頂点（next_node）について、順番に処理を実施
  graph[now].each do |next_node|
    # もし隣接する頂点（next_node）が未訪問なら、その頂点を訪問し、再帰的に#dfsを呼び出す
    dfs(next_node, graph, unvisited) if unvisited[next_node]
  end
end

# 入力の読み込み
N, X = gets.split.map(&:to_i) #=> 5, 2

# グラフの初期化
graph = Array.new(N) { [] }
(N - 1).times do
  a, b = gets.split.map(&:to_i)
  graph[a - 1] << b - 1 # 頂点aと頂点bを結ぶ辺をグラフに追加
  graph[b - 1] << a - 1 # 頂点bと頂点aを結ぶ辺をグラフに追加（無向グラフ）
end
# p graph #=> [[1, 2], [0, 3], [0], [1, 4], [3]]
##【補足】
## 木の構成(入力例1のケース)
## 頂点1（graph[0]）は頂点2（graph[1]）と頂点3（graph[2]）に接続
## 頂点2（graph[1]）は頂点1（graph[0]）と頂点4（graph[3]）に接続
## 頂点3（graph[2]）は頂点1（graph[0]）に接続
## 頂点4（graph[3]）は頂点2（graph[1]）と頂点5（graph[4]）に接続
## 頂点5（graph[4]）は頂点4（graph[3]）に接続

# 各頂点の隣接リストをソート ※深さ優先探索の際に、隣接する頂点を番号が小さい順に訪れるという条件を満たすため
graph.each { |adj| adj.sort! }
# p graph #=> [[1, 2], [0, 3], [0], [1, 4], [3]]

# 未訪問フラグの初期化
unvisited = Array.new(N, true) #=> [true, true, true, true, true]

# 深さ優先探索の実行
dfs(X - 1, graph, unvisited)

入力例1の木（グラフ）の構造

    1
   / \
  2   3
 / 
4
|
5

🟨 ベルマン - フォード法

グラフの最短路問題を解くアルゴリズム。

最短路問題では、辺にコストの付いた「辺重み付きグラフ」が与えられ、「始点」と「終点」が指定されている。始点から終点へ至る路のうち、間を通る辺のコストの総和が最も小さいものを求める問題。

  • 入力グラフの頂点数を$n$、辺数を$m$とした場合の計算時間：$O(nm)$
    • ベルマン - フォード法は、コストの更新操作を$n$巡すれば停止する
    • 1巡にかかる時間は$O(m)$
    • 従って、全体の計算時間は$O(nm)$となる

負のコストを含む辺が存在しても正しく動作する

実装例（Ruby）

解答コード例 
# 入力の読み込み
## 頂点の個数を表す整数 N, 枝の本数を表す整数 M, 頂点の番号を表す整数 S
N, M, S = gets.split.map(&:to_i) #=> 入力例1：5, 5, 1
edges = []
M.times do
  a, b, c = gets.split.map(&:to_i)
  edges << [a - 1, b - 1, c]  # 0 - indexed に変換
end
# p edges #=> 入力例1：[[0, 1, 4], [0, 2, 9], [1, 3, 1], [3, 4, 3], [4, 1, 3]]

# 初期化
INF = Float::INFINITY
dist = Array.new(N, INF)
dist[S - 1] = 0  # 始点の距離を 0 に設定
# p dist #=>入力例1：[0, Infinity, Infinity, Infinity, Infinity]

# ベルマンフォード法の実行
(N - 1).times do
  edges.each do |a, b, c|
    # 頂点aにまだ到達していない場合(dist[a] == INF)、その辺を使って最短距離を更新する意味がないのでスキップする
    # 頂点aを経由してbに移動するコスト(dist[a] + c)が、現在のbへの最短距離(dist[b])よりも小さい場合、その値で更新する
    if dist[a] != INF && dist[a] + c < dist[b]
      dist[b] = dist[a] + c
    end
  end
end

# 結果の出力
dist.each do |d|
  puts d == INF ? "inf" : d
end

🟨 ダイクストラ法

グラフの最短路問題を解くアルゴリズム。
始点から終点へ至る経路のうち、間を通る辺のコストの総和が最も小さいものを求める。

各頂点への最短路を一つずつ決定していきながらグラフを探索する。

  • 入力グラフの頂点数を$n$、辺数を$m$とした場合の計算時間
    • 何も工夫しない場合：$O(n^2)$
    • データ構造を工夫した場合：$O(m + n \log n)$

ダイクストラ法の計算時間は、使用するデータ構造によって異なる

負のコストを含む辺が存在する場合、最短路が正しく求まらないことがある

ベルマン-フォード法と比べ、ダイクストラ法は選ぶ頂点を工夫することで、効率良く最短路を求めている

実装例（Ruby）

解答コード例 
# 入力の読み込み
h, w = gets.split.map(&:to_i) #=> 3, 6
grid = Array.new(h) { gets.split.map(&:to_i) } #=> [[0, 3, 1, 4, 1, 5], [9, 2, 6, 5, 3, 5], [3, 9, 7, 9, 3, 2]]

# ダイクストラ法のために初期化
INF = Float::INFINITY
dist = Array.new(h) { Array.new(w, INF) }
dist[0][0] = grid[0][0] # スタート地点のコスト
# p dist
#=> [
#     [0, Infinity, Infinity, Infinity, Infinity, Infinity],
#     [Infinity, Infinity, Infinity, Infinity, Infinity, Infinity],
#     [Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]
#   ]

# 移動可能な4方向
directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]

# ダイクストラ法の実行
queue = []
queue.push({x: 0, y: 0, cost: grid[0][0]})
# p queue #=> [{:x=>0, :y=>0, :cost=>0}]

# ダイクストラ法の実行
while queue.any?
  # 最小のコストを持つ要素を取り出す
  queue.sort_by! { |e| e[:cost] }
  current = queue.shift
  x, y, current_cost = current[:x], current[:y], current[:cost]

  # 現在のコストがすでに最小コストを更新している場合はスキップ
  next if current_cost > dist[x][y]

  # 隣接する4方向をチェック
  directions.each do |dx, dy|
    # 現在の位置 (x, y) から、移動方向 (dx, dy) に基づいて次に移動する予定の座標を計算
    nx, ny = x + dx, y + dy

    # 「次に移動しようとしている座標 nx（行番号）と ny（列番号）が盤面の範囲内にあるか」をチェック
    if nx >= 0 && nx < h && ny >= 0 && ny < w
      new_cost = current_cost + grid[nx][ny]

      # より小さいコストで到達できる場合、コストを更新
      if new_cost < dist[nx][ny]
        dist[nx][ny] = new_cost
        queue.push({x: nx, y: ny, cost: new_cost})
      end
    end
  end
end
# p dist #=> [[0, 3, 4, 8, 9, 14], [9, 5, 10, 13, 12, 17], [12, 14, 17, 22, 15, 17]]

# ゴール地点の最小コストを出力
puts dist[h-1][w-1] #=> 17

🟨 A* （エー・スター）

グラフの最短路問題を解くアルゴリズム。

ダイクストラ法を発展させたもの。

ダイクストラ法は、終点から遠ざかる方向の頂点の最短路も決定するが、結局これは使われないので無駄になる。

A*は、予め最短コスト（推定値）をヒントとして設定し、その情報を利用することで、無駄な探索を省くように改良したもの。

推定値が実際のコストに近いほど、探索の効率が良い

実際のコストからかけ離れたコストをヒューリスティックコスト（人の手で予め設定する推定コスト）として使うと、ダイクストラ法よりもかえって効率が悪くなってしまうことや、正しい答えが求まらなくなる場合もある

A*は、ゲームプログラミングにおいてプレイヤーを追いかける敵の動きの計算等によく使用される

🟪 クラスカル法

グラフの最小全域木を求めるアルゴリズム。

辺にコストの付いた「辺重み付きグラフ」が与えられた時、そのグラフから辺を選び、選んだ辺のみを使用し全ての頂点を繋げる。ただし、選んだ辺のコストの総和が最小となるようにする。

  • 入力グラフの頂点数を$n$、辺数を$m$とした場合の計算時間：$O(m \log m)$

全ての頂点を繋げる辺集合のことを「全域木」という。
求まった解は、コストが最小の全域木なので「最小全域木」と呼ばれる。

最小全域木は唯一とは限らない。
候補となる辺が複数ある場合に、どの辺を選ぶかに依存する。

最小全域木は、インターネットにおけるルーターの配送経路を決めるアルゴリズム等に利用されている

🟪 プリム法

グラフの最小全域木を求めるアルゴリズム。

このアルゴリズムでは、「領域」というものを考える。

①まず頂点を一つ選択し、領域に加える。
②次に、領域とそれ以外を結ぶ辺をすべて候補として考える。
③候補の中で、コストが一番小さい辺を選ぶ。※最小コストが複数ある場合にはどれを選んでも良い
④これを次の頂点で同様に続ける。

  • 入力グラフの頂点数を$n$、辺数を$m$とした場合の計算時間
    • 単純に実装した場合：$O(nm)$
    • 工夫したデータ構造を使用した場合：$O(m \log n)$

計算時間は、領域内と領域外を結ぶ辺の管理方法と、その中から最小コストの辺を選ぶ方法に依存する

🟩 マッチングアルゴリズム

頂点を共有しない辺の集合を「マッチング」という。
マッチングは、頂点同士をペアにすることを意味している。

マッチングに含まれている辺の数をマッチングの「サイズ」という。

マッチングは「割り当て」に対応しており、極めて応用範囲の広い概念である

その他

他にも、セキュリティやクラスタリング、符号化のアルゴリズム等が存在します。
※本記事では割愛

参考

アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?