程序员编程艺术第四十一章 四十二章 荷兰国旗 矩阵相乘Strassen算法
分享一下我老師大神的人工智能教程!零基礎,通俗易懂!http://blog.csdn.net/jiangjunshow
也歡迎大家轉載本篇文章。分享知識,造福人民,實現我們中華民族偉大復興!
? ? ? ?第四十一章~四十二章:荷蘭國旗問題、矩陣相乘之Strassen算法
前言
? ? 本文要講的兩個問題:荷蘭國旗和矩陣相乘之Strassen算法都跟分治法相關,故把這兩個問題放到了一起。所謂分治,便是分而治之的意思,好比打戰時面對敵人龐大的武裝部隊,采取避其主力,各個擊破的策略。
? ? 有何問題,歡迎隨時不吝指正,thanks。
第十一章、荷蘭國旗問題
題目描述
現有紅白藍三個不同顏色的小球,亂序排列在一起,請重新排列這些小球,使得紅白藍三色的同顏色的球在一起。這個問題之所以叫荷蘭國旗,是因為我們可以將紅白藍三色小球想象成條狀物,有序排列后正好組成荷蘭國旗。如下圖所示:
????
思路分析
? ? 初看此題,我們貌似除了暴力解決并無好的辦法,但聯想到我們所熟知的快速排序算法呢?我們知道,快速排序時基于分治模式處理的,對一個典型子數組A[p...r]排序的分治過程為三個步驟:
? ? 也就是說,快速排序的主要思想便是依托于一個partition分治過程,每一趟排序的過程中,選取的主元都會把整個數組排列成一大一小的序列,繼而遞歸排序完整個數組。
? ? 如下偽代碼所示:
快速排序算法的關鍵是PARTITION過程,它對A[p..r]進行就地重排:
PARTITION(A, p, r)
1? x ← A[r]
2? i ← p - 1
3? for j ← p to r - 1
4?????? do if A[j] ≤ x
5???????????? then i ← i + 1
6????????????????? exchange A[i] <-> A[j]
7? exchange A[i + 1] <-> A[r]
8? return i + 1
繼而遞歸完成整個排序過程:
QUICKSORT(A, p, r)
1 if p < r
2??? then q ← PARTITION(A, p, r)?? //關鍵
3???????? QUICKSORT(A, p, q - 1)
4???????? QUICKSORT(A, q + 1, r)
舉個例子如下:i 指向數組頭部前一個位置,j 指向數組頭部元素,j 在前,i 在后,雙雙從左向右移動。
① j 指向元素2時,i 也指向元素2,2與2互換不變
? ? ?i p/j
? ?2 ? 8 ? 7 ? 1 ? 3 ? 5 ? 6 ? 4(主元)
② 于是j 繼續后移,直到指向了1,1 <= 4,于是i++,i 指向8,故j 所指元素1 與 i 所指元素8 位置互換:
? ? ??? ? ? i ? ? ? ? j
? ?2 ? 1 ? 7 ? 8 ? 3 ? 5 ? 6 ? 4
③ j 繼續后移,指到了元素3,3 <= 4,于是同樣i++,i 指向7,故j 所指元素3 與 i 所指元素7 位置互換:
? ? ?? ? ? ? ? ?i ? ? ? ? j
? ?2 ? 1 ? 3 ? 8 ? 7 ? 5 ? 6 ? 4
④ j 一路后移,沒有再碰到比主元4小的元素:
? ???? i ? ? ? ? ? ? ? ? ? j
? ?2 ? 1 ? 3 ? 8 ? 7 ? 5 ? 6 ? 4
⑤ 最后,A[i + 1] <-> A[r],即8與4交換,所以,數組最終變成了如下形式:
? ? ? ? 2 ? 1 ? 3 ? 4 ? 7 ? 5 ? 6 ? 8
ok,至此快速排序第一趟完成。就這樣,4把整個數組分成了倆部分,2 1 3,7 5 6 8,再遞歸對這倆部分分別進行排序。
全部過程可以參看此文:快速排序算法,或看下我以前在學校里畫的圖:
? ? 而我們面對的問題是,重新排列使得所有球排列成三個不同顏色的球,是否可以設定三個指針,借鑒partition過程呢?
解法一、partition分治
? ? 通過前面的分析得知,這個問題,類似快排中partition過程。只是需要用到三個指針,一前begin,一中current,一后end,倆倆交換。
??? 為什么,第三步,current指2,與end交換之后,current不動了列,對的,正如algorithm__所說:current之所以與begin交換后,current++、begin++,是因為此無后顧之憂。而current與end交換后,current不動,end--,是因有后顧之憂。
? ? 讀者可以試想,你最終的目的無非就是為了讓0、1、2有序排列,試想,如果第三步,current與end交換之前,萬一end之前指的是0,而current交換之后,current此刻指的是0了,此時,current能動么?不能動啊,指的是0,還得與begin交換列。
??? ok,說這么多,你可能不甚明了,直接引用下gnuhpc的圖,就一目了然了:
????
????
? ? 參考代碼如下://引用自gnuhpcwhile( current<=end )????? {?????????? ? if( array[current] ==0 )?????????? ?? {?????????????? ????? swap(array[current],array[begin]);??????????????? ????? current++;??????????????? ????? begin++;????????? ?? }?????????? ?? else if( array[current] == 1 )????????? ?? {?????????????? ????? current++;????????? ?? } ????????? ?? else //When array[current] =2 ?? {???????????? ????? swap(array[current],array[end]);????????????? ????? end--;????????? ?? }??? }? ? 本章完。
第四十二章:矩陣相乘之Strassen算法
題目描述
? ? 請編程實現矩陣乘法,并考慮當矩陣規模較大時的優化方法。
思路分析
? ? 根據wikipedia上的介紹:兩個矩陣的乘法僅當第一個矩陣B的列數和另一個矩陣A的行數相等時才能定義。如A是m×n矩陣和B是n×p矩陣,它們的乘積AB是一個m×p矩陣,它的一個元素其中?1?≤?i?≤?m,?1?≤?j?≤?p。
? ??
? ? 值得一提的是,矩陣乘法滿足結合律和分配率,但并不滿足交換律,如下圖所示的這個例子,兩個矩陣交換相乘后,結果變了:
? ? ?下面咱們來具體解決這個矩陣相乘的問題。
解法一、暴力解法
? ? 其實,通過前面的分析,我們已經很明顯的看出,兩個具有相同維數的矩陣相乘,其復雜度為O(n^3),參考代碼如下:
//矩陣乘法,3個for循環搞定? void Mul(int** matrixA, int** matrixB, int** matrixC)? {? ?for(int i = 0; i < 2; ++i)?? ?{? ??for(int j = 0; j < 2; ++j)?? ??{? ???matrixC[i][j] = 0;? ???for(int k = 0; k < 2; ++k)?? ???{? ????matrixC[i][j] += matrixA[i][k] * matrixB[k][j];? ???}? ??}? ?}? }解法二、Strassen算法
? ? 在解法一中,我們用了3個for循環搞定矩陣乘法,但當兩個矩陣的維度變得很大時,O(n^3)的時間復雜度將會變得很大,于是,我們需要找到一種更優的解法。
? ? 一般說來,當數據量一大時,我們往往會把大的數據分割成小的數據,各個分別處理。遵此思路,如果丟給我們一個很大的兩個矩陣呢,是否可以考慮分治的方法循序漸進處理各個小矩陣的相乘,因為我們知道一個矩陣是可以分成更多小的矩陣的。
? ? 如下圖,當給定一個兩個二維矩陣A B時:
? ? 這兩個矩陣A B相乘時,我們發現在相乘的過程中,有8次乘法運算,4次加法運算:
? ? 矩陣乘法的復雜度主要就是體現在相乘上,而多一兩次的加法并不會讓復雜度上升太多。故此,我們思考,是否可以讓矩陣乘法的運算過程中乘法的運算次數減少,從而達到降低矩陣乘法的復雜度呢?答案是肯定的。
? ? 1969年,德國的一位數學家Strassen證明O(N^3)的解法并不是矩陣乘法的最優算法,他做了一系列工作使得最終的時間復雜度降低到了O(n^2.80)。
? ? 他是怎么做到的呢?還是用上文A B兩個矩陣相乘的例子,他定義了7個變量:
? ? 如此,Strassen算法的流程如下:
- 兩個矩陣A B相乘時,將A, B, C分成相等大小的方塊矩陣:
;
- 可以看出C是這么得來的:
- 現在定義7個新矩陣(讀者可以思考下,這7個新矩陣是如何想到的):
- 而最后的結果矩陣C 可以通過組合上述7個新矩陣得到:
? ? 表面上看,Strassen算法僅僅比通用矩陣相乘算法好一點,因為通用矩陣相乘算法時間復雜度是,而Strassen算法復雜度只是。但隨著n的變大,比如當n >> 100時,Strassen算法是比通用矩陣相乘算法變得更有效率。
? ? 如下圖所示:
解法三、持續優化
? ? 根據wikipedia上的介紹,后來,Coppersmith–Winograd 算法把 N* N大小的矩陣乘法的時間復雜度降低到了:,而2010年,Andrew Stothers再度把復雜度降低到了,一年后的2011年,Virginia Williams把復雜度最終定格為:
參考文獻
后記
? ? 編程藝術原計劃寫到第五十章,如今只剩下最后八章,感謝各位一直以來的關注。預祝本博客所有的讀者新春快樂,在馬年一切都能心想事成,thanks。
? ? July、二零一四年一月二十八日。
???????????給我老師的人工智能教程打call!http://blog.csdn.net/jiangjunshow
你好! 這是你第一次使用 **Markdown編輯器** 所展示的歡迎頁。如果你想學習如何使用Markdown編輯器, 可以仔細閱讀這篇文章,了解一下Markdown的基本語法知識。新的改變
我們對Markdown編輯器進行了一些功能拓展與語法支持,除了標準的Markdown編輯器功能,我們增加了如下幾點新功能,幫助你用它寫博客:
功能快捷鍵
撤銷:Ctrl/Command + Z
重做:Ctrl/Command + Y
加粗:Ctrl/Command + B
斜體:Ctrl/Command + I
標題:Ctrl/Command + Shift + H
無序列表:Ctrl/Command + Shift + U
有序列表:Ctrl/Command + Shift + O
檢查列表:Ctrl/Command + Shift + C
插入代碼:Ctrl/Command + Shift + K
插入鏈接:Ctrl/Command + Shift + L
插入圖片:Ctrl/Command + Shift + G
合理的創建標題,有助于目錄的生成
直接輸入1次#,并按下space后,將生成1級標題。
輸入2次#,并按下space后,將生成2級標題。
以此類推,我們支持6級標題。有助于使用TOC語法后生成一個完美的目錄。
如何改變文本的樣式
強調文本 強調文本
加粗文本 加粗文本
標記文本
刪除文本
引用文本
H2O is是液體。
210 運算結果是 1024.
插入鏈接與圖片
鏈接: link.
圖片:
帶尺寸的圖片:
當然,我們為了讓用戶更加便捷,我們增加了圖片拖拽功能。
如何插入一段漂亮的代碼片
去博客設置頁面,選擇一款你喜歡的代碼片高亮樣式,下面展示同樣高亮的 代碼片.
// An highlighted block var foo = 'bar';生成一個適合你的列表
- 項目
- 項目
- 項目
- 項目
- 計劃任務
- 完成任務
創建一個表格
一個簡單的表格是這么創建的:
| 電腦 | $1600 |
| 手機 | $12 |
| 導管 | $1 |
設定內容居中、居左、居右
使用:---------:居中
使用:----------居左
使用----------:居右
| 第一列文本居中 | 第二列文本居右 | 第三列文本居左 |
SmartyPants
SmartyPants將ASCII標點字符轉換為“智能”印刷標點HTML實體。例如:
| Single backticks | 'Isn't this fun?' | ‘Isn’t this fun?’ |
| Quotes | "Isn't this fun?" | “Isn’t this fun?” |
| Dashes | -- is en-dash, --- is em-dash | – is en-dash, — is em-dash |
創建一個自定義列表
Markdown如何創建一個注腳
一個具有注腳的文本。2
注釋也是必不可少的
Markdown將文本轉換為 HTML。
KaTeX數學公式
您可以使用渲染LaTeX數學表達式 KaTeX:
Gamma公式展示 Γ(n)=(n?1)!?n∈N\Gamma(n) = (n-1)!\quad\forall n\in\mathbb NΓ(n)=(n?1)!?n∈N 是通過歐拉積分
Γ(z)=∫0∞tz?1e?tdt .\Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,. Γ(z)=∫0∞?tz?1e?tdt.
你可以找到更多關于的信息 LaTeX 數學表達式here.
新的甘特圖功能,豐富你的文章
ganttdateFormat YYYY-MM-DDtitle Adding GANTT diagram functionality to mermaidsection 現有任務已完成 :done, des1, 2014-01-06,2014-01-08進行中 :active, des2, 2014-01-09, 3d計劃一 : des3, after des2, 5d計劃二 : des4, after des3, 5d- 關于 甘特圖 語法,參考 這兒,
UML 圖表
可以使用UML圖表進行渲染。 Mermaid. 例如下面產生的一個序列圖::
張三李四王五你好!李四, 最近怎么樣?你最近怎么樣,王五?我很好,謝謝!我很好,謝謝!李四想了很長時間,文字太長了不適合放在一行.打量著王五...很好... 王五, 你怎么樣?張三李四王五這將產生一個流程圖。:
鏈接長方形圓圓角長方形菱形- 關于 Mermaid 語法,參考 這兒,
FLowchart流程圖
我們依舊會支持flowchart的流程圖:
- 關于 Flowchart流程圖 語法,參考 這兒.
導出與導入
導出
如果你想嘗試使用此編輯器, 你可以在此篇文章任意編輯。當你完成了一篇文章的寫作, 在上方工具欄找到 文章導出 ,生成一個.md文件或者.html文件進行本地保存。
導入
如果你想加載一篇你寫過的.md文件或者.html文件,在上方工具欄可以選擇導入功能進行對應擴展名的文件導入,
繼續你的創作。
mermaid語法說明 ??
注腳的解釋 ??
總結
以上是生活随笔為你收集整理的程序员编程艺术第四十一章 四十二章 荷兰国旗 矩阵相乘Strassen算法的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: C网跟G网是什么意思?
- 下一篇: js实现简易打点计时器