iniwap

iniwap的博客

他的个人主页  他的博客

帮同学搞定了硕士论文,蚁群算法求解K短路,高人多多指教

iniwap  2011年04月29日 星期五 23:01 | 2933次浏览 | 5条评论

研究问题:

   

图为北京市城市轨道交通的部分网络,图中只列举了主要的车站和换乘站。线路上的数字表示的是在该区间的运行时分,下表为在换乘站换乘时的换乘时间。

换乘站

换乘起、止线路

换乘走行时间(min)

d

4号线

13号线

8

4号线

2号线

4

13号线

2号线

9

13号线

4号线

7

2号线

4号线

4

2号线

13号线

3

f

4号线

2号线

4

2号线

4号线

5

j

13号线

2号线

5

2号线

13号线

6

求出O(起点站)-D(终点站)的K短路(花费时间最少),就是从起点站到终到站的花费时间最少的路径、第二短路径、…….第k短路径。(限制条件是换乘不能超过三次,直到第k短路所花费的时间多于最小花费时间的10min(包括等于10min)时为止)

--------------------------------------------------分割线----------------------------

同学的硕士论文,哥帮实现的,这个得炫下。

方案:蚁群算法求解K短路

关于蚁群算法:老衲未做深入的研究,仿生学类算法,具有一定的随机性,针对本问题则显示出了一定的局限性,由于站点的不可重复性和不可回头性,蚂蚁容易走入死胡同,对蚂蚁的各项参数要求较高。而且迭代次数无法预知,蚁群算法非一定从最大值向最小值收敛,不过基本可以保证最短路径的有效性,第K短路则不能保证解的完备性,这与蚁群算法本身特性相关。老衲不才,不做深入探讨,高人足下留情!

输出:

源码:展示部分

 

评论

我的评论:

发表评论

请 登录 后发表评论。还没有在Zeuux哲思注册吗?现在 注册 !
邹建

回复 邹建  2011年05月09日 星期一 14:02

跟遗传算法都在一个书架,还没有弄来看过

0条回复

薛仁杰

回复 薛仁杰  2011年05月08日 星期日 11:23

最近在搞遗传算法。也是用python写的

3条回复

暂时没有评论

Zeuux © 2024

京ICP备05028076号