算法平台框架

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的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。