TVM 实战： 用llvm提高人工智能模型推理速度
下面为记录人工智能推理加速过程，基于TVM
总体脉络：
1.TVM安装 2.TVM测试及使用3.AutoTVM使用4.编译导出so/dll5.在C++中调用生成的so/dll
零、什么是TVM
TVM是apache基金会开放的人工智能模型编译框架，由华人 陈天琦博士初始开发。陈博士本科毕业于上海交大ACM班，有极深的计算机理论基础，有名的xgboost就是出自他手。
通常我们使用人工智能模型进行前向推理的方式是这样:
1.训练模型
这一步骤对于广大炼丹师来说非常熟悉了，可以使用tensorflow或pytorch之类工具进行模型训练，得到模型文件（网络结构和参数）。
2.使用推理引擎部署模型
推理一般我们可以使用上面提到的人工智能框架的前向推理功能进行处理。稍讲究一点的可以使用专用的人工智能推理框架，比如onnxruntime(ORT),NCNN(腾讯出品）等。这种方式可以理解为解释方式（类比于python语言的解释运行方式）。在这一方式下，我们需要先加载模型，用通过的推理引擎创建网络结构并加载好网络参数，再将需要推理的数据输入模型，得到最后的推理结果。
另一种方式就是所谓的JIT方式，类似java或其它带JIT的语言（如php8.0)，比如你可以直接在java中创建代码并调用tvm进行推理。这种情况下TVM引擎没有完全发挥优化能力。
第三种方式，最复杂但是最高效的方式：TVM编译。将推理引擎和模型编译优化成nativecode方式。你可以想象成自己写的一套函数，函数中已经硬编码了网络模型的参数，可以从整体上对整个模型加参数进行编译优化，得到最好性能的推理功能函数（算子和模型已经融为一体）
第三四方式：在IOT设备上，可以使用裸金属方式，即不需要操作系统支持的程序下，生成推理库，只依赖c运行库，无需操作系统介入，适合IOT设备。
我们将一步一步引导大家测试第二三种方式的使用，终极目标是在auto TVM基础上实现第三种方式。
AutoTVM使用模板创建搜索空间来帮助我们进一步优化算法，以达到性能调优的目的。即auto-tunning。
auto-tuning分两个步骤：第一步定义搜索空间；第二步是运行搜索算法来探索这个空间。在本教程中，你可以了解如何在TVM中执行这两个步骤。下面通过矩阵乘法展示auto-tuning的完整工作流程。
本文可能会涉及autoTVM实作手法。
一、TVM安装请参考官方文档： https://tvm.apache.org/docs/install/index.html
在ubuntu18.04下安装：
1.安装基础环境
sudoapt-getupdatesudoapt-getinstall-ypython3python3-devpython3-setuptoolsgcclibtinfo-devzlib1g-devbuild-essentialcmakelibedit-devlibxml2-dev2.下载源码
gitclone--recursivehttps://github.com/apache/tvmtvm3.进入tvm目录
mkdirbuildcpcmake/config.cmakebuild3.下载llvm预编译包：
https://releases.llvm.org/download.html
从下面下载自己需要的包，解压后放到某个目录，我放到了/opt下
我的路径是：
/opt/clang+llvm-10.0.0-x86_64-linux-gnu-ubuntu-18.04/注意上面的路径依使用的llvm版本有不同而不同。
4.修改刚才复制的config.cmake文件
修改这行：set(USE_LLVM /path/to/your/llvm/bin/llvm-config)
我的值是 set(USE_LLVM/opt/clang+llvm-10.0.0-x86_64-linux-gnu-ubuntu-18.04/bin/llvm-config)
注意上面的路径，依自己的clang的解压目录而变化（clang和llvm在本文中的意思相同，不作区别）
5.编译
cdbuildcmake..make-j46.安装tvm库
mkdir/opt/tvm
将build目录下的libtvm打头的so文件复制到/opt/tvm下
当前的两个文件是：
libtvm_runtime.so libtvm.so
至少编译完成，下面安装python下的tvm
二、安装python版本TVM
切换到刚才下载的tvm源码的目录，即那个tvm目录。在此目录下还有先前创建的build目录的。
确保你的python命令运行后提示是python3版本。
cdpython;pythonsetup.pyinstall--user;cd..
安装完成后，运行python
输入importtvm并回车
如果没有报错，刚表明安装tvm成功。
三、TVM测试gitclonehttps://github.com/google/googletestcdgoogletestmkdirbuildcdbuildcmake..makesudomakeinstall
切换到刚才的tvm源码目录（下面有我们创建的build)
运行测试脚本：
./tests/scripts/task_cpp_unittest.sh
或
makecpptest
四、AutoTVM自动调优https://blog.csdn.net/hw5226349/article/details/92019491
五、C++端部署及导出so
https://zhuanlan.zhihu.com/p/60981432
六、后记
关于四、五节的内容，为了内容完整，引用了几个网上的文章，后面会完善。
动物识别——人工智能
实验三产生式系统推理一、实验目的本实验课程是计算机、智能、物联网等专业学生的一门专业课程，通过实验，帮助学生更好地掌握人工智能相关概念、技术、原理、应用等；通过实验提高学生编写实验报告、总结实验结果的能力；使学生对智能程序、智能算法等有比较深入的认识。1.掌握人工智能中涉及的相关概念、算法；2.熟悉人工智能中的知识表示方法；3.掌握问题表示、求解及编程实现；4.理解产生式系统的结构原理与实际应用；5.掌握产生式规则表示及规则库组建的实现方法；6.熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法。
二、基本要求1.实验前，复习《人工智能》课程中的有关内容。2.准备好实验数据。3.编程要独立完成，程序应加适当的注释。4.完成实验报告。
三、实验软件使用C或C++（Visualstudio或其它开发环境）（不限制语言使用）。
四、实验内容：以动物识别系统为例，用选定的编程语言建造规则库和综合数据库，开发能进行正确的正向推理或反向推理的推理机。正向推理过程从已知事实出发，通过规则库求得结论，或称数据驱动方式。推理过程是：规则集中的规则前件与事实库中的事实进行匹配，得匹配的规则集合。从匹配规则集合中选择一条规则作为使用规则。执行使用规则的后件，将该使用规则的后件送入事实库中。重复这个过程直至达到目标。
1动物分类规则集（1）若某动物有奶，则它是哺乳动物。（2）若某动物有毛发，则它是哺乳动物。（3）若某动物有羽毛，则它是鸟。（4）若某动物会飞且生蛋，则它是鸟。（5）若某动物是哺乳动物且有爪且有犬齿且目盯前方，则它是食肉动物。（6）若某动物是哺乳动物且吃肉，则它是食肉动物。（7）若某动物是哺乳动物且有蹄，则它是有蹄动物。（8）若某动物是有蹄动物且反刍食物，则它是偶蹄动物。（9）若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。（10）若某动物是食肉动物且黄褐色且有黑色斑点，则它是金钱豹。（11）若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点，则它是长颈鹿。（12）若某动物是有蹄动物且白色且有黑色条纹，则它是斑马。（13）若某动物是鸟且不会飞且长腿且长脖子且黑白色，则它是驼鸟。（14）若某动物是鸟且不会飞且会游泳且黑白色，则它是企鹅。（15）若某动物是鸟且善飞且不怕风浪，则它是海燕。下面是该规则集所形成的（部分）推理网络：图1动物识别系统部分推理网络
1.2问题描述由上述动物识别规则组成规则库，推理机采用正向推理算法或反向推理算法，实现对动物的查询。如给出初始事实：F1：某动物有毛发F2：吃肉F3：黄褐色F4：有黑色条纹目标条件为：该动物是什么？3规则库扩充(选做)在上述规则集(Ⅰ)基础上增加以下规则集(Ⅱ)：（1）兔子：有毛发，有奶，善跳跃，唇裂；（2）猫：有毛发，有奶，善捕鼠，脚有肉垫；（3）犀牛：有毛发，有奶，鼻子上有角，褐色，皮糙肉后，皮糙肉厚，有蹄；（4）熊猫：有毛发，有奶，黑眼圈，四肢短小；（5）鹦鹉：鸟类，上嘴鹰钩，会模仿人说话；（6）鸭子：鸟类，腿短，嘴扁平，善潜水游泳；（7）鹰：鸟类，上嘴鹰钩，有爪，吃肉；（8）鸭子：有羽毛，卵生，善游泳，嘴扁平，腿短；（9）鹅：有羽毛，卵生，善潜水游泳，白色或黑色，颈长，嘴大，腿长，颈部有肉只凸起；（10）鸦：有羽毛，卵生，黑色，嘴大；（11）鹰：有羽毛，卵生，有爪，吃肉，上嘴鹰钩；（12）鹦鹉：有羽毛，卵生，上嘴鹰钩，能模仿人说话；（13）青蛙：卵生，生活在水中，生活在陆地，有皮肤呼吸，用肺呼吸，皮肤光滑，吃昆虫，会变色；（14）蝾螈：卵生，生活在水中，生活在陆地，有皮肤呼吸，用肺呼吸，吃昆虫，皮肤粗糙，四肢扁，背部黑色；（15）蟾蜍：卵生，生活在水中，生活在陆地，有皮肤呼吸，用肺呼吸，吃昆虫，皮肤粗糙；（16）比目鱼：用鳃呼吸，身体有鳍，生活在海洋中，身体扁平，两眼在头部同侧；（17）鲫鱼：用鳃呼吸，身体有鳍，生活在淡水中，身体扁平，头高尾部窄；（18）蛇：生活在陆地，用肺呼吸，胎生，身体有鳞或甲，身体圆而细长，吃小动物；（19）壁虎：生活在陆地，用肺呼吸，胎生，身体有鳞或甲，有四肢，尾巴细长易断，吃昆虫；（20）乌龟：生活在陆地，用肺呼吸，胎生，身体有鳞或甲，身体圆而扁，有坚硬的壳；（21）玳瑁：生活在陆地，用肺呼吸，胎生，身体有鳞或甲，壳为黄褐色，皮肤光滑，有黑斑；（22）鳄鱼：生活在陆地，用肺呼吸，胎生，身体有鳞或甲，有四肢，善游泳，皮硬黑褐色。要求在动物分类规则集(Ⅰ)的基础上添加上述22条知识，共构成29种动物的知识库系统，对原有动物分类系统进行扩充和修改。
五、实验程序组成(1)使用的结构Rule类，类中存放一个int类型的指针和重载了一个运算符==，用于后续与int类型的数组作比较。(2)使用的各种函数//用于中间状态操作的函数Boolinclude(Rulerule,int*ch);//判断ch中含有rule全部元素Voidclean(Rulerule,int*ch);//删除ch中与rule相同的元素boolzero(int*ch);//判断ch中是否全部元素都为0Boolcheck(int*ch,int*p);//判断ch中是否还含有p中元素//规则库函数Intrule1(int*ch);//一级规则，可以直接由条件推理出Intrule2(int*ch,intrule1);//二级规则，需要结合一级推理结果Intrule3(int*ch,intrule2);//三级规则，需要结合二级推理结果//推理结果处理函数Intresult(int*ch,intrule3);//根据rule3的结果进行分析Voidshow(inta);//根据推理得出的序号输出相应文字(3)部分实验代码：
//规则库intrule1(int*ch){if(!zero(ch)){//有奶->哺乳动物Rulerule1;intt1=1;rule1.rule=&t1;if(include(rule1,ch)){clean(rule1,ch);return24;}//有毛发->哺乳动物Rulerule2;intt2=2;rule2.rule=&t2;if(include(rule2,ch)){clean(rule2,ch);return24;}//有羽毛->鸟Rulerule3;intt3=3;rule3.rule=&t3;if(include(rule3,ch)){clean(rule3,ch);return25;}//会飞，能生蛋->鸟Rulerule4;intt[2]={4,5};rule4.rule=&t[0];if(include(rule4,ch)){clean(rule4,ch);return25;}}elsereturn0;}intrule2(int*ch,intrule1){if(!zero(ch)){switch(rule1){//哺乳动物case24:{//有爪，有犬齿，目盯前方->食肉动物Rulerule5;intt[3]={6,7,8};rule5.rule=&t[0];if(include(rule5,ch)){clean(rule5,ch);return26;}//吃肉->食肉动物Rulerule6;intt1=9;rule6.rule=&t1;if(include(rule6,ch)){clean(rule6,ch);return26;}//有蹄->有蹄动物Rulerule7;intt2=10;rule7.rule=&t2;if(include(rule7,ch)){clean(rule7,ch);return27;}return24;};//鸟case25:{//不会飞，长腿，长脖子，黑白色->鸵鸟Rulerule8;intt[4]={14,15,19,20};rule8.rule=&t[0];if(include(rule8,ch)){clean(rule8,ch);return33;}//不会飞，会游泳，黑白色->企鹅Rulerule9;intt1[3]={19,20,21};rule9.rule=&t1[0];if(include(rule9,ch)){clean(rule9,ch);return34;}//善飞，不怕风浪->海燕Rulerule10;intt2[2]={22,23};rule10.rule=&t2[2];if(include(rule10,ch)){clean(rule10,ch);return35;}return25;};}}elsereturnrule1;}intrule3(int*ch,intrule2){if(!zero(ch)){switch(rule2){//食肉动物case26:{//黄褐色，黑色条纹->老虎Rulerule11;intt1[2]={12,17};rule11.rule=&t1[0];if(include(rule11,ch)){clean(rule11,ch);return29;}//黄褐色，黑色斑点->金钱豹Rulerule12;intt2[2]={12,13};rule12.rule=&t2[0];if(include(rule12,ch)){clean(rule12,ch);return30;}return26;};//有蹄动物case27:{//反刍->偶蹄动物Rulerule13;intt1=11;rule13.rule=&t1;if(include(rule13,ch)){clean(rule13,ch);return28;}//长腿，长脖子，黄褐色，暗斑点->长颈鹿Rulerule15;intt3[4]={12,14,15,16};rule15.rule=&t3[0];if(include(rule15,ch)){clean(rule15,ch);return31;}//白色，黑色条纹->斑马Rulerule14;intt4[2]={17,18};rule14.rule=&t4[0];if(include(rule14,ch)){clean(rule14,ch);return32;}return27;};}returnrule2;}elsereturnrule2;}六、实验结果分析：初始界面：
输入题设条件：
得出结果：
实验心得：①实验中采用了对规则的分级保证了推理的中间过程的完善性，不过这也使得本程序中的可用规则全为最基本的规则，若是从中间过程开始的推理，如推理条件以哺乳动物为基本条件的推理，需要用于自行推理出哺乳动物的基本条件。②规则库与记录用户输入条件的数组以指针*ch的形式存放，原本在确定条件数量的时候想用ch[]!=NULL的，可是会出现越界的情况，后来观察错误发现越界后数值都十分大或小，故重新设置边界条件为-50~50用来计算条件数量，也算一种取巧。
完整代码：#includeusingnamespacestd;//单条规则形式classRule{public:int*rule;booloperator==(int*ch);};boolRule::operator==(int*ch){inti=0;while(ch[i]>-50&&ch[i]intrulelong=0,same=0;while(-50if(rule.rule[m]==ch[i])same++;}}if(same==rulelong)returntrue;elsereturnfalse;}//删除已使用过的条件:在ch中删除相应规则rule1voidclean(Rulerule,int*ch){intrulelong=0,i=0;while(rule.rule[rulelong]>-50&&rule.rule[rulelong]-50&&ch[i]if(rule.rule[m]==ch[i]){ch[i]=0;break;}m++;}i++;}}//全0判断boolzero(int*ch){inti=0;while(ch[i]>-50&&ch[i]intsame=0,chlong=0;while(ch[chlong]>-50&&ch[chlong]same++;chcopy[i]=0;}//比较same和ch长度if(same==chlong)returntrue;elsereturnfalse;}//规则库intrule1(int*ch){if(!zero(ch)){//有奶->哺乳动物Rulerule1;intt1=1;rule1.rule=&t1;if(include(rule1,ch)){clean(rule1,ch);return24;}//有毛发->哺乳动物Rulerule2;intt2=2;rule2.rule=&t2;if(include(rule2,ch)){clean(rule2,ch);return24;}//有羽毛->鸟Rulerule3;intt3=3;rule3.rule=&t3;if(include(rule3,ch)){clean(rule3,ch);return25;}//会飞，能生蛋->鸟Rulerule4;intt[2]={4,5};rule4.rule=&t[0];if(include(rule4,ch)){clean(rule4,ch);return25;}}elsereturn0;}intrule2(int*ch,intrule1){if(!zero(ch)){switch(rule1){//哺乳动物case24:{//有爪，有犬齿，目盯前方->食肉动物Rulerule5;intt[3]={6,7,8};rule5.rule=&t[0];if(include(rule5,ch)){clean(rule5,ch);return26;}//吃肉->食肉动物Rulerule6;intt1=9;rule6.rule=&t1;if(include(rule6,ch)){clean(rule6,ch);return26;}//有蹄->有蹄动物Rulerule7;intt2=10;rule7.rule=&t2;if(include(rule7,ch)){clean(rule7,ch);return27;}return24;};//鸟case25:{//不会飞，长腿，长脖子，黑白色->鸵鸟Rulerule8;intt[4]={14,15,19,20};rule8.rule=&t[0];if(include(rule8,ch)){clean(rule8,ch);return33;}//不会飞，会游泳，黑白色->企鹅Rulerule9;intt1[3]={19,20,21};rule9.rule=&t1[0];if(include(rule9,ch)){clean(rule9,ch);return34;}//善飞，不怕风浪->海燕Rulerule10;intt2[2]={22,23};rule10.rule=&t2[2];if(include(rule10,ch)){clean(rule10,ch);return35;}return25;};}}elsereturnrule1;}intrule3(int*ch,intrule2){if(!zero(ch)){switch(rule2){//食肉动物case26:{//黄褐色，黑色条纹->老虎Rulerule11;intt1[2]={12,17};rule11.rule=&t1[0];if(include(rule11,ch)){clean(rule11,ch);return29;}//黄褐色，黑色斑点->金钱豹Rulerule12;intt2[2]={12,13};rule12.rule=&t2[0];if(include(rule12,ch)){clean(rule12,ch);return30;}return26;};//有蹄动物case27:{//反刍->偶蹄动物Rulerule13;intt1=11;rule13.rule=&t1;if(include(rule13,ch)){clean(rule13,ch);return28;}//长腿，长脖子，黄褐色，暗斑点->长颈鹿Rulerule15;intt3[4]={12,14,15,16};rule15.rule=&t3[0];if(include(rule15,ch)){clean(rule15,ch);return31;}//白色，黑色条纹->斑马Rulerule14;intt4[2]={17,18};rule14.rule=&t4[0];if(include(rule14,ch)){clean(rule14,ch);return32;}return27;};}returnrule2;}elsereturnrule2;}//推理结果处理intresult(int*ch,intrule3){//三重推理后还有剩余元素if(!zero(ch)){//剩余有效重复元素正常返回，无效重复元素返回0switch(rule3){case24:{intt1[2]={1,2};int*p1=&t1[0];if(check(ch,p1))//未通过check判定return24;elsereturn0;//查无此动物}case25:{intt2[3]={3,4,5};int*p2=&t2[0];if(check(ch,p2))return25;elsereturn0;}case26:{intt3[6]={1,2,6,7,8,9};int*p3=&t3[0];if(check(ch,p3))return26;elsereturn0;}case27:{intt4[]={1,2,10};int*p4=&t4[0];if(check(ch,p4))return27;elsereturn0;}case28:{intt5[]={1,2,10,11};int*p5=&t5[0];if(check(ch,p5))return28;elsereturn0;}case29:{intt6[]={1,2,6,7,8,9,12,17};int*p6=&t6[0];if(check(ch,p6))return29;elsereturn0;}case30:{intt7[]={1,2,6,7,8,9,12,13};int*p7=&t7[0];if(check(ch,p7))return30;elsereturn0;}case31:{intt8[]={1,2,10,12,14,15,16};int*p8=&t8[0];if(check(ch,p8))return31;elsereturn0;}case32:{intt9[]={1,2,10,17,18};int*p9=&t9[0];if(check(ch,p9))return32;elsereturn0;}case33:{intt10[]={3,4,5,14,15,19,20};int*p10=&t10[0];if(check(ch,p10))return33;elsereturn0;}case34:{intt11[]={3,4,5,19,20,21};int*p11=&t11[0];if(check(ch,p11))return34;elsereturn0;}case35:{intt12[]={3,4,5,22,23};int*p12=&t12[0];if(check(ch,p12))return35;elsereturn0;}}}//三种推理后无剩余元素elsereturnrule3;}//根据返回值进行输出voidshow(inta){switch(a){case0:{coutcoutcoutcoutcoutcoutcout0};intq=1;for(inti=0;q!=0;i++){cin>>test[i];q=test[i];}//读数，并写入ch数组intnum=0;while(test[num]!=0)num++;int*ch=newint[num];for(inti=0;i传统人工智能中的三大问题
基于神经网络和大样本统计规律的深度学习越来越走入瓶颈，人工智能的发展越来越向基于符号推理和因果推理的传统人工智能回归。AI算法工程师不能把眼光仅仅局限在海量样本的统计规律上，而应该学习并掌握基于符号推理和小样本学习的传统人工智能技术。否则，当深度学习的热点一过，你很可能无法适应企业和市场对AI的新的需求。
本文介绍了传统人工智能要解决的三大问题：问题求解、博弈和谓词逻辑。它们都是基于符号推理和白盒推理的。了解相应的解决方案和算法有助于算法工程师开拓眼界，加深对算法本质的理解，增加解决问题、适应未来需求的能力。
1.传统人工智能的三大问题人工智能包括传统人工智能和现代人工智能两部分。机器学习、深度学习、遗传算法和强化学习是现代人工智能的主要分支。他们主要解决分类、回归、聚类、关联和生成等问题。而传统人工智能主要解决问题求解、博弈和谓词逻辑三大问题。
传统人工智能之所以重要是因为：
传统人工智能的算法比较成熟、可靠、有效。很多能够用传统人工智能解决的问题就不应该使用复杂且成本高昂的现代人工智能方法。比如求上海到北京之间的最短路径问题，用A*算法就要比深度神经元网络高效得多；传统人工智能更基础。很多应用场景中，现代人工智能方法必须在传统人工智能基础上发挥作用。比如战胜围棋世界冠军李世石的AlphaGo其基础部分仍然是博弈算法，而残差神经元网络（深度学习技术之一）只不过在评价棋局优劣时发挥了作用。作为一个算法工程师，如果你只懂深度学习不懂博弈算法，是很难编写出高效的围棋程序的；深度学习是基于黑盒推理的，往往知其然而不知其所以然。也就是说，它能解决问题，但是我们不知道它为什么能解决问题。而传统人工智能的各种算法一般都是基于白盒推理的，知其然更知其所以然；更重要的是，我们不能以“有没有用”为标准来评价传统人工智能。就像数学中某些当时看来“没有用”的理论和方法一样，当它“有用”时你再去研究它就迟了。2.问题求解2.1状态和状态转化这里的问题是指可以用状态来描述的，且起始状态和终止状态明确的问题。比如，八数码问题的一个可能的起始状态如下图所示：
在一个3*3的网格中随机放置了1-8八个数码。其中有一个网格是空着的。这个空网格可以跟上下左右四个方向的任何一个临近的数码交换。但不能跟斜方向上的数码交换。比如上图中空网格可以和右边的那个数码3相交换，得到的子状态就是：
八数码问题就是研究如何用最少的次数移动空网格，从而使得八个数码最终呈现出如下所示的终止状态：
2.2搜索树
问题求解的一个最简单的方法就是构造搜索树。方法是：
把初始状态看成是根结点，构成仅含有一个结点的搜索树T；任选T中的一个候选结点a，把它的所有可能的子结点都挂在a之下。这个过程称为对a的扩展。所谓候选结点就是没有被扩展过的结点；不断重复2）直到找到终止状态，或者没有候选结点为止。下图就是一个搜索树的例子（其中排除了重复的结点）。尽管上述算法并不能保证给出最少移动次数，甚至我们都不能保证它一定能终止（如果我们不排除重复结点的话），但是它仍然给出了问题求解算法的最基本框架。问题求解的各种算法（比如宽度优先、深度优先、爬山法、分支定界法和A*算法等）就是在这个框架基础上按照不同思路进行优化的结果。
比如宽度优先搜索，就是在算法的第2)步选择距离根结点最近的候选结点优先扩展。这个方法找到的第一个解一定也是最优解。所谓解就是从根结点到终止结点的一个路径。
所谓分支定界法就是在找到一个解之后，就把这个解的路径长度与以前找到的解的路径长度相比较，只保留路径短的那个。以后我们在扩展任何一个结点时，都要看看当前路径的长度是否短于解的路径长度。如果回答是“否“，则当前这个结点就没有必要扩展下去了。
至于其他更高明的算法，比如A*，这里就不再赘述。感兴趣的同学请关注方老师博客http://fanglin.blog.csdn.net。
与八数码问题类似的著名问题还有：
华容道问题：见上图，一个4*5的棋盘上有曹操、卒、马云、......大小不同的棋子。4个卒的大小都是1*1，黄忠、赵云、张飞和马超的大小是1*2，关羽的大小是2*1，曹操最大，大小是2*2。棋盘上还有两个1*1的空格以便棋子移动。游戏的目的是把曹操移到下方关口位置处，从而逃出华容道；八皇后问题：在8*8的国际象棋棋盘上（见下图）如何放置八个皇后使得任意两个皇后都不在同一行、同一列或者同一斜线上；求两个城市之间的最短路径问题；背包问题：给定有限个物品以及每个物品的重量以及价值，比如罐头200克6元，手机125克5000元，等等。另外再给你一个最大负重为2000克的背包。问在不超过最大负重的情况下应该在背包中放置哪些物品从而获得最大的价值？路径规划问题，怎样规划一个或者多个快递小哥的路径使得他们跑最少的路把一堆快递送到客户手中。这个问题还可以扩展到物流规划、船舶航运规划上。八皇后问题
解决这些问题的关键在于如何描述问题的状态以及父状态如何生成子状态。比如最短路径问题中，状态就可以用当前所在的城市表示。城市与城市之间有道路直接连通的就可以构成父子状态的转换。由于道路一般是双向的，则父子状态的转换也是双向的。
而背包问题的状态可以用背包里当前所拥有的所有物品的集合表示。所谓子状态就是往父状态背包里添加任意一个不超重的物品构成的。
3.博弈3.1博弈树我们通常所说的博弈其实是博弈的最简单形式，即信息全透明的封闭环境下的两人零和博弈。围棋、象棋、国际象棋等都是这样的博弈。而扑克、麻将、多人跳棋等就不是。以下除非特指，所谓博弈都是指这种两人零和博弈。
博弈要解决的问题是：当人类棋手下一步棋之后，电脑该如何应对呢？跟搜索树一样，博弈所采用算法也是从当前的根结点出发构建博弈树。以井字棋为例，井字棋是一种两人轮流在一个3*3的棋盘上下棋的游戏。目的是看谁先把自己的棋连成了一行、一列或者一条斜线。与中国的五子棋类似。以下是井字棋博弈树的部分结构：
井字棋的博弈树
与搜索树不同的是：
博弈树在扩展过程中，是双方轮流下棋的。而搜索树无需这样的考虑；搜索树通常要考虑从根结点到当前结点的耗费，而A*算法甚至还要考虑从当前结点到可能的终止结点的预期耗费。耗费越小越好。而博弈树通常只考虑当前状态对双方的价值。价值越大越好，价值也称为得分。得分可以小于0（这表示对对方有利）；由于我们考虑的仅仅是两人零和博弈，所以当一个状态对一方的价值（或者说得分）是v的话，则同一个状态对另一方的价值就是-v；如果某个状态下，当前走棋的一方已经获胜的话（比如井字棋中己方有三个棋子已经连成一条线），则他的得分就是正无穷大或接近无穷大，而另一方的得分就是负无穷大或接近负无穷大；由于结点的数目会呈几何指数增加，所以博弈树和搜索树一样，都要解决组合爆炸问题。3.2简单博弈算法简单博弈算法主要思想是：
博弈树上所有结点的得分都相对于当前下棋的一方计算。正得分表示对他有利，负得分表示对对方有利；采用深度优先方法扩展候选结点。也就是说，优先扩展离根结点远的结点；为了避免组合爆炸，当博弈树的高度达到一定高度h时，就停止扩展。此时当前结点的得分采用估算法或者深度学习方法获得。这个问题下面还要谈；当一个结点的所有子结点的得分都确定之后，就可以确定该结点的得分。结点的得分总是等于所有子结点得分中最大得分的相反数。比如，假设所有子结点的得分分别是-3，12，7，-10，则当前结点的得分就是-12。这是因为，博弈算法假设对方是理性的，总是会走对他自己最有利的一步棋。而这一步的得分如果是v的话，对当前下棋的一方就是-v。因为是两人零和博弈嘛！有意思的是，这个方法也可以用来计算当前结点的父结点的得分。包括当前结点在内的所有兄弟节点中最大得分的相反数就是父结点的得分。所谓兄弟结点就是父结点相同的结点。这个过程可以不断地向上传播直到根结点；根结点的所有子结点中得分最大的那个就是计算机的解。假设下图是一个限高4层的博弈树，其中所有叶子结点的得分都已经估算出来了：
博弈树（叶子结点的得分已被估算出来）
我们的问题是：A、B、C三个结点中，电脑会选择哪个下棋呢？我们只需沿着叶子结点向上，一层一层计算各个结点的得分即可。记住：每个非叶子结点的得分等于其所有子结点中最大得分的相反数。下面是计算结果：
从叶子结点出发向上一层层计算得分
根据上述结果我们显然知道，电脑应该选择结点A作为自己的应对。
3.3估算得分可能有人会问，我怎么估算结点的得分呢？这要看你们下的是什么棋。如果是井字棋，一般来说正中间的那个位置特别重要，谁占据了那个位置应该给谁高分。给多少分您就自己看着办吧。如果是象棋，可以计算一下双方的剩余棋力，比如“车”给100分，“兵”给1分。然后以双方的棋力差作为得分。这个方法没有考虑棋子的位置。其他棋类游戏都可以以此类推。
值得一提的是，深度学习方法可以在估算得分时发挥重要作用。AlphaGo等就是采用这个方法解决了围棋的组合爆炸问题。由于这个问题比较复杂，并且超出了本文的讨论范围，这里不再赘述。有兴趣的读者可以参考我以后的文章。
3.4Alpha-Beta剪裁绝大多数博弈游戏都面临组合爆炸问题。即随着结点的指数级扩展，博弈树的规模很快就达到天文数字。围棋的博弈程序就是基于这个原因才长期得不到解决直到引入深度学习方法。
Alpha-Beta剪裁算法可以部分地解决这个问题。它的核心思想就是：如果当前结点的某个兄弟结点的得分是v，则当前结点的所有子结点的得分都必须小于-v。只要其中有一个子结点的得分大于或者等于-v，则当前结点及其以它为根结点的整个子树都可以从博弈树上删除。如下图：
Alpha-Beta剪裁示例
假设D的得分是4，E是D的兄弟结点。则E的子结点F和G的得分都必须小于-4。否则就应该把以E为根结点的子树从博弈树上删除。为什么呢？假设F的得分是-3，这意味着E和所有兄弟结点的最大得分至少是-3即：
max_value>=-3
前面我们讲过，E的得分应该等于-max_value。根据上面公式，我们得出E的得分必然小于等于3，从而小于D的得分4。这意味着我们根本就没有必要去扩展E的任何其他子结点了（比如G），因为即使扩展了G，E的得分也不会大于4。这就是Alpha-Beta剪裁的原理！
所以，使用Alpha-Beta剪裁算法时，博弈树的扩展常采用深度优先策略。这不仅更节省空间（因为没有必要保存整棵博弈树，只需把当前路径上的结点保存在一个堆栈中即可），更重要的是，深度优先策略有助于算法快速找到一个叶子结点，从而能把该结点的得分用来对相关结点进行剪裁。
关于Alpha-Beta剪裁的更多细节请关注方老师的博客。我在实践中使用这个方法实现了包括井字棋、五子棋、黑白棋等游戏的开发，证明了它的有效性。
4.谓词逻辑4.1命题、谓词和规则谓词逻辑主要研究如何进行逻辑推理。逻辑推理的基础是事实和规则。“张三和李四是朋友”，“太阳总是从东方升起”等就是事实。事实在谓词逻辑中是以命题的形式给出的。比如上述两个事实对应的命题分别是：
Is_Friend(“张三”,“李四”)
Rise_From（“Sun”,”Oriental”）
这里Is_Friends和Rise_From就是谓词，双引号扩起来的是字符串型逻辑常量。
规则形如：
If 条件 then 结论
其中条件和结论都是命题。比如：
IfIs_Friend(X,Y)thenIs_Friend(Y,X)
这个规则的含义是：如果X是Y的朋友，那么Y也是X的朋友。言下之意：朋友是相互的，不存在X是Y的朋友而Y却不是X朋友的情况。其中X和Y都是逻辑变量。
4.2逻辑运算和复合命题两个谓词之间可以用“and”或者“or”连接，分别表示“与”运算和“或”运算。比如，Is_Father(X,Y)andIs_Father(Y,Z)表示X是Y的父亲，Y是Z的父亲。这样由多个命题经过逻辑运算构成的命题称为复合命题。。
第三个逻辑运算是“not”，表示逻辑“非”操作。它是一个一元运算符。含义自明。
这样我们就可以用复合命题构成复杂的规则。比如：
IfIs_Father(X,Y)andIs_Father(Y,Z)thenIs_Grandpa(X,Z)
这个规则的意思是说：如果X是Y的父亲，Y是Z的父亲，则X是Z的爷爷。
4.3自动逻辑推理当我们把已知的命题和规则罗列在一起时，就能进行逻辑推理。逻辑推理的方法主要有两种，第一种是著名的三段式。比如，所有的猫都是哺乳动物，凯蒂是一只猫，所以凯蒂是哺乳动物。
第二种是利用规则进行反向推导。比如，假设我们想知道Tom的爷爷是谁。这实际上是求解命题Is_Grandpa(X, “Tom”)中X的值。怎么做呢？首先我们可以寻找所有结论是谓词Is_Grandpa的规则，这样的规则目前只有一条那就是：
IfIs_Father(X,Y)andIs_Father(Y,Z)thenIs_Grandpa(X,Z)
然后把Z=“Tom”代入其条件部分，则原命题Is_Grandpa(X, “Tom”)被替换为求解两个命题：
Is_Father(X，Y）andIs_Father(Y,“Tom”)
而求解这两个命题的方法是递归地调用上述步骤，直到所有命题都可以用三段式解决为止。
我们可以开发一个系统自动完成上述推理过程，这就是自动推理系统。事实上逻辑程序设计语言Prolog就是干这事的。如果你想自己开发一个这样的自动逻辑推理系统，你一定要注意：满足当前命题的规则可能不止一个，你应该在找到第一个答案前把所有可能的路径都走一遍而不是一旦一条路径走不通就下结论说原命题不成立。
递归显然不能满足这个要求，所以自动推理系统通常采用的是回溯法。如果你对如何构建自动推理系统感兴趣，请关注我以后的文章。
4.4高阶谓词逻辑我们前面所说的谓词逻辑实际是一阶谓词逻辑，也就是说，谓词的参数要么是变量，要么是常量。如果谓词的参数也是谓词，则这样的谓词就是二阶谓词。这已经超出了本文的讨论范围，本文不再赘述。
4.5谓词逻辑的应用谓词逻辑特别适合构建基于规则的专家系统、决策支持系统和规则系统。这与深度学习基于大量样本的黑盒推理完全不同。深度学习是从特殊（的样本）出发归纳出一般性的结论，谓词逻辑则是从一般性的规则出发推导出特殊情况下的结论，这是两个截然相反的过程。人脑就是这两个过程的完美结合体。
5.结束语本文简单介绍了传统人工智能的问题求解、博弈和谓词逻辑，目的是帮助非计算机专业的算法工程师开拓眼界增加认知的。要想了解更多的详情还需要你系统学习《人工智能》课程，或者关注我的博客。