三、贪婪算法
概念：贪婪算法是一种不追求最优解，只希望得到较为满意解的方法 。
贪婪算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间 。贪婪算法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况 。例如平时购物找钱时，为使找回的零钱的硬币数最少，不考虑找零钱的所有各种发表方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种 。这就是在使用贪婪算法 。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排 。如只有面值分别为1、5和11单位的硬币，而希望找回总额为15单位的硬币 。按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币 。但最优的解应是3个5单位面值的硬币 。
四、蚁群算法
蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术 。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为 。
自然界的种群相当广泛,但大部分都有以下的能力: 蚂蚁们总能找到食物源和蚂蚁窝之间的最短路径. 一旦这条最短路径被发现, 蚂蚁们就能在这条路上排成一行, 在食物源和蚂蚁窝之间搬运食物. 蚂蚁们是怎么做到的呢?
我们知道,2点间直线距离最短. 但蚂蚁们显然不具备这样的视力和智慧. 它们无法从远处看到食物源, 也无法计划一个合适的路径来搬运食物. 蚂蚁们采用的方法是全体在老窝的周围区域进行地毯式搜索.而他们之间的是通过分泌化学物质在爬过的路径上,这种化学物质叫(Pheromone).
蚂蚁们习惯选择信息素浓度高的路径. 下面的图解释了蚂蚁们的工作原理.
刚开始离开窝的时候, 蚂蚁们有两条路径选择: R1和R2. 这两者机会相当. 蚂蚁们在爬过R1和R2的时候都留下了信息素. 但是, 由于R2的距离短, 所需要的时间就少, 而信息素会挥发, 所以蚂蚁们留在R2上的信息素浓度就高. 于是,越来越多的蚂蚁选择R2作为最佳路径, 即使它们是从R1来到食物源,也将选择R2返回蚂蚁窝. 而从老巢里出发的蚂蚁们也越来越倾向于R2. 在这样的趋势下, R1渐渐变的无人问津了
根据蚂蚁们选择路径的方法而得到的启发, Dr. Dorigo在1991年发表了(Ant algorithm). 十多年来, 蚂蚁算法,以及各种改进过的蚂蚁算法,被广泛的应用在实际生活的各个方面. 在应用中,它可以作为网络路由控制的工具. 在交通控制中, 它也成功解决了车辆调度问题.在图表制作中, 它被用来解决颜色填充问题. 此外, 它还可以被用来设计大规模的时刻表. 而问题,既在多个不同地点间往返的最佳路径选择问题, 应该算是蚂蚁算法最重要的用途了
【人工智能基础算法】
推荐阅读
- 中国茶叶的分类和基础知识(详细)
- 汽车|人工智能的普及，当然会让一部分职业“消失”，某些工作会被替代
- 算法面试 - 水壶问题
- 烧制优良紫砂茶具奠定茶物质基础
- 零基础自学办公软件 如何学习办公软件
- 命理学七政天星（四余 七政四余排盘算法初篇）
- 一文了解人工智能学科
- LRU算法详解及最简单的Java实现
- 指纹识别算法基本原理介绍
- 什么是排序算法的稳定性？