演算法平台框架

A. 如何學習演算法框架

深度學習對於初學者而言，需要注意些什麼問題，如何快速入門；
對比當前比較流行的深度學習框架，並分析各種框架的優缺點；
針對用 python 實現各種演算法模型時遇到的問題進行討論；
討論在學習 TensorFlow 並用其實現 Inception V1-V4 ，ResNet，DenseNet 等深度神經網路的過程中的難點，和在過程中出現的問題；
用現有演算法框架實現自己的圖像識別系統。

B. AI系統架構之演算法平台設計

明確需求之後，演算法平台的設計就比較明確了，業界可以參考的例子包括facebook的fblearner和Uber的Michelangelo（如下圖）。

可以看到，演算法平台包含幾個環節：

* 數據准備

主要是如何准備數據，並且管理數據在離線、近線和在線模式之間的分布。

* 模型訓練和評估

主要是使用各種基礎平台（Spark/Tensorflow/Xgboost等)訓練模型，從數據中獲取可以應用的模型和規則。

訓練出來的模型，需要進行驗證和評估，評估包括在訓練集、測試集和時間外驗證集上的表現，檢查模型的性能表現（KS、AUC等）、擬合程度和時間衰減。

* 模型服務與業務整合

在離線選擇好模型之後，就可以把它放到線上做實際的應用了，在真實系統中驗證假設是否成立。

落地路徑：線上系統-》到訓練平台

在充滿遺留系統的老企業或者人力不足的新企業，往往需要從線上系統開始。對於訓練過程，經常看到成立幾年的數據團隊，還在使用單機電腦訓練模型，在數據量不大的場景，半人肉的訓練短期是可以接受的，考慮到單機版的sklearn、keras這么流行，也可以理解這一點。

從收益角度來看，AI系統的最大價值體現在與業務結合的部分，例如促進增長、降低成本等，其次才是對人效的提升，例如自動運營、自動訓練。看清楚這一點，也就認同了從線上到線下的落地路徑。

線上系統設計

線上系統包含兩個部分，一部分負責模型打分，也就是inference，另外一部分是策略，以及與業務系統對接。

inference部分面臨的問題，是如何支持各種不同的建模工具，例如sas、python、spark等等，如果對性能並發要求不高，就可以使用pmml的對應語言實現，快速上線獲取短期勝利。

策略部分，一般可以映射成規則，使用drools這樣的規則引擎實現，可以解決最初一段時間的絕大部分需求。

C. 遺傳演算法的基本框架

遺傳演算法不能直接處理問題空間的參數，必須把它們轉換成遺傳空間的由基因按一定結構組成的染色體或個體。這一轉換操作就叫做編碼，也可以稱作(問題的)表示(representation)。
評估編碼策略常採用以下3個規范:
a)完備性(completeness):問題空間中的所有點(候選解)都能作為GA空間中的點(染色體)表現。
b)健全性(soundness): GA空間中的染色體能對應所有問題空間中的候選解。
c)非冗餘性(nonrendancy):染色體和候選解一一對應。
目前的幾種常用的編碼技術有二進制編碼，浮點數編碼，字元編碼，變成編碼等。
而二進制編碼是目前遺傳演算法中最常用的編碼方法。即是由二進制字元集{0,1}產生通常的0,1字元串來表示問題空間的候選解。它具有以下特點：
a)簡單易行
b)符合最小字元集編碼原則
c)便於用模式定理進行分析，因為模式定理就是以基礎的。 進化論中的適應度，是表示某一個體對環境的適應能力，也表示該個體繁殖後代的能力。遺傳演算法的適應度函數也叫評價函數，是用來判斷群體中的個體的優劣程度的指標，它是根據所求問題的目標函數來進行評估的。
遺傳演算法在搜索進化過程中一般不需要其他外部信息，僅用評估函數來評估個體或解的優劣，並作為以後遺傳操作的依據。由於遺傳演算法中，適應度函數要比較排序並在此基礎上計算選擇概率，所以適應度函數的值要取正值。由此可見，在不少場合，將目標函數映射成求最大值形式且函數值非負的適應度函數是必要的。
適應度函數的設計主要滿足以下條件：
a）單值、連續、非負、最大化
b) 合理、一致性
c）計算量小
d）通用性強。
在具體應用中，適應度函數的設計要結合求解問題本身的要求而定。適應度函數設計直接影響到遺傳演算法的性能。 遺傳演算法中初始群體中的個體是隨機產生的。一般來講，初始群體的設定可採取如下的策略:
a)根據問題固有知識，設法把握最優解所佔空間在整個問題空間中的分布范圍，然後，在此分布范圍內設定初始群體。
b)先隨機生成一定數目的個體，然後從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數達到了預先確定的規模。

D. android源碼里有哪些比較好的演算法或框架推薦

Android中對於圖形界面以及多媒體的相關操作比較容易實現。而且對於大多數
手機
用戶來說，他們主要也就是根據這些方面的功能來對系統那個進行修改。我們可以通過本文介紹的Android多媒體框架的源碼解讀，來具體分析一下這方面的基本知識。
Android多媒體框架的代碼在以下目錄中：external/opencore/。這個目錄是Android多媒體框架的根目錄，其中包含的子目錄如下所示：
* android：這裡面是一個上層的庫，它基於PVPlayer和PVAuthor的SDK實現了一個為Android使用的Player和Author。
* baselibs：包含數據結構和線程安全等內容的底層庫
* codecs_v2：這是一個內容較多的庫，主要包含編解碼的實現，以及一個OpenMAX的實現
* engines：包含PVPlayer和PVAuthor引擎的實現
* extern_libs_v2：包含了khronos的OpenMAX的頭文件
* fileformats：文件格式的據具體解析(parser)類
* nodes：編解碼和文件解析的各個node類。
* oscl：操作系統兼容庫
* pvmi： 輸入輸出控制的抽象介面
* protocols：主要是與網路相關的RTSP、RTP、HTTP等協議的相關內容
* pvcommon：pvcommon庫文件的Android.mk文件，沒有源文件。
* pvplayer：pvplayer庫文件的Android.mk文件，沒有源文件。
* pvauthor：pvauthor庫文件的Android.mk文件，沒有源文件。
* tools_v2：編譯工具以及一些可注冊的模塊。
Splitter的定義與初始化
以wav的splitter為例，在fileformats目錄下有解析wav文件格式的pvwavfileparser.cpp文件，在nodes目錄下有pvmf_wavffparser_factory.cpp，pvmf_wavffparser_node.h， pvmf_wavffparser_port.h等文件。
我們由底往上看，vwavfileparser.cpp中的PV_Wav_Parser類有InitWavParser()，GetPCMData()，RetrieveFileInfo()等解析wav格式的成員函數，此類應該就是最終的解析類。我們搜索PV_Wav_Parser類被用到的地方可知，在PVMFWAVFFParserNode類中有PV_Wav_Parser的一個指針成員變數。
再搜索可知，PVMFWAVFFParserNode類是通過PVMFWAVFFParserNodeFactory的CreatePVMFWAVFFParserNode()成員函數生成的。而CreatePVMFWAVFFParserNode()函數是在PVPlayerNodeRegistry::PVPlayerNodeRegistry()類構造函數中通過PVPlayerNodeInfo類被注冊到Oscl_Vector<PVPlayerNodeInfo, OsclMemAllocator> 的vector中，在這個構造函數中，AMR，mp3等node也是同樣被注冊的。
由上可知，Android多媒體框架中對splitter的管理也是與ffmpeg等類似，都是在框架的初始化時注冊的，只不過Opencore注冊的是每個splitter的factory函數。
綜述一下splitter的定義與初始化過程：
每個splitter都在fileformats目錄下有個對應的子目錄，其下有各自的解析類。
每個splitter都在nodes目錄下有關對應的子目錄，其下有各自的統一介面的node類和node factory類。
播放引擎PVPlayerEngine類中有PVPlayerNodeRegistry iPlayerNodeRegistry成員變數。
在PVPlayerNodeRegistry的構造函數中，將 AMR, AAC, MP3等splitter的輸入與輸出類型標示和node factory類中的create node與release delete介面通過PVPlayerNodeInfo類push到Oscl_Vector<PVPlayerNodeInfo, OsclMemAllocator> iType成員變數中。
當前Splitter的匹配過程
PVMFStatus PVPlayerNodeRegistry::QueryRegistry(PVMFFormatType& aInputType, PVMFFormatType& aOutputType, Oscl_Vector<PVUuid, OsclMemAllocator>& aUuids)函數的功能是根據輸入類型和輸出類型，在已注冊的node vector中尋找是否有匹配的node，有的話傳回其唯一識別標識PVUuid。
從QueryRegistry這個函數至底向上搜索可得到，在android中splitter的匹配過程如下：
android_media_MediaPlayer.cpp之中定義了一個JNINativeMethod(java本地調用方法)類型的數組gMethods，供java代碼中調用MultiPlayer類的setDataSource成員函數時找到對應的c++函數
1.{"setDataSource", "(Ljava/lang/String;)V", (void *)
android_media_MediaPlayer_setDataSource},
2.static void android_media_MediaPlayer_setDataSource
(JNIEnv *env, jobject thiz, jstring path)
此函數中先得到當前的MediaPlayer實例，然後調用其setDataSource函數，傳入路徑
3.status_t MediaPlayer::setDataSource(const char *url)
此函數通過調getMediaPlayerService()先得到當前的MediaPlayerService， const sp<IMediaPlayerService>& service(getMediaPlayerService());
然後新建一個IMediaPlayer變數， sp<IMediaPlayer> player(service->create(getpid(), this, fd, offset, length));
在sp<IMediaPlayer> MediaPlayerService::create(pid_t pid, const sp<IMediaPlayerClient>& client, const char* url)中
調status_t MediaPlayerService::Client::setDataSource(const char *url)函數，Client是MediaPlayerService的一個內部類。
在MediaPlayerService::Client::setDataSource中，調sp<MediaPlayerBase> MediaPlayerService::Client::createPlayer(player_type playerType)
生成一個繼承自MediaPlayerBase的PVPlayer實例。

E. 進化演算法的框架

進化演算法是以達爾文的進化論思想為基礎，通過模擬生物進化過程與機制的求解問題的自組織、自適應的人工智慧技術。生物進化是通過繁殖、變異、競爭和選擇實現的；而進化演算法則主要通過選擇、重組和變異這三種操作實現優化問題的求解。如圖1： 1、t=0
2、初始化群體p(0)
3、評估初始化群體p(0)
4、while終止條件不滿足do
5、 重組操作：p(t)=r(p(t))
6、 變異操作：p(t)=m(p(t))
7、 評估操作：p(t)
8、 選擇操作：p(t+1)=s(p(t)UQ)
9、 t=t+1
10、end 圖1：進化演算法基本框架
其中r、m、s分別表示重組運算元、變異運算元、選擇運算元。

F. Miller Rabin演算法的演算法基本框架

目前的基於概率的素數測試演算法一般都遵循一種基本的 框架[1]。給定一個正奇數n，定義一個集合W(n)屬於集合Z(n) (Z(n)是模n的非負整數集合)並有如下屬性：(1) 給定一個屬於集合Z(n) 的非負整數a ，可以在多項式時間復雜度內判斷a 是否屬於集合W(n) ；(2) 如果n是一個素數，那麼Z(n) 中屬於集合W(n) 的元素 的個數為0； (3)如果n是一個合數，那麼Z(n)中屬於集合W(n)的元素的個數大於等於n/2。如果n是一個合數，那麼集合W(n) 中的元素叫作合數n 的證據，集合L(n)=Z(n)－W(n)中的元素叫作合數n的偽證。 基於概率的素數測試演算法的基本思路是：定義一個符合以上規則的集合W(n)，對待測整數n隨機選擇屬於集合Z(n)的元 素a，檢查a 是否屬於集合W(n)，如果a 屬於W(n)則可以確定n 是一個合數，如果a不屬於W(n) 則n是素數的可能性大於等於1/2。對n 隨機地選擇元素a相對獨立地作 t 輪這樣的測試，則n是素數的可能性可以被控制在 1-(1/2)t以上。

G. 回溯演算法的演算法框架

（pascal語言） proceretry(i:integer);varbeginifi>nthen輸出結果elseforj:=下界to上界dobeginx[i]:=h[j];if可行{滿足限界函數和約束條件}thenbegin置值；try(i+1);end;end;（c++）以下以一道題目為例，素數環問題
將從1到n這n個整數圍成一個圓環，若其中任意2個相鄰的數字相加，結果均為素數，那麼這個環就成為素數環。 #include<iostream>#include<cmath>#include<cstdio>usingnamespacestd;intans[21]={0},tot=0;boola[21]={0};voidprint(){tot++;cout<<No.<<tot<<':';for(inti=1;i<=20;i++)cout<<ans[i]<<'';cout<<endl;}boolisprime(intx1,intx2){inti=x1+x2,f;for(f=2;f<=sqrt(i);f++)if(i%f==0)returnfalse;returntrue;}intsearch(intt){for(inti=1;i<=20;i++){if(a[i]==false&&isprime(ans[t-1],i)){ans[t]=i;a[i]=true;if(t==20&&isprime(ans[1],ans[20]))print();elsesearch(t+1);a[i]=false;}}}intmain(){search(1);printf(Thetotalis%d,tot);}

H. 簡述回溯法的2種演算法框架,並分別舉出適合用這兩種框架解決的一個問題實例

回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
基本思想
在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。（其實回溯法就是對隱式圖的深度優先搜索演算法）。 若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。 而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束

一般表達
可用回溯法求解的問題P，通常要能表達為：對於已知的由n元組（x1，x2，…，xn）組成的一個狀態空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關於n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。

規律
我們發現，對於許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（j<=i）元組（x1，x2，…，xj）一定也滿足d中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，xj）違反d中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反d中僅涉及到x1，x2，…，xi的一個約束，n≥i≥j。因此，對於約束集d具有完備性的問題p，一旦檢測斷定某個j元組（x1，x2，…，xj）違反d中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題p的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的演算法。