蚁群算法中转移概率是怎么用的.不同的蚂蚁为什么会选择不同的路径
答案:2 悬赏:40 手机版
解决时间 2021-01-27 19:33
- 提问者网友:蔚蓝的太阳
- 2021-01-27 13:44
蚁群算法中转移概率是怎么用的.不同的蚂蚁为什么会选择不同的路径
最佳答案
- 五星知识达人网友:舊物识亽
- 2021-01-27 15:16
因为不同路径的信息素和启发信息不同,所以向每条路径转移的概率也不同;
具体实现可以运用轮盘赌选择,转移概率越大的路径就会有更多的蚂蚁选择.。
Prime 算法和 Kruskal 算法都是用来求加权连通简单图中权和最小的支撑树(即最小树)的,Prime算法的时间复杂度为O(n^2) (n 为顶点数),Kruskal 算法的时间复杂度为 O(eln(e)) (e为边数),这两种算法都是多项式时间算法,也就是说,最小树问题已经有了有效算法去求解,属于P问题。
Dijkstra 算法求解的是加权连通简单图中一个顶点到其它每个顶点的具有最小权和的有向路,最简单版本的时间复杂度是O(n^2),也是多项式时间算法。
而蚁群算法是一种近似算法,它不是用来解决已存在精确有效算法的问题的,而是用来解决至今没有找到精确的有效算法的问题的,比如旅行商问题(TSP)。
旅行商问题也可以说是求“最短路径”,但它是求一个完全图的最小哈密顿圈,这个问题至今未找到多项式时间算法,属于NPC问题,也就是说,当问题规模稍大一点,现有的精确算法的运算量就会急剧增加。
文中的某些观点引自知乎大神余幸恩,感谢帮忙!~
具体实现可以运用轮盘赌选择,转移概率越大的路径就会有更多的蚂蚁选择.。
Prime 算法和 Kruskal 算法都是用来求加权连通简单图中权和最小的支撑树(即最小树)的,Prime算法的时间复杂度为O(n^2) (n 为顶点数),Kruskal 算法的时间复杂度为 O(eln(e)) (e为边数),这两种算法都是多项式时间算法,也就是说,最小树问题已经有了有效算法去求解,属于P问题。
Dijkstra 算法求解的是加权连通简单图中一个顶点到其它每个顶点的具有最小权和的有向路,最简单版本的时间复杂度是O(n^2),也是多项式时间算法。
而蚁群算法是一种近似算法,它不是用来解决已存在精确有效算法的问题的,而是用来解决至今没有找到精确的有效算法的问题的,比如旅行商问题(TSP)。
旅行商问题也可以说是求“最短路径”,但它是求一个完全图的最小哈密顿圈,这个问题至今未找到多项式时间算法,属于NPC问题,也就是说,当问题规模稍大一点,现有的精确算法的运算量就会急剧增加。
文中的某些观点引自知乎大神余幸恩,感谢帮忙!~
全部回答
- 1楼网友:杯酒困英雄
- 2021-01-27 16:27
因为不同路径的信息素和启发信息不同,所以向每条路径转移的概率也不同。
具体实现可以运用轮盘赌选择,转移概率越大的路径就会有更多的蚂蚁选择。
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯