智能算法考试练习题及解析

智能算法考试练习题及解析边上的实际距离：S->B:2S->D:3B->C:1D->C:1C->G:3解析：A*算法是一种经典的启发式搜索算法，其评估函数f(n)=g(n)+h(n)，其中g(n)是从起点到节点n的实际代价，h(n)是从节点n到目标节点的估计代价。A*算法总是选择f(n)值最小的节点进行扩展。搜索过程：1.初始状态：*OPEN表：{(S,g=0,h=8,f=0+8=8)}//(节点,g值,h值,f值)*CLOSED表：{}2.第一步：*从OPEN表中选择f值最小的节点S（f=8）。*将S从OPEN表移至CLOSED表。*扩展S，其邻接节点为B和D。*对B：g(B)=g(S)+S->B距离=0+2=2；h(B)=5；f(B)=2+5=7。OPEN表加入(B,2,5,7)。*对D：g(D)=g(S)+S->D距离=0+3=3；h(D)=4；f(D)=3+4=7。OPEN表加入(D,3,4,7)。*OPEN表：{(B,2,5,7),(D,3,4,7)}(按f值排序，f值相同可按节点顺序)*CLOSED表：{S}3.第二步：*OPEN表中B和D的f值均为7，假设优先选择字母顺序靠前的B。*将B从OPEN表移至CLOSED表。*扩展B，其邻接节点为C。*对C：g(C)=g(B)+B->C距离=2+1=3；h(C)=3；f(C)=3+3=6。OPEN表加入(C,3,3,6)。*OPEN表：{(C,3,3,6),(D,3,4,7)}*CLOSED表：{S,B}4.第三步：*从OPEN表中选择f值最小的节点C（f=6）。*将C从OPEN表移至CLOSED表。*扩展C，其邻接节点为G。*对G：g(G)=g(C)+C->G距离=3+3=6；h(G)=0；f(G)=6+0=6。OPEN表加入(G,6,0,6)。*OPEN表：{(G,6,0,6),(D,3,4,7)}*CLOSED表：{S,B,C}5.第四步：*从OPEN表中选择f值最小的节点G（f=6）。*G是目标节点，搜索结束。最短路径：S->B->C->G。其总代价g(G)为6。---三、机器学习基础-决策树练习题3：ID3算法构建决策树题目描述：序号年龄收入学生信用等级是否购买电脑:---:-----:-----:---:-------:-----------1青年高否一般否2青年高否好否3中年高否一般是4老年中否一般是5老年低是一般是6老年低是好否7中年低是好是8青年中否一般否9青年低是一般是10老年中是一般是11青年中是好是12中年中否好是13中年高是一般是14老年中否好否解析：ID3算法使用信息增益（InformationGain）来选择分裂属性。信息增益越大，表示使用该属性进行分裂所获得的“纯度提升”越大，因此优先选择。步骤1：计算数据集D的经验熵H(D)。数据集D共有14个样本。“是”的样本数：9个；“否”的样本数：5个。H(D)=-(9/14)*log2(9/14)-(5/14)*log2(5/14)。计算得：H(D)≈-(9/14)*0.6826-(5/14)*1.4855≈-0.439+(-0.530)≈0.969(熵值为正，此处计算过程省略具体小数保留，最终结果约为0.969)。步骤2：分别计算每个属性的信息增益。以“年龄”属性为例计算信息增益Gain(D,年龄)：“年龄”有三个可能取值：青年、中年、老年。*青年（样本数5）：“是”2，“否”3。H(青年)=-(2/5)log2(2/5)-(3/5)log2(3/5)≈0.971。*中年（样本数4）：“是”4，“否”0。H(中年)=0(纯节点)。*老年（样本数5）：“是”3，“否”2。H(老年)=-(3/5)log2(3/5)-(2/5)log2(2/5)≈0.971。条件熵H(D|年龄)=(5/14)*0.971+(4/14)*0+(5/14)*0.971≈(10/14)*0.971≈0.693。信息增益Gain(D,年龄)=H(D)-H(D|年龄)≈0.969-0.693=0.276。同理，可以计算出“收入”、“学生”、“信用等级”的信息增益（此处省略详细计算步骤，实际解题时需完整计算）：*收入属性的信息增益经计算约为0.029。*学生属性：*是（样本数5）：“是”4，“否”1→H≈0.722。*否（样本数9）：“是”5，“否”4→H≈0.991。*H(D|学生)=(5/14)*0.722+(9/14)*0.991≈0.258+0.637≈0.895。*Gain(D,学生)≈0.969-0.895=0.074。*信用等级属性的信息增益经计算约为0.048。步骤3：比较信息增益大小。Gain(D,年龄)≈0.276，Gain(D,学生)≈0.074，Gain(D,信用等级)≈0.048，Gain(D,收入)≈0.029。“年龄”属性的信息增益最大。结论：根节点应选择年龄属性进行分裂。---四、进化算法基础练习题4：遗传算法基本操作题目描述：在遗传算法中，假设当前种群中有两个染色体（采用二进制编码）：A=____和B=____。1.若采用单点交叉，交叉点位置为从左往右数第3位与第4位之间（即“|”处：101|100和011|011），请写出交叉后产生的两个新染色体。2.若对染色体A（____）的第4位（从左往右数，第一位为最左）基因进行基本位变异（0变1，1变0），请写出变异后的染色体。解析：遗传算法通过选择、交叉和变异等遗传操作实现种群的进化。1.单点交叉：单点交叉是指在两个父代染色体的相同位置随机选择一个交叉点，然后交换交叉点右侧的基因片段。*父代A：101|100*父代B：011|011*交换交叉点右侧片段后：*子代A：101011→____*子代B：011100→____2.基本位变异：基本位变异是指对染色体的某一位基因进行翻转。*原染色体A：101100（第4位为1）*变异后（第4位由1变为0）：101000→____---总结本文通过四道典型的智能算法练习题，涵盖了搜索算法、启发式搜索、决策树构建以及遗传算法等核心知识点。这些题目不仅