Re: [新闻] 超狂数学教授活用算法 高铁分段买票竟
楼主: orz8809ed (姜丝猪人) 2017-08-15 14:30:54
小弟学店资工系 简单介绍一下这个算法
作者在文中已经有提到是dijkstra's algorithm 戴克斯奥拉算法
主要用在最短路径的探讨上
其实可以应用在很复杂的铁路系统
可惜台湾高铁连一圈都没有连起来 所以简单很多
范例影片 https://www.youtube.com/watch?v=5GT5hYzjNoo&t=5s
我们拿高铁台北站来作范例
影片中会有无限符号可以想成无法直接买到那站的车票 要转车所以暂时是未知
票价图
先把台北站可以到达的票价都先列出来
" target="_blank">![]()
" class="img-responsive" />
这是从台北坐到各站的价钱
台北->南港再到各站的价钱 比对之后没有比较便宜的 所以照抄下来
台北到南港已经是最便宜 用红色底标注
" target="_blank">![]()
" class="img-responsive" />
然后比对从台北->板桥 再到各站的价格有无较便宜
刚刚忘记放数据了 这里开始会放 未标注地名的是代表台北到该站再到各站的价钱
像下图是台北到板桥再到各站 (台北到板桥:40 + 板桥到各站:x)
有标注地名的是表示从哪一站过来的
" target="_blank">![]()
" class="img-responsive" />
所以可以看到从台北直达还是都比较便宜
下一站 桃园
台北->桃园->各站
" target="_blank">![]()
" class="img-responsive" />
这里可以看到某些站的价格已经打平了
不过打平还不够
" target="_blank">![]()
" class="img-responsive" />
下一站 新竹
台北->新竹->各站
" target="_blank">![]()
" class="img-responsive" />
还是打平的状态
下一站 苗栗
各位同胞们我们在台北->苗栗->嘉义终于省了10块钱啦(用蓝色标注
" target="_blank">![]()
" class="img-responsive" />
所以嘉义那边地名改成苗栗 以后到嘉义都要先到苗栗转车
苗栗忘记打出来了= ="
下一站 台中
还是打平 这边要注意到嘉义都要在苗栗转车 所以到嘉义路径是
台北->苗栗->台中->嘉义
" target="_blank">![]()
" class="img-responsive" />
下一站 彰化
还是一样 数据忘记截= =" 抱歉
" target="_blank">![]()
" class="img-responsive" />
下一站 云林
" target="_blank">![]()
" class="img-responsive" />
还4一样
" target="_blank">![]()
" class="img-responsive" />
下一站 嘉义
由于前面知道 台北到嘉义在苗栗转车会比较便宜 所以剩下的台南和高雄都会在苗栗转车
也就是 台北->苗栗->嘉义->各站 这样子
" target="_blank">![]()
" class="img-responsive" />
左营再便宜了10元
下一站 台南
" target="_blank">![]()
" class="img-responsive" />
没有比较便宜
" target="_blank">![]()
" class="img-responsive" />
所以根据dijkstra's 算法
台北->苗栗->嘉义->左营
这样转车到左营的确可以便宜20元
不过这是没有考虑时间的问题
如果考虑进时间的话
相信绝对还是是台北高雄直达CP值最高的
在此做个简单的介绍 有误还请指正
如果变成考题学弟妹不要怪我030
作者在文中已经有提到是dijkstra's algorithm 戴克斯奥拉算法
主要用在最短路径的探讨上
其实可以应用在很复杂的铁路系统
可惜台湾高铁连一圈都没有连起来 所以简单很多
范例影片 https://www.youtube.com/watch?v=5GT5hYzjNoo&t=5s
我们拿高铁台北站来作范例
影片中会有无限符号可以想成无法直接买到那站的车票 要转车所以暂时是未知
票价图
先把台北站可以到达的票价都先列出来
" target="_blank">
这是从台北坐到各站的价钱
台北->南港再到各站的价钱 比对之后没有比较便宜的 所以照抄下来
台北到南港已经是最便宜 用红色底标注
" target="_blank">
然后比对从台北->板桥 再到各站的价格有无较便宜
刚刚忘记放数据了 这里开始会放 未标注地名的是代表台北到该站再到各站的价钱
像下图是台北到板桥再到各站 (台北到板桥:40 + 板桥到各站:x)
有标注地名的是表示从哪一站过来的
" target="_blank">
所以可以看到从台北直达还是都比较便宜
下一站 桃园
台北->桃园->各站
" target="_blank">
这里可以看到某些站的价格已经打平了
不过打平还不够
" target="_blank">
下一站 新竹
台北->新竹->各站
" target="_blank">
还是打平的状态
下一站 苗栗
各位同胞们我们在台北->苗栗->嘉义终于省了10块钱啦(用蓝色标注
" target="_blank">
所以嘉义那边地名改成苗栗 以后到嘉义都要先到苗栗转车
苗栗忘记打出来了= ="
下一站 台中
还是打平 这边要注意到嘉义都要在苗栗转车 所以到嘉义路径是
台北->苗栗->台中->嘉义
" target="_blank">
下一站 彰化
还是一样 数据忘记截= =" 抱歉
" target="_blank">
下一站 云林
" target="_blank">
还4一样
" target="_blank">
下一站 嘉义
由于前面知道 台北到嘉义在苗栗转车会比较便宜 所以剩下的台南和高雄都会在苗栗转车
也就是 台北->苗栗->嘉义->各站 这样子
" target="_blank">
左营再便宜了10元
下一站 台南
" target="_blank">
没有比较便宜
" target="_blank">
所以根据dijkstra's 算法
台北->苗栗->嘉义->左营
这样转车到左营的确可以便宜20元
不过这是没有考虑时间的问题
如果考虑进时间的话
相信绝对还是是台北高雄直达CP值最高的
在此做个简单的介绍 有误还请指正
如果变成考题学弟妹不要怪我030
作者: seafox5566 (老猫) 2017-08-15 14:32:00
1f帅
作者: shiburin (废文制造机) 2017-08-15 14:32:00
嗯跟我想的一样
作者: mcmcmc (mcmcmc) 2017-08-15 14:34:00
操作不难 难的是证明为何是对的
作者: Cybershit (BMI<18der肥宅) 2017-08-15 14:34:00
高铁路线基本上只是一条炼 看不出Dijkstra's的特点
作者: seuil ( ) 2017-08-15 14:35:00
算法厉害 可以算出便宜20元 跟我用纸笔算的一样
作者: wemee (方天画) 2017-08-15 14:35:00
楼下跳针贪婪法则跟旅行背包解高铁问题
作者: hipab (嗨趴) 2017-08-15 14:40:00
楼下负cycle shortest path 让高铁无限循环
作者: end81235 (21) 2017-08-15 14:49:00
在说什么啊，每条路的成本不同，要看成不同的路啊
作者: fate201 (Licht) 2017-08-15 14:52:00
每条路的票价当成距离就好了 最终移动距离都相同啊
作者: end81235 (21) 2017-08-15 14:52:00
和一条炼有什么关系？路径画出来就是一张网
作者: Cybershit (BMI<18der肥宅) 2017-08-15 14:53:00
楼上 你有听过最短路径树吗还一张网勒...
作者: end81235 (21) 2017-08-15 14:54:00
…台北到台中，台中再到高雄，和台北到高雄是三条线讲这样够白了吧…
作者: Cybershit (BMI<18der肥宅) 2017-08-15 14:56:00
不是很明白你想表达什么 Dijkstra's只会留下到某个点
作者: end81235 (21) 2017-08-15 14:56:00
最短路径树是说，由某一个起点的角度来看的结果
作者: end81235 (21) 2017-08-15 14:57:00
和高铁是直的是弯的，有没有分枝没有关系
作者: Cybershit (BMI<18der肥宅) 2017-08-15 14:57:00
这求的是单源最短路径 我想你指的是all pairs
作者: Cybershit (BMI<18der肥宅) 2017-08-15 15:00:00
3楼? 你现在是在想证明吗
作者: end81235 (21) 2017-08-15 15:01:00
4楼啦，看错
作者: Cybershit (BMI<18der肥宅) 2017-08-15 15:02:00
这样说好了 假设a到b有5种相异路径 成本不尽相同算法跑完 只会留下一种成本最低的路径 其他的都不管单源最短路径的情况下啦假设起点就是a 那Dijkstra's一旦走到了b 走法肯定是成本最低 所以之后再有路径可以到b都无视 因为不会改善a到b 或是a经过b到其他点的距离在一条炼的情况下这看不出来 因为只会一直往前钻
作者: end81235 (21) 2017-08-15 15:08:00
……
作者: Cybershit (BMI<18der肥宅) 2017-08-15 15:08:00
哦应该说我错了 这不算是一条炼 因为各站间可以直达我误会你了 你是对的
作者: end81235 (21) 2017-08-15 15:09:00
感谢原po补充
作者: Cybershit (BMI<18der肥宅) 2017-08-15 15:09:00
所以原图的确是一张网 不是一条炼
作者: end81235 (21) 2017-08-15 15:10:00
不会，互相讨论
作者: zzzz8931 (肥宅) 2017-08-15 15:18:00
时间复杂度？