人工智能-搜索

2019/04/10 10:10
阅读数 44

搜索是人工智能很重要的一种解决问题的途径,以下对各种搜索进行一个分类总结。

首先是搜索的定义,我们要解决一个问题,要经过很多步骤才能达到最终的目标,搜索就是要找到这些步骤,即解决问题的方法。

搜索有其局限性,它必须依赖于现有的知识,它不能自己学习知识,人工智能解决问题的另外一种途径就是学习,通过学习可以创造或者吸取新的知识。

下面是正文

搜索(Search)

求解一个问题就是一系列动作,并且搜索是为达到目标寻找这些动作的过程。

针对不同数据结构:

  • 图搜索

  • 树搜索

 

经典搜索(Classic Search)

  • 无信息搜索(uninformed search 即盲目搜索,没有除定义之外的信息)

    按照节点的扩展顺序区分

    • 宽度优先(breadth-first),用FIFO队列实现

    • 深度优先(depth-first):拓展最深的未扩展节点,用LIFO队列实现

      • 深度受限搜索(depth-limited):限制搜索深度

      • 迭代加深搜索(iterative deepening):结合深度优先与宽度优先的优势

    • 一致代价搜索(uninform-cost):扩展最低代价的未扩展节点

    • 双向搜索(bidirectional )

    无信息搜索的策略评价

    • 完备性:是否总能找到一个存在的解

    • 时间复杂性

    • 空间复杂性

    • 最优性:是否总能找到最优的解

     

  • 有信息搜索(informed search 亦称启发式搜索,采用问题定义外的信息,能够找到比无信息搜索更有效的解)

    • 最佳优先搜索(best-first):基于评价函数选择最优拓展节点,大多数该类算法还包括一个启发式函数

      • 贪心搜索

      • A*搜索

以上的搜索是经典搜索,它们的特点是

  • 可观测

  • 确定性

  • 已知环境

经典搜索保留搜索的路径,其路径就是问题的解

但在很多问题中,到达目标的路径不重要,因此就有了超越经典搜索

 

有路径-->无路径

超越经典搜索(Beyond Classical Search)

分为局部搜索与群体智能

  • 局部搜索(local search)

    不关注路径,搜索后不保留路径,其优点为

    1.占用内存小

    2.能在大的或者无限的空间中找到合理的解

    • 爬山法(hill-climbing):一种迭代算法,开始时随机选取一解,对其不断优化

      • 随机爬山法(Stochastic hill-climbing):向上移动的过程中随机选择,收敛速度慢

      • 首选爬山法(First-choice hill-climbing):随机生成后继节点,直到出现更好的

      • 随机重启爬山法(Random-restart hill-climbing):完备性高,接近于1

    • 局部束搜索(Local Beam Search)

      • 随机束搜索(Stochastic Beam Search)

    • 禁忌搜索(Tabu Search)

      三种策略

      • 禁止策略(Forbidding strategy)

      • 释放策略(Freeing strategy)

      • 短期策略(Short-term strategy)

    • 模拟退火(Simulated Annealing):一种在大搜索空间逼近全局最优解的元启发方法

    • 遗传算法(Genetic Algorithms):一种模仿自然选择过程的启发式算法

  • 群体智能(Swarm Intelligence)

    通过大量智能体通过合作实现,它是分布式的、自组织的、在一个环境内分布的。

    • 蚁群优化(Colony Optimization):受蚁群寻炸食物的行为的启发,用于发现一个图上的最佳路径

    • 粒子群优化(Particle Swarm Optimization):受鱼类,鸟类群体行为的社会行为启发

     

     

    单智能体-->多智能体

对抗搜索(Adversarial Search)

我们在针对其他智能体做规划时,那些智能体有可能也在做着规划

以上搜索针对单智能体,而对抗搜索针对多智能体

  • 博弈(Game)

  • 零和博弈(Zero sum games):智能体之间完全对立

  • 非零和博弈(Non-zero sum games):智能体之间是自主的方式

  • 完全信息(Perfect information)/不完全信息(Imperfect information)

  • 确定性(Deterministic)/随机性(Stochastic)

    • 剪枝 (Alpha-Beta Pruning)

      博弈树的大小往往呈指数增加,通过剪枝,可以减小博弈树,加快搜索时间

    • 启发评价函数(Heuristic Evaluation Function)

      尽管通过剪枝可以去掉博弈树的大部分,但是搜索的深度依然很深,因此用评价函数计算在指定位置该博弈的期望值

    • 随机博弈(Stochastic Game)

      一种有一定概率转换的动态博弈

    • 蒙特卡罗方法(Monte-Carlo Methods)

      凭借重复随机采样来获得数值结果

    • 蒙特卡罗树搜索(MCTS Monte-Carlo Tree Search)

      将蒙特卡洛仿真与博弈树搜索相结合

 

约束满足问题(Constraint Satisfaction Problem)

状态必须满足若干约束的对象

标准搜索中状态不可分割,GSP中状态用因子表示,是一系列变量。

GSP问题通常复杂性很高

范畴

  • 有限/无限

  • 离散/连续

    约束

  • 线性/非线性

  • 1元/多元

  • 回溯搜索(Backtracking Search)

原文出处:https://www.cnblogs.com/zhanghad/p/12483761.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部