陳鍾誠

暴力法 Brute Force

在演算法的理論領域，暴力法幾忽視很少被提到的一個，但是在實務上，很多時候我們會採用暴力法來解題！

舉例而言、有時我們會採用暴力法來破解某個帳號的密碼。

假如該密碼的長度不是很長，而且都是英文大小寫或數字，那麼就有機會在 $(26*2+10)^n = 62^n$ 的計算次數內破解該密碼。

對於長度為 4 的密碼，可以在 $62^4=14776336$ 次計算內將密碼暴力破解。

怎樣暴力呢？就是把方程式裡每個變數，都從《最小到最大》算一遍，然後看看是否有符合解答的結果！

舉例而言，假如我們要求解

$x^2-4x+1=0$

而且假如我們知道《解答》在之間，那麼我們可以從 -100 到 +100，每隔 0.01 計算一次，如果有非常接近 0 的結果，那對應的 x 值就是解答了。以下是用暴力法求解 $x^2-4x+1=0$ 的程式。

檔案： bruteForce.js

https://github.com/ccccourse/se/blob/master/algorithm/08-bruteForce/solve/bruteForce1.js

function f(x) {
  return x*x-4*x+1;
}

for (var x=-100; x<=100; x+=0.001) {
  if (Math.abs(f(x)) < 0.001)
    console.log("x=", x, " f(x)=", f(x));
}

該暴力法程式的執行結果如下：

$ node bruteForce.js
x= 0.268000000113438  f(x)= -0.00017600039294918268
x= 3.7320000001131377  f(x)= -0.00017599960809100423

不考慮速度的話，這種方法其實非常強大，你只要將 f(x) 寫成副程式，就可以列出任何的 f(x)=0 的解答。

像是要求方程式 $\frac{sin(x^2+2x)}{x^3} = 0$ 時，只要把函數 f(x) 換成 $f(x)=\frac{sin(x^2+2x)}{x^3}$，還是可以列出相當符合條件的答案！

檔案： bruteForce2.js

https://github.com/ccccourse/se/blob/master/algorithm/08-bruteForce/solve/bruteForce2.js

function f(x) {
  return sin(x*x+2*x)/x*x*x;
}

for (var x=-100; x<=100; x+=0.001) {
  if (Math.abs(f(x)) < 0.001)
    console.log("x=", x, " f(x)=", f(x));
}

上述程式的執行結果如下，只是找到了太多 f(x) 非常接近 0 的解，得要再過濾一下，讓每個區域只傳回一個最接近零的解。

D:\Dropbox\gitbook\rlab\code\solveEquation>node bruteForce2.js
x= -8.15999999988748  f(x)= -0.0009591341662344855
x= -1.999999999886453  f(x)= 4.5418779845626724e-10
x= -0.021999999886562205  f(x)= 0.0009570498717614835
x= -0.020999999886562204  f(x)= 0.0008724877870570477
x= -0.019999999886562203  f(x)= 0.000791793010175386
x= -0.018999999886562202  f(x)= 0.0007149721474338136
x= -0.0179999998865622  f(x)= 0.0006420317778407609
x= -0.0169999998865622  f(x)= 0.0005729784528665162
x= -0.0159999998865622  f(x)= 0.0005078186962133998
x= -0.014999999886562199  f(x)= 0.00044655900358536667
x= -0.013999999886562198  f(x)= 0.00038920584245704287
x= -0.012999999886562197  f(x)= 0.00033576565184219716
x= -0.011999999886562196  f(x)= 0.0002862448420616496
x= -0.010999999886562195  f(x)= 0.0002406497945106185
x= -0.009999999886562194  f(x)= 0.00019898686142551006
x= -0.008999999886562193  f(x)= 0.00016126236565015064
x= -0.007999999886562192  f(x)= 0.00012748260040146528
x= -0.006999999886562192  f(x)= 0.00009765382903460421
x= -0.005999999886562192  f(x)= 0.00007178228480751984
x= -0.004999999886562192  f(x)= 0.000049874170644996144
x= -0.003999999886562192  f(x)= 0.00003193565890213333
x= -0.0029999998865621923  f(x)= 0.00001797289112728971
x= -0.0019999998865621923  f(x)= 0.000007991977824483308
x= -0.0009999998865621923  f(x)= 0.0000019989982152556445
x= 1.134378077582987e-10  f(x)= 2.5736272459477198e-20
x= 0.0010000001134378078  f(x)= 0.000002000999118756898
x= 0.002000000113437808  f(x)= 0.000008007979511478681
x= 0.003000000113437808  f(x)= 0.00001802689287776661
x= 0.004000000113437808  f(x)= 0.00003206365843608212
x= 0.005000000113437808  f(x)= 0.00005012416268243532
x= 0.006000000113437808  f(x)= 0.00007221425914855319
x= 0.007000000113437808  f(x)= 0.00009833976815952997
x= 0.008000000113437808  f(x)= 0.00012850647659096262
x= 0.009000000113437809  f(x)= 0.00016272013762557382
x= 0.01000000011343781  f(x)= 0.00020098647050932508
x= 0.01100000011343781  f(x)= 0.00024331116030702323
x= 0.012000000113437811  f(x)= 0.00028969985765742233
x= 0.013000000113437812  f(x)= 0.0003401581785278241
x= 0.014000000113437813  f(x)= 0.0003946917039681801
x= 0.015000000113437814  f(x)= 0.0004533059798646973
x= 0.016000000113437815  f(x)= 0.0005160065166929512
x= 0.017000000113437816  f(x)= 0.0005827987892705086
x= 0.018000000113437817  f(x)= 0.0006536882365090636
x= 0.019000000113437818  f(x)= 0.0007286802611660879
x= 0.02000000011343782  f(x)= 0.0008077802295960021
x= 0.02100000011343782  f(x)= 0.0008909934715008663
x= 0.02200000011343782  f(x)= 0.0009783252796805963
x= 1.0350000001134347  f(x)= 0.0003805209790674367
x= 4.112000000113146  f(x)= -0.0008109997278331277
x= 4.96300000011343  f(x)= 0.0007453837110089035
x= 6.16000000011383  f(x)= 0.0007240722293772872

雖然這個方法很好用，但是有個重大的缺點！

這個重大的缺點就是：「暴力法的速度比較慢」！

當變數很多，或是範圍很大時，會非常的慢！

像是求解 $x^2+y^2-z = 0$ 這樣三個變數的方程式，就會需要執行 $\frac{(100-(-100))}{0.001}^3$ 次函數計算，也就是八千兆次，如果有六個變數，就需要算 ( 八千兆 * 八千兆 ) 次。

所以，通常很少人用《暴力法》解決問題！

我們可以想出更好的方法，來求解方程式的根！

求解方程式的方法還有很多，像是《二分搜尋法、爬山演算法、迭代法》等等。

雜湊現金 – 區塊鏈挖礦

範例程式： https://github.com/ccccourse/se/blob/master/algorithm/08-bruteForce/digitalcach/mining.js

const crypto = require('crypto');

let record = {
  nonce: 0,
  data: 'john => mary : $2.7; george => john : $1.3',
}

function hash (text) {
  return crypto.createHmac('sha256', '').update(text).digest('hex')
}

function mining(record) {
  for (var nonce=0; nonce<1000000000000; nonce++) {
    record.nonce = nonce
    let h = hash(JSON.stringify(record))
    if (h.startsWith('00000')) return { nonce: nonce, hash: h }
  }
}

console.log(mining(record))

執行結果:

$ node mining
{ nonce: 419709,
  hash: '000000b464c7f27bf31e475758e614f189742772fd4f137424de8df9a56d9b5b' }
$ node mining
{ nonce: 419709,
  hash: '000000b464c7f27bf31e475758e614f189742772fd4f137424de8df9a56d9b5b' }

隨機版挖礦

https://github.com/ccccourse/se/blob/master/algorithm/08-bruteForce/digitalcach/miningRandom.js

const crypto = require('crypto');

let record = {
  nonce: 0,
  data: 'john => mary : $2.7; george => john : $1.3',
}

function hash (text) {
  return crypto.createHmac('sha256', '').update(text).digest('hex')
}

function mining(record) {
  // for (var nonce=0; nonce<1000000000000; nonce++) {
  while (true) {
    let nonce = Math.floor(Math.random()*99999999)
    record.nonce = nonce
    let h = hash(JSON.stringify(record))
    if (h.startsWith('00000')) return { nonce: nonce, hash: h }
  }
}

console.log(mining(record))

執行結果

csienqu-teacher:digitalcach csienqu$ node miningRandom.js
{ nonce: 93322139,
  hash:
   '00000a397ac30bf8bdd2231fc488186d01795544ac6c6c61c9ddd929ef6a2f78' }
csienqu-teacher:digitalcach csienqu$ node miningRandom.js
{ nonce: 71260011,
  hash:
   '000001ea8ffbff5bbc02bdc30dfbad19972aad6f55c577522b585d2cee21195a' }
csienqu-teacher:digitalcach csienqu$ node miningRandom.js
{ nonce: 75892054,
  hash:
   '00000af97625476c91b59a48120939e64a749f1da8d2823077805c9b153e028e' }
csienqu-teacher:digitalcach csienqu$ node miningRandom.js
{ nonce: 41468301,
  hash:
   '00000e962faa1d35f1d2020881ea78e411ed085158fa3509d0bc8f3cb978ba8e' }
csienqu-teacher:digitalcach csienqu$ node miningRandom.js
{ nonce: 53203594,
  hash:
   '0000046402ca0f25adfa6747d89fa62a4d04c026727951ae264c80ecb664d966' }

《布林邏輯滿足問題》(SAT)

除了破解密碼之外，我們也會用《暴力法》解決很多《沒有聰明解法》的問題。舉例而言、在《計算理論》領域，我們知道《布林邏輯滿足問題》(SAT) 是一種 NP-Complete 問題，這代表我們沒有《快速的方法》可以解決 SAT 問題，這時我們就可以考慮用《暴力法》來解決 SAT 問題，雖然可能會花很久的時間，甚至在《布林變數很多的時候》算超久都不會有答案，但是因為沒有《快速方法》可以解決，所以只好採用這樣的方式。

現在、就讓我們介紹一下《布林邏輯滿足問題》(SAT) ，然後用《暴力法》來解決它吧！

一個布林邏輯式，是包含 AND, OR, NOT 的運算式，寫程式的人應該都很熟悉。

舉例而言， (x && !y) 是個布林邏輯式，當我們給定 x=1, y=0 的時候，可以滿足該算式，因為 (1 && !0) == (1&&1) == 1 。

我們可以用 node.js 來計算布林邏輯式：

$ node
> x=1
1
> y=0
0
> x&&y
0
> x&&!y
true
> x||y
1
> z=1
1
> (x&&y)||(x&&!z)
false
> (x&&!y)||(x&&z)
true
>

在上面的例子中，我們使用 0, 1 代替 JavaScript 當中的 false, true，這樣寫會比較好懂，只是有時計算結果會是 false 或 true，而不是 0 或 1而已！

以下是一個求解 SAT 問題的程式：

https://github.com/ccccourse/se/blob/master/algorithm/17-npcomplete/SAT/sat.js

function satisfy(exp, vars, values) { // 測試 exp 在指令 vars[0..i]=values[0..i] 時，是否能被滿足。
  if (values.length === vars.length) {
    let assign = {}
    for (var i in vars) {
      assign[vars[i]] = values[i]
    }
    with (assign) {
      let result = eval(exp)
      console.log('%j => %d', assign, result)
      if (result) return values
    }
    return
  }
  let v0 = values.slice(0)
  let v1 = values.slice(0)
  v0.push(0)
  v1.push(1)
  return satisfy(exp, vars, v0) || satisfy(exp, vars, v1)
}

function SAT(exp, vars) {
  console.log('exp=', exp)
  let values = satisfy(exp, vars, [])
  return values
}

console.log(SAT('(x||y)&&(!x||!z)&&(x)&&(y)', ['x', 'y', 'z']))
console.log(SAT('(x)&&(!x)&&(!y)&&(!z)', ['x', 'y', 'z']))

讓我們執行看看！

$ node sat.js
exp= (x||y)&&(!x||!z)&&(x)&&(y)
{"x":0,"y":0,"z":0} => 0
{"x":0,"y":0,"z":1} => 0
{"x":0,"y":1,"z":0} => 0
{"x":0,"y":1,"z":1} => 0
{"x":1,"y":0,"z":0} => 0
{"x":1,"y":0,"z":1} => 0
{"x":1,"y":1,"z":0} => 1
[ 1, 1, 0 ]
exp= (x)&&(!x)&&(!y)&&(!z)
{"x":0,"y":0,"z":0} => 0
{"x":0,"y":0,"z":1} => 0
{"x":0,"y":1,"z":0} => 0
{"x":0,"y":1,"z":1} => 0
{"x":1,"y":0,"z":0} => 0
{"x":1,"y":0,"z":1} => 0
{"x":1,"y":1,"z":0} => 0
{"x":1,"y":1,"z":1} => 0
undefined

您可以看到第一個式子 (x||y)&&(!x||!z)&&(x)&&(y) 在 {x:1, y:1, z:0} 的時候被滿足了，因此結果印出 [1,1,0]。

但是第二個式子 (x)&&(!x)&&(!y)&&(!z) 完全無法被滿足，因此 (x,y,z) 的八種組合都傳回 0，於是最後就失敗傳回 undefined 了。

其實暴力法不只可以用在《布林算式》或者《猜密碼問題》上，也可以用來解決一些《數值問題》，舉例而言假如我們想知道函數 f(x,y,z) 在 -10 < x,y,z < 10 區間的最小值，也可以密密麻麻的從 (x,y,z) = (-10,-10,-10) 開始列舉，每隔 0.1 列舉一次，這樣只要該函數在 0.1 的範圍內不會變化太大，就應該可以找到《差不多最好的解答》了！

f(-10, -10, -10)=...
f(-10, -10, -9.9)=...
...
f(-10, -10,  9.9)=...
f(-10, -10,  10)=...
...
f( 10,  10, -10)=...
f( 10,  10, -9.9)=...
...
f( 10,  10,  9.9)=...
f( 10,  10,  10)=...

結語

以上就是暴力法的原理，透過這樣《完全暴力列舉》的方式，雖然可能需要很久，但卻是很有系統的解決方式。

當然、速度永遠是個問題，有些問題用暴力法計算兩千年也算不出來，此時就不應該用暴力法，而應該尋找一些比較聰明的方式了！

思考

使用『蒙地卡羅＋暴力法』合併後會有什麼優缺點呢？

Edit on GitHub