z****e
发帖数: 54598 | 1 这种图
http://upload.wikimedia.org/wikipedia/commons/f/fc/Rail_map_of_
你要构建一个从其中一个节点到另外一个节点的线路
你觉得容易么？
不需要太复杂
你就实现
要求输入任意两点，输出最短路径
就这么一个简单需求
够你的机器算半天了 |
z****e
发帖数: 54598 | 2 就这么简单的需求
我觉得搞不好就比leetcode上120题时候最难那题要难 |
b*******s
发帖数: 5216 | 3 LOL
【在 z****e 的大作中提到】
: 就这么简单的需求
: 我觉得搞不好就比leetcode上120题时候最难那题要难
|
z****e
发帖数: 54598 | 4 你例假还没来完是吧？
【在 b*******s 的大作中提到】
: LOL
|
b*******s
发帖数: 5216 | 5 in this case, there are limited nodes, no more than 5000 I guess. so it is
just a permutation (with conditions to reduce results) + Dijkstra
and the results could be pre-calced and cached
you just made my day |
z****e
发帖数: 54598 | 6 呵呵，你还记得leetcode的word ladder 2算了多久么？
【在 b*******s 的大作中提到】
: in this case, there are limited nodes, no more than 5000 I guess. so it is
: just a permutation (with conditions to reduce results) + Dijkstra
: and the results could be pre-calced and cached
: you just made my day
|
b*******s
发帖数: 5216 | 7 you tell me
【在 z****e 的大作中提到】
: 呵呵，你还记得leetcode的word ladder 2算了多久么？
|
z****e
发帖数: 54598 | 8 你不会试一下么？
【在 b*******s 的大作中提到】
: you tell me
|
b*******s
发帖数: 5216 | 9 totally crap
its so zhaoce
【在 z****e 的大作中提到】
: 呵呵，你还记得leetcode的word ladder 2算了多久么？
|
z****e
发帖数: 54598 | 10 让你试一下就crap了？
foxpro真不是盖的
还有啊，或者的意思理解了没有啊？
没事不要搞得跟娘们一样好不好？
很讨厌你诶
【在 b*******s 的大作中提到】
: totally crap
: its so zhaoce
|
|
|
z****e
发帖数: 54598 | 11 再问你一点
你还记得leetcode里面做cache了没有？
这一题的话
你做这一题的时候难道没有预先构建一下road map？
【在 b*******s 的大作中提到】
: totally crap
: its so zhaoce
|
z****e
发帖数: 54598 | 12 把你做这题的时间点算出来
乘以500w试一下，看过没过1s
【在 b*******s 的大作中提到】
: totally crap
: its so zhaoce
|
z****e
发帖数: 54598 | 13 而且你有没有意识到，这个东西是动态的
其中一个路段满了，你得找到就近绕道的
否则票的利用率大幅下降，你要有变通的方式
就这么一个简单的改变，你的cache就不能用了
你也不用悲愤，就先给你从最简单的说起
然后一点一点往里面加，加着加着，你就崩溃了
你很快就会发现，你之前的假设都是错的
事实上不用加，你的机器已经有些撑不住了
我怀疑光读就撑不住，你这里最好跟二爷解word ladder 2的时候一样
先做一个hash，否则一般的查找一样可以让你挂掉
【在 b*******s 的大作中提到】
: in this case, there are limited nodes, no more than 5000 I guess. so it is
: just a permutation (with conditions to reduce results) + Dijkstra
: and the results could be pre-calced and cached
: you just made my day
|
b*******s
发帖数: 5216 | 14 only you cant find a solution, get smart!
【在 z****e 的大作中提到】
: 而且你有没有意识到，这个东西是动态的
: 其中一个路段满了，你得找到就近绕道的
: 否则票的利用率大幅下降，你要有变通的方式
: 就这么一个简单的改变，你的cache就不能用了
: 你也不用悲愤，就先给你从最简单的说起
: 然后一点一点往里面加，加着加着，你就崩溃了
: 你很快就会发现，你之前的假设都是错的
: 事实上不用加，你的机器已经有些撑不住了
: 我怀疑光读就撑不住，你这里最好跟二爷解word ladder 2的时候一样
: 先做一个hash，否则一般的查找一样可以让你挂掉
|
z****e
发帖数: 54598 | 15 哦，是么？
一个连或者都不能理解的人跟我谈smart？
foxpro能撑得住这种压力不？
【在 b*******s 的大作中提到】
: only you cant find a solution, get smart!
|
s******y
发帖数: 416 | 16 问题是为什么每次定票都要算一次最短路径呢？有限图，两点间最短路是可以预先算好
的。读出来就是了。这也要动态生成，难怪要500个核啊。
【在 z****e 的大作中提到】
: 这种图
: http://upload.wikimedia.org/wikipedia/commons/f/fc/Rail_map_of_
: 你要构建一个从其中一个节点到另外一个节点的线路
: 你觉得容易么？
: 不需要太复杂
: 你就实现
: 要求输入任意两点，输出最短路径
: 就这么一个简单需求
: 够你的机器算半天了
|
w***g
发帖数: 5958 | 17 丢人现眼啊。现在你说的所有的东西都不可信了。
【在 z****e 的大作中提到】
: 这种图
: http://upload.wikimedia.org/wikipedia/commons/f/fc/Rail_map_of_
: 你要构建一个从其中一个节点到另外一个节点的线路
: 你觉得容易么？
: 不需要太复杂
: 你就实现
: 要求输入任意两点，输出最短路径
: 就这么一个简单需求
: 够你的机器算半天了
|
s******y
发帖数: 416 | 18 才看明白你想说啥。
你说的是车次调度，不是一个问题。人是坐车，人和人之间不存在抢铁路的问题。买票
时，有多少选择是固定的，不存在动态计算问题。
【在 z****e 的大作中提到】
: 而且你有没有意识到，这个东西是动态的
: 其中一个路段满了，你得找到就近绕道的
: 否则票的利用率大幅下降，你要有变通的方式
: 就这么一个简单的改变，你的cache就不能用了
: 你也不用悲愤，就先给你从最简单的说起
: 然后一点一点往里面加，加着加着，你就崩溃了
: 你很快就会发现，你之前的假设都是错的
: 事实上不用加，你的机器已经有些撑不住了
: 我怀疑光读就撑不住，你这里最好跟二爷解word ladder 2的时候一样
: 先做一个hash，否则一般的查找一样可以让你挂掉
|
d***a
发帖数: 13752 | 19 可以用蛮干的方法。车站的数目大约有几百个，起点和终点的组合
大约十万个，事先算好最短路径，存在内存里，这样就是O(1)的
复杂度了。:)
话说版上怎么搞得这么你死我活的？至于吗。
【在 z****e 的大作中提到】
: 这种图
: http://upload.wikimedia.org/wikipedia/commons/f/fc/Rail_map_of_
: 你要构建一个从其中一个节点到另外一个节点的线路
: 你觉得容易么？
: 不需要太复杂
: 你就实现
: 要求输入任意两点，输出最短路径
: 就这么一个简单需求
: 够你的机器算半天了
|
m**********j
发帖数: 8645 | 20 你难道不知道文人相轻吗？
【在 d***a 的大作中提到】
: 可以用蛮干的方法。车站的数目大约有几百个，起点和终点的组合
: 大约十万个，事先算好最短路径，存在内存里，这样就是O(1)的
: 复杂度了。:)
: 话说版上怎么搞得这么你死我活的？至于吗。
|
|
|
m**********j
发帖数: 8645 | 21 说实话，我一直觉得这几位不自己出来单干，不自己开公司拿合同，真是浪费了。
【在 d***a 的大作中提到】
: 可以用蛮干的方法。车站的数目大约有几百个，起点和终点的组合
: 大约十万个，事先算好最短路径，存在内存里，这样就是O(1)的
: 复杂度了。:)
: 话说版上怎么搞得这么你死我活的？至于吗。
|
l*****9
发帖数: 9501 | 22 算两点之间的路径，不在古德霸的要求里，即使联票，也是客户指定转车站。所以，订
票问题和图无关 |
c****t
发帖数: 19049 | 23 赵老师思路真是宽广。不过network optimization是operation research的领域。现在
实用中都是上数值逼近，要用commercial solver（大多core code都是FORTRAN写的）
。network规模大点的话是没办法做动态的。没数你这图有多少节点，不过现在最
powerful的commercial solvers要解这个最短路径估计也差不多要10~20分钟。
另外您那些AI/ML的讨论不怎么靠谱。您几位编程大牛还是掐编程就好，我们小辈也能
多学点有用的
【在 z****e 的大作中提到】
: 这种图
: http://upload.wikimedia.org/wikipedia/commons/f/fc/Rail_map_of_
: 你要构建一个从其中一个节点到另外一个节点的线路
: 你觉得容易么？
: 不需要太复杂
: 你就实现
: 要求输入任意两点，输出最短路径
: 就这么一个简单需求
: 够你的机器算半天了
|
n****6
发帖数: 570 | 24 路径算好cache就行了。允许用户家路径就行了。每次算路径太浪费时间。
【在 c****t 的大作中提到】
: 赵老师思路真是宽广。不过network optimization是operation research的领域。现在
: 实用中都是上数值逼近，要用commercial solver（大多core code都是FORTRAN写的）
: 。network规模大点的话是没办法做动态的。没数你这图有多少节点，不过现在最
: powerful的commercial solvers要解这个最短路径估计也差不多要10~20分钟。
: 另外您那些AI/ML的讨论不怎么靠谱。您几位编程大牛还是掐编程就好，我们小辈也能
: 多学点有用的
|
p***o
发帖数: 1252 | 25 还是先学学基本算法，至少得明白shortest path, min-cost flow, generalize
network flow的区别吧 ...
【在 c****t 的大作中提到】
: 赵老师思路真是宽广。不过network optimization是operation research的领域。现在
: 实用中都是上数值逼近，要用commercial solver（大多core code都是FORTRAN写的）
: 。network规模大点的话是没办法做动态的。没数你这图有多少节点，不过现在最
: powerful的commercial solvers要解这个最短路径估计也差不多要10~20分钟。
: 另外您那些AI/ML的讨论不怎么靠谱。您几位编程大牛还是掐编程就好，我们小辈也能
: 多学点有用的
|
d******e
发帖数: 2265 | 26 这位兄弟你不要来显眼了。
你说这个问题博士论文都写多少本了。
但是工业上也就近似解。
一般都是预先算好或者部分算好在存起来。计算时间真不是问题。
【在 z****e 的大作中提到】
: 这种图
: http://upload.wikimedia.org/wikipedia/commons/f/fc/Rail_map_of_
: 你要构建一个从其中一个节点到另外一个节点的线路
: 你觉得容易么？
: 不需要太复杂
: 你就实现
: 要求输入任意两点，输出最短路径
: 就这么一个简单需求
: 够你的机器算半天了
|
z****e
发帖数: 54598 | 27 你这种就是属于典型上下文不看就开始扯淡的
我现在不需要跟你说那么复杂
就假设你们做的cache都能成立
好吧
我告诉你，500w/s的数量级
就是最简单的hash都能算死你，让你直接崩掉
不信写出来试试，这里大概有50个车站，估计还不止
那来回就有50*49这里就大概2500个路径要存了
hash假设这里无碰撞，这个最理想了，不算难为你了
就是这样，我还是觉得500w/s是找死的节奏
也就是光查都不够
如果是一个cpu的话，基本上没戏，两个cpu就要处理死锁的问题
事实上这里动态路径一定存在
a->b->c->d->e
中间如果c->d段没票了，有人要买从a->e段的票
这个时候必须绕道，你怎么办？
这个时候就要近似解，这个时候就两种可能
当场算，或者再从一个cache中取，当场算500w/s不用说了，肯定死
从cache中取的话，那就不只2500个组合了，上5000个小意思
这里又有碰撞问题
我现在不需要说太复杂的东西，就是最简单的需求
500w/s，就撑不住了
【在 d******e 的大作中提到】
: 这位兄弟你不要来显眼了。
: 你说这个问题博士论文都写多少本了。
: 但是工业上也就近似解。
: 一般都是预先算好或者部分算好在存起来。计算时间真不是问题。
|
b******0
发帖数: 101 | 28 预先算好了存起来，听起来不错。可怎么知道哪条线有票呢？一条不行了再去看另一条
？一秒500w扛得住吗？ |
z****e
发帖数: 54598 | 29 你说的没有错
基本上是这个道理
所以动态生成路径基本上是没戏
我后来想了想，500w/s的压力
就是光查两个hash都不够
假设内存足够大
都不需要动态生成路径那么复杂
就是最简单的查找，500w/s也是要死的节奏
【在 c****t 的大作中提到】
: 赵老师思路真是宽广。不过network optimization是operation research的领域。现在
: 实用中都是上数值逼近，要用commercial solver（大多core code都是FORTRAN写的）
: 。network规模大点的话是没办法做动态的。没数你这图有多少节点，不过现在最
: powerful的commercial solvers要解这个最短路径估计也差不多要10~20分钟。
: 另外您那些AI/ML的讨论不怎么靠谱。您几位编程大牛还是掐编程就好，我们小辈也能
: 多学点有用的
|
b*******s
发帖数: 5216 | 30 这么直观的解都想不到，唉
也是个常数级的
【在 b******0 的大作中提到】
: 预先算好了存起来，听起来不错。可怎么知道哪条线有票呢？一条不行了再去看另一条
: ？一秒500w扛得住吗？
|
