01 January 2018

这是人工智能课程的复习提纲,希望也可以作为一个简要的人工智能算法介绍和索引。

第一部分:搜索问题

深度优先搜索

算法如下,递归调用,每次往后走一步,直到找到解(第1行),或者确定这条路找不到解(第2行)。

其缺点在于

  1. 有时候搜索深度太深,接近暴力搜索 -> 可以相应的限制深度;
  2. 搜索过的状态会重复搜索,陷入死循环 -> 可以记录访问过的状态,不要重复访问;

可以对其进行相应的改进,每次传入的参数不再是想要搜寻的状态$s$,而是到这个状态所经历的状态列表$s_list$。 深度优先搜索

  1. 是一个通用的与问题无关的方法;
  2. 一般不能保证找到最优解;
  3. 深度限制不合理的时候可能找不到解;
  4. 最坏情况搜索空间等同于暴力搜索;
  5. 节省内存,仅储存从初始节点到当前节点的路径;

宽度优先搜索

算法框架如下 宽度优先搜索

  1. 是一个与问题无关的方法;
  2. 当问题解存在的时候一定能找到解;当解的代价随路径长度单调增加的时候,一定能找到最优解;
  3. 内存消耗较大,要记录当前搜索到的所有可能路径;

启发式搜索



blog comments powered by Disqus