人工智能2023秋季总结
人工智能2020秋季杂谈：
机器学习比较难，所以我跑到人工智能这里来避避风头
第一关：知识的表示1.一阶谓词逻辑杂谈：谓词逻辑，关键是谓词，其实我觉得就是汉语转化为“英语”
先上菜鸟题：老王喜欢妹子并不是所有的男人都喜欢妹子有些男人不是老王再上经典的猴子吃香蕉的题：设房间里有一只猴子，位于a
在c处有一串香蕉，（猴子想吃，但摘不到）
房间b处有一个箱子（如果猴子站到箱子上，就可以摘到香蕉）
解析：要解决这个问题，需要一定的套路。首先，找到有哪些东西（猴子，香蕉，箱子）；其次，定义谓词
静态属性：
位置关系：AT（x,y）,其中x的个体域为{monkey,banana,box},y的个体域为{a,b,c}
（如果以后涉及到位移的问题，首先应该想到的就是位置关系）
ONBOX：表示猴子在箱子上面
HB：猴子摘到香蕉
从上面就可以找到问题的初始状态和目标状态：
AT（monkey,a）AT（monkey,c）
AT(box,b)AT(box,c)
AT(banana,c)AT(banana,c)
~ONBOXONBOX
~HBHB
动态属性：动作
GOTO(x,y):表示猴子从x处走到y处
PUSHBOX(x,y):表示猴子推着箱子从x处移动到y处
CLIMBBOX:表示猴子爬上箱子
GRASP：表示猴子摘到香蕉
这些条件对应的先决条件和动作：
…(这个东西比较长，一阶谓词用来表示一个状态过程，我怀疑一面纸才能写下，考试应该不会出这种类型的大题，大家熟悉一下他的流程就好。个人觉得像这种给出一个解决方案的题目是不会限制你使用那种知识表示的方法的，下面还会讲一些其他的知识表示和推理的方法)
2.产生式系统杂谈：
步骤就是：列出综合数据库->列出初始状态和目标状态->穷举出可能发生的情况（这一步最难）->实例化找到解
要是第三步暂时想不到，可以先把第四步的解得到，然后再抽象出第三步
上面的猴子吃香蕉问题传教士与野人问题
倒水的问题3.语义网络杂谈：类似java的UML类图建模，这里主要是把握住“对象”，然后建立以此为突破点，将其他事物的关系都扯上去
事物和概念：
动物能运动、会吃。鸟是一种动物，鸟有翅膀、会飞。鱼是一种动物，鱼生活在水中、会游泳。
事物和概念：
王强是理想公司的经理;理想公司在中关村;王强28岁。
情况表示事件和动作节点常河给江涛一个优盘
4.框架杂谈：就是填写个人信息表（不仅是填实例，还要抽象出实例的类型），英语水平差就很难受了
第二关：确定性知识推理杂谈：这一章虽然写的多，但是难点就两个：解释，置换。其实指派就是自己根据个体域赋值，置换记住常/变可替换变就行。
题一（解释）简单理解，我给你一个解释：要是某某为1（1是个体域的值），xxx，然后谓词的值将会是xxx,最后这个公式的值就是T/F。
题二（鲁滨逊归结原理的证明题）杂谈：复习一下步骤。假设已知F1，F2要推出G。
把{F1,F2,~G}放在一起做成一个子句集，如果能归结出空，则证明。
题三（归结反演用来求取问题的答案）杂谈：爱或者不爱，只能选择一个。
假设张被盗，公安局派出5个人去调查。案情分析时，侦察员A说：“赵与钱至少有一个人作案”；
B说：“钱和孙至少有一个人作案”；
C说：“孙和李至少有一个人作案”
D说：“赵和孙至少有一个人与此案无关”
E说：“钱和李至少有一个人与此案无关”
如果这5个人的话都可信，试用归结演绎推理求出谁是盗窃犯。
第三关：搜索策略(这一关是最难的)杂谈：搜索策略解决问题的方法有两种：状态空间法（画圈圈）和问题规约法（与/或树）。
题一（状态空间）杂谈：其实这类问题和上面说的产生式系统很像的，大家可以仔细对比一下
农夫问题
有一农夫带一条狼，一只羊和一筐菜欲从河的左岸乘船到河的右岸，但受下列条件的限制：
（1）船太小，农夫每次只能带一样东西过河；
（2）如果没有农夫看管，则狼要吃羊，羊要吃菜；
请设计一个过河方案，使得农夫，狼，羊，菜都能不受损失地过河，画出相应的状态空间图。
提示：
（1）用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在作案，1表示在右岸。
（2）把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。
题二（盲目的深搜和广搜）杂谈：图搜索算法比较难，下面讨论的主要是树搜索算法。结点的扩展顺序是最重要的。以往大家都是在一个的具体图上讨论深搜和广搜，这里扩展结点十分形象，下面的一个题是需要自己抽象的。
圆盘问题：
设有大小不等的三个圆盘A,B,C，套在一根轴上，每个盘上都标有数字1，2，3，4，并且每个圆盘上都可以独立地绕轴逆时针转动，每次转动90°，其初始状态S0和目标状态Sg如下图所示，请用广度优先搜索和深度优先搜索，求出从S0到Sg的路径。
题三：代价树的广度优先搜索杂谈：在生成的结点中按照代价从小到大排序，每次找到代价最小的结点进行扩展。
下面是一个比较经典的算法题——旅行商问题，由于篇幅比较长，有些分支就没有画出来了。
题四：启发式搜索杂谈：启发式搜索关键是找出一个启发函数。
设有如下结构的移动将牌游戏：
BBWWE其中，B表示黑色将牌，W表示白色将牌，E表示空格。游戏规则走法：
（1）任意一个将牌可移入相邻的空格，规定其代价为1；
（2）任何一个将牌可相隔一个其他的将牌跳入空格，其代价为跳过将牌的数目加1。
游戏要达到的目标是把所有的W都移到B的左边。对这个问题，请定义一个启发函数h(n),并给出这个启发函数产生的搜索树，判别这个启发函数是否满足下界要求？在求出的搜索树中，对所有节点是否满足单调限制。
补充一个小知识点：
不可纳的，一定不满足单调限制。
题五：与或树（计算解树的代价）杂谈：要想找到最优解树，必须要计算解树的代价。本题就是一个计算解树代价的题，熟悉一下套路即可。
题六：博弈树，α-β剪枝第四关：贝叶斯网络杂谈：贝叶斯网络这一块儿，主要是掌握两个规则，链式法则和条件依赖。
题一：独立性判断条件独立详细说明
题二基于贝叶斯网络的概率计算杂谈:这里主要指的是枚举法的精确计算，也没有MCMC算法。比较容易理解，大家掌握一下基本套路就行。
求解农夫过河问题
问题：一个农夫带着一匹狼、一只羊、一颗白菜要过河，只有一条船而且农夫每次最多只能带一个动物或物品过河，并且当农夫不在的时候狼会吃羊，羊会吃白菜，列出所有安全将所有动物和物品带过河的方案。
思路分析：显然这不是一个最优解的问题，最容易想到的方法就是遍历了，设法用遍历列举出所有可能出现的情况，根据条件选取出其中所有正确的解路径。把每个状态看作一个节点的话，那么节点的子节点可以设计为4个，分别对应的情况是：农夫单独过河、农夫带狼过河、农夫带羊过河、农夫带白菜过河，则所有的情况顶多构成一棵满4叉树。因为其中有的状态是不合法的，可以通过约束进行裁剪，实际这棵4叉树会小得多。问题解的模型就确定下来了，接下来是需要用一种搜索方法找到树中所有合法的解路径，我用的是深度优先搜索对这棵4叉树进行路径搜索，当搜索到的节点为最终目标节点时，那么从起始节点到该目标节点经过的路径就是一个解路径，直到搜索完这棵树后就能找到所有的解路径了。
tips:
1、为了程序能够便于表示，状态可以用4位二进制数来表示，0000（int类型为0）代表初始状态，从左往右每一位依次表示农夫、狼、羊、白菜，0表示在起始岸，1代表在目的岸，则目标状态为1111（int类型为15）。故用整型0-15这16个数字就可以表示所有状态了。
2、当程序进行深度优先搜索时，需要记录下该路径经过的节点（状态），因为节点（状态）是不能重复的，重复的情况没有意义，比如开始农夫把羊带到对岸，然后又把羊带回来，则此时重复了起始状态这就没有任何意义，而且也会让程序无限循环。所以用一个introute[16]数组就可以记录任何一条路径（因为一条路径顶多占满所有16个状态），数组的下标就表示该状态，数组的内容就记录上一个节点（状态）即其下标，比如route[15]=5表示节点（状态）15（即目标状态1111）上一个节点（状态）是5（即0101），再翻译白一点就是最后一步为农夫带羊过河（0101至1111）。
C语言代码：
#includeintfamerLocation(intcurrentLocation)//判断农民的位置{if((currentLocation&8)==8){return1;}else{return0;}}intwolfLocation(intcurrentLocaiton)//判断狼的位置{if((currentLocaiton&4)==4){return1;}else{return0;}}intgoatLocation(intcurrentLocation)//判断羊的位置{if((currentLocation&2)==2){return1;}else{return0;}}intcabbageLocation(intcurrentLocation)//判断白菜的位置{if((currentLocation&1)==1){return1;}else{return0;}}intjudgeSafe(intcurrentLocation)//判断当前状态是否安全{//安全返回1，不安全返回0inta,b,c,d;a=famerLocation(currentLocation);b=wolfLocation(currentLocation);c=goatLocation(currentLocation);d=cabbageLocation(currentLocation);if(a!=b&&b==c)//当农夫和狼位置不同而狼和羊位置相同时不安全{return0;}elseif((a!=c)&&(c==d))//当农夫和羊位置不同而羊和白菜位置相同时不安全{return0;}else{return1;}}voidprintRoute(introute[16])//根据一个路径数组输出一条路径{intlocation=15;while(location!=-2){printf("%d",location);location=route[location];}printf(" ");}voidprocess(introute[16],intcurrentLocation)//算法核心，输入要处理的路径route[16]和该路径当前最新位置currentLocation{if(route[15]==-1)//如果该路径还未到达目的状态{intmover;for(mover=1;mover