brute force

形容詞

原始的なプログラミングスタイルを表す。プログラマーが、問題を単純化するために自分の知性を使う代わりにコンピューターの処理能力に頼り、しばしば規模の問題を無視して、小さな問題に適した素朴な方法を大きな問題に直接適用するもの。この用語はプログラミングのスタイルを指しても使える。brute-forceなプログラムは、繰り返しだらけで、エレガンスや有用な抽象を欠いた、強引で退屈なやり方で書かれている(brute force and ignoranceも参照)。

brute-forceなアルゴリズムのcanonicalな例は、古典的なNP-困難問題である‘巡回セールスマン問題’(TSP)に関連する。たとえばある人がボストンにいて、他のN都市へ車で行きたいとする。移動距離を最小にするには、どの順序で都市を訪れるべきか? brute-force法は、単にあらゆる可能な経路を生成して距離を比較することである。動作は保証され実装も簡単だが、このアルゴリズムは、明らかにばかげた経路(ボストンからサンフランシスコとニューヨークを経由してその順でヒューストンへ行くなど)さえ考慮する点で、明らかに非常に愚かである。非常に小さなNではうまくいくが、Nが増えると急速にばかげて非効率になる(N = 15では、すでに考慮すべき経路が1,307,674,368,000通りあり、N = 1000では——まあ、bignumを参照)。あいにく、brute force以上の良い一般解がないこともある。NP-、rubber-hose cryptanalysisも参照。

brute-forceプログラミングのより単純な例は、大きなリストの中から最小の数を見つけるのに、まず既存のプログラムでリストを昇順にソートし、それから先頭の最初の数を取る、というものである。

brute-forceプログラミングが実際に愚かとみなされるべきかどうかは、文脈による。問題がそれほど大きくなければ、brute-force解に費やす余分なCPU時間は、より‘知的な’アルゴリズムの開発に要するプログラマー時間より安くつくかもしれない。さらに、より知的なアルゴリズムは、速度の改善で正当化される以上の長期的な複雑さのコストやバグ探しを意味するかもしれない。

Unixの共同発明者Ken Thompsonは、「迷ったら、力任せ(brute force)を使え」という警句を口にしたと言われる。彼はおそらくこれをha ha only seriousとして意図したのだろうが、brittleな‘賢い’ものより単純で頑健で移植性のあるアルゴリズムを好んだオリジナルのUnixカーネルの方針は、そのOSの成功の重要な要因だったように思われる。ソフトウェア設計における他の多くのトレードオフと同様、brute forceと、複雑で精妙に調整された巧妙さとの選択は、しばしば工学的な目利きと繊細な美的判断の両方を要する難しいものである。