開発ドキュメント · アルゴリズム
グラフ探索 · 最短経路と最小全域木 · 動的計画法 · 貪欲法 · 分割統治法 · バックトラッキング
グラフ探索は BFS や DFS で到達可能な頂点をすべて訪問する手法で、重みなし最短経路、連結成分、閉路検出、トポロジカルソートの基礎です。
全6章のガイドダイクストラ法・ベルマン–フォード法・ワーシャル–フロイド法で最短経路を求め、クラスカル法とプリム法で最小全域木を作る方法をまとめます。
全6章のガイド動的計画法(DP)は重なり合う部分問題の答えを記録して再利用する手法で、指数時間かかる探索を表の計算に置き換え、最適化や数え上げを効率よく解きます。
全6章のガイド貪欲法は各段階でその時点で最善に見える選択を行い、後戻りしない設計手法です。区間スケジューリング、ハフマン符号、分割可能ナップサックを高速に解きます。
全6章のガイド