over 2 years ago

0 緣起

極小值(minimal = local minimum)與最小值(global minimum)的差異在於,最小值必須小於或等於所有我們關心的數值,極小值只要小於或等於「附近」的數值就可以了。在很大一塊 Optimization/AI 的領域中,尋找極小值,一直都是滿重要的課題之一。不過我們今天來關心的是「離散版」的極小值。

1 簡單版的問題

在一個 大小的矩形土地上,每一格都有一個高度,而且所有的高度都不一樣。在下雨過後,水總是會往比較低的地方流過去。假設這個矩形土地以外的地方都是陡峭的山壁,請問你能不能快速找到一個積水的地方?也就是說,找到一個位置,使得這個位置相鄰的兩格(邊界處為一格)的高度都比這個位置來得高?

假設用來表達這一系列土地的高度已經給定於陣列 ,我們想要實作的是一個以下的函數:

int* findLocalMinimum(int A[], int n);

我們可以利用二分搜尋法來解決這個問題。

2 真正的問題

如果我們現在把問題改成 大小的矩形土地上,每一格都有著不同的高度。請你找出任何一格極小值。

性質

如果一個連通的區域,其邊界上最小值,與之相鄰的格子較低的那格若在這個連通區域內,則這個區域內必定有極小值。證明如後:我們從邊界上的最小值出發,由於所有高度都不相同,我們每一次可以往四周走一步前往更低的地方。最後停下來的格子必定落在這個連通的區域內(否則必定經過邊界而與當初所選取的「最小值」矛盾)。

一個分而治之的作法

我們可以藉由以上的性質,得到以下的分而治之演算法:每一次把邊界與正中間的十字區域中,最小值找出來。若這個最小值本身是極小值,那我們就找到答案了。否則的話,看看最小值隔壁更小的一格屬於以下 A, B, C, D 哪一個區域,然後把搜索範圍縮小到四分之一,記得把邊界也包含進去(為什麼?)。

效率分析

每一次我們花費 的時間掃遍整個矩形的邊界和中間十字部分,並且遞迴進入其中一個 的區域內。因此我們可以列式

解得

3 衍伸的問題

如果我們現在把問題改成 大小的矩形土地呢?

如果矩形是長條形狀的,每一次切十字所需要檢查的格子數會變成 。但事實上,若是一開始的情形,我們只需要檢查短邊就可以了:然後把狀況沿著短邊的方向切成兩半,直到矩形的形狀接近正方形,再套用回前一節的技巧即可。

如此一來,不妨假設 ,時間複雜度為

解得 。值得一提的是,當 的時候這方法會退化至 ;當 的時候這方法會退化至 ,剛好完美符合前面兩個題目的複雜度。

← 分而治之法(一):快速冪計算 分而治之法(三):尋找中位數 →
 
comments powered by Disqus