力づく法・分割統治法・動的計画法 - アルゴリズム学習(その5) - $shibayu36->blog;アルゴリズムの設計手法として、力ずく法・分割統治法・動的計画法というような考え方があった。新しいアルゴリズムを学ぶ時、どの設計手法でやっているのだろうかと意識しておくと、頭に入りやすい気がした。そこで、自分の頭を整理するためにメモを書いておく。自分用メモなので、情報の正確さについては保証がない。 力づく法 全探索する方法 アルゴリズムの考え方としては単純なことが多いが、かなり遅いものになることが多い 例えば、Nクイーンなら、N個の置き方を全通り作って、それぞれが条件をみたすか確認し、条件を満たしたら返すようなもの。Nの二乗のなかから、N個の組み合わせを作って試すので、計算が膨大になる 例えば文字列マッチなら、1文字ずつずらしながら、マッチさせたいパターンとテキストの文字を比較していくようなもの 分割統治法 Wikipediaによると、そのままでは解決できない大きな問題を小さな問題に分割し、
