📖
アルゴリズムとデータ構造の復習用
アルゴリズムとデータ構造の復習用
目次
基本的なデータ構造
配列（Array）
┌───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ → インデックス
├───┼───┼───┼───┼───┼───┤
│ 8 │ 4 │ 6 │ 1 │ 3 │ 9 │ → 値
└───┴───┴───┴───┴───┴───┘
特徴
- 連続したメモリ空間に要素を格納
- インデックスによる高速アクセス（O(1)）
- 挿入・削除は遅い（O(n)）
Pythonでの実装例
# Pythonではlistが配列の役割を果たす
arr = [8, 4, 6, 1, 3, 9]
# 要素へのアクセス
print(arr[2]) # 出力: 6
# 要素の追加
arr.append(7) # [8, 4, 6, 1, 3, 9, 7]
# 要素の挿入
arr.insert(1, 5) # [8, 5, 4, 6, 1, 3, 9, 7]
# 要素の削除
arr.pop(2) # 4を削除: [8, 5, 6, 1, 3, 9, 7]
連結リスト（Linked List）
┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐
│ 8 │ ●─┼───>│ 4 │ ●─┼───>│ 6 │ ●─┼───>│ 1 │ / │
└───┴───┘ └───┴───┘ └───┴───┘ └───┴───┘
データ ポインタ データ ポインタ データ ポインタ データ NULL
特徴
- 各ノードがデータと次のノードへのポインタを持つ
- 挿入・削除が高速（O(1)）（ただし、該当位置までの移動が必要）
- ランダムアクセスが遅い（O(n)）
Pythonでの実装例
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def display(self):
elements = []
current = self.head
while current:
elements.append(current.data)
current = current.next
return elements
# 使用例
ll = LinkedList()
ll.append(8)
ll.append(4)
ll.append(6)
ll.append(1)
print(ll.display()) # 出力: [8, 4, 6, 1]
スタック（Stack）
↑ 上から追加・取り出し (LIFO)
┌───┐
│ 9 │ ← Top
├───┤
│ 3 │
├───┤
│ 6 │
├───┤
│ 4 │
└───┘
特徴
- 後入れ先出し（LIFO: Last-In-First-Out）
- 主な操作：push（追加）、pop（取り出し）、peek（参照）
- すべての操作が O(1)
Pythonでの実装例
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
return None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# 使用例
stack = Stack()
stack.push(4)
stack.push(6)
stack.push(3)
stack.push(9)
print(stack.peek()) # 出力: 9
print(stack.pop()) # 出力: 9
print(stack.pop()) # 出力: 3
キュー（Queue）
← 取り出し 追加 →
┌───┬───┬───┬───┬───┐
│ 8 │ 4 │ 6 │ 1 │ 3 │
└───┴───┴───┴───┴───┘
Front Rear
特徴
- 先入れ先出し（FIFO: First-In-First-Out）
- 主な操作：enqueue（追加）、dequeue（取り出し）
- すべての操作が O(1)（適切な実装の場合）
Pythonでの実装例
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.popleft()
return None
def front(self):
if not self.is_empty():
return self.items[0]
return None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# 使用例
queue = Queue()
queue.enqueue(8)
queue.enqueue(4)
queue.enqueue(6)
queue.enqueue(1)
queue.enqueue(3)
print(queue.front()) # 出力: 8
print(queue.dequeue()) # 出力: 8
print(queue.dequeue()) # 出力: 4
ハッシュテーブル（Hash Table）
┌─────────┐
│ ハッシュ関数 │
└─────┬───┘
キー │
"apple" ──┴──> hash("apple") = 2
│
┌───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ → インデックス
├───┼───┼───┼───┼───┤
│ │ │ ● │ │ │
└───┴───┴─┬─┴───┴───┘
│
┌───┴────┐
│ "apple" │
│ 100 │ → (キー, 値)のペア
└────────┘
特徴
- キーから値へのマッピングを提供
- 平均的な挿入・検索・削除の時間計算量は O(1)
- 最悪の場合は O(n)（衝突が多い場合）
Pythonでの実装例
# Pythonではdictがハッシュテーブルの実装
hash_table = {}
# 要素の追加
hash_table["apple"] = 100
hash_table["banana"] = 200
hash_table["cherry"] = 300
# 要素の取得
print(hash_table["banana"]) # 出力: 200
# 要素の存在確認
print("apple" in hash_table) # 出力: True
# 要素の削除
del hash_table["apple"]
ヒープ（Heap）
┌───┐
│ 1 │ ← 根（最小値）
└─┬─┘
┌─────┴─────┐
┌─┴─┐ ┌─┴─┐
│ 3 │ │ 2 │
└─┬─┘ └─┬─┘
┌───┴───┐ ┌───┴───┐
┌─┴─┐ ┌─┴─┐ │ │
│ 5 │ │ 4 │ │ │
└───┘ └───┘ └───────┘
特徴
- 特殊な二分木（完全二分木）
- 最小ヒープ：各ノードの値は子ノードの値以下
- 最大ヒープ：各ノードの値は子ノードの値以上
- 最小値/最大値の取得が O(1)、挿入と削除が O(log n)
Pythonでの実装例
import heapq
# 最小ヒープの作成
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 4)
heapq.heappush(min_heap, 2)
# 最小値の取得（削除せず）
print(min_heap[0]) # 出力: 1
# 最小値の取得と削除
print(heapq.heappop(min_heap)) # 出力: 1
print(heapq.heappop(min_heap)) # 出力: 2
# リストからヒープを作成
arr = [5, 3, 1, 4, 2]
heapq.heapify(arr) # arrをその場で最小ヒープに変換
print(arr) # 出力: [1, 3, 2, 4, 5]
# 最大ヒープとして使用（値を負にする）
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
print(-heapq.heappop(max_heap)) # 出力: 5
木構造（Tree）
┌───┐
│ A │ ← 根
└─┬─┘
┌─────┼─────┐
┌─┴─┐ ┌─┴─┐ ┌─┴─┐
│ B │ │ C │ │ D │ ← 内部ノード
└─┬─┘ └───┘ └─┬─┘
┌───┴───┐ ┌─┴─┐
┌─┴─┐ ┌─┴─┐ ┌─┴─┐
│ E │ │ F │ │ G │ ← 葉ノード
└───┘ └───┘ └───┘
特徴
- 階層的なデータ構造
- 根（ルート）から始まり、子ノードへと枝分かれする
- 二分木：各ノードが最大2つの子を持つ木
Pythonでの実装例（二分木）
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# 二分木の作成
root = TreeNode('A')
root.left = TreeNode('B')
root.right = TreeNode('C')
root.left.left = TreeNode('D')
root.left.right = TreeNode('E')
root.right.left = TreeNode('F')
# 木の走査（深さ優先探索 - 前順）
def preorder(node):
if node:
print(node.value, end=' ')
preorder(node.left)
preorder(node.right)
# 木の走査（深さ優先探索 - 中順）
def inorder(node):
if node:
inorder(node.left)
print(node.value, end=' ')
inorder(node.right)
# 木の走査（深さ優先探索 - 後順）
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node.value, end=' ')
print("前順走査: ", end='')
preorder(root) # 出力: A B D E C F
print("\n中順走査: ", end='')
inorder(root) # 出力: D B E A F C
print("\n後順走査: ", end='')
postorder(root) # 出力: D E B F C A
グラフ（Graph）
B
/ \
/ \
A D
\ /
\ /
C
特徴
- ノード（頂点）とエッジ（辺）からなるデータ構造
- 有向グラフ：エッジに方向がある
- 無向グラフ：エッジに方向がない
- 重み付きグラフ：エッジに値（重み）が付いている
Pythonでの実装例（隣接リスト）
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v, directed=False):
if u not in self.graph:
self.graph[u] = []
if v not in self.graph:
self.graph[v] = []
self.graph[u].append(v)
if not directed:
self.graph[v].append(u)
def print_graph(self):
for vertex in self.graph:
print(f"{vertex} -> {' '.join(map(str, self.graph[vertex]))}")
# 使用例
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
g.print_graph()
# 出力:
# A -> B C
# B -> A D
# C -> A D
# D -> B C
基本的なアルゴリズム
探索アルゴリズム
線形探索（Linear Search）
┌───┬───┬───┬───┬───┬───┐
│ 8 │ 4 │ 6 │ 1 │ 3 │ 9 │
└───┴───┴───┴───┴───┴───┘
↓ ↓ ↓ ↓ ↓ ↓
順番に一つずつ比較する
特徴
- 配列を先頭から順に探索
- 時間計算量：O(n)
- 空間計算量：O(1)
Pythonでの実装例
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
arr = [8, 4, 6, 1, 3, 9]
print(linear_search(arr, 3)) # 出力: 4
print(linear_search(arr, 7)) # 出力: -1
二分探索（Binary Search）
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │
└───┴───┴───┴───┴───┴───┴───┴───┘
↑
中央の要素と比較し、
半分ずつ探索範囲を狭めていく
特徴
- ソートされた配列が前提
- 中央の要素と比較し、探索範囲を半分に絞る
- 時間計算量：O(log n)
- 空間計算量：O(1)（反復版）、O(log n)（再帰版）
Pythonでの実装例
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
arr = [1, 2, 3, 4, 5, 6, 7, 8]
print(binary_search(arr, 5)) # 出力: 4
print(binary_search(arr, 9)) # 出力: -1
深さ優先探索（Depth-First Search, DFS）
A
/ \
B C
/ \ \
D E F
特徴
- グラフやツリーの探索アルゴリズム
- スタックを使用（再帰呼び出しまたは明示的なスタック）
- 可能な限り深く探索してから、バックトラック
- 時間計算量：O(V + E)（Vは頂点数、Eは辺数）
- 空間計算量：O(V)
Pythonでの実装例
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# 隣接リストとしてのグラフ
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
print("DFS:", end=' ')
dfs(graph, 'A') # 出力: DFS: A B D E C F
幅優先探索（Breadth-First Search, BFS）
A レベル0
/ \
B C レベル1
/ \ \
D E F レベル2
特徴
- グラフやツリーの探索アルゴリズム
- キューを使用
- 現在の深さのすべてのノードを探索してから次の深さに進む
- 時間計算量：O(V + E)
- 空間計算量：O(V)
Pythonでの実装例
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
vertex = queue.popleft()
print(vertex, end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 隣接リストとしてのグラフ
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
print("BFS:", end=' ')
bfs(graph, 'A') # 出力: BFS: A B C D E F
ソートアルゴリズム
バブルソート（Bubble Sort）
各パス毎に隣接要素を比較し、必要に応じて交換
┌───┬───┬───┬───┬───┐
│ 5 │ 3 │ 8 │ 1 │ 2 │ 初期状態
└───┴───┴───┴───┴───┘
↓ ↓
比較・交換
┌───┬───┬───┬───┬───┐
│ 3 │ 5 │ 8 │ 1 │ 2 │
└───┴───┴───┴───┴───┘
↓ ↓
比較
┌───┬───┬───┬───┬───┐
│ 3 │ 5 │ 8 │ 1 │ 2 │
└───┴───┴───┴───┴───┘
↓ ↓
比較・交換
特徴
- 隣接する要素を比較し、必要に応じて交換
- 時間計算量：O(n²)
- 空間計算量：O(1)
Pythonでの実装例
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# 最後のi個は既にソート済み
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
arr = [5, 3, 8, 1, 2]
print(bubble_sort(arr)) # 出力: [1, 2, 3, 5, 8]
選択ソート（Selection Sort）
最小値を見つけて先頭と交換
┌───┬───┬───┬───┬───┐
│ 5 │ 3 │ 8 │ 1 │ 2 │ 初期状態
└───┴───┴───┴───┴───┘
* * * * *
最小値1を探す
┌───┬───┬───┬───┬───┐
│ 1 │ 3 │ 8 │ 5 │ 2 │ 1と5を交換
└───┴───┴───┴───┴───┘
* * * *
最小値2を探す
特徴
- 各パスで最小値を見つけ、適切な位置に配置
- 時間計算量：O(n²)
- 空間計算量：O(1)
Pythonでの実装例
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 最小値と現在の位置を交換
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
arr = [5, 3, 8, 1, 2]
print(selection_sort(arr)) # 出力: [1, 2, 3, 5, 8]
挿入ソート（Insertion Sort）
ソート済み部分に新しい要素を挿入
┌───┬───┬───┬───┬───┐
│ 5 │ 3 │ 8 │ 1 │ 2 │ 初期状態
└───┴───┴───┴───┴───┘
↑ →
ソート済み
┌───┬───┬───┬───┬───┐
│ 3 │ 5 │ 8 │ 1 │ 2 │ 3を適切な位置に挿入
└───┴───┴───┴───┴───┘
↑ ↑ →
ソート済み
特徴
- ソート済みの部分配列に新しい要素を適切な位置に挿入
- 小さな配列やほぼソートされた配列に効率的
- 時間計算量：O(n²)
- 空間計算量：O(1)
Pythonでの実装例
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# keyより大きい要素を右に移動
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
arr = [5, 3, 8, 1, 2]
print(insertion_sort(arr)) # 出力: [1, 2, 3, 5, 8]
マージソート（Merge Sort）
分割して再帰的にソート、その後マージ
┌───┬───┬───┬───┬───┐
│ 5 │ 3 │ 8 │ 1 │ 2 │ 初期状態
└───┴───┴───┴───┴───┘
↙ ↘
┌───┬───┐ ┌───┬───┬───┐
│ 5 │ 3 │ │ 8 │ 1 │ 2 │ 分割
└───┴───┘ └───┴───┴───┘
↙ ↘ ↙ ↘
┌───┐ ┌───┐ ┌───┐ ┌───┬───┐
│ 5 │ │ 3 │ │ 8 │ │ 1 │ 2 │ さらに分割
└───┘ └───┘ └───┘ └───┴───┘
↘ ↙ | ↙ ↘
┌───┬───┐ | ┌───┐ ┌───┐
│ 3 │ 5 │ | │ 1 │ │ 2 │ さらに分割
└───┴───┘ | └───┘ └───┘
| | ↘ ↙
| | ┌───┬───┐
| | │ 1 │ 2 │ マージ
| | └───┴───┘
| ↘ ↙
| ┌───┬───┬───┐
| │ 1 │ 2 │ 8 │ マージ
| └───┴───┴───┘
↘ ↙
┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 5 │ 8 │ 最終マージ
└───┴───┴───┴───┴───┘
特徴
- 分割統治法を使用
- 配列を分割し、再帰的にソートしてからマージ
- 時間計算量：O(n log n)
- 空間計算量：O(n)
Pythonでの実装例
def merge_sort(arr):
if len(arr) <= 1:
return arr
# 分割
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# 再帰的にソート
left = merge_sort(left)
right = merge_sort(right)
# マージ
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
arr = [5, 3, 8, 1, 2]
print(merge_sort(arr)) # 出力: [1, 2, 3, 5, 8]
def find_subset(nums, target_sum):
"""
和がtarget_sumになる部分集合を見つける
Args:
nums: 整数のリスト
target_sum: 目標の和
Returns:
和がtarget_sumになる部分集合（存在しなければ空リスト）
"""
n = len(nums)
# DP配列の初期化（どの数字を使ったかも記録）
dp = [None] * (target_sum + 1)
dp[0] = [] # 空集合で和が0
# DPテーブルを埋める
for i, num in enumerate(nums):
for j in range(target_sum, num - 1, -1):
if dp[j - num] is not None:
dp[j] = dp[j - num] + [num]
return dp[target_sum] if dp[target_sum] is not None else []
# 使用例
nums = [3, 34, 4, 12, 5, 2]
target = 9
is_possible = subset_sum(nums, target)
print(f"和が{target}になる部分集合は存在する? {is_possible}")
subset = find_subset(nums, target)
print(f"和が{target}になる部分集合: {subset}")
最長増加部分列（Longest Increasing Subsequence, LIS）
配列: [10, 22, 9, 33, 21, 50, 41, 60, 80]
LIS: [10, 22, 33, 41, 60, 80] (長さ6)
DP表:
i | A[i] | LIS[i]
--+------+-------
0 | 10 | 1
1 | 22 | 2
2 | 9 | 1
3 | 33 | 3
4 | 21 | 2
5 | 50 | 4
6 | 41 | 4
7 | 60 | 5
8 | 80 | 6
特徴
- 配列の中から順序を保ったまま取り出した、最も長い増加部分列を見つける
- 動的計画法で効率的に解ける
- 二分探索を使って更に高速化可能
- 時間計算量: O(n²)（単純なDP）、O(n log n)（二分探索版）
- 空間計算量: O(n)
Pythonでの実装例
def longest_increasing_subsequence(nums):
"""
最長増加部分列の長さを求める（O(n²)版）
Args:
nums: 整数のリスト
Returns:
LISの長さ
"""
if not nums:
return 0
n = len(nums)
# dp[i]はnums[i]で終わるLISの長さ
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
def longest_increasing_subsequence_optimized(nums):
"""
最長増加部分列の長さを求める（O(n log n)版）
Args:
nums: 整数のリスト
Returns:
LISの長さ
"""
import bisect
if not nums:
return 0
# tails[i]は長さi+1のLISの最後の要素の最小値
tails = []
for num in nums:
# 二分探索で挿入位置を見つける
pos = bisect.bisect_left(tails, num)
# 新しい最長部分列ができる場合
if pos == len(tails):
tails.append(num)
# 既存の部分列を改善する場合
else:
tails[pos] = num
return len(tails)
def print_lis(nums):
"""
最長増加部分列自体を求める
Args:
nums: 整数のリスト
Returns:
LISのリスト
"""
if not nums:
return []
n = len(nums)
# dp[i]はnums[i]で終わるLISの長さ
dp = [1] * n
# 経路復元用の配列
prev = [-1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
prev[i] = j
# LISの長さが最大になる終点を見つける
max_length = max(dp)
max_index = dp.index(max_length)
# LISを復元
lis = []
while max_index != -1:
lis.append(nums[max_index])
max_index = prev[max_index]
return list(reversed(lis))
# 使用例
nums = [10, 22, 9, 33, 21, 50, 41, 60, 80]
lis_length = longest_increasing_subsequence(nums)
print(f"最長増加部分列の長さ: {lis_length}")
lis_optimized = longest_increasing_subsequence_optimized(nums)
print(f"最長増加部分列の長さ（最適化版）: {lis_optimized}")
lis = print_lis(nums)
print(f"最長増加部分列: {lis}")
重み付きグラフの応用
最大フロー問題（Maximum Flow Problem）
容量
┌──(10)──┐
│ ▼
S ──(5)─► A ──(9)─► T
│ ▲ ▲
└──(15)─► B ─(4)──────┘
最大フロー = 5 + 9 + 4 = 18
特徴
- ネットワークフローの基本問題
- 始点から終点への最大流量を求める
- フォード-ファルカーソン法、エドモンズ-カープ法、ディニック法などが知られている
- 応用例: 輸送網、通信網、マッチング問題
- 時間計算量:
- フォード-ファルカーソン法: O(max_flow * E)
- エドモンズ-カープ法: O(V * E²)
- ディニック法: O(V² * E)
Pythonでの実装例（エドモンズ-カープ法）
from collections import deque
def edmonds_karp(graph, source, sink):
"""
エドモンズ-カープ法による最大フロー計算
Args:
graph: {ノード: {隣接ノード: 容量}} 形式の有向グラフ
source: 始点
sink: 終点
Returns:
最大フロー値
"""
def bfs(graph, flow, source, sink):
"""BFSで増加路を見つける"""
visited = {source: None}
queue = deque([source])
while queue:
u = queue.popleft()
for v in graph[u]:
# 残余容量が正で、未訪問なら進む
residual = graph[u][v] - flow[u].get(v, 0)
if residual > 0 and v not in visited:
visited[v] = u
queue.append(v)
if v == sink:
break
# 終点に到達できなければNone
if sink not in visited:
return None
# 経路を復元
path = []
u = sink
while u != source:
path.append(u)
u = visited[u]
path.append(source)
path.reverse()
return path
# フロー初期化
flow = {u: {} for u in graph}
max_flow = 0
# 増加路がある限り繰り返す
while True:
path = bfs(graph, flow, source, sink)
if path is None:
break
# 経路上の最小残余容量を見つける
residual = float('inf')
for i in range(len(path) - 1):
u, v = path[i], path[i + 1]
residual = min(residual, graph[u][v] - flow[u].get(v, 0))
# フローを更新
for i in range(len(path) - 1):
u, v = path[i], path[i + 1]
flow[u][v] = flow[u].get(v, 0) + residual
flow[v][u] = flow[v].get(u, 0) - residual
max_flow += residual
return max_flow
# 使用例
graph = {
'S': {'A': 5, 'B': 15},
'A': {'T': 9, 'B': 0},
'B': {'A': 10, 'T': 4},
'T': {}
}
max_flow = edmonds_karp(graph, 'S', 'T')
print(f"最大フロー: {max_flow}")
二部グラフのマッチング（Bipartite Matching）
左側の頂点: A, B, C
右側の頂点: 1, 2, 3, 4
エッジ:
A -- 1
A -- 2
B -- 2
B -- 3
C -- 3
C -- 4
最大マッチング:
A -- 1
B -- 2
C -- 3
特徴
- 二部グラフで最大数の辺を選び、どの頂点も高々1つの辺に含まれるようにする問題
- 最大フロー問題の特殊ケースとして解ける
- フォード-ファルカーソン法の特殊版である、増加路アルゴリズムでも解ける
- ハンガリアン法（Kuhn-Munkres法）は重み付き二部マッチングを解く
- 時間計算量: O(V * E)（増加路アルゴリズム）
Pythonでの実装例（増加路アルゴリズム）
def bipartite_matching(graph, left):
"""
二部グラフの最大マッチングを求める
Args:
graph: {ノード: [隣接ノード]} 形式のグラフ
left: 左側の頂点集合
Returns:
マッチングを表す辞書 {左側の頂点: 右側の頂点}
"""
def dfs(u, visited):
"""増加路を探すDFS"""
for v in graph[u]:
if v in visited:
continue
visited.add(v)
# vが未マッチングか、vのマッチング先から新しい経路があるなら
if v not in matching_right or dfs(matching_right[v], visited):
matching_right[v] = u
matching_left[u] = v
return True
return False
matching_left = {} # 左側の頂点 -> 右側の頂点
matching_right = {} # 右側の頂点 -> 左側の頂点
# 増加路を探す
for u in left:
if u not in matching_left:
visited = set()
dfs(u, visited)
return matching_left
# 使用例
graph = {
'A': ['1', '2'],
'B': ['2', '3'],
'C': ['3', '4'],
'1': ['A'],
'2': ['A', 'B'],
'3': ['B', 'C'],
'4': ['C']
}
left = {'A', 'B', 'C'}
matching = bipartite_matching(graph, left)
print(f"最大マッチング: {matching}")
# マッチング辺の数を表示
print(f"マッチングのサイズ: {len(matching)}")
まとめと比較
データ構造の選択ガイド
| データ構造 | 長所 | 短所 | 適した用途 |
|---|---|---|---|
| 配列 | ランダムアクセスが高速、メモリ効率が良い | 挿入・削除が遅い | 要素の順序が重要、頻繁なアクセスが必要 |
| 連結リスト | 挿入・削除が高速 | ランダムアクセスが遅い | 動的なサイズ変更、頻繁な挿入・削除 |
| スタック | LIFO操作が高速 | ランダムアクセスができない | 関数呼び出し、構文解析、履歴管理 |
| キュー | FIFO操作が高速 | ランダムアクセスができない | 待ち行列、BFS、イベント処理 |
| ハッシュテーブル | 検索・挿入・削除が非常に高速 | 順序の保持ができない | 高速な辞書操作、重複除去 |
| 二分探索木 | 順序付きの操作が高効率 | バランスが崩れると性能低下 | ソートされたデータの効率的な検索 |
| ヒープ | 最大/最小要素の取得が高速 | 他の要素の検索が遅い | 優先度付きキュー、ヒープソート |
| トライ木 | 文字列検索が高速 | メモリ使用量が多い | オートコンプリート、辞書検索 |
| グラフ | 複雑な関係を表現できる | 実装と操作が複雑 | ネットワーク、経路探索、関係モデリング |
| 分離集合 | 集合操作が高速 | 他の操作は制限されている | クラスタリング、連結性判定 |
| セグメント木 | 区間クエリと更新が高速 | 実装が複雑 | 競技プログラミング、区間演算 |
アルゴリズムの比較
| アルゴリズム種類 | 代表例 | 時間計算量 | 空間計算量 | 適した問題 |
|---|---|---|---|---|
| 探索アルゴリズム | ||||
| 線形探索 | - | O(n) | O(1) | 小さなデータ集合、不整列データ |
| 二分探索 | - | O(log n) | O(1) | ソート済みデータの高速検索 |
| グラフ探索 | DFS, BFS | O(V + E) | O(V) | 迷路、ネットワーク探索、最短経路 |
| ヒューリスティック探索 | A*, 遺伝的アルゴリズム | 問題による | 問題による | 最適化問題、NP困難な問題 |
| ソートアルゴリズム | ||||
| 比較ベース | クイックソート, マージソート | O(n log n) | O(log n)~O(n) | 一般的なソートタスク |
| 非比較ベース | カウントソート, バケットソート | O(n + k) | O(n + k) | 範囲が限られた整数のソート |
| 動的計画法 | ||||
| - | ナップサック問題, 最長増加部分列 | 問題による | 問題による | 最適部分構造を持つ問題 |
| グラフアルゴリズム | ||||
| 最短経路 | ダイクストラ法, ベルマン-フォード法 | O((V+E)log V)~O(VE) | O(V) | 経路探索、ナビゲーション |
| 最小全域木 | クラスカル法, プリム法 | O(E log E) | O(V+E) | ネットワーク設計、クラスタリング |
| ネットワークフロー | フォード-ファルカーソン法 | O(max_flow * E) | O(V+E) | 輸送問題、マッチング |
| 文字列アルゴリズム | ||||
| パターンマッチング | KMP, Rabin-Karp | O(n+m) | O(m) | テキスト検索、DNA配列解析 |
| 数値アルゴリズム | ||||
| 整数論 | ユークリッドの互除法 | O(log min(a,b)) | O(1) | 暗号技術、数論的計算 |
| 近似アルゴリズム | ||||
| - | シミュレーテッドアニーリング | 問題による | 問題による | NP困難な最適化問題 |
重要なアルゴリズム設計パラダイム
-
分割統治法（Divide and Conquer）
- 問題を小さな部分問題に分割し、それぞれを解いてから結合
- 例: マージソート、クイックソート、二分探索
- 特徴: 再帰的な実装が多い、並列化の可能性
-
動的計画法（Dynamic Programming）
- 重複する部分問題の解を記録して再利用
- 例: フィボナッチ数列、ナップサック問題、最短経路
- 特徴: メモ化、ボトムアップまたはトップダウンアプローチ
-
貪欲法（Greedy Algorithm）
- 各ステップで局所的に最適な選択を行う
- 例: ダイクストラ法、ハフマン符号化、活動選択問題
- 特徴: 単純で効率的だが、常に最適解を保証しない
-
バックトラッキング（Backtracking）
- 解の候補を段階的に構築し、条件を満たさない場合は戻る
- 例: N-クイーン問題、迷路探索、組み合わせ最適化
- 特徴: 探索空間を効率的に枝刈り
-
ヒューリスティックと近似アルゴリズム（Heuristics & Approximation）
- 厳密な最適解ではなく、「良い」解を効率的に見つける
- 例: 遺伝的アルゴリズム、シミュレーテッドアニーリング
- 特徴: NP困難な問題に対して現実的な時間で解を得る
プログラミングコンテストでの選択指針
-
問題の特性を見極める
- 入力サイズの制約から適切なアルゴリズム複雑性を判断
- 特殊ケース（整列済みデータなど）を活用できないか考慮
-
シンプルから開始
- まず単純なアプローチで解け、その後最適化
- 境界条件を注意深く処理
-
適切なデータ構造を選択
- 必要な操作（挿入、削除、検索など）に最適なものを選ぶ
- メモリ制約を考慮
-
アルゴリズムの前提条件を確認
- 例: 二分探索にはソート済みデータが必要
- 例: ダイクストラ法は負の重みを扱えない
-
時間とメモリのトレードオフを考慮
- 前計算とキャッシュで実行時間を短縮
- 必要に応じてメモリ効率とのバランスを取る### 部分和問題（Subset Sum Problem）
与えられた整数の集合: [3, 34, 4, 12, 5, 2]
目標値: 9
DP表:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
-------+---+---+---+---+---+---+---+---+---+---+
φ | T | F | F | F | F | F | F | F | F | F |
-------+---+---+---+---+---+---+---+---+---+---+
3 | T | F | F | T | F | F | F | F | F | F |
-------+---+---+---+---+---+---+---+---+---+---+
34 | T | F | F | T | F | F | F | F | F | F |
-------+---+---+---+---+---+---+---+---+---+---+
4 | T | F | F | T | T | F | F | T | F | F |
-------+---+---+---+---+---+---+---+---+---+---+
12 | T | F | F | T | T | F | F | T | F | F |
-------+---+---+---+---+---+---+---+---+---+---+
5 | T | F | F | T | T | T | F | T | T | T |
-------+---+---+---+---+---+---+---+---+---+---+
2 | T | F | T | T | T | T | T | T | T | T |
-------+---+---+---+---+---+---+---+---+---+---+
解: True（部分集合 [3, 4, 2] の和は9）
特徴
- 整数集合の中から、和が特定の値になる部分集合を見つける問題
- NP完全問題だが、動的計画法で疑似多項式時間で解ける
- 時間計算量: O(n * sum)（nは要素数、sumは目標和）
- 空間計算量: O(sum)
Pythonでの実装例
def subset_sum(nums, target_sum):
"""
部分和問題を解く
Args:
nums: 整数のリスト
target_sum: 目標の和
Returns:
和がtarget_sumになる部分集合が存在すればTrue
"""
n = len(nums)
# DP配列の初期化
dp = [False] * (target_sum + 1)
dp[0] = True # 空集合で和が0
# DPテーブルを埋める
for num in nums:
for j in range(target_sum, num - 1, -1):
dp[j] = dp[j] or dp[j - num]
return dp[target_sum]
def find_subset(nums, target_sum):
"""
和がtarget_sumになる部分集合を見つける
Args:
nums: 整数のリスト
target_sum: 目標の和
Returns:
和がtarget_sumになる部分集合（存在しなければ空リスト）
"""
n = len(nums)
# DP配列の初期化（どの数字を使ったかも記録）
dp = [None] * (target_sum + 1)
dp[0] = [] # 空集合で和が0
# DPテーブルを埋める
for i, num in enumerate(nums):
for j in range(target_sum, num - 1, -1):
if dp[j - num] is not None:### 整数論アルゴリズム
#### 最大公約数（Greatest Common Divisor, GCD）とユークリッドの互除法
72と54の最大公約数を求める:
72 = 54 × 1 + 18
54 = 18 × 3 + 0
よって、gcd(72, 54) = 18
##### 特徴
- 2つ以上の整数の最大公約数を求める
- ユークリッドの互除法は効率的なアルゴリズム
- 拡張ユークリッドアルゴリズムでは、ベズーの係数も計算可能
- 時間計算量：O(log(min(a, b)))
- 空間計算量：O(1)（反復版）、O(log(min(a, b)))（再帰版）
##### Pythonでの実装例
```python
def gcd(a, b):
"""
ユークリッドの互除法による最大公約数の計算
Args:
a, b: 整数
Returns:
aとbの最大公約数
"""
while b:
a, b = b, a % b
return a
def extended_gcd(a, b):
"""
拡張ユークリッドアルゴリズム
ax + by = gcd(a, b) となるx, yを求める
Args:
a, b: 整数
Returns:
(gcd, x, y): 最大公約数とベズーの係数
"""
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
def lcm(a, b):
"""
最小公倍数の計算
Args:
a, b: 整数
Returns:
aとbの最小公倍数
"""
return a * b // gcd(a, b)
# 使用例
a, b = 72, 54
print(f"gcd({a}, {b}) = {gcd(a, b)}")
print(f"lcm({a}, {b}) = {lcm(a, b)}")
gcd_val, x, y = extended_gcd(a, b)
print(f"{a} * {x} + {b} * {y} = {gcd_val}")
素数判定と素因数分解
エラトステネスのふるい:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
2を素数としてマーク、2の倍数を削除
3を素数としてマーク、3の倍数を削除
...
結果: 2, 3, 5, 7, 11, 13, 17, 19 が素数
特徴
- 素数判定: 与えられた数が素数かどうかを判定
- 素因数分解: 与えられた数を素数の積として表現
- エラトステネスのふるいは一定範囲内の素数を効率的に列挙
- トライアル除算、ミラー-ラビンテスト、ポラード・ロー法などがある
- 時間計算量：
- エラトステネスのふるい: O(n log log n)
- トライアル除算: O(√n)
- ミラー-ラビンテスト: O(k log³ n)（kはテスト回数）
Pythonでの実装例
def is_prime_simple(n):
"""
単純な素数判定（トライアル除算）
Args:
n: 判定対象の整数
Returns:
素数ならTrue、そうでなければFalse
"""
if n <= 1:
return False
if n <= 3:
return True
# 2と3で割り切れるかをチェック
if n % 2 == 0 or n % 3 == 0:
return False
# 6k±1形式の数で割り切れるかをチェック
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
def sieve_of_eratosthenes(n):
"""
エラトステネスのふるいで素数リストを生成
Args:
n: 上限値
Returns:
n以下の素数のリスト
"""
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
i = 2
while i * i <= n:
if is_prime[i]:
# iの倍数を削除
for j in range(i * i, n + 1, i):
is_prime[j] = False
i += 1
# 素数リストを作成
primes = [i for i in range(n + 1) if is_prime[i]]
return primes
def prime_factorization(n):
"""
素因数分解
Args:
n: 分解対象の整数
Returns:
素因数とその指数のディクショナリ
"""
factors = {}
# 2で割り切れる限り割る
while n % 2 == 0:
factors[2] = factors.get(2, 0) + 1
n //= 2
# 3以上の奇数で割っていく
i = 3
while i * i <= n:
while n % i == 0:
factors[i] = factors.get(i, 0) + 1
n //= i
i += 2
# 最後に残った数が1より大きければ、それも素因数
if n > 1:
factors[n] = factors.get(n, 0) + 1
return factors
def miller_rabin(n, k=5):
"""
ミラー-ラビン素数判定法
Args:
n: 判定対象の整数
k: テスト回数
Returns:
素数である確率が高ければTrue
"""
import random
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0:
return False
# n-1 = 2^r * d (dは奇数)
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
# k回のテスト
for _ in range(k):
a = random.randint(2, n - 2)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
# 使用例
print(f"10は素数か: {is_prime_simple(10)}")
print(f"17は素数か: {is_prime_simple(17)}")
primes = sieve_of_eratosthenes(20)
print(f"20以下の素数: {primes}")
n = 60
factors = prime_factorization(n)
print(f"{n}の素因数分解: {factors}") # 出力: {2: 2, 3: 1, 5: 1} (2^2 * 3^1 * 5^1)
print(f"997は素数か (ミラー-ラビン): {miller_rabin(997)}")
モジュラ逆数（Modular Inverse）と中国剰余定理（Chinese Remainder Theorem）
モジュラ逆数の例:
3 * 4 ≡ 1 (mod 11)
なので、4は3のモジュラ逆数 (mod 11)
中国剰余定理の例:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
を満たすxを求める
特徴
- モジュラ逆数: ax ≡ 1 (mod m) となるxを求める
- 中国剰余定理: 連立合同式の解を効率的に計算
- 応用例: RSA暗号、秘密分散法、ガウス消去法
- 時間計算量:
- 拡張ユークリッドによるモジュラ逆数: O(log m)
- 中国剰余定理: O(n²)（nは合同式の数）
Pythonでの実装例
def mod_inverse(a, m):
"""
aのmodulo mにおける逆数を計算
a * x ≡ 1 (mod m)を満たすx
Args:
a: 整数
m: 法
Returns:
モジュラ逆数（存在しない場合はNone）
"""
g, x, y = extended_gcd(a, m)
if g != 1:
# 逆数が存在しない
return None
else:
# 負の値を調整
return (x % m + m) % m
def chinese_remainder_theorem(remainders, moduli):
"""
中国剰余定理
x ≡ r_i (mod m_i) を満たすxを求める
Args:
remainders: 余り [r_1, r_2, ..., r_n]
moduli: 法 [m_1, m_2, ..., m_n]
Returns:
連立合同式の解（すべての法の積を法とする）
"""
n = len(remainders)
if n != len(moduli):
raise ValueError("余りと法の数が一致しません")
# すべての法の積を計算
product = 1
for m in moduli:
product *= m
result = 0
for i in range(n):
# m_i以外の法の積
p = product // moduli[i]
# pとm_iは互いに素であることが必要
inv = mod_inverse(p, moduli[i])
if inv is None:
raise ValueError("解が存在しません")
# 中国剰余定理の公式
result += remainders[i] * p * inv
return result % product
# 使用例
a, m = 3, 11
inv = mod_inverse(a, m)
print(f"{a}のmod {m}における逆数: {inv}")
print(f"確認: ({a} * {inv}) % {m} = {(a * inv) % m}")
remainders = [2, 3, 2]
moduli = [3, 5, 7]
result = chinese_remainder_theorem(remainders, moduli)
print(f"連立合同式の解: {result}")
# 各合同式が満たされているか確認
for i in range(len(moduli)):
print(f"{result} ≡ {remainders[i]} (mod {moduli[i]}): {result % moduli[i] == remainders[i]}")
ヒューリスティック探索
遺伝的アルゴリズム（Genetic Algorithm）
1. 初期集団生成:
[個体1, 個体2, 個体3, ..., 個体N]
2. 適合度評価:
[評価値1, 評価値2, 評価値3, ..., 評価値N]
3. 選択:
高評価な個体を選択 → [個体1, 個体4, 個体7, ...]
4. 交叉:
個体1 + 個体4 → 新個体A
個体7 + 個体1 → 新個体B
...
5. 突然変異:
一部の個体にランダムな変化を与える
6. 世代交代:
新しい集団ができあがる
ステップ2-6を繰り返し、最適解を探索
特徴
- 自然淘汰のプロセスを模倣した最適化アルゴリズム
- 交叉、突然変異などの遺伝的操作で解候補を進化させる
- 複雑な探索空間で局所最適解を避けるのに有効
- 応用例: スケジューリング問題、巡回セールスマン問題、パラメータ最適化
- 時間計算量: 問題設定と終了条件に大きく依存
Pythonでの実装例（巡回セールスマン問題）
import random
import numpy as np
class GeneticAlgorithm:
def __init__(self, cities, pop_size=100, elite_size=20, mutation_rate=0.01, generations=500):
"""
遺伝的アルゴリズムの初期化
Args:
cities: 都市の座標リスト [(x1, y1), (x2, y2), ...]
pop_size: 個体数
elite_size: エリート個体数
mutation_rate: 突然変異率
generations: 世代数
"""
self.cities = cities
self.pop_size = pop_size
self.elite_size = elite_size
self.mutation_rate = mutation_rate
self.generations = generations
def distance(self, city1, city2):
"""2都市間の距離"""
return np.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)
def route_distance(self, route):
"""巡回路の総距離"""
distance = 0
for i in range(len(route)):
from_city = self.cities[route[i]]
to_city = self.cities[route[(i + 1) % len(route)]]
distance += self.distance(from_city, to_city)
return distance
def initial_population(self):
"""初期集団の生成"""
population = []
for _ in range(self.pop_size):
# 都市の添え字のランダムな順列
route = random.sample(range(len(self.cities)), len(self.cities))
population.append(route)
return population
def fitness(self, route):
"""適合度（距離の逆数）"""
return 1 / self.route_distance(route)
def rank_routes(self, population):
"""個体を適合度でランク付け"""
fitness_results = {}
for i in range(len(population)):
fitness_results[i] = self.fitness(population[i])
return sorted(fitness_results.items(), key=lambda x: x[1], reverse=True)
def selection(self, ranked_population):
"""ルーレット選択"""
selection_results = []
# エリート選択
for i in range(self.elite_size):
selection_results.append(ranked_population[i][0])
# ルーレット選択
fitness_sum = sum(rank[1] for rank in ranked_population)
for _ in range(self.pop_size - self.elite_size):
pick = random.random() * fitness_sum
current = 0
for i in range(len(ranked_population)):
current += ranked_population[i][1]
if current >= pick:
selection_results.append(ranked_population[i][0])
break
return selection_results
def create_mating_pool(self, population, selection_results):
"""交配プール作成"""
return [population[i] for i in selection_results]
def crossover(self, parent1, parent2):
"""順序交叉（OX）"""
child = [-1] * len(parent1)
# 交叉点をランダムに選択
start, end = sorted(random.sample(range(len(parent1)), 2))
# 親1から一部を受け継ぐ
for i in range(start, end + 1):
child[i] = parent1[i]
# 親2から残りを受け継ぐ
j = 0
for i in range(len(parent2)):
if parent2[i] not in child:
while j < len(child) and child[j] != -1:
j += 1
if j < len(child):
child[j] = parent2[i]
return child
def breed_population(self, mating_pool):
"""新しい世代を生成"""
children = []
# エリートは無条件で次世代に
for i in range(self.elite_size):
children.append(mating_pool[i])
# 交叉で残りの個体を生成
for i in range(self.pop_size - self.elite_size):
parent1 = random.choice(mating_pool)
parent2 = random.choice(mating_pool)
child = self.crossover(parent1, parent2)
children.append(child)
return children
def mutate(self, individual):
"""突然変異（位置交換）"""
for i in range(len(individual)):
if random.random() < self.mutation_rate:
j = random.randint(0, len(individual) - 1)
individual[i], individual[j] = individual[j], individual[i]
return individual
def mutate_population(self, population):
"""集団全体の突然変異"""
return [self.mutate(individual) for individual in population]
def next_generation(self, current_population):
"""次世代の作成"""
ranked_pop = self.rank_routes(current_population)
selection_results = self.selection(ranked_pop)
mating_pool = self.create_mating_pool(current_population, selection_results)
children = self.breed_population(mating_pool)
return self.mutate_population(children)
def run(self):
"""遺伝的アルゴリズムを実行"""
population = self.initial_population()
for _ in range(self.generations):
population = self.next_generation(population)
# 最良の個体を取得
best_route_index = self.rank_routes(population)[0][0]
best_route = population[best_route_index]
return best_route, self.route_distance(best_route)
# 使用例
# 15都市のランダムな座標を生成
np.random.seed(42)
cities = [(np.random.randint(0, 200), np.random.randint(0, 200)) for _ in range(15)]
ga = GeneticAlgorithm(cities)
best_route, distance = ga.run()
print(f"最適な巡回路: {best_route}")
print(f"総距離: {distance:.2f}")
シミュレーテッドアニーリング（Simulated Annealing）
開始温度 T_start
現在の解 s = 初期解
最良解 s_best = s
繰り返し:
温度 T を更新（徐々に下げる）
新しい解 s' を生成（現在の解の近傍）
ΔE = f(s') - f(s) # コスト関数の変化
if ΔE < 0 then # より良い解なら常に受け入れる
s = s'
else # 悪い解でも確率的に受け入れる
確率 exp(-ΔE / T) で s = s' とする
if f(s) < f(s_best) then
s_best = s
Tが十分小さくなったら終了
特徴
- 物理学の焼きなまし過程を模倣した最適化アルゴリズム
- 局所最適解から抜け出す能力を持つ
- パラメータ調整（冷却スケジュール）が性能に影響
- 応用例: 巡回セールスマン問題、スケジューリング、VLSI設計
- 時間計算量: 温度スケジュールや近傍生成に依存
Pythonでの実装例（巡回セールスマン問題）
import math
import random
import numpy as np
def simulated_annealing(cities, temp=10000, cooling_rate=0.995, stopping_temp=1e-8, stopping_iter=100000):
"""
シミュレーテッドアニーリングによる巡回セールスマン問題の解法
Args:
cities: 都市の座標リスト [(x1, y1), (x2, y2), ...]
temp: 初期温度
cooling_rate: 冷却率
stopping_temp: 停止温度
stopping_iter: 停止イテレーション数
Returns:
(最適経路, 距離)
"""
def distance(city1, city2):
"""2都市間の距離"""
return np.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)
def route_distance(route):
"""ルートの総距離"""
total = 0
for i in range(len(route)):
from_city = cities[route[i]]
to_city = cities[route[(i + 1) % len(route)]]
total += distance(from_city, to_city)
return total
def accept_probability(old_cost, new_cost, temperature):
"""受理確率"""
if new_cost < old_cost:
return 1.0
return math.exp(-(new_cost - old_cost) / temperature)
# 初期解のランダム生成
current_route = list(range(len(cities)))
random.shuffle(current_route)
best_route = current_route.copy()
current_distance = route_distance(current_route)
best_distance = current_distance
# メインループ
iteration = 1
current_temp = temp
while current_temp > stopping_temp and iteration < stopping_iter:
# 新しい解を生成（2点交換）
new_route = current_route.copy()
i, j = sorted(random.sample(range(len(cities)), 2))
new_route[i:j+1] = reversed(new_route[i:j+1])
# 新しい解のコスト
new_distance = route_distance(new_route)
# 受理判定
if random.random() < accept_probability(current_distance, new_distance, current_temp):
current_route = new_route
current_distance = new_distance
# 最良解の更新
if current_distance < best_distance:
best_route = current_route.copy()
best_distance = current_distance
# 温度更新
current_temp *= cooling_rate
iteration += 1
return best_route, best_distance
# 使用例
np.random.seed(42)
cities = [(np.random.randint(0, 200), np.random.randint(0, 200)) for _ in range(15)]
best_route, distance = simulated_annealing(cities)
print(f"最適な巡回路: {best_route}")
print(f"総距離: {distance:.2f}")
動的計画法の応用
編集距離（Levenshtein Distance）
文字列1: "kitten"
文字列2: "sitting"
DP表:
| φ | s | i | t | t | i | n | g |
------+---+---+---+---+---+---+---+---+
φ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
------+---+---+---+---+---+---+---+---+
k | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
------+---+---+---+---+---+---+---+---+
i | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
------+---+---+---+---+---+---+---+---+
t | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
------+---+---+---+---+---+---+---+---+
t | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
------+---+---+---+---+---+---+---+---+
e | 5 | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
------+---+---+---+---+---+---+---+---+
n | 6 | 6 | 5 | 4 | 3 | 3 | 2 | 3 |
------+---+---+---+---+---+---+---+---+
編集距離 = 3
特徴
- 2つの文字列間の類似度を測定する方法
- 1つの文字列をもう1つに変換するために必要な最小操作数
- 操作: 挿入、削除、置換
- 時間計算量: O(m * n)（mとnは文字列の長さ）
- 空間計算量: O(m * n)
Pythonでの実装例
def levenshtein_distance(s1, s2):
"""
2つの文字列間のレーベンシュタイン距離を計算
Args:
s1, s2: 比較する文字列
Returns:
編集距離
"""
# 文字列の長さ
m, n = len(s1), len(s2)
# DPテーブルの初期化
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 最初の行と列を初期化
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# DPテーブルを埋める
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
# 文字が一致する場合
dp[i][j] = dp[i-1][j-1]
else:
# 文字が一致しない場合、3つの操作から最小コストを選択
dp[i][j] = min(
dp[i-1][j] + 1, # 削除
dp[i][j-1] + 1, # 挿入
dp[i-1][j-1] + 1 # 置換
)
return dp[m][n]
def print_edit_operations(s1, s2):
"""編集操作を表示"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(
dp[i-1][j] + 1,
dp[i][j-1] + 1,
dp[i-1][j-1] + 1
)
# 操作を逆順にたどる
i, j = m, n
operations = []
while i > 0 or j > 0:
if i > 0 and j > 0 and s1[i-1] == s2[j-1]:
# 一致
operations.append(f"Keep '{s1[i-1]}'")
i -= 1
j -= 1
elif i > 0 and j > 0 and dp[i][j] == dp[i-1][j-1] + 1:
# 置換
operations.append(f"Replace '{s1[i-1]}' with '{s2[j-1]}'")
i -= 1
j -= 1
elif i > 0 and dp[i][j] == dp[i-1][j] + 1:
# 削除
operations.append(f"Delete '{s1[i-1]}'")
i -= 1
elif j > 0 and dp[i][j] == dp[i][j-1] + 1:
# 挿入
operations.append(f"Insert '{s2[j-1]}'")
j -= 1
operations.reverse()
return operations
# 使用例
s1 = "kitten"
s2 = "sitting"
distance = levenshtein_distance(s1, s2)
print(f"'{s1}'から'{s2}'への編集距離: {distance}")
operations = print_edit_operations(s1, s2)
print("編集操作:")
for op in operations:
print(f" {op}")
```## 高度なアルゴリズム
### 高度なグラフアルゴリズム
#### トポロジカルソート（Topological Sort）
┌─────┐
│ 1 │
└──┬──┘
│
▼
┌────┐ ┌────┐ ┌────┐
│ 2 │ │ 3 │ │ 4 │
└──┬─┘ └──┬─┘ └────┘
│ │
│ ▼
│ ┌────┐
└─►│ 5 │
└────┘
トポロジカルソートの結果: 1, 4, 3, 2, 5
または 1, 2, 3, 4, 5
など（有効な順序は複数ある）
##### 特徴
- 有向非巡回グラフ（DAG）の頂点を線形順序で並べるアルゴリズム
- 各頂点が先行する頂点より前に来ないように並べる
- DFSまたはカーン（Kahn）のアルゴリズムを使用して実装可能
- 時間計算量：O(V + E)
- 空間計算量：O(V)
##### Pythonでの実装例（DFSによる実装）
```python
def topological_sort(graph):
"""
DFSを使用したトポロジカルソート
Args:
graph: {ノード: [隣接ノードのリスト]} 形式の有向グラフ
Returns:
トポロジカル順序のリスト
"""
def dfs(node, visited, temp_mark, result):
# 一時的なマークがある場合、閉路がある
if node in temp_mark:
raise ValueError("グラフは循環的です")
# 未訪問の場合のみ処理
if node not in visited:
# 一時的にマーク
temp_mark.add(node)
# 隣接ノードに対してDFS
for neighbor in graph.get(node, []):
dfs(neighbor, visited, temp_mark, result)
# 訪問済みとしてマーク
visited.add(node)
# 一時マークを削除
temp_mark.remove(node)
# 結果リストの前に追加
result.insert(0, node)
visited = set()
temp_mark = set()
result = []
# すべてのノードに対してDFS
for node in graph:
if node not in visited:
dfs(node, visited, temp_mark, result)
return result
# 使用例
graph = {
1: [2, 3, 4],
2: [5],
3: [5],
4: [],
5: []
}
print(topological_sort(graph)) # 出力: [1, 4, 3, 2, 5]
強連結成分（Strongly Connected Components）
┌──►1──┐
│ ▼
┌──4◄────2
│ │ │
▼ ▼ │
6 5◄────┘
強連結成分:
[1, 2, 4, 5], [6]
特徴
- 有向グラフ内の強連結成分（どの頂点からでも他のすべての頂点に到達可能な最大部分グラフ）を見つける
- コサラジュ（Kosaraju）、タージャン（Tarjan）、ガボウ（Gabow）のアルゴリズムがある
- 時間計算量：O(V + E)
- 空間計算量：O(V)
Pythonでの実装例（コサラジュのアルゴリズム）
def kosaraju(graph):
"""
コサラジュのアルゴリズムで強連結成分を見つける
Args:
graph: {ノード: [隣接ノードのリスト]} 形式の有向グラフ
Returns:
強連結成分のリストのリスト
"""
def dfs_first(node, visited, stack):
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs_first(neighbor, visited, stack)
stack.append(node)
def dfs_second(node, visited, component):
visited.add(node)
component.append(node)
for neighbor in reversed_graph.get(node, []):
if neighbor not in visited:
dfs_second(neighbor, visited, component)
# グラフのすべてのノードを取得
nodes = set(graph.keys())
for values in graph.values():
nodes.update(values)
# グラフの反転を作成
reversed_graph = {node: [] for node in nodes}
for node in graph:
for neighbor in graph[node]:
reversed_graph[neighbor].append(node)
# 一度目のDFSで終了順にノードを積む
visited = set()
stack = []
for node in nodes:
if node not in visited:
dfs_first(node, visited, stack)
# 二度目のDFSで強連結成分を見つける
visited = set()
components = []
while stack:
node = stack.pop()
if node not in visited:
component = []
dfs_second(node, visited, component)
components.append(component)
return components
# 使用例
graph = {
1: [2],
2: [4, 5],
4: [1, 5, 6],
5: [],
6: []
}
sccs = kosaraju(graph)
print("強連結成分:", sccs) # 出力: 強連結成分: [[6], [5], [1, 2, 4]]
最小コストフロー（Minimum Cost Flow）
(容量,コスト)
┌──────────┐
│ ▼
S ──(5,1)─► A ─(3,3)─► T
│ ▲ ▲
└──(3,4)─► B ─(4,2)───┘
特徴
- ネットワークフロー問題の一種
- 容量制約とコスト最小化を同時に満たすフローを計算
- 応用例：輸送問題、マッチング問題、ネットワーク設計
- 一般的な解法としてサイクル消去法、コストスケーリング法がある
- 時間計算量：問題設定と解法による
Pythonでの実装例（サイクル消去法）
import heapq
def minimum_cost_flow(graph, capacities, costs, source, sink, required_flow):
"""
最小コストフローを計算する
Args:
graph: {ノード: [隣接ノードのリスト]}
capacities: {(u, v): 容量}
costs: {(u, v): コスト}
source: 始点
sink: 終点
required_flow: 必要なフロー量
Returns:
(総コスト, {(u, v): フロー量})
"""
# 残余ネットワーク
residual_capacities = {edge: cap for edge, cap in capacities.items()}
for u, v in capacities:
if (v, u) not in residual_capacities:
residual_capacities[(v, u)] = 0
# フロー
flow = {edge: 0 for edge in capacities}
# 総コスト
total_cost = 0
# 現在のフロー量
current_flow = 0
while current_flow < required_flow:
# ダイクストラ法で最短路を見つける
dist = {node: float('infinity') for node in graph}
dist[source] = 0
prev = {node: None for node in graph}
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v in graph[u]:
if (u, v) in residual_capacities and residual_capacities[(u, v)] > 0:
cost = costs.get((u, v), -costs.get((v, u), 0))
if dist[u] + cost < dist[v]:
dist[v] = dist[u] + cost
prev[v] = u
heapq.heappush(pq, (dist[v], v))
# 経路がない場合は終了
if dist[sink] == float('infinity'):
break
# 経路に沿って残余容量最小値を見つける
path_flow = required_flow - current_flow
u = sink
while u != source:
p = prev[u]
path_flow = min(path_flow, residual_capacities[(p, u)])
u = p
# フローを更新
u = sink
while u != source:
p = prev[u]
residual_capacities[(p, u)] -= path_flow
residual_capacities[(u, p)] += path_flow
if (p, u) in flow:
flow[(p, u)] += path_flow
else:
flow[(u, p)] -= path_flow
total_cost += path_flow * costs.get((p, u), -costs.get((u, p), 0))
u = p
current_flow += path_flow
if current_flow < required_flow:
return None, None # 必要なフロー量を送れない
return total_cost, flow
# 使用例
graph = {'S': ['A', 'B'], 'A': ['T'], 'B': ['A', 'T'], 'T': []}
capacities = {('S', 'A'): 5, ('S', 'B'): 3, ('B', 'A'): 2, ('A', 'T'): 3, ('B', 'T'): 4}
costs = {('S', 'A'): 1, ('S', 'B'): 4, ('B', 'A'): 1, ('A', 'T'): 3, ('B', 'T'): 2}
cost, flow = minimum_cost_flow(graph, capacities, costs, 'S', 'T', 5)
print(f"最小コスト: {cost}")
print(f"最適フロー: {flow}")
文字列アルゴリズム
Z アルゴリズム
文字列 S = "ababcababaad"
Z配列 Z = [x, 0, 3, 0, 0, 0, 3, 0, 2, 0, 1, 0]
Z[i]は、S[0...i-1]とS[i...n-1]の共通接頭辞の長さ
例: Z[2] = 3 は、"ababcababaad"と"abcababaad"の共通接頭辞"abc"の長さ
特徴
- 文字列とそのサフィックスの共通接頭辞の長さを効率的に計算
- パターンマッチングやその他の文字列アルゴリズムの基礎
- 時間計算量：O(n)
- 空間計算量：O(n)
Pythonでの実装例
def z_function(s):
"""
Z配列を計算する
Args:
s: 入力文字列
Returns:
Z配列
"""
n = len(s)
z = [0] * n
z[0] = n # 自分自身との比較は全長が一致
# [l,r]は現在のZ-boxを表す
l, r = 0, 0
for i in range(1, n):
if i <= r:
# i はZ-box内にあるので、既知の結果を利用
z[i] = min(r - i + 1, z[i - l])
# Z値を明示的に計算（または拡張）
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
# 新しいZ-boxが現在のものより右に延びる場合は更新
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
return z
def string_matching(text, pattern):
"""
Zアルゴリズムを使用した文字列マッチング
Args:
text: 検索対象テキスト
pattern: 検索パターン
Returns:
パターンが見つかった位置のリスト
"""
# パターンと区切り文字とテキストを連結
combined = pattern + "$" + text
z = z_function(combined)
# パターンの長さと一致するZ値を持つ位置を探す
pattern_len = len(pattern)
results = []
for i in range(pattern_len + 1, len(combined)):
if z[i] == pattern_len:
# テキスト内の位置に変換
results.append(i - pattern_len - 1)
return results
# 使用例
text = "ababcababaad"
pattern = "aba"
matches = string_matching(text, pattern)
print(f"パターン '{pattern}' がテキスト '{text}' の位置 {matches} で見つかりました")
# 出力: パターン 'aba' がテキスト 'ababcababaad' の位置 [0, 5] で見つかりました
ラビン-カープアルゴリズム（Rabin-Karp Algorithm）
テキスト: "abcdefgh"
パターン: "def"
ハッシュ値を使った比較:
"abc" → hash(1)
"bcd" → hash(2)
"cde" → hash(3)
"def" → hash(4) ← パターンのハッシュと一致
"efg" → hash(5)
特徴
- ハッシュ関数を使用した文字列検索アルゴリズム
- ローリングハッシュにより効率的に計算
- 複数パターンの同時検索に適している
- 平均時間計算量：O(n + m)、最悪時間計算量：O(n * m)
- 空間計算量：O(1)
Pythonでの実装例
def rabin_karp(text, pattern):
"""
ラビン-カープアルゴリズムによる文字列検索
Args:
text: 検索対象テキスト
pattern: 検索パターン
Returns:
パターンが見つかった位置のリスト
"""
n = len(text)
m = len(pattern)
if m > n:
return []
# ハッシュのパラメータ
d = 256 # 文字集合のサイズ
q = 101 # 素数（ハッシュ値のモジュロ）
# 初期ハッシュ値
pattern_hash = 0
text_hash = 0
h = 1
# h = d^(m-1) % q
for i in range(m - 1):
h = (h * d) % q
# パターンと最初のウィンドウのハッシュ値を計算
for i in range(m):
pattern_hash = (d * pattern_hash + ord(pattern[i])) % q
text_hash = (d * text_hash + ord(text[i])) % q
results = []
# テキストをスライディングウィンドウで走査
for i in range(n - m + 1):
# ハッシュ値が一致したら文字を一つずつ比較
if pattern_hash == text_hash:
match = True
for j in range(m):
if text[i + j] != pattern[j]:
match = False
break
if match:
results.append(i)
# 次のウィンドウのハッシュ値を計算
if i < n - m:
text_hash = (d * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % q
if text_hash < 0:
text_hash += q
return results
# 使用例
text = "abcdefgh"
pattern = "def"
matches = rabin_karp(text, pattern)
print(f"パターン '{pattern}' がテキスト '{text}' の位置 {matches} で見つかりました")
# 出力: パターン 'def' がテキスト 'abcdefgh' の位置 [3] で見つかりました
計算幾何学
凸包（Convex Hull）
点集合:
• •
• • • •
• • •
• • •
•
凸包:
•---•
/| \
• | \
| \ •
| \ |
| \ |
• \ |
\ \ |
•-----•
特徴
- 点集合を包む最小の凸多角形を計算
- グラハムスキャン、ジャービスマーチ、分割統治法などのアルゴリズムがある
- 応用例：衝突検出、パターン認識、最近点対問題
- 時間計算量：O(n log n)（グラハムスキャン）
- 空間計算量：O(n)
Pythonでの実装例（グラハムスキャン）
def convex_hull(points):
"""
グラハムスキャンを使用して点集合の凸包を計算
Args:
points: [(x, y), ...] 形式の点のリスト
Returns:
凸包を構成する点のリスト
"""
def orientation(p, q, r):
"""
点p, q, rの方向を判定
戻り値: 0 → 一直線, 1 → 時計回り, 2 → 反時計回り
"""
val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
if val == 0:
return 0
return 1 if val > 0 else 2
def squared_dist(p1, p2):
"""2点間の距離の二乗"""
return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
n = len(points)
if n < 3:
return points # 点が3つ未満なら全点が凸包
# 最も左下の点を見つける
min_y_idx = 0
for i in range(1, n):
if points[i][1] < points[min_y_idx][1] or (points[i][1] == points[min_y_idx][1] and points[i][0] < points[min_y_idx][0]):
min_y_idx = i
# 最も左下の点と他の点を入れ替え
points[0], points[min_y_idx] = points[min_y_idx], points[0]
# 残りの点を極座標順（反時計回り）でソート
p0 = points[0]
def compare(p1, p2):
o = orientation(p0, p1, p2)
if o == 0:
return -1 if squared_dist(p0, p1) <= squared_dist(p0, p2) else 1
return -1 if o == 2 else 1
# Pythonのsortedは比較関数としてkeyを使用
sorted_points = [p0] + sorted(points[1:], key=lambda p: (
# p0から見た偏角でソート
math.atan2(p[1] - p0[1], p[0] - p0[0]),
# 同じ偏角なら距離が近い順
squared_dist(p0, p)
))
# Graham Scanを実行
stack = [sorted_points[0], sorted_points[1]]
for i in range(2, n):
# スタックの上の2点と現在の点が時計回りになる間、
# スタックから点をポップ
while len(stack) > 1 and orientation(stack[-2], stack[-1], sorted_points[i]) != 2:
stack.pop()
stack.append(sorted_points[i])
return stack
# 使用例
import math
points = [(0, 0), (1, 1), (2, 2), (3, 1), (3, 3), (1, 3), (0, 2)]
hull = convex_hull(points)
print("凸包を構成する点:", hull)
線分交差判定（Line Segment Intersection）
P1
|
|
P3----P4
|
|
P2
特徴
- 2つの線分が交差するかどうかを判定
- 向きの変化（orientation）を利用して効率的に計算
- コンピュータグラフィックス、衝突検出などで応用
- 時間計算量：O(1)
- 空間計算量：O(1)
Pythonでの実装例
def do_segments_intersect(p1, p2, p3, p4):
"""
2つの線分p1-p2とp3-p4が交差するかを判定
Args:
p1, p2: 線分1の端点 (x, y)
p3, p4: 線分2の端点 (x, y)
Returns:
交差する場合True、そうでなければFalse
"""
def orientation(p, q, r):
"""
点p, q, rの方向を判定
戻り値: 0 → 一直線, 1 → 時計回り, 2 → 反時計回り
"""
val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
if val == 0:
return 0
return 1 if val > 0 else 2
def on_segment(p, q, r):
"""点qが線分p-r上にあるかを判定"""
return (q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and
q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1]))
# 4つの向きを計算
o1 = orientation(p1, p2, p3)
o2 = orientation(p1, p2, p4)
o3 = orientation(p3, p4, p1)
o4 = orientation(p3, p4, p2)
# 一般的な場合
if o1 != o2 and o3 != o4:
return True
# 特殊なケース
# p1, p2, p3が一直線で、p3がp1-p2上にある
if o1 == 0 and on_segment(p1, p3, p2):
return True
# p1, p2, p4が一直線で、p4がp1-p2上にある
if o2 == 0 and on_segment(p1, p4, p2):
return True
# p3, p4, p1が一直線で、p1がp3-p4上にある
if o3 == 0 and on_segment(p3, p1, p4):
return True
# p3, p4, p2が一直線で、p2がp3-p4上にある
if o4 == 0 and on_segment(p3, p2, p4):
return True
# 交差しない
return False
# 使用例
p1 = (1, 1)
p2 = (1, 4)
p3 = (0, 2)
p4 = (3, 2)
print(f"線分{p1}-{p2}と線分{p3}-{p4}は", end=" ")
if do_segments_intersect(p1, p2, p3, p4):
print("交差します")
else:
print("交差しません")
# 出力: 線分(1, 1)-(1, 4)と線分(0, 2)-(3, 2)は 交差します
```# アルゴリズムとデータ構造の基本ガイド
Discussion