“盛拓传媒杯”SQL数据库编程大赛第三期评分及所有参赛选手答题公布！

rollingpig

不应当大于 应该是笔误，其实是： 应当不大于


比如说，

已知北京-上海直通2000KM

那么如果过程中有北京-徐州-上海 = 2100, 那么，这个路径事先可以排除。

原帖由 lugionline 于 2011-4-10 16:12 发表



我没空看所有oracle的解答，你问裁剪说的是几号，那就按你标准答案里的第一个解法来说好了，请问这个解法最后计算表中的数据量是多少级别的（均摊后）？

那么 SQL3_1的解答中到底处理了多少数据？为什么构造全路径的反而更好呢？

另外我随便找了个答案，比方 SQL3-32，我是看不懂oracle, 其中这段：
       and  instr(t.path ,'/'||a.arrive||'/') =0  --新终点不应当再已过路径中
       left join a ta --如果原路径终点 = 新路径起点 ,新产生的路径不应当大于 已知最短路径
       on        t.arrive =  a.depart
             and t.depart = ta.depart
             and a.arrive = ta.arrive
             and t.distance + a.distance  >= ta.distance                    

这个 “新产生的路径不应当大于 已知最短路径”
          “and t.distance + a.distance  >= ta.distance”

到底是 应当大于？不应当大于？ ta不是基本路径么？而且这个过滤有什么用？

请问为什么这个答案叫做“使用递归with，注释详尽”，而SQL3_1据说注释都能扣好多分，我比了下两个脚本，好像注释也没什么差别呢？

lugionline

原帖由 rollingpig 于 2011-4-10 18:17 发表
不应当大于 应该是笔误，其实是： 应当不大于


比如说，

已知北京-上海直通2000KM

那么如果过程中有北京-徐州-上海 = 2100, 那么，这个路径事先可以排除。

但是代码中的意思是什么？是应当不大于吗？ 我怎么看好像是 新构造的路径 要 大于等于 基本路径？不懂Oracle哦，但是ta表好像是基本路径啊

如果是这样，那么代码是不是错了，比方 a-b 1000, a-c-b 900 这种情况？

另外你的脚本是不是3-13？你的本质还是构造所有路径的方法啊，只是对路径做了预处理，比直接构造好，和我的做法还是有区别的

rollingpig

先说
3-32吧。

你看到了

left join a ta --如果原路径终点 = 新路径起点 ,新产生的路径不应当大于 已知最短路径
       on        t.arrive =  a.depart
             and t.depart = ta.depart
             and a.arrive = ta.arrive
             and t.distance + a.distance  >= ta.distance

后面还有一句

      where ta.depart is null and tb.depart is null

left join 然后被join的table的值是 null, 相当于not exists 或者 not in 的逻辑。

我的的确是3-13. 不清楚你的解法是哪个？

rollingpig

另外，说到分隔符，因为题目中已经限定场景，基本可以认为是中国的城市，所以城市名中不可能出现/\'等符号，所以用这些符号作为分隔符不会被扣分，而如果需要有分隔符而没使用分隔符，则会被认为是考虑不周全而扣分。
但是，如果代码中巧妙的绕过分隔符限制，可以作为加分项。

--仅代表个人意见

rollingpig

再说到算法。

评委在考虑的时候首先考虑是不是能正确得到最短路径，包括分隔符，多次换乘等。

然后考虑的是性能，如果都能得到正确答案，那么，跑得快的就可以认为是好的算法。

最后就是可读性和扩展性

当然，还有就是所谓的“妙处”，就是很巧妙的应用了很少有人用到的代码，而达到目的。

--仅代表个人意见

lugionline

原帖由 rollingpig 于 2011-4-10 19:22 发表
先说
3-32吧。

你看到了

left join a ta --如果原路径终点 = 新路径起点 ,新产生的路径不应当大于 已知最短路径
       on        t.arrive =  a.depart
             and t.depart = ta.depart
             and a.arrive = ta.arrive
             and t.distance + a.distance  >= ta.distance

后面还有一句

      where ta.depart is null and tb.depart is null

left join 然后被join的table的值是 null, 相当于not exists 或者 not in 的逻辑。

我的的确是3-13. 不清楚你的解法是哪个？

哦，那这个代码是没有错的。

我的是3-1，我现在明白为什么你在全连通图中这么快了，因为这种情况下你的routesprobe已经基本上包括了所有点对间的最佳路径了。但是很多时候往往是点和点之间不存在直接的路径，或者是3层之内不存在直接路径，比方多阶段的路径,这时候
  AND        NOT EXISTS (--距离不比之前算过的最佳路径长

这个过滤每次都会失败，应此后面构造的路径数量仍然会按指数级别递增

你可以考虑下这种情况

a1, a2, a3, a4 和 b1, b2, b3, b4 之间有路径
b1, b2, b3, b4 和 c1, c2, c3, c4 之间有路径
。。。
y1, y2, y3, y4 和 z1, z2, z3, z4 之间有路径

这时 allpathprobe 中很多节点的距离数据基本上不存在

lugionline

所以说本质上你的方法和3-32或者和标准解法的第一种是一样的，改变不了路径数量按指数级别增长的命运，我看不出这些按路径构造的方法到底快哪里了？

当然那个floyd的算法除外，那个本质上也是N^3的算法。

这个题目要快还是要用bellman,但是我想不出用一个SQL来实现

rollingpig

我的本质和3-32是一样的，和标准解法的第二种是一样的。

但是这并不是就等于全构造，因为中间多了动态剪裁，就是刚才说的那段代码。

1. 
   
2. 
   
3. 
   
4. left join a ta --如果原路径终点 = 新路径起点 ,新产生的路径不应当大于 已知最短路径
   
5.        on        t.arrive =  a.depart
   
6.              and t.depart = ta.depart
   
7.              and a.arrive = ta.arrive
   
8.              and t.distance + a.distance  >= ta.distance
   
9.       where ta.depart is null and tb.depart is null
   

复制代码

以最简单的例子来解释：

北京
上海
徐州
广州
4个城市全连通，

全路径是
Level 1 : 4*3  =12
Level 2 : 4*3*2 = 24
Level 3 : 4*3*2*1 = 24

Total : 60



但是加了动态裁剪，在直通最快的情况（这中情况在实际中最多）下：

Level 1还是一样：4*3 = 12
Level 2没了，因为所有的有换乘情况的距离都大于等于直通。

这样，速度就快了5倍。

而且，如果全连同的城市越多，这个倍数就越大。

所以，并不是说11g的递归就一定好，它好就好在能够进行动态裁剪，从而提高性能，使相关算法成为一个好算法.

当然，我的写法其实多了两样东西：
第一个就是用city_id代替city_name进行运算，完全摆脱city_name的形式束缚。
第二个就是多了先计算特定Level内的最佳路径，从而降低后面可能的运算量，这个在理想的“直通最快”的时候效果不明显，但是在“直通不最快”大量出现的时候，效果就特别明显。

原帖由 lugionline 于 2011-4-10 20:31 发表
所以说本质上你的方法和3-32或者和标准解法的第一种是一样的，改变不了路径数量按指数级别增长的命运，我看不出这些按路径构造的方法到底快哪里了？

当然那个floyd的算法除外，那个本质上也是N^3的算法。

这个题目要快还是要用bellman,但是我想不出用一个SQL来实现

[ 本帖最后由 rollingpig 于 2011-4-10 21:08 编辑 ]

rollingpig

我倒是觉得公开出来的评分表应该可以更详尽一些。

比如说，包括各个方面的得分，包括在OO各种情况下的性能数据，在LW给出的各种情况的是否成功等。

lugionline

原帖由 rollingpig 于 2011-4-10 21:07 发表
我的本质和3-32是一样的，和标准解法的第二种是一样的。

但是这并不是就等于全构造，因为中间多了动态剪裁，就是刚才说的那段代码。

你的意思我明白，但是你这个是动态剪裁吗？probe的数据是一次性构造的，在后面的计算过程中是不会变化的，只要后面能被改进的记录越多，那么你每次计算出来的结果集就越大，而且这个是以指数级别增长的 （虽然你构造时多计算了几步，这个结果比直接用routing表要好）

比方有一对节点 A, B 不出现在你初始的probe中，那么A到B之间的路径都可能出现在你最终的结果表中,因为你的裁剪每次都会失败

不知道我的理解对不对