AI相关

最近老牛（BOSS） 喊来了个西班牙的教授Evan，上了几节AI的课。感觉讲的不错，就做个简要记录。

引用

问题：
8-puzzlehttp://www.8puzzle.com/
如
324           123
6_1    to    8_4
875           765
找到解或找到最优解

引用

数据结构：
决策树呗 根节点为初始状态；某一节点的子节点为符合移动规则移动后产生的状态。
对应此数据源结构的目标：
找到一个节点，其对应的状态就是
123
8_4
765

有了数据结构，那么开始考虑算法：

引用

  广度优先；
  深读优先；
  iterative deepening；
  algorithm A
  iterative deepening A*。

A 广度优先：
每次expand树的时候，总是先横向扩展，直到横向扩展结束，才开始向下扩展。
可以确定的是，假如每条路径的cost都相同，那么肯定能找到最优路径。
耗费内存。

B 深度优先：
每次expand树的时候，总是先竖向扩展，直到竖向扩展结束（需设定阈值即层数），才开始横向扩展。
无法保证能找到最优路径。
少量耗费内存。只需保存需设定阈值的个数的节点。
需设定阈值。

C iterative deepening
结合了广度优先和深度优先。
创建树，撤销树，创建树，撤销树……
第n次创建树，使用阈值n，采用深度优先的方式创建。
for instance：
第一次创建仅root。
第二次，root，child11；root，child12；……root，child1x。
第三次，…………
…………………………
第n次，root，child11，child21……childn1；root，child11，child21……childn2；……

假如每条路径的cost都相同，那么肯定能找到最优路径。
量耗费内存。

D algorithm A
想法：每次在选择优先查看和扩展的节点时，采取某一策略来抉择。
定义g(n)为从root到节点n的代价。h(n)从节点n到目标节点的估计代价。 f(n)=g(n)+h(n)。algorithm A就是根据f(n)选取下次查看和扩展的节点（取最小）。
当h(n)<h*(n)时，那么肯定能找到最优路径。h*(n)从节点n到目标节点的真实代价。

E iterative deepening A*
在iterative deepening的基础上加入cut-off函数。
使用cut-off函数决定深度优先，深到什么程度。
for instance：
step0：root。计算f(root)，为下一次的截断值cut-off。
step1：root开始使用深度优先扩展，每一次的深度扩展都扩展到f(parent(n))<=cut-off。使用这种方式构建树。min(f(leaf))为下一次的截断值cut-off。
…………

ok，差不多就这些了～～