人工智能算法

人工智能算法完整版分享！内容覆盖，盲目搜索，知情搜索以及受到自然启发的搜索。适用于学习人工智能算法的小伙伴们学习。

人工智能算法

• 盲目搜索
  • 状态空间图
    • 设定状态变量及确定值域
    • 确定状态组，分别列出初始状态集和目标状态集
    • 定义并确定操作集
    • 估计全部状态空间数，并尽可能列出全部状态空间或给予描述
    • 当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解
  • 回溯算法
    • 完备性
    • 最优性
    • 时间复杂度
    • 空间浮渣度
  • 贪婪算法
    • 核心思想是每次都选择局部最优解，但该算法并不能保证最后得出的结果是全局最优解
    • 大部分的贪婪算法都是基于图的方式寻找最优路径
    • 贪婪算法比较典型的案例就是最短路径搜索
  • 深度优先算法
    • 与广度优先搜索算法类似，唯一不同的是，它是沿着树的深度遍历数的节点，尽可能遍历搜索数的分支
    • 它会首先遍历根节点的第一个子节点，接着遍历子节点的第一个子节点，并沿着树的深度一直遍历下去
  • 广度优先算法
    • 解决自动寻路功能的算法之一
    • 作为一种常见的图形搜索算法，它也被广泛应用于解决其他各类算法问题
    • 一般情况下，对于一个节点，它的邻居节点的集合被称作open list，而在这个节点被遍历之前，其他所有已经遍历过的节点存于close list中
  • 迭代加深算法
    • 完备性：当分支因子有限时，算法完备
    • 最优性：当路径代价是结点深度的非递减函数时该算法是最优的
    • 时间复杂度：与宽度优先搜索算法一致
    • 空间复杂度
• 知情搜索
  • 启发法
    • 计算机科学的两大基础目标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法，但启发式算法则试图一次提供一或全部目标
      • 计算机科学的两大基础目标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一或全部目标
  • 爬山法
    • 爬山法爬山法就是完全的贪心算法，每一步都选最优位置，可能只能得到局部最优解
    • 随机重启爬山法，当爬山步数超过一定值时，会重新打乱棋盘，重新“爬山”
  • 最陡爬坡法
    • 最陡上山法的平均路径长度更短，但是搜索耗散却比首选爬山法多，原因是，为了得到最陡的子结点，需要探查所有的相邻子节点
  • 最佳优先搜索
    • 试图扩展离目标最近的结点，理由是这样可能可以很快找到解
  • 分支定界法
    • 求解LRP问题，收敛的准则是计算意义上的
    • 最基本的一种求解整数规划的方法
  • A*算法
    • A算法的搜索效率很大程度上取决于估价函数 h(n)
    • 在满足**h(n)≤h(n)**的前提下，h(n)的值越大越好
    • 信息性：h(n)的值越大，说明它携带的启发性信息越多，A算法搜索时扩展的节点就越少，搜索的效率就越高
• 受到自然启发的搜索
  • 遗传规划
    • 对于以往难以解决的函数优化问题 ,复杂的多目标规划问题 ,工农业生产中的配管、配线问题 ,以及机器学习 ,图象识别 ,人工神经网络的权系数调整和网络构造等问题
  • 蚂蚁聚居地优化
    • 是一种用来在图中寻找优化路径的机率型技术
    • 子其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质主题
  • 模拟退火
    • 是一种基于Monte Carlo迭代求解策略的随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性
    • 其目的在于为具有NP（Non-deterministic Polynomial）复杂性的问题提供有效的近似求解算法，它克服了其他优化过程容易陷入局部极小的缺陷和对初值的依赖性
  • 粒子群
    • 以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性
  • 禁忌搜索
    • 是一个用来跳出局部最优的搜寻方法
    • TS是人工智能的一种体现，是局部领域搜索的一种扩展
    • 禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动
    • 为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向