Branch and Bound

Branch and Bound

中文譯作「分支定界」,以遞迴的方式,來列舉數據範圍、數據區間,找出數據界限的方法。

先把一段數據區間分成幾段較小的區間。如果有一段區間,我們當下看不出它是不是正確區間,就把該區間分得更細,並遞迴下去,釐清細節;如果能看出,就停止遞迴。

branch是指當一段區間不確定界限,就分割區間,並遞迴下去。bound是指當一段區間確定了界限,並停止遞迴。

Extremum

求連續函數的極值

運用Bisection Method的概念,也可以求連續函數的極值——最大值、最小值。由於最大值和最小值無法使用夾擠的方式求得,在這裡必須換個想法。

求連續函數的最大值:
1. 先求得區段 [a,b] 的中間點 c。
2. 以 c 為中心點,向左右拓展成 a' 和 b'。
   拓展的距離是 [a,b] 的一半再一半,等同於 [a,c] 的一半,也等同於 [c,b] 的一半。
3. 判斷 f(a')、f(b')、f(c) 三者當中何者最大,並將 c 移動到最大的那邊去。
  (如果 f(c) 是最大的,則不必移動)
4. 循環的做下去,逐次把拓展距離減半即可。

如果函數有許多區域極大值或區域極小值時,則可以細切整段函數,然後各區段分別做一次Bisection Method,整合之後就可以求出整體的最大值或最小值。粗略的程式碼如下所示:

UVa 10228