『問題解決力を鍛える アルゴリズムとデータ構造』学習メモ

Ch01 what's algorithm

• algorithm: 問題を解くための方法、手順
• binary searchとlinear search
• どんなケースも同じやり方で答えを導ける
• Depth-First Search(DFS)
  • とりあえず突き進むを行き詰るまで繰り返す
  • 探索順序を工夫すると劇的な性能差になるのが魅力。
• Breadth-First Search(BFS)
  • 出発点に近いところから順に探索
  • 何かを達成するための最小手順を知るために使える
• DFS, BFSとも、グラフ上の探索と考えると見通しがよくなる

• matching

  • 2 category間のつながりの問題
    • internet広告配信、レコメンドシステム、マッチングアプリ、シフトスケジューリングなどで使える

• 章末問題

  • 1.4: 九九で2桁の和が6になるものに目をつけるといいのかもしれない
  • 1.6: BFS。地図上の最短経路を求める。

Ch02 計算量とオーダー記法

• 調べるべき組み合わせをマトリックスで考える→ 図2.3
• 一般的なパソコンで1秒間に処理できる計算ステップの回数: 10⁹
• 各オーダーでの入力サイズと計算ステップ回数の関係→ 表2.2
• 指数時間: O(N!), O(2^N)
• 多項式時間: N^dの定数倍で上から抑えられるもの
• 定数時間: O(1)
• 計算量: 以降は最悪計算時間量を指す
• ランダウのO記法の詳細
  • オメガ、シータ
• 章末問題
  • 2.1 N^1/2 > logN
  • 2.2 処理の意味が書いてある。それでも答えられる。
  • 2.3 素数でない数は2からN^1/2までのいずれかを約数に持つ。
  • 2.4 証明なら数学的帰納法がよい。選択肢の数の推移をみる。
  • 2.5 N = 2^kとして考え、対数を扱う。
  • 2.6 分数を積分して対数を出す。

Ch03 設計技法(1): 全探索

• 意義
  • 全探索アルゴリズムを考案することで、解きたい問題の構造に対する深い理解を獲得できることがある。
  • → 結果的に高速なアルゴリズムの設計に結び付くこともある。
• 線形探索
  • 全ての基礎となる重要なアルゴリズム。
  • 多量のデータから特定のデータを探し出す。
  • 条件を満たすものの場所も求める
  • 最小値を求める
  • ペアの全探索
  • 組み合わせの全探索
    • N個の整数からなる集合の部分集合は2^N通りある
    • 部分集合に整数の二進法表現を用いる。
      • code3.5, 表3.2 bit演算で判定する
      • 1 << i: 二進法表現で右からi桁目のみが0であるような値を表す(最も右を0桁目とする)。

• まとめ

  • 全探索は、解きたい問題に対して、考えられるすべての可能性を調べ上げることで解決する手法
  • すべての基礎となる重要なもの。

• 章末問題

  • 3.3
    • worst, second（変数の名前づけについて）
    • 共にINFで初期化で〇
  • 3.4
    • max, minを求めればOK
  • 3.5
    • それぞれの値を2で何回割れるか求める。
    • なんかor演算でも行けたりしないかな
  • 3.6
    • z = N - x - yでok
  • 3.7
    • bitでプラスの位置を表せば〇

Ch04 設計技法(2): 再帰と分割統治法

• 様々な問題に対して、簡潔かつ明快なアルゴリズムを記述できる。
• 再帰関数のテンプレート: basecaseでreturn。その他は再帰。
  • basecaseに対する処理が重要。
  • 引数がbasecaseに近づくようにする。
• 再帰の例
  • ユークリッドの互除法
  • フィボナッチ数列
    • 呼び出しの流れ: 図4.2
• → メモ化, キャッシュ
  • メモにあるかどうかを判定して、あればメモから返せばよい。
  • メモ化: 動的計画法というフレームワークを再帰関数で実現したもの。
• 再帰関数を用いる全探索
  • 部分和問題
    • N番目について場合分け: 図4.4, code4.9
    • メモ化
• 分割統治法
  • 与えられた問題をいくつかの部分問題に分解し、各部分問題を再帰的に解き、それらの解を組み合わせて元の問題の解を構成するアルゴリズム技法。
  • 基礎的な考え方。
  • 真価を発揮するとき: すでに多項式時間のアルゴリズムが得られている問題に対して、より高速なアルゴリズムを設計するために、分割統治法を意識的に用いるとき
  • 入力サイズNに関する計算時間T(N)についての漸化式を考える。
• まとめ
  • 再帰関数を用いる本来の目的: 問題をより小さな問題に分割して解く
    • この考え方に基づくフレームワーク: 分割統治法
• 章末問題
  • 4.1 basecaseと、basecaseに近づく処理を考える。
  • 4.3 三項間漸化式を特性方程式を用いて解く。等比数列を作る。
  • 4.4 T(N)についての漸化式を考える。フィボナッチ数列と同様の増加。-5^1/2の方は0に収束する。
  • 4.5
    • 753それぞれの有無を判定するフラグを使う。フラグは二進法表現が〇。
    • 753だけ使えるのをちゃんと読む。753いずれかを付け足していくことで列挙できる。
    • counterは共有する。
  • 4.6 メモ化。再帰の前で計算済みか確認。計算済みならメモをreturn。

Ch05 設計技法(3): 動的計画法

• 動的計画法
  • 与えられた問題全体を一連の部分問題に上手に分解し、各部分問題に対する解をメモ化しながら、小さな部分問題から大きな部分問題へと順に解を求めていく手法。
  • 分野横断的に適用できる
    • e.g.
      • ナップサック問題
      • スケジューリング問題
      • 発電計画問題
      • 編集距離(diff command)
      • 音声認識パターンマッチング問題
      • 文章の分かち書き
      • 隠れマルコフモデル
  • 一連の部分問題への分解の仕方のパターンは多くない。
• 例題
  • Frog 問題
    • グラフの問題としてとらえる。
    • 過程をメモの値に集約
    • 部分構造最適性: 元の問題の最適性を考えるときに、小さな部分問題についても最適性が要請される
      • → このような構造を利用して最適値を順に決定していく手法が、動的計画法
• 動的計画法に関連する諸概念
  • 緩和
    • テンプレート関数の使用
  • pull-based, push-based
  • 緩和処理の順序のポイントは、頂点uから頂点vへと遷移する辺に関する緩和処理を成立させるためには、dp[u]が確定している必要があること。
  • 全探索のメモ化としての動的計画法
    • 単純な全探索アルゴリズムで指数時間となる問題について、動的計画法により多項式時間アルゴリズムを導ける。
    • 探索過程を集約している → 動的計画法
• ナップサック問題
  • 動的計画法以外にも解法がある。
  • 動的計画法の部分問題の作り方の基本的なパターン: N個の対象物{0,1,...,N-1}に関する問題に対して、最初のi個の対象物{0,1,...,i-1}に関する問題を部分問題として考える。
  • 各段階においていくつかの選択肢が存在するという状況は、動的計画法を有効に適用できそうだということを示す。
  • 考えたテーブル設計でうまく遷移が作れなかった場合に、添え字を付け加えることで遷移が成立するようにする作業がよくある。
    • 添え字を追加する作業: 選択肢をまとめ上げる粒度を細かくすることに対応。
  • 動的計画法: 考えられる場合をグループごとにまとめるイメージの手法。グループの個数とグループ間の遷移の個数が最終的な計算量。
  • 選ぶときと選ばないときの遷移を式にする。
    • 図5-10: テーブル更新の様子。選ばなかった場合の同じウェイトの値と比較している。
• 編集距離
  • 応用: diff command, spell checker, 空間認識・画像認識・音声認識などのパターンマッチング, バイオインフォマティクス(系列アラインメント)
  • テーブル定義: dp[i][j]←Sの最初のi文字分と、Tの最初のj文字分との間の編集距離
  • 編集距離: 対応を作る/ 最小コスト弾性マッチング問題: マッチさせる
• 区間分割の仕方を最適化
  • 区間の表し方。要素の両端と間に番号を振る。[l, r)
  • K: 区間の数。N: 要素の数。t: 0からNまでの区切り。
  • dpのサイズ*緩和処理の対象となる遷移の個数に計算量が依存する。
• まとめ
  • 動的計画法は多くの問題に有効
  • テーブルの設計パターンは意外と少ない。
  • 固有の問題に対して、大局的なパターンと、その問題に固有の事情とを分けて考えられるようになることが大事。
• 章末問題
  • 全体として: 値の定義と、chmax/ chminによって、ループ間の比較は必要なくなる。
  • 5.1 a,b,cについて添え字を加えると、chmax(dp[i+1][k], dp[i][j] + a[i][k])と表すことができる。
    • ↑ a[i],b[i],c[i]とも添え字でまとめてしまうと1行で書くことができる。
    • chmaxは選択肢の数分呼ぶ。次のdpの値を選択肢の数分だけ比較して最大にする。
  • 5.2 dpには値ではなくboolを入れればOK
  • 5.3 5.2と同じ
  • 5.4 boolではなく個数を値として持たせる
  • 5.5 毎回のa[i]について、Wを超えない範囲で足し続けてよい。
    • ただし、Wに対してループしているので、1度足せばよい。
    • 同じi(またはi+1)内で遷移できるパターン
  • 5.6 値で最後の整数の使用回数の最小値を保持する
  • 5.7 dpに文字数を入れる。i, jのとき、S[i], T[j]はカウントされていないため、これらが一致するかどうかで増えるか決まる。
  • 5.8 各区間の平均値は別で求める必要あり。
    • 区間は、要素数の間では遷移がない。区間数でのみ遷移する。追加する区間は場合分けが必要なため、区間追加のためのループが必要になる。これがもう1回分のＮとなる。
  • 5.9 （以降解答なし）start, endが必要だが、endは要素数で表せる。dp[要素数（終了位置）][開始位置]のテーブルを持つ。
    • chmin(dp[i][j], dp[i-s][j] + dp[i][j+s])で求められそう。sは区切りで、要素数の分だけ1つずつ繰り返し試す。

Ch06 設計技法(4): 二分探索法

• 配列の二分探索
  • 配列がソート済みであることが必要。
  • O(logN)
• C++のstd::lower_bound()
  • 値keyが属する区間を特定
• 一般化した二分探索法
  • 各整数xに対してtrue/falseの2値で判定される条件Pが与えられていて、ある整数l. r(l < r)が存在して、以下が成立しているとする。
    • P(l) = false
    • P(r) = true
    • ある整数M(l < M <= r)が存在して、x<Mなるxに対してP(x) = falseであり、x>=Mなるxに対してP(x) = trueである。
  • このとき、D = r - lとして、二分探索法はMをO(logD)の計算量で求めることができるアルゴリズムといえる。
  • leftは常にfalse側、rightは常にtrue側
  • プログラムのデバッグでも使っている考え方
  • （整数ではなく）実数上の二分探索法(二分法ともいう)も可能。求めたい精度によって終了条件を規定する。
• さらに一般化した二分探索法
  • 単調性の仮定を外した二分探索法
  • 一般化した実数上の二分探索法: ある実数区間において連続な関数f(x)が与えられ、その区間に属する2点l, r(l < r)に対して、f(l), f(r)のうちの一方が正で一方が負であるとする。このとき二分探索法（二分法）によって、f(x)=0を満たす実数x(l < x < r)のうち1つを、いくらでも高い精度で求めることができる。
    • 単調性の仮定を外す代わりに関数fに連続性を課す。中間値の定理がxの存在を保証。
• 応用例(1): 年齢当てゲーム
• 応用例(2): std::lower_bound()の活用例
  • ペア和のK以上の中での最小値
    • a[i]を固定して、bについて二分探索。O(NlogN)。
• 応用例(3): 最適化問題を判定問題に
  • 「～という条件を満たす最小値を求めよ」→「xが条件を満たすかどうかを判定せよ」。
  • 最大値の最小化。
    • 「N個すべての値をx以下にできるかどうかを判定してください。」
• 応用例(4): medianを求める
  • median: 小さい順に(N-1)/2番目の値のこと
  • 「N個の非負整数a[0],..,a[N-1]のうち、x未満の整数が(N-1)/2個あるかどうかを判定してください。」
• まとめ
  • 二分探索法をより汎用性の高い手法として捉える。
    • 特に、最適化問題を判定問題に帰着させる考え方は、実用的にも有力な手法
• 章末問題
  • 6.1 まずはソートが必要。あとは、a[i]より大きいことを条件として、right, leftの範囲を絞って要素が1つになるよう、二分探索をすればOK。
  • 6.2 3つ配列があるときは、真ん中を固定することで、ループを1重で済ませられる。あとはただの二分探索。
  • 6.3 O(N^3logN)までしかできなかった。4組のときは、2組ずつ処理することでN²のオーダーで処理できる。
  • 6.4 条件の関数をまず書く。条件に渡すのは、二分探索でのmid。条件判定によって左端か右端にmidを入れる。
    • 条件は、midに対して指定の処理が可能かどうかのみ。
    • 最小値の最大化。ソート+二分探索。
    • Mはただ与えられた値に過ぎない。
    • https://hcpc-hokudai.github.io/archive/algorithm_binary_search_001.pdf
  • 6.5 2重の二分探索。a[0]b[0]..a[N-1]b[N-1]の中間を条件に渡し、さらにa[0]..a[N-1]のループ中で、それぞれb[0]..b[N-1]について二分探索をする。(確認していないけどたぶんあってると思う)
  • 6.6 さらに一般化した二分探索法（ある実数区間において連続な関数f(x)が与えられ、二分探索法（二分法）によって、f(x)=0を満たす実数x(l\<x\<r)のうち1つを、いくらでも高い精度で求めることができる。）の例。
    • sinとかなんか計算は言語に任せてしまえばよい。関数の連続性が重要。
    • すべての解ではなく、ある範囲の1つの解を求めたいときに二分探索法を使える。
  • 6.7 累積和を使うように思うが、分からない。問題の内容も少し違うような。

Ch07 設計技法(5): 貪欲法

• 貪欲法とは
  • 1step先のことのみを考えて、最善の選択を繰り返す方法論。
    • 後先を考えず、その場での最善を選択することを繰り返す方法論。
• 貪欲法が最適解を導くとは限らない
  • 貪欲法によって最適解が導ける問題は、その構造自体によい性質が内包されている可能性が高い。
  • e.g. 最小全域木問題
    • ﾏﾄﾛｲﾄﾞ性、離散凸性
• 貪欲法パターン(1): 交換しても悪化しない
  • 最適化問題は、「探索範囲を予め絞れないか」の考察がきわめて有効
    • f(x') >= f(x)が成立する、ある性質Pを満たすx'を、xを変形して得る。
      • e.g. 区間スケジューリング問題
        • 与えられたN個の区間に対して、どの順序で「選ぶ」「選ばない」の選択をしていくかを上手に定めることが肝要
        • 一般に、区間に関する問題に取り組むときは、まず区間の終端時間でソートすると考えやすくなることが多い。
        • 任意の区間の選び方に対し、終端時刻が最も早い区間を選ぶように変更できる→区間スケジューリング問題の解として、「p（終端時刻が最も早い区間）を含むもの」のみに探索候補を絞ってよいことがわかる。
        • 処理
          • A: 残っている区間のうち、終端時刻が最も早いものを選ぶ（貪欲法）
          • B: その選んだ区間と重なる区間を消す
• 貪欲法パターン(2): 現在がよいほど未来もよい
  • 貪欲法が成立するための単調性
  • Multiple Array
    • 後ろから1ステップずつ考えればよい。
• まとめ
  • 貪欲法：「後先のことを考えず、次のステップのことのみを考えた場合の最善の選択を繰り返す」
  • 問題の構造に関する考察のポイント
    • 探索範囲を絞ることで、現実的な計算時間で全探索が可能になる
    • 意思決定の順序をある基準にそって固定してよいことがわかるので、その順序に沿ったDPによって最適解が求められる
  • 問題の構造をしっかり考察したうえで、その構造を活かしたアルゴリズムを設計することの面白さ
• 章末問題
  • 7.1 a[0]..a[N-1]について繰り返す。その中で、b[0]..b[N-1]に対して二分探索でよさそう。
  • 7.2 青の点のx座標を常に最小を選ぶことで、y座標についてのみ考えれば済むようになる。y座標のmaxとなる点rAは、rが選ばれなかった場合や、よりy座標が小さいrA'に対して常に交換できる。そのため、貪欲法を使用できる。
    • 別のものを使うか、使わなかった場合に対してかならず交換できるとき、貪欲法を使用できる。
  • 7.3 締め切り順にソート。あとは各締め切りを使った時間の合計と比較していけばokと思う。

Ch08 データ構造(1): 配列、連結リスト、ハッシュテーブル

• データ構造を学ぶ意義
  • data structure: データの持ち方
  • クエリ: データ構造に値を挿入して管理したり、データ構造から所望の値を取り出したりするような要求
    • 挿入、削除、含むか判定
  • どのようなデータ構造を用いるかによって、計算時間に大きな差が生じる: 表8.1
• 配列
  • 大量のデータに対し、1つ1つの要素に気軽にアクセスできるようにするためのデータ構造
  • std::vector, list(Python)
  • 〇: 「データa[i]にアクセスする処理」を高速に行える。ランダムアクセス〇。
  • × : 末尾以外の挿入、削除
  • zero-based: 添え字について
• 連結リスト
  • 〇: 挿入、削除
  • × : ランダムアクセス×
  • 各要素をポインタでつなげる
  • ダミーノード: 番兵
  • 自己参照構造体を用いる。自分自身の型へのポインタをメンバに持つ構造体のこと。
• 連結リストの挿入操作と削除操作
  • 挿入の実装
  • 削除の実装
    • 双方向連結リスト
• 配列と連結リストの比較
  • 連結リストは限られた場面で大きな力。
  • 連結リストは、単体ではなく、様々なデータ構造の部品として活用されることが多い。
  • 要素xの検索処理は、いずれもO(N)
    • → ハッシュテーブル: 平均的にO(1)で検索
    • → 平衡二分探索木: O(logN)で検索
  • ハッシュテーブルは、「i番目の要素」や「次の要素」といった、各要素間の順序に関する情報を持たないデータ構造であることに注意が必要。
• ハッシュテーブル
  • T[x]: データ構造中に値xが存在するかを表す値（true/false）
    • T[x]: バケット。バケットソートもある。とても魅力的な考え。
  • バケットを汎用化したものがハッシュテーブル。
  • 整数とは限らない一般的なデータ集合Sの各要素に対し、0 <= h(x) < Mを満たす整数h(x)に対応させる。
    • h(x): ハッシュ関数, 値はハッシュ値
    • x: key
    • どのキーx∈Sに対してもハッシュ値h(x)が異なるようなハッシュ関数を、完全ハッシュ関数
  • 完全ハッシュ関数を設計し、配列Tを用意することで、「挿入」「削除」「検索」といったクエリそれぞれをO(1)で実行できる。
  • O(M)のメモリ容量を必要とする
  • 文字列の集合に対するハッシュ関数: ローリングハッシュ
  • ハッシュの衝突対策
    • 各ハッシュ値ごとに連結リストを作成する
  • ハッシュテーブルの計算量
    • 単純一様ハッシュの仮定
      • ハッシュテーブルの各要素にアクセスする計算量は、平均的にO(1+N/M)となる。
        • α = N/M: 負荷率
        • α = 1/2程度とすれば、十分にO(1)の計算量を達成できる
  • C++, Pythonにおけるハッシュテーブル
    • std::unordered_set, set
    • set(C++)は、いずれのクエリもO(logN)で十分高速。平衡二分探索木の一種である赤黒木を用いて実現されている
  • 連想配列
    • 連想配列を実現するデータ構造として、ハッシュテーブルを使うことができる
    • → 連想配列中の各要素へのアクセスをすべて平均的にO(1)で実行できる
    • e.g. std::unordered_map, dict
    • std::mapは、std::setと同じく多くの場合は赤黒木で実現
• まとめ
  • 配列、連結リスト、ハッシュテーブルについて、「挿入」「削除」「検索」といったクエリに対するパフォーマンスを比較
  • 処理したいクエリに応じて、適切なデータ構造を用いることが肝要。→ 表8.5
• 章末問題
  • 8.5 ハッシュテーブルを使えばいけると思う
  • 8.7 片方はハッシュテーブルを使って、もう片方でループ。K - b[i] = a[j]となるaがあるかどうかハッシュテーブルで判定する

Ch09 データ構造(2): スタックとキュー

• stack, queueの概念
  • 「次々と降ってくるタスクをどのような順序で処理していくか」についての考え方を表現するデータ構造
  • push(x): xを挿入
  • pop(): データ構造から要素を1つ取り出す
  • isEmpty(): データ構造が空か調べる
  • pop時にどの要素を選ぶかにおいて、さまざまなデータ構造を設計する
  • queueではenqueue, dequeue
  • stack: ものが積みあがった状態
    • LIFO
    • e.g. web browserの訪問履歴, text editorのundo系列
  • queue: 古いデータから先に処理。
    • FIFO
    • e.g. 航空券予約のキャンセル待ち処理、印刷機のジョブスケジューリング
• stack, queueの動作と実装
  • いずれも配列を用いて簡単に実現
  • queueはメモリ管理を効率よく行いながら実装することが大変 → 実践的にはstd::queueの使用が〇
  • stackの動作と実装
    • top(: 最後に挿入された要素の添え字の次の添え字) を用いる
      • 「スタックに格納されている要素数」も表す
  • queueの動作と実装
    • 両端が開いている
    • リングバッファ
• まとめ
  • stack, queueは、コンピュータサイエンス全域で登場する基本的な考え方。
  • 重要な応用例: グラフ探索。DFSやBFSという重要なグラフ探索技法を設計できる。
• 章末問題
  • https://qiita.com/drken/items/6a95b57d2e374a3d3292
  • 9.3 (をスタックに入れて、)でpopすればよさそう。
  • 9.2 被演算子をpush, 演算子でpop

Ch10 データ構造(3): グラフと木

• グラフ: 対象物の関係性を数理的に表すもの
  • 連結でサイクルを持たないものは木
  • 木の形状を用いたデータ構造として有用なものを見る
• グラフ
  • グラフの考え方
    • 対象物の関係性を表す
    • 対象物を〇(頂点、vertex)、対象物間の関係を線(辺、edge)で表す
    • グラフの描画は一意ではない
    • グラフGを、頂点の集合Vと、辺の集合Eの組として定義する
      • G = (V, E)
      • 各辺e ∈ E を2つの頂点vi, vj ∈ Vの組と定義して、e = (vi, vj)と表す
    • 隣接(adjacent): 辺eで結ばれていること。隣接した両端は端点(end)という。
    • 接続(incident): 辺eは両endに接続しているという。
    • 重み付きグラフ: 各辺eに実数値または整数値をとる重みが付随したグラフ
    • 多重辺: 複数本の辺が同一頂点間を結ぶ
    • 自己ループ: 両endが同じとなる辺e
    • 単純グラフ: 多重辺も自己ループも持たないグラフ
  • 有向グラフと無向グラフ
    • 有向グラフ: 一方通行の道路といったものをモデル化するのに有効
      • (vi, vj)と(vj, vi)を区別する
  • ウォーク、サイクル、パス
    • いずれも部分グラフ(subgraph)の一種であり、重要
    • ウォーク(walk): sからtへと隣接する頂点をたどっていくことで到達できるとき、s-t walk（s-t路）という。
      • s: 始点、t: 終点
    • サイクル(閉路): 始点と終点が同じウォーク
    • パス(道): 同じ頂点を2度以上通らないウォーク
    • 有向グラフにおいては、始点から終点への方向に沿っている必要がある
    • 長さ: 重み付きグラフでは、それらに含まれる辺の重みの総和。重みなしグラフでは辺の本数。
  • 連結性
    • 連結: 無向グラフGの任意の2頂点s, tに対してs-tパスが存在するとき、Gは連結であるという。
    • 図10-7: 2つのグラフではなく、全体で1つの連結でないグラフが描かれている
    • 連結成分: Gを構成するそれぞれの連結グラフ
    • 連結とは限らないグラフに関する問題を解くときに、まず連結グラフに対する結果を求めてから、それを各連結成分に対して適用するとうまくいくことが多々ある。
      • e.g. 二部グラフ判定
• グラフを用いる定式化の例
  • グラフは非常に強力な数理科学的ツール
  • グラフを用いてモデル化することで、グラフに関する問題として捉えなおすことができる
  • 対象物をグラフを用いて定式化する
  • ソーシャルネットワーク
    • small world現象
    • コミュニティの検出、影響力の高い人を検出、ネットワークの情報伝播力を解析
  • 交通ネットワーク
    • 道路: 交差点がグラフの頂点、鉄道: 駅が頂点
    • 各頂点間の長さは平均的に大きい
    • 平面的。平面グラフ: どの2本の辺も交差しないように平面上に描くことができる
  • ゲームの局面遷移
    • グラフの探索で、必勝法がわかる
  • タスクの依存関係
    • タスクの依存関係をグラフとして整理→適切なタスク順序を決定、クリティカルパスを求める
• グラフの実装
  • コンピュータ上でグラフを扱うためのデータの持ち方、データ構造
    • 隣接リスト表現と隣接行列表現。隣接リスト表現を扱う
      • ↑効率よいアルゴリズムを設計できることが多々あるため
  • 隣接リスト表現
    • 各頂点について、辺でつながる頂点をリストアップ
    • G[v]がvの隣接頂点を表す
    • 入力
      • N(頂点数) M(辺数) と、各辺が渡される
• 重み付きグラフの実装
  • 重み付きの辺を表す構造体Edgeを用意
  • G[v]がvに接続している辺の集合を表す
  • 最短路問題に使う
• 木
  • 無向グラフG=(V, E)が木である: Gが連結で、かつサイクルを持たない
  • 根付き木(rooted tree) ←→ 根なし木(unrooted tree)
    • 特定の1つの頂点を根(root)
    • 頂点に接続している辺が1本のみのもの: 葉(leaf)
    • 親、子、兄弟
  • 部分木と、木の高さ
    • 部分木のroot以外の頂点を子孫
  • 根付き木上の2頂点のパスはただ1つに決まる(根なしも同様)
    • 根とvを結ぶパスの長さ: vの深さ。根の深さは0
    • 根付き木の各頂点の深さの最大値: 木の高さ
• 順序木と二分木
  • 根付き木の構造を用いて、多彩なデータ構造を考えられる
    • ヒープ、二分探索木、Union-Find
  • 順序木と二分木
    • 根付き木において、各頂点vの子頂点の順序を考慮するとき、特に順序木という
      • 兄と弟を区別
      • 表現方法
        • 親頂点へのポインタ、｛各子頂点へのポインタを格納した可変長配列/ 「第1子」を表す頂点へのポインタ、「次の弟」を表す頂点へのポインタ｝
      • すべての頂点に対して高々k個の子頂点しか持たないものをk分木という
        • 二分木において、左側の子頂点を根とした部分木を左部分木、右は右部分木
        • 二分木は、計算量解析において好都合な形状→様々なデータ構造において二分木の構造を採用
          • ヒープ、二分探索木
  • 強平衡二分木
    • 根付き木の構造を持つデータ構造は、多くの場面で、各クエリを処理する計算量がO(h)(hは木の高さ) → 高さをできるだけ抑える
    • → 強平衡二分木: 二分木であり、すべての葉の深さが高々1しか違わないもの
    • 頂点数をNとして、高さがO(logN)
    • すべての葉の深さが等しい二分木: 完全二分木
• 二分木を用いるデータ構造の例(1): ヒープ
  • 正確には二分ヒープを扱う
  • ヒープとは
    • 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
      • 頂点vの親頂点をpとしたとき、key[p] >= key[v]が成立する
      • 木の高さをhとしたとき、木の深さh-1以下の部分については、完全二分木を形成している
      • 木の高さをhとしたとき、木の深さhの部分については、頂点が左詰めされている
    • → ヒープは特に強平衡二分木となっている → 様々なクエリをO(logN)で処理できる
      • 挿入、最大値の取得、最大値の削除が〇
      • 値の検索は× → 平衡二分探索木を使う
  • ヒープの実現方法
    • 配列を用いて実現
    • ヒープの深さdの各頂点を配列の2^d-1,...,2^d+1-2番目に対応
    • 関係性
      • 配列中の添字がkである頂点の左右の子頂点の、配列中の添字がそれぞれ2k+1, 2k+2
      • 配列中の添字がkである頂点の親頂点の、配列中の添字が[(k-1)/2]
  • ヒープのクエリ処理
    • 挿入
      • 挿入した値をキー値にもつ頂点とその親である頂点との間でヒープの条件を満たした状態になるまでキー値の交換を繰り返す
    • 削除
      • 最後尾の頂点を根に持ってくる。その後は挿入と同様、ヒープの条件を満たすまで子の大きい値と交換していく。
  • ヒープの実装例
  • O(N)時間でヒープの構築ができる
• 二分木を用いるデータ構造の例(2): 二分探索木
  • 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
    • 任意の頂点vに対し、vの左部分木に含まれるすべての頂点v'に対して、key[v]>=key[v']が成立し、vの右部分木に含まれるすべての頂点v'に対して、key[v]<=key[v']が成立する
  • いずれのクエリ処理も、木の高さ分の計算量
  • 平衡二分探索木にすることで、O(logN)でクエリを処理できる。ヒープの機能の1つである最大値を取得する処理もO(logN)となる。
    • 実際はO記法で省略される定数部分が大きいので、ヒープで足りればヒープが簡便で〇
• まとめ
  • グラフは、対象物の関係性を表すことができる強力な数理科学的ツール
  • グラフとして定式化して、問題を見通す
  • 特殊なグラフとしての木
    • 順序木は、連結リストの構造をより豊かにしたもの
    • → ヒープや二分探索木などの多彩なデータ構造を設計
• 章末問題
  • 10.5 サイクルを持たないのが木

Ch11 データ構造(4): Union-Find

• グループ分けを効率的に管理するデータ構造
• 根付き木の構造を用いる
• Union-Findとは
  • グループ分けを管理するデータ構造
  • 以下のクエリを高速に処理する
    • issame(x, y): 要素x, yが同じグループに属するかどうか調べる
    • unite(x, y): 要素xを含むグループと、要素yを含むグループとを併合する
• Union-Findの仕組み
  • 1つ1つのグループが根付き木を構成するようにして実現
  • ヒープや二分探索木とは異なり、二分木である必要はない
  • root(x)
    • 要素xを含むグループ（根付き木）の根を返す
    • O(h)
    • issame(), unite()を実現
• Union-Findの計算量を削減する工夫
  • union by size(or union by rank)
  • 経路圧縮
  • 実際上はO(1)とみなせる
• union by size
  • 頂点数の小さい方の根付き木を、大きい方に併合する
  • → 各根付き木の高さをO(logN)で抑えられる
  • 頂点xの深さが1増加するときは、頂点xを含む根付き木の頂点数も2倍以上になる
  • サイズの小さいほうのデータ構造を大きいほうに併合するという手法は、データ構造を併合する場面で一般的に使える
• 経路圧縮
  • xから上へと進んでいって根に到達するまで経路中の各頂点に対し、その親を根に張り替える
• Union-Findの実装
  • 構造体として実装
  • par, siz
• Union-Findの応用: グラフの連結成分の個数
  • 連結成分をグループとして扱う
  • root(x) == xを満たすxを数える
  • O(|E|α(|V|))
• まとめ
  • Union-Findはグループ分けを効率的に管理するデータ構造
  • シンプルな実現方法、奥が深い
  • 適用範囲が広い
  • グラフに関する問題は、Union-Findによっても解くことができる
  • クラスカル法の高速化のためにも使う
• 章末問題
  • 11.1 各辺でループ。各辺のみつながないUnion-Findで、連結成分の個数が2つになればその辺が橋となる
  • 11.2 https://drken1215.hatenablog.com/entry/2019/03/03/224600
    • グラフのクエリ問題で辺を削除するのはとても扱いづらい
    • 辺を追加すると読み替える
    • 求める値が異なる
    • issame(a, b)=trueだったらcontinue, falseなら連結成分の個数が減る
    • グループ分けの問題なので、Union-Findが使える
  • 11.3 道路についてと鉄道についてそれぞれのUnion-Findを持つ
    • サイズを求めればそれぞれのみで行ける頂点の個数が分かる
  • 11.4 重み付きUnion-Findを使う
    • https://qiita.com/drken/items/cce6fc5c579051e64fab#abc-087-d-people-on-a-line
    • 直接つなげるのではなく、連結成分同士をつなげる
    • rootまでの重みを持つ。差が重みになる
    • 差が合わなかったらfalse、マージし切れたら（連結し切れたら）〇

Ch12 ソート

• 分割統治法、ヒープなどのデータ構造、乱択アルゴリズムの考え方など、さまざまなアルゴリズム技法を学ぶことができる題材
• ソートアルゴリズムに用いられるアルゴリズム技法を学ぶ
• ソートとは
  • 与えられたデータの列を、所定の順序に従って整列
  • 実用上とても重要な処理
  • 前処理としても使われる
  • 実用的にも理論的にも重要な処理 → 多数のアルゴリズムがある
• ソートアルゴリズムの良し悪し
  • in-place性と安定性
    • 以下の尺度で良し悪しを評価
      • 計算量
      • in-place性（追加で必要な外部メモリ容量）
      • 安定性（安定ソートかどうか）
    • 基本的なアルゴリズムのため使用機会が多い＆使用時のコンピュータの環境も多岐にわたる特徴がある
      • → 計算量だけでは評価しきれない
    • in-place
      • 外部メモリをほとんど必要とせず、与えられた配列内部のswap操作でソート処理を実現
      • e.g. 挿入ソート、ヒープソート
      • 組込系などのコンピュータ資源の限られた環境では〇
    • 安定
      • ソートの前後で同一の値を持つ要素間で順序関係が保たれること
      • 挿入ソート、マージソートは安定。クイックソート、ヒープソートは安定ではない。
  • どのソートアルゴリズムがよいか
    • ほとんどの場面で、各言語の標準ライブラリを用いれば十分
    • ソートの使いどころの習熟が重要
• 挿入ソート
  • 動作と実装
    • 左からi枚がソートされている状態から、i+1枚目がソートされている状態にする
  • 計算量と性質
    • 最悪はO(N)
    • 場合によっては、クイックソートより高速
    • O(N²)なソートアルゴリズム（他はバブルソートや選択ソートがある）としては以下のよい性質をもつ
      • in-place
      • 安定
• マージソート
  • 動作と実装
    • 分割統治法を活用したソートアルゴリズム
      • 配列を半分に分割し、左右それぞれを再帰的にソートしておき、その両者を併合する
    • 右側の外部配列を降順にして左側の外部配列とつなげることで、つなげた配列の両端を比較して小さい方を抜き出すことを繰り返すだけで済むようになる。
      • → 左右の外部配列が空かどうか確認不要になって〇
  • 計算量と性質
    • O(NlogN)
    • not in-place
      • → 組込系など、ソフトウェアの移植性を重視しつつアルゴリズムを常に高速に動作させたい場合には採用されにくい
      • ただし、必要なメモリ容量は入力受け取りに要するメモリ容量の高々定数倍なので、問題ない場面も多い
    • 安定〇
  • 計算量解析の詳細
    • b^k = N
    • マージソートではa=b=2なのでO(NlogN)
    • 分割統治法の計算量を分解して考えられる
      • 再帰の根の部分において、併合作業に要する計算量O(N) ← a < b
        • 再帰の分岐数が小さくなることで最終的に根の部分が支配的になるため。
      • 再帰の根からの深さが1の部分において、併合作業に要する計算時間 ← a = b
        • 両者が均衡することで、木の各深さにおける計算量がすべてO(N)。それに木の高さO(logN)をかける。
      • 再帰の葉の部分に要する計算時間の総和のオーダーO(N^logba) ← a > b
        • 再帰の分岐数が大きくなることで最終的に葉の部分が支配的になるため。
      • 図12-5
• クイックソート
  • 動作と実装
    • 配列の中から適当な要素pivotを選び出し、配列全体をpivot未満のグループとpivot以上のグループに分割して、それぞれを再帰的に解く
    • 添え字を2つ使って、いったん選んだpivotを右端に移し、配列を左から順に走査
    • a[j]がpivotより小さかったら、a[i]とa[j]をswapしてiを進める
    • 最後にa[i]とpivotをswap
    • 外部配列を必要とせずin-place
  • 計算量と性質
    • 最悪時間計算量はθ(N²)
      • ただし、1:99でも、常に1:99ならO(NlogN)になる程度
    • 実用上はマージソートより高速に動作
    • ヒープソートとのハイブリッド方式であるイントロソートをベースとした実装がC++にある
  • 乱択クイックソート
    • ここまでのクイックソートは、平均的なケースには高速だが、悪意あるケースに弱い
    • → 乱択クイックソート
    • 入力分布に偏りがある場面では、乱択化をする
    • → O(NlogN)
    • 1 + 1/2 + ... + 1/N = O(logN)を用いて解析
      • i, i+1, ... , j-1, j番目の要素の中でi, j番目のどちらかの要素が最初に選択される確率を使う
• ヒープソート
  • 最悪でも計算量はO(NlogN)
  • 安定ではなく、平均的な速度ではクイックソートに劣る
  • ただし、ヒープ自体が重要なデータ構造
    • ダイクストラ法を高速化するときにもヒープが活躍する
  • ソートしたい配列自体をヒープにすることで、in-placeになる
• ソートの計算量の下界
  • 比較ソートアルゴリズム: ソート順序が入力要素の比較にのみ基づいて決定される
    • 最悪の場合は、Ω(NlogN)回の比較が必要
  • 2^h >= N!から求めていく
• バケットソート
  • 比較ソートアルゴリズムではない
  • ソートしたい配列aの各要素値は0以上A未満の整数値であるという仮定の下で、O(N+A)
  • バケットソートのアイディアを示す配列
    • num[x]←配列a中に値xを持つ要素が何個存在するか
  • AがA=O(N)であると考えられる程度の小ささである場合に限られる
  • 累積和を取り、値a[i]が全体の中で何番目に小さいかを求める
• まとめ
  • 分割統治法、その計算量解析、乱択アルゴリズムの考え方など、さまざまなアルゴリズム技法を扱った
    • ソートに限らず、数多くの問題の解決に役立てられる
  • ソート自体もさまざまなアルゴリズムの前処理としてしばしば有効
    • e.g. 配列の二分探索、貪欲法、コンピュータグラフィックス
  • ソートは数多くのアルゴリズム設計において基本的な役割を果たす
• 章末問題
  • 12.1 インデックスと値の組を配列で持つ。値でソート。ソート後のインデックスを入れる。元のインデックスでソート。
    • ソートする。それぞれの値で二分探索する。どちらもO(NlogN)。
  • 12.2 金額と本数の組を配列で持つ。金額でソートして足していけばOK。
  • 12.5 http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad11/ad11-06.pdf
    • たぶんこれ
    • 軸要素の選び方を工夫することで、次の反復での要素数を3/4n以下とできる
  • 12.6 もう1回同じ問題に当たったら考えよう
    • https://img.atcoder.jp/tenka1-2017/editorial.pdf

Ch13 グラフ(1): グラフ探索

• グラフ探索を学ぶ意義
  • あらゆるグラフアルゴリズムの基礎
  • 単にグラフに関する問題を解決できるだけでなく、さまざまな対象物に対する探索を見通しよく扱えるようになる
  • ウォーク、サイクル、パスや連結性も自在に扱える
• DFS,BFS
  • グラフ探索の基本形
    • 問題設定: グラフ上の代表的な1つの頂点s∈Vを指定して、sから辺をたどって到達できる各頂点を探索する
    • stack(DFS), queue(BFS)を用いて実現
    • todo, seenを管理する
    • seen[x] = trueならばその頂点xを飛ばすのが重要
• 再帰関数を用いるDFS
  • 簡潔に実装できる
  • 再帰関数を用いることで、「行きがけ順」「帰りがけ順」という重要な概念も明快なものになる
• 「行きがけ順」と「帰りがけ順」
  • 頂点vをtodoから取り出すタイミングと、再帰関数dfs(G, v)を呼び出すタイミングが同じ ← これが行きがけ順
  • 再帰関数dfs(G, v)を抜けるタイミング ← 帰りがけ順
  • 行きがけ順では、vの子孫となる頂点はすべてvよりも後に登場
  • 帰りがけ順では、vの子孫となる頂点はすべてvよりも前に登場
    • DAGのトポロジカルソート順を求める際にも重要
• 最短路アルゴリズムとしてのBFS
  • 探索の始点となる頂点sから、各頂点への最短路を求めるアルゴリズムともみなせる
  • dist, queで管理
  • グラフGの任意の辺E=(u, v)について、dist[u]とdist[v]の差は1以下
  • BFSはdistの値が小さくなるところから順に探索するアルゴリズム
• DFS, BFSの計算量
  • グラフG=(V, E)に対するアルゴリズムの計算量を述べるときは、通常は、頂点数|V|, 変数|E|の2つを入力サイズとする
  • 密グラフ: |E|=θ(|V|^2)
    • e.g. 完全グラフ: すべての頂点間に辺があるような単純グラフ
  • 疎グラフ: |E|=O(|V|)
    • e.g. 各頂点について接続している辺の本数が高々k本であるようなグラフ
  • DFS, BFSとも、O(|V| + |E|)
  • グラフを入力として受け取るのと同等の計算量で探索可能
• グラフ探索例(1): s-tパスを求める
  • 頂点sを始点としたグラフ探索。その過程で頂点tを訪問したかどうかを調べることで解ける
• グラフ探索例(2): 二部グラフ判定
  • 二部グラフ: グラフを左右のカテゴリに分割して、同じカテゴリ内の頂点間には辺がない状態にできること
  • 白に隣接した頂点はすべて黒に塗る。逆も同じ。
  • 両端点が同色であるような辺が検出されたら、二部グラフでないことが確定する ←→ 探索が終了すれば二部グラフ
• グラフ探索例(3): トポロジカルソート
  • 与えられた有向グラフに対し、各頂点を辺の向きに沿うように順序づけて並び替えること
  • 応用例: makeの依存関係解決処理
  • 与えられるグラフGが有向サイクルを持たないことが必要十分条件 ← このような有向グラフをDAG(Directed Acyclic Graph)と呼ぶ
  • トポロジカルソート順は一般には一意ではなく、複数通り考えられる
  • 再帰関数を用いるDFSに、ほんの少し手を加えるだけで実現可能
  • idea: DFSにおける再帰関数を抜けた順序に頂点を並べ、それを逆順に並べ直すことでトポロジカルソート順が得られる
• グラフ探索例(4): 木上の動的計画法
  • 根なし木に対しても便宜的に根をどれか1つ決めて根付き木とすることで、しばしば見通しが良くなる
    • 木に根を指定することで、「系統樹」としての構造が生まれる
  • ある1つの頂点を決めて根にすることで形成される根付き木の形状を求める問題を考える
    • 各頂点vに対して以下の値を求める
      • 頂点vの深さ
      • 頂点vを根とした部分木のサイズ（部分木に含まれる頂点数）
    • 子情報をまとめる処理のため、BFSよりDFS
    • 木がサイクルを持たないことを利用して、実装を簡潔にする
      • 根なし木を根付き木としたときの各頂点の深さを求める
    • 部分木サイズの漸化式
      • subtree_size[v] = 1 + Σc:(vの子頂点)subtree_size[c]
      • 1は頂点v自身
      • 頂点vの各子頂点cに対してsubtree_size[c]が確定している必要がある
      • → 帰りがけ時に実行する必要がある
    • 子頂点についての情報を用いて、親頂点についての情報を更新する: DPを木に対して適用
    • O(|V|)
  • 各頂点の深さ: 行きがけ時に求めた
  • 各頂点を根としたときの部分木のサイズ: 帰りがけ時に求めた
  • 行きがけ順を意識した処理は「親頂点についての情報を子頂点に配る」のに適していて、帰りがけ順を意識した処理は「子頂点の情報を集めて親頂点の情報を更新する」のに適している
• まとめ
  • グラフ探索の技法として、DFS, BFS。あらゆるグラフアルゴリズムの基礎となる重要なもの。
    • 最短路アルゴリズムはBFSを一般化したもの
    • ネットワークフローでは、サブルーチンとしてグラフ探索技法
• 章末問題
  • 13.6 https://qiita.com/drken/items/a803d4fc4a727e02f7ba#4-6-%E3%82%B5%E3%82%A4%E3%82%AF%E3%83%AB%E6%A4%9C%E5%87%BA
    • 与えられたグラフがサイクルを含むということは、ある頂点 v に対して、頂点 v から出発した探索が、v から行くことのできる全頂点の探索を終えるよりも先に (すなわち帰りがけの状態になる前に)、v に戻って来てしまうということ

Ch14 グラフ(2): 最短路問題

• グラフの各辺に重みがある場合の最短路問題に対する解法を見る
• → 現実世界の問題への応用範囲が飛躍的に広がる
• DPや貪欲法の応用がある
• 最短路問題とは
  • グラフ上で長さが最小の路（ウォーク）を求める問題
  • l(e): 各辺の重み
  • l(W): 路W(walk)の長さ
  • l(C): 閉路(cycle)Cの長さ
  • l(P): 道P(path)の長さ
  • カーナビや鉄道の乗換案内サービスという応用が広いだけでなく、理論的にも重要な問題
  • 重み付き有向グラフ
    • 一般性が高い考察対象
  • 単一始点最短路問題
    • 各頂点への最短路を重ね合わせると頂点s(=0)を根とした根付き木になる
  • 負辺と負閉路
    • 負閉路はいくらでも路長を小さくできる
    • 負閉路を持たないか、始点から負閉路に到達できない、または負閉路から頂点vに到達できない場合は、最短路を求められる
• 最短路問題の整理
  • DAG上の最短路問題を考えるときは、「どの辺から順に緩和していけばよいか」があらかじめ自明であった
  • 閉路を持つグラフでは、どの辺から順に緩和していけばよいかが明らかでない → より高度なアルゴリズムが必要
    • ベルマン・フォード法: 負の重みの辺も含むグラフ
    • ダイクストラ法: 辺の重みがすべて非負なグラフ
    • DP: DAG
    • 重みなしグラフ: BFS
• 緩和
  • DPで導入した緩和。chmin。
  • 更新したかどうかをboolで返すようにする
  • いずれの最短路アルゴリズムも、始点sから各頂点vへの最短路長を推定する値d[v]を管理し、各辺についての緩和を繰り返していくもの
  • 図14-4: 最短路を求めることを、ひもをピンと張ることと解釈する
  • 緩和の持つ意味
    • 図14-5: 数直線上にプロット
    • 各節点を少しずつ節点s方向へと引き寄せていくアルゴリズム
    • 「どの辺に対して緩和を行っても節点の位置が更新されない状態」となったならば、アルゴリズムを終了できる
• DAG上の最短路問題: 動的計画法
  • DAGにおける緩和処理の順序のポイント
    • 各辺e=(u, v)に対して緩和処理を実施するときには、頂点uに対するd[u]が真の最短路長に収束している
    • ↑ トポロジカルソートで担保。緩和すべき辺の順序を明らかにできる
• 単一始点最短路問題: ベルマン・フォード法
  • 有効閉路を含む有向グラフに対しても最短路を求めることのできるアルゴリズムを考える
  • もし始点sから到達できる負閉路が存在するならばその旨を報告し、負閉路が存在しないならば各頂点vへの最短路を求めるアルゴリズム
  • 辺の重みがすべて非負であることが保証されている場合は、ダイクストラ法が〇
  • アイディア
    • 「各辺に対して一通り緩和する（順序は不問）」という操作を、最短路長推定値d[v]が更新されなくなるまで反復する
    • 高々|V|-1回の反復で、d[v]の値が真の最短路長d[v]に収束する
    • → 各辺に対する緩和をO(|V|)回反復するため、O(|V||E|)
    • |V|回目の反復時にある辺e=(u, v)が存在して、辺eに関する緩和によってd[v]の値が更新されるとき、始点sから到達可能な負閉路がある
  • 実装
    • 更新が発生しなければ反復を打ち切る
  • 正当性
    • 路を道にしても長さは減少しない
• 単一始点最短路問題: ダイクストラ法
  • すべての辺が非負であることが分かっている場合には、より効率的
  • 2種類のダイクストラ法
    • 実現するためのデータ構造として何を用いるかによって、計算量が変わる
      • 単純に実装した場合の、計算量O(|V|^2)の方法
      • ヒープを用いる場合の、計算量O(|E|log|V|)の方法
    • 密グラフでは前者が〇、疎グラフでは後者が〇
  • 単純なダイクストラ法
    • 貪欲法に基づいたアルゴリズム
    • 各辺が非負と分かっている場合は、最短路長推定値d[v]を動的に更新していく過程で、緩和を行うべき頂点順序が自動的に決まる構造になる
    • 「すでに最短路が求められていることが確定している頂点の集合S」を管理する
      • 「まだSに含まれていない頂点vのうち、d[v]の値が最小の頂点」に着目(始点とする頂点を探す)
      • →　頂点vをSに挿入し、頂点vを始点とする各辺について緩和
  • 直感的なイメージ
    • 「各節点を左から順にひもをピンと張っていく動作」をアルゴリズムとして実現したもの
    • 右手のつまみを選び、節点vとほかの節点間のひもをピンと張っていく
  • 正当性
    • 数学的帰納法で示す
  • 疎グラフの場合: ヒープを用いた高速化
    • 疎グラフであればO(|V|log|V|)
    • ダイクストラ法の高速化を目指す部分
      • 使用済みでない頂点vのうち、d[v]の値が最小の頂点vを求める部分
    • ヒープの各要素
      • 使用済みでない頂点v
      • その頂点vにおけるd[v]
    • 更新後のd[v]の値を新たにヒープに挿入する
      • 古いd[v]はごみとして残るだけなので問題ない
      • ヒープサイズは高々|E|
    • 最良優先探索
    • 取り出したdよりdist[v]が小さいときは、(d, v)はごみ
    • https://cpprefjp.github.io/reference/queue/priority_queue.html
      • 要素の型、内部コンテナ、昇順降順を指定する
• 全点対間最短路問題: フロイド・ワーシャル法
  • DPに基づいて解く
  • O(|V|^3)
  • フロイド・ワーシャル法におけるDP
    • dp[k][i][j]←頂点0,1,...,k-1のみを中継地点として通ってよいとした場合の、頂点iから頂点jへの最短路長
    • dp[k][i][j]の値を用いて、dp[k+1][i][j]の値を更新することを考える
    • 実際はdpは2次元でよく、kからk+1の更新はin-place
    • dp[v][v]<0となる頂点vが存在すれば、負閉路がある
  • for文の構造は、トロピカル線形代数と呼ばれる分野で、ある種の行列の累乗計算を実現したものとみなせる
• 参考: ポテンシャルと差分制約系
  • ポテンシャル: 各節点間がピンと張られているとは限らない場合において、各節点の位置関係としてあり得るもの
    • 各頂点vに対して値p[v]が定まっているとき、任意の辺e=(u, v)に対して、p[v]-p[u]<=l(e)を満たすようなp
  • 最短路問題の最適性の証拠
    • 頂点sから頂点vへ到達可能であるとする。このとき、d*[v]=max{p[v]-p[s]|pはポテンシャル}が成立する
      • pをポテンシャルとしてp[v]-p[s]のmaxを求める問題が、sを始点としてvへの最短路長を求める問題の双対問題となっていることを表す
    • →　差分制約系の最適化問題に対し、適切なグラフを構築して最短路アルゴリズムを適用して解くことができることがわかる
• まとめ
  • グラフ上の最短路を求める問題の解放として、古典的によく知られているものをまとめた章。
  • DP、貪欲法、グラフ探索、ヒープなどの、アルゴリズム設計技法・データ構造が活躍
  • 最短路問題は実用上重要な問題なだけでなく、理論的に重要な位置づけ
• 章末問題
  • 14.1 トポロジカルソート→DP
  • 14.2 https://drken1215.hatenablog.com/entry/2019/02/16/075900
  • 14.3 https://drken1215.hatenablog.com/entry/2019/07/01/111500
    • 頂点vを(v, 0), (v, 1), (v, 2)に拡張する
  • 14.4 https://betrue12.hateblo.jp/entry/2018/12/08/000020
    • 0-1BFS.両端に挿入できるキューを使う．
  • 14.5 http://fluffyowl.hatenablog.com/entry/2017/11/07/194832
    • https://img.atcoder.jp/arc084/editorial.pdf
    • 全ての正整数は，1から始めて，以下の2つの操作の繰り返しで作れる
      • 1足す．各桁の和は1増える．
      • 10倍する．各桁の和は変わらない．
    • 各頂点をmodKで同一視することで，頂点を0からK-1のK個で考えることができる．
    • 1から0への最短路を求める．
    • 0-1BFSを用いる
    • modKで0の集合 = Kの倍数の集合

Ch15 グラフ(3): 最小全域木問題

• ネットワーク設計において基本的な問題の1つ
• いくつかの通信拠点をすべて通信用ケーブルでつなぎ，すべての建物間で通信できるようにしたいとする．これを最小コストで実現する方法を問う問題．
• クラスカル法で解く．
  • 貪欲法に基づく．
    • 構造自体によい性質が内包されている．
    • きわめて深淵で美しい理論が背後にある問題．
• 最小全域木問題とは
  • w(e): グラフの各辺の重み
  • Gの部分グラフであって木であるもののうち，Gの全頂点をつなぐものを全域木(T)と呼ぶ．
    • w(T): 重みは，w(e)の総和．
  • 最小全域木問題とは，重みが最小の全域木を求める問題．
    • 最小の長さのケーブルで全地点を接続する問題．
• クラスカル法
  • 最小全域木を求めるクラスカル法
    • 辺集合Tを空集合とする．
    • 各辺を重みが小さい順にソートして，e0,e1,...,eM-1とする．
    • 各i=0,1,...,M-1に対して:
      • Tに辺eiを追加したときに，サイクルが形成されるならば:
        • 辺eiを破棄
      • サイクルが形成されないならば:
        • Tにeiを追加
    • Tが求める最小全域木となる．
• クラスカル法の実装
  • グラフGの各辺を，辺の重みが小さい順にソート．
  • Union-Findを用いることで，効率的に実現．
    • 開始時点では，Union-Findの各頂点が単独で別々のグループを形成している状態とする．
    • 新たな辺e=(u,v)を追加するとき，Union-Find上の点u',v'について，unite(u',v')を実施する
      • サイクルが形成されてしまうかどうかを，u'とv'が同じグループに属するかで判定できる
    • O(|E|log|V|)
• 全域木の構造
  • クラスカル法は，自然な貪欲法に基づくアルゴリズムだが，最適解が求められる理由・正当性を見る．
  • カット
    • グラフG=(V,E)のカットとは，頂点集合Vの分割(X,Y)
    • X,Yはともに非空集合
    • X∪Y=V, X∩Y=∅を満たす必要がある．
    • Xに含まれる頂点とYに含まれる頂点を結ぶ辺をカット辺
    • カット辺全体の集合をカットセット
  • 基本サイクル
    • 全域木TとTに含まれない辺eで形成されるサイクル
    • 基本サイクル上の別の辺fを1つ取って新たな全域木T'を作る．
      • fは(基本)サイクル上なので，T'も全域木となる．
    • 最小全域木の基本サイクルに関する性質
      • 連結な重み付き無向グラフGにおいて，Tを最小全域木とする．Tに含まれない辺eを1つとって，Tとeに関する基本サイクルをCとする．このとき，Cに含まれる辺のうち，辺eは重みが最大の辺となっている．
  • 基本カットセット
    • Tに含まれる辺eを1つとり，eを取り除くことによって分割される2つの部分木の頂点集合をX,Yとする．
    • (X,Y)のカットに伴うカットセットを，Tとeに関する基本カットセットと呼ぶ．
    • 最小全域木の基本カットセットに関する性質
      • 連結な重み付き無向グラフGにおいて，Tを最小全域木とする．Tに含まれる辺eを1つとって，T,eに関する基本カットセットをCとする．このとき，Cに含まれる辺のうち，辺eは重みが最小の辺となる．
• クラスカル法の正当性
  • 最小全域木の最適性条件
    • 以下の2条件が同値
      • Tは最小全域木である
      • Tに含まれない任意の辺eに対して，Tとeに関する基本サイクルにおいてeの重みは最大
    • クラスカル法によって求められる全域木はBを満たすので，最小全域木
  • 局所最適解
  • 全域木間での辺の交換
    • 連結な重み付きグラフG=(V,E)において，2つの相異なる全域木をS,Tとする.Sには含まれるがTには含まれないeを1つとる．このとき，Tに含まれるがSには含まれない辺fが存在して，S'=S-e+fも全域木となる．
    • S,eに関する基本カットセットと，T,eに関する基本サイクルにともに含まれる辺のうちeでない辺がf．
  • → SをS’とすることでTに近づく
  • w(S)>=w(S')>=w(S'')>=...>=s(T)
  • ここまでの議論はﾏﾄﾛｲﾄﾞに一般化できる．
    • ﾏﾄﾛｲﾄﾞ: 離散的な凸集合を表すもの
    • ﾏﾄﾛｲﾄﾞの概念をさらに拡張したM凸集合を考えることもできる．
    • → 離散凸解析
• まとめ
  • ネットワーク設計において最も基本的な問題の1つである最小全域木問題を解いた．
    • クラスカル法で解く．
      • 貪欲法，Union-Find.
  • 最小全域木問題は，背後に非常に深淵で美しい理論を持つ．
    • 最小全域木の最適性条件を，全域木の局所的な性質のみを用いて記述できることが，最小全域木問題の持つ構造の豊かさを示す．
• 章末問題
  • 15.2 https://jag-icpc.org/?plugin=attach&refer=2012%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=MedianTree.pdf
    • 最小全域木の中央値を求めればよい
    • クラスカル法を実行
  • 15.3 https://drken1215.hatenablog.com/entry/2020/11/04/221100
    • 辺がある場合とない場合の最小全域木の重みが異なる場合は，辺が必須
      • 不可欠かどうか→ある場合とない場合を比べるのがよい
    • ある最小全域木が含む辺だけを考えればよい

Ch16 グラフ(4): ネットワークフロー

• ネットワークフロー理論: 「きれいに解ける」問題の代表
  • グラフアルゴリズムの中でも特に流麗で鮮やかな体系を持つ．
  • 輸送ネットワークにおけるトラフィックを考える問題を1つの動機として発展したが，さまざまな分野の問題に応用され，豊かな成果．
• ネットワークフローを学ぶ意義
  • 「効率よく多項式時間で解ける問題」を象徴する存在．
  • 興味深い性質や構造がある．
  • 多彩な応用
    • 連結度，二部マッチング，プロジェクト選択
  • ある程度の制約条件までは表現できる柔軟性もある．
  • ネットワークフローで解ける問題を見逃すのはもったいない．
  • 最大流問題と最小カット問題を見る．
• グラフの連結度
  • 最大流問題において，各辺の容量を1とした特殊なケース．
  • 辺連結度
    • 頂点sから頂点tに対して互いに辺を共有しないs-tパスの本数の最大値が，グラフの2頂点s,tに関する辺連結度．
    • グラフネットワークの頑健性を評価するもの．
    • 互いに辺を共有しないこと: 辺素(edge-disjoint).
    • カットセットの辺の本数: カットの容量→辺連結度になる．
  • 最小カット問題
    • (辺の容量が1の場合)有向グラフG=(V,E)と2頂点s,t∈Vが与えられる．s-tカットのうち，容量が最小のものを求める．
    • 辺連結度に関する問題の弱双対性
      • 辺素なs-tパスの最大本数<=s-tカットの最小容量．
      • 任意のs-tカットを考えて，c(S,T)>=kであることを見る．
      • 意味(s-tカットの容量がちょうどkのとき)
        • 辺素なs-tパスの最大本数=k
        • s-tカットの最小容量=k
    • →　辺連結度に関する問題の強双対性
      • 辺素なs-tパスの最大本数=s-tカットの最小容量
      • 辺連結度を求める問題と最小カット問題は双対
  • 辺連結度を求めるアルゴリズムと強双対性の証明
    • フォード・ファルカーソン法を，各辺の容量が1のグラフに対して適用したものを見る
    • 「s-tパスを追加でとれるならとる」という処理を繰り返す，という貪欲法に基づいたアルゴリズムによって求められる．
    • 残余グラフを考える
      • 残余グラフ: s-tパスをとったとき，パス上の各辺に対して逆向きの辺を張りなおしたグラフ
    • 2頂点s-t間の辺連結度を求めるアルゴリズム
      • パスの本数を表す変数をf(←0)と初期化する．
      • 残余グラフG'をもとのグラフGで初期化する．
      • while G'において，s-tパスPが存在するならば:
        • f++
        • G'をPに関する残余グラフに更新
      • fが求める連結度
    • 図16-6: k本の辺素なs-tパスを得るとき，容量kのカットを構成できることを示す．
      • →c(S,T)=k
    • kが最大でもO(|V|)であり，各反復においてs-tパスを見つける処理はO(|E|)→全体でO(|V||E|)
• 最大流問題と最小カット問題
  • 各辺eが容量c(e)をもつ一般の場合の最大流問題を考える
  • 各辺eに対して流量を表す値x(e)があって，以下の条件を満たすとき，xをフロー(許容フロー)という．
    • 任意の辺eに対して，0<=x(e)<=c(e).
    • 任意のs,t以外の頂点vにおいて，vに入る辺eに対するx(e)の総和と，vから出ていく辺eに対するx(e)との総和が等しい．
  • 各辺eに対するx(e)を辺eの流量
  • 頂点sから出ていく辺eに対するx(e)の総和を，フローxの総流量
  • 総流量が最大のフローを最大フロー
  • 最大フローを求める問題を最大流問題
  • フローの性質
    • 辺素: 容量が1の辺に2以上の流量を流せないことを意味する
    • 任意のカット(S,T)に対し，SからTへ出ていく各辺eの流量x(e)の総和から，TからSへ入ってくる各辺eの流量x(e)の総和を引いた値が，フローxの総流量に一致する．
      • どこを観察しても流量が一定
  • 最小カット問題との双対性
    • c(S,T): s-tカット(S,T)に含まれる辺eの容量c(e)の総和(s-tカット(S,T)の容量)．
    • 最小カット問題
      • 容量つき有向グラフG=(V,E)と2頂点s,t∈Vが与えられる．s-tカットのうち，容量が最小のものを求める．
    • 最大流最小カット定理
      • 最大フローの総流量=s-tカットの最小容量
      • 「残余グラフ上で見つけたs-tパス上にフローを流せるだけ流す」という処理を，残余グラフ上にs-tパスがなくなるまで繰り返すことで証明する．
        • フォード・ファルカーソン法というアルゴリズム
  • フォード・ファルカーソン法
    • 残余グラフでは，uからvへはc(e)-x(e)の容量を持つ辺を張る
    • vからuへはc(e')+x(e')の容量の辺を張る
    • 残余グラフ上のs-tパスPを1つ見つけて，Pに含まれる辺の容量の最小値fのフローをP上に流す．
    • 最大流を求めるフォード・ファルカーソン法
      • フロー流量を表す変数FをF←0で初期化
      • 残余グラフG'を元のグラフGで初期化
      • while 残余グラフG'においてs-tパスPが存在するならば:
        • fをパスP上の各辺の容量の最小値
        • F+=f
        • パスP上に大きさfのフローを流す
        • 残余グラフG'を更新
      • Fが求める最大流量
    • 証明は辺連結度と同様
    • O(F|E|)
      • Fは「個数」ではなく「数値」なので，多項式時間ではない
      • 擬多項式時間: 数値に関して多項式であるが実際には多項式でない計算量
  • フォード・ファルカーソン法の実装
    • 難所:各辺e=(u,v)に対して，逆向きの辺e'=(v,u)を取得できるようにする
      • グラフGの入力受け取り時に，辺e=(u,v)を，配列G[u]の最後尾に挿入するときに，同時に配列G[v]に対しても，容量0の逆辺e'=(v,u)を最後尾に挿入する．「e'がG[v]のなかで何番目の要素に相当するかを示す変数rev」を辺eにもたせ，同様の変数をe'にも持たせる．
      • 辺e=(u,v)の逆辺はG[v][e.rev]と表せる
• 応用例(1): 二部マッチング
  • 新たに頂点s,tを用意してグラフネットワークを作ることで，最大流問題に帰着させられる．
• 応用例(2): 点連結度
  • 辺連結度: 「ネットワークの破壊は「辺」で発生する」という辺故障モデルでネットワークの耐故障性を評価
  • 点連結度: 「ネットワークの破壊は「頂点」で発生する」という点故障モデルでネットワークの耐故障性を評価
  • 点素: 2本のパスが点素であるとは，頂点を共有しないこと
  • 点素なs-tパスの最大本数と，s-t間を分断するために破壊する必要のある頂点数の最小値とが等しいという強双対性．この値を点連結度．
  • 各頂点vを2頂点vin, voutに分裂させることで，辺連結度を求める問題に帰着
• 応用例(3): プロジェクト選択問題
  • プロジェクト選択問題で考慮する制約条件
    • u番目のボタンを押すならば，v番目のボタンを押さなければならない．
  • この制約下で得られる総利得を最大にする問題を考える．
  • 露天採鉱問題
  • コストを最小化する問題に読み替える
  • プロジェクト選択を，カットに帰着するアイディア
    • {s,t.0,1}を頂点集合に持つグラフであって，以下の条件を満たすものを構成したい
      • ボタン0,1をともに押すときのコストが，S={s,0,1},T=V-Sのカットの容量に一致
      • ボタン0のみ→S={s,0}
      • ボタン1のみ→S={s,1}
      • ボタンをともに押さない→S={s}
    • →図16.19
    • このグラフ上で最小カット問題を解くことで，ボタンの押し方の最適解を求められる．
  • N個のボタンとM個の制約条件に対しても自然に拡張できる．
• まとめ
  • ネットワークフロー理論はとても美しい理論体系．
  • 1956年に最大流最小カット定理がフォード・ファルカーソンによって示されてから，爆発的に研究が進んだ．
  • ある問題に対して考案したアルゴリズムで得られた解の最適性を示すために，双対問題の実行可能解を構成し，それをもって「最適性の証拠」とする論法は，組み合わせ最適化問題において典型的な手法として定着．
    • → 豊かな組み合わせ構造が次々と明らかとなった．
  • → 多項式時間で解けない問題が浮き彫りになった．
    • NP完全，NP困難．
• 章末問題
  • 16.1 M頂点の先に頂点tを設定し，最小のs-tカットを求める．
  • 16.2 https://drken1215.hatenablog.com/entry/2019/02/15/190700
    • s-t間の最短路それぞれについて，距離を1伸ばす必要がある．
    • 最短路が複数ありうるため，1つの辺を伸ばせばよいということではない．
    • それぞれのカットの容量が，最短路を1伸ばすためのコストとなる．
    • → 最小カット問題を解けばよい．
  • 16.3 https://jag-icpc.org/?plugin=attach&refer=2014%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=F.pdf
    • 最大流を流した後の残余グラフを考える．
    • 残余グラフで使っていないすべての辺について，sから行ける頂点集合Xにvが含まれ，tから行ける頂点集合Yにuが含まれているか調べて，カウントする．
  • 16.4 互いに素でないカード間に辺を張り，s,tを用意して最大流問題に帰着させればよさそう．
    • https://drken1215.hatenablog.com/entry/2019/02/22/011600
  • 16.5 https://qiita.com/drken/items/7f98315b56c95a6181a4
    • 最大安定集合問題
    • 点被覆と安定集合の関係
      • 一般の無向グラフにおいて，点被覆の補集合は安定集合をなし，安定集合の補集合は点被覆をなす．
    • 最小辺被覆と最大マッチングの関係
      • 孤立点のない一般の無向グラフで最大マッチングが得られているとする．マッチングの端点となっていない頂点それぞれにつき1本ずつ枝を追加すると，それが最小辺被覆となる．
    • https://drken1215.hatenablog.com/entry/2019/06/17/221400
    • https://www.slideshare.net/drken1215/ss-86894312
      • 最小点被覆の補集合は最大安定集合
      • 補助グラフを作る
        • マッチング枝は右から左，それ以外は左から右
        • 左側の頂点のうち，マッチングの端点でない頂点を赤く塗る
        • 赤く塗った頂点から矢印の向きに進んでいって到達できる頂点を赤く塗る
        • 左側の白い頂点と右側の赤い頂点が最小点被覆
    • 上記のように，二部マッチング，最小点被覆を求めて，その補集合が答え
  • 16.6 https://img.atcoder.jp/arc085/editorial.pdf
    • 最小カット問題の解法は，以下のような問題を解くことができる
      • 変数q[s],q[t],q[1],...,q[v]を考える
      • 罰金条件(x,y,z)がたくさん与えられる．q[x]=0,q[y]=1なら罰金z円．
      • 変数に0,1のどちらかを割り当て，罰金を最小化する．a[s]=0,a[t]=1は固定．
      • 変数が頂点，罰金条件が辺
    • まず，iを壊してjを壊さないケースについて，(i,j,∞)を追加する．
    • a[i]<=0→(S,i,-a[i]), a[i]>0→(i,T,a[i])
      • 左と右それぞれに罰金の辺を張る．
      • 左は処理をする頂点，右は処理をしない頂点の集合を作るための辺となる．
    • 処理をした場合の集合と処理をしない場合の集合の2つを作った時の，最小カットを求める．
    • https://betrue12.hateblo.jp/entry/2019/07/05/012450

Ch17 PとNP

• 問題の難しさの測り方
  • 問題間の難しさの比較
    • 多項式時間帰着
      • 問題Xが問題Yに対して同等以上に困難であるとは，問題Xを解く多項式アルゴリズムが導けたならば，それを用いて問題Yを解く多項式時間アルゴリズムも導けることをいう．
• PとNP
  • 判定問題と最適化問題
  • P, NPは判定問題の集合
  • クラスP: 多項式時間アルゴリズムが存在する判定問題の全体
  • 安定集合問題
    • 無向グラフG=(V,E)において，頂点集合の部分集合S⊂Vが安定集合であるとは，Sのどの2頂点も辺で結ばれないこと．
    • 正の整数kが与えられたとき，サイズがk以上の安定集合が存在するかどうか判定する．
  • ハミルトンサイクル問題
    • 有向グラフG=(V,E)において，各頂点をちょうど1度ずつ含むサイクル．
    • グラフGがハミルトンサイクルを持つか判定する．
  • クラスNP: 判定問題の答えがYesである場合において，そのYesである証拠が存在して，それをYesであることを多項式時間で検証できるもの．
    • PはNPに属する．
  • P⊂NP⊂EXP
    • EXP: 指数時間アルゴリズムで解ける問題のクラス
• P≠NP予想
  • NPに属するがPに属さないという問題が見つかっていない．
• NP完全
  • 判定問題Xが以下の条件を満たすとき，クラスNP完全に属するという
    • X∈NPである
    • NPに属するすべての問題Yに対し，YをXに多項式時間帰着可能である．
  • 充足可能性問題(SAT)
  • それぞれは互いに同等に難しい．
• 多項式時間帰着の例
  • 点被覆問題
  • 部分和問題
• NP困難
  • 問題Xに対し，あるNP完全問題Yが存在して，Xが多項式時間アルゴリズムで解けるならばYも多項式時間アルゴリズムで解けるとき，XはクラスNP困難に属するという．また，NP困難に属する問題をNP困難問題という．
  • 最大安定集合問題
  • 最小点被覆問題
  • 巡回セールスマン問題(TSP)
• 停止性問題
  • NPに属さないがNP困難
  • コンピュータプログラムPと，そのプログラムへの入力Iが与えられる．Iを入力としてPを実行したとき，Pが有限時間で停止するかどうかを判定する．
• まとめ
  • 現実に解決できそうもない難問Xと出くわしたときは，知られているNP困難問題Yをどれか1つ持ってきて，YをXに帰着できないか考えることが有効．
• 章末問題
  • (メモなし)

Ch18 難問対策

• NP困難問題との対峙
  • 個別な入力ケースに対しては，現実的な時間で解を導ける可能性がある．
• 特殊ケースで解ける場合
  • 区間スケジューリング問題を，特殊なグラフに対する最大安定集合問題とみなせる．
  • 最大安定集合問題を多項式時間で解くことができるグラフのクラス
    • 二部グラフ
    • 木
  • 重み付き最大安定集合問題
    • 各頂点v∈Vに重みw(t)のついた木G=(V,E)が与えられる．木Gの安定集合としてさまざまなものを考えたときの，安定集合に含まれる頂点の重みの総和の最大値を求める．
  • 重み付き最大安定集合問題に対する木上のDP
    • dp1[v]: 頂点vを根とする部分木内での安定習合の重みのmax（頂点vを選ばない場合）
    • dp2[v]: 頂点vを根とする部分木内での安定習合の重みのmax（頂点vを選ぶ場合）
  • DPによる解法は，「木っぽさが強いグラフ」に対する解法へと自然につながるため重要．
    • 木幅: グラフが木にどれくらい近いか．
• 貪欲法
  • 緩和: 問題の条件を少し緩めて扱いやすくする． → 緩和問題．
    • 連続緩和: 特に，整数値しか取りえない変数に対して連続値もとりうるようにする緩和
  • ナップサック問題に対する貪欲法の改良
  • 根本的に近似アルゴリズムとしての性能も改善．
• 局所探索と焼きなまし法
  • 近傍: 「ほんの少し変更を加えたもの」
  • 局所最適解が全体の最適解とは限らない．
  • → 焼きなまし法．f(x)の値が改善されないような近傍への移行も確率的に許す．
    • 温度と呼ばれるパラメータでその確率を制御する．
• 分岐限定法
  • 枝刈り
  • 「これから探索しようとしているノード以降がそれまでの最良解Lより良い解を導く可能性がない」と判断できたら，そのノード以下の探索を打ち切る．
  • 理論的な計算量は下げないが，現実世界の実際の問題に対しては極めて高速に動作することが多々ある．
• 整数計画問題への定式化
  • 最適化問題において
    • f: 目的関数
    • 条件x∈S: 制約
    • 制約をみたすx: 実行可能解
    • fを最小にするx: 最適解
    • 最適解xに対するfの値: 最適値
  • 整数変数を用いて，目的関数と制約条件がともに1次式で表せるような最適化問題を，整数計画問題という．
  • ナップサック問題を含むため，NP困難．
  • 高性能な整数計画ソルバーが開発されているため，大きなサイズの問題も解けうる．
• 近似アルゴリズム
  • A(I)>=(1/k)OPT(I)が成立するとき，Aはk-近似アルゴリズム．kはAの近似比．
    • A: 近似解を求める多項式時間アルゴリズム
    • I: 入力
    • A(I): 入力Iに対する解
    • OPT(I): Iに対する最適値
• まとめ
  • 本全体としてのまとめ
  • 「実践的なアルゴリズム設計技能を磨く」
  • 既存のアルゴリズムの成り立ちの理解と，問題解決への実践．
  • 効率的に解けない問題を知ることも，重要な技能．
  • 部分的に発生する小問題の解決のために，グラフ探索，DP，貪欲法などを使える．
• 章末問題
  • 18.2 https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
    • 木上のDP