The Algorithm Design Manual Second Edition 自分なりメモ

問題が複雑な場合は、簡単な問題に落として考える

• グラフ -> 木
• 二次元 -> 一次元

貪欲の簡単な証明

• 貪欲で構成した状態が、状態を変化してもよくならないことをいう
• ある状態からスタートしたとき、ある変化を繰り返すとよくなることを示し、最後に到達する状態が貪欲で構成した状態であることをいう

簡単な貪欲の反例の見つけ方

単純に考える

• 小さく考える

  • Amateur algorists tend to draw a big messy instance and then stare at it helplessly. The pros look carefully at several small examples, because they are easier to verify and reason about."

• 網羅的に考える

  • There are only a small number of possibilities for the smallest nontrivial value of n. For example, there are only three interesting ways two intervals on the line can occur: (1) as disjoint intervals, (2) as overlapping intervals, and (3) as properly nesting intervals, one within the other. All cases of three intervals (including counter-examples to both movie heuristics) can be systematically constructed by adding a third segment in each possible way to these three instances.

• 弱みを見つける
  • 最大を取る貪欲だったら、最大を取ってはいけない場合を考える
• 極端なものを考える

  • Many counter-examples are mixtures of huge and tiny, left and right, few and many, near and far. It is usually easier to verify or rea- son about extreme examples than more muddled ones. Consider two tightly bunched clouds of points separated by a much larger distance d. The optimal TSP tour will be essentially 2d regardless of the number of points, because what happens within each cloud doesn’t really matter.

再帰は数学的帰納法である

多くのアルゴリズムは数学的帰納法で証明できる。また、再帰の妥当性も数学的帰納法で証明できる。

定式化の手法

• 順列
• 部分集合
  • cluster
  • collection
  • committee,
  • group,
  • packaging
  • selection
• 木
  • 階層
  • 支配関係
  • 祖先・子孫関係
  • 分類学
• グラフ
  • 関係データ、状態間の関係
• 多角形
• 点
• 文字列

再帰的な構造

オブジェクトを再起的に記述するには、分解規則と基底ケースが必要である。例えば、{}が基底ケースになる

• 順列

  要素を一つ削除しても順列

• 部分集合

• 木

  要素を一つ削除しても木、部分木という概念

• グラフ

  要素を一つ削除してもグラフ、左右に分けても2つのグラフ

• 多角形

• 点
• 文字列

引用元

• The Algorithm Design Manual Second Edition