八大算法思想(四)------------------分治算法

基本思想

分治法的設(shè)計思想是:將一個難以直接解決的大問題匆瓜,分割成一些規(guī)模較小的相同問題奔则,以便各個擊破蛮寂,分而治之。

分治策略是:對于一個規(guī)模為n的問題应狱,若該問題可以容易地解決(比如說規(guī)模n較小)則直接解決祠丝,否則將其分解為k個規(guī)模較小的子問題疾呻,這些子問題互相獨立且與原問題類型一致,遞歸地解這些子問題写半,然后將各子問題的解合并得到原問題的解岸蜗。

分治是很多高效算法的基礎(chǔ),如排序算法(快速排序叠蝇,歸并排序)璃岳,傅立葉變換(快速傅立葉變換)……

分治與遞歸像一對孿生兄弟,經(jīng)常同時應用在算法設(shè)計之中悔捶,并由此產(chǎn)生許多高效算法铃慷。

使用場景

分治法所能解決的問題一般具有以下幾個特征:

1) 該問題的規(guī)模縮小到一定的程度就可以容易地解決

2) 該問題可以分解為若干個規(guī)模較小的相同問題蜕该,即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)犁柜。

3) 利用該問題分解出的子問題的解可以合并為該問題的解;

4) 該問題所分解出的各個子問題是相互獨立的堂淡,即子問題之間不包含公共的子子問題馋缅。

第一條特征是絕大多數(shù)問題都可以滿足的,因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加绢淀;

第二條特征是應用分治法的前提它也是大多數(shù)問題可以滿足的萤悴,此特征反映了遞歸思想的應用;

第三條特征是關(guān)鍵皆的,能否利用分治法完全取決于問題是否具有第三條特征覆履,如果具備了第一條和第二條特征,而不具備第三條特征费薄,則可以考慮用貪心法或動態(tài)規(guī)劃法内狗。

第四條特征涉及到分治法的效率,如果各子問題是不獨立的义锥,則分治法要做許多不必要的工作柳沙,重復地解公共的子問題,此時雖然可用分治法拌倍,但一般用動態(tài)規(guī)劃法較好赂鲤。

實例

可使用分治法求解的一些經(jīng)典問題:

二分搜索噪径;合并排序、快速排序数初;大整數(shù)乘法找爱、Strassen矩陣乘法;棋盤覆蓋泡孩;線性時間選擇车摄;最接近點對問題;循環(huán)賽日程表仑鸥;漢諾塔

二分查找

二分查找(基于有序數(shù)組)

/*基于遞歸的二分查找*/

public int rank(Key key,int lo,int hi)

{                       

        if(hi<lo)

            return lo;

        int mid = lo+(hi-lo)/2;

        int cmp = key.compareTo(keys[mid]);

        if(cmp > 0)

            return rank(key, mid+1, hi);

        else if(cmp < 0)

            return rank(key, lo, mid-1);

        else return mid;

}

漢諾塔

在漢諾塔游戲中吮播,有三個分別命名為A、B眼俊、C的塔座意狠,幾個大小各不相同,從小到大依次編號得圓盤疮胖。最初环戈,所有得圓盤都在A塔座上,其中最大得圓盤在最下面澎灸,然后是第二大院塞,以此類推。

游戲的目的是 將所有的圓盤從塔座A移動到塔座B性昭,塔座C用來放置臨時圓盤迫悠,游戲的規(guī)則如下:

1、一次只能移動一個圓盤

2巩梢、任何時候都不能將一個較大的圓盤壓在較小的圓盤上面.

3创泄、除了第二條限制,任何塔座的最上面的圓盤都可以移動到其他塔座上

image

漢諾塔問題解決思想:

在解決漢諾塔問題時括蝠,事實上我們不是最關(guān)心圓盤1開始應該挪到哪個塔座上鞠抑,而是關(guān)心最下面的圓盤4。 當然忌警,我們不能直接移動圓盤4搁拙,但是圓盤4最終將從塔座A移動到塔座B。按照游戲規(guī)則法绵,在移動圓盤4之前的情況一定如下圖箕速。

image

四個圓盤從A移動到B,就要考慮如何將前三個圓盤從A移動到C朋譬,然后將圓盤4從A移動到B盐茎,最后將前三個圓盤從C移動到B。

但是上面的步驟可以重復利用徙赢!將問題規(guī)淖帜縮刑皆健:

三個圓盤從A移動到C,就要考慮如何將前兩個圓盤從A移動到B窑业,然后將圓盤3從A移動到C钦幔,最后將前兩個圓盤從B移動到C。

持續(xù)簡化這個問題常柄,最終我們將只需要處理一個圓盤從一個塔座移動到另一個塔座的問題鲤氢。

public class Moved {

    private static int count = 1;

    public static void main(String[] args) {

        moved(4, "第一根柱子", "第二根柱子", "第三根柱子");

    }

    /**

    * @param i  圓盤數(shù)量

    * @param a  圓盤初始所在塔座

    * @param b  圓盤將要移動到的塔座

    * @param c  輔助圓盤移動的塔座

    */

    public static void moved(int i, String a, String b, String c){

        if(i == 1){

            disPaly(1, a, b);

        }else{

            moved(i-1, a, c, b);  //將i-1根圓盤由A移動到C

            disPaly(i, a, b);  //將圓盤i由A移動到B

            moved(i-1, c, b, a);  //將i-1根圓盤由C移動到B

        }

    }

    public static void disPaly(int i,String a,String b){

        System.out.println("第"+count+"步:移動第"+i+"個塔從"+a+"到"+b);

        count++;

    }

}

運行結(jié)果:

第1步:移動第1個塔從第一根柱子到第三根柱子

第2步:移動第2個塔從第一根柱子到第二根柱子

第3步:移動第1個塔從第三根柱子到第二根柱子

第4步:移動第3個塔從第一根柱子到第三根柱子

第5步:移動第1個塔從第二根柱子到第一根柱子

第6步:移動第2個塔從第二根柱子到第三根柱子

第7步:移動第1個塔從第一根柱子到第三根柱子

第8步:移動第4個塔從第一根柱子到第二根柱子

第9步:移動第1個塔從第三根柱子到第二根柱子

第10步:移動第2個塔從第三根柱子到第一根柱子

第11步:移動第1個塔從第二根柱子到第一根柱子

第12步:移動第3個塔從第三根柱子到第二根柱子

第13步:移動第1個塔從第一根柱子到第三根柱子

第14步:移動第2個塔從第一根柱子到第二根柱子

第15步:移動第1個塔從第三根柱子到第二根柱子
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市西潘,隨后出現(xiàn)的幾起案子卷玉,更是在濱河造成了極大的恐慌,老刑警劉巖秸架,帶你破解...
    沈念sama閱讀 211,265評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件揍庄,死亡現(xiàn)場離奇詭異咆蒿,居然都是意外死亡东抹,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,078評論 2 385
  • 文/潘曉璐 我一進店門沃测,熙熙樓的掌柜王于貴愁眉苦臉地迎上來缭黔,“玉大人,你說我怎么就攤上這事蒂破×蠼鳎” “怎么了?”我有些...
    開封第一講書人閱讀 156,852評論 0 347
  • 文/不壞的土叔 我叫張陵附迷,是天一觀的道長惧互。 經(jīng)常有香客問我,道長喇伯,這世上最難降的妖魔是什么喊儡? 我笑而不...
    開封第一講書人閱讀 56,408評論 1 283
  • 正文 為了忘掉前任,我火速辦了婚禮稻据,結(jié)果婚禮上艾猜,老公的妹妹穿的比我還像新娘。我一直安慰自己捻悯,他們只是感情好匆赃,可當我...
    茶點故事閱讀 65,445評論 5 384
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著今缚,像睡著了一般算柳。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上姓言,一...
    開封第一講書人閱讀 49,772評論 1 290
  • 那天埠居,我揣著相機與錄音查牌,去河邊找鬼。 笑死滥壕,一個胖子當著我的面吹牛纸颜,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播绎橘,決...
    沈念sama閱讀 38,921評論 3 406
  • 文/蒼蘭香墨 我猛地睜開眼胁孙,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了称鳞?” 一聲冷哼從身側(cè)響起涮较,我...
    開封第一講書人閱讀 37,688評論 0 266
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎冈止,沒想到半個月后狂票,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,130評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡熙暴,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,467評論 2 325
  • 正文 我和宋清朗相戀三年闺属,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片周霉。...
    茶點故事閱讀 38,617評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡掂器,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出俱箱,到底是詐尸還是另有隱情国瓮,我是刑警寧澤,帶...
    沈念sama閱讀 34,276評論 4 329
  • 正文 年R本政府宣布狞谱,位于F島的核電站乃摹,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏跟衅。R本人自食惡果不足惜孵睬,卻給世界環(huán)境...
    茶點故事閱讀 39,882評論 3 312
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望与斤。 院中可真熱鬧肪康,春花似錦、人聲如沸撩穿。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,740評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽食寡。三九已至雾狈,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間抵皱,已是汗流浹背善榛。 一陣腳步聲響...
    開封第一講書人閱讀 31,967評論 1 265
  • 我被黑心中介騙來泰國打工辩蛋, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人移盆。 一個月前我還...
    沈念sama閱讀 46,315評論 2 360
  • 正文 我出身青樓悼院,卻偏偏與公主長得像,于是被迫代替她去往敵國和親咒循。 傳聞我的和親對象是個殘疾皇子据途,可洞房花燭夜當晚...
    茶點故事閱讀 43,486評論 2 348

推薦閱讀更多精彩內(nèi)容