全探索(Brute Force Search)

brute-force-search.png

ありうる可能性をすべて試して最良の解を求める方法
探索系のすべての基本です!
まずは全探索をして、そのあともっと省略できるところがないのかどうか考えるのです。
問題で出てくるものとして多いのは、おおまかにいうとありうる組み合わせをすべて列挙して条件に合うものは何個?というものを求めるものが多いです。

全探索の方法の種類

  • for文
  • 再起関数
深さ優先探索 再起関数,スタック
幅優先探索 キュー、大きめの配列

for文で全探索

int count=0;//条件に合うものの数をカウントする
for(int i=0;i<ありうる可能性の数;i++){
   for(int j=0;j<ありうる可能性の数;j++){
      for(int k=0;k<ありうる可能性の数;k++){
         //最も内側のループでありうる可能性すべてのシミュレーションが行われます。
          //なにか条件にあうかどうかテストしたりする処理を書きます。
          if(条件に合うかどうか) count++;
     }
 }
}

という風に何重でも、問題文に合わせてfor分で囲います。
そうすることにより、最も内側のループでありうる可能性すべてのシミュレーションが行われます。

TopCoderでBruteForce系の問題

  • WritingWords…Brute Forceの問題の中で最も簡単なものと思われる。
  • CheckFunction…Brute Forceの問題の中でも簡単なものと思われる。
  • Chooser….わりと易しい問題なので初心者におすすめ。
  • Price….異なる価格を示す顧客に対して、最も合計金額を高くして売りつける方法は?という問題。

サポートサイト Wikidot.com