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

lugionline

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

这个我可不同意

城市之间很可能不存在直通距离，比方我不知道上海 到 北京有没有*直通*的路径 （京沪高铁？）

lugionline

你去试下我上面提到的多阶段路径就知道了

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

可能数据少了看不出来，但是数据多的话...你全连通的100个节点可以很快算出来，但是上面这个例子可能根本算不出结果，

希望我没猜错

lastwinner

原帖由 rollingpig 于 11-4-10 21:31 发表
我倒是觉得公开出来的评分表应该可以更详尽一些。

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

事实上有限的时间内做出评判，很难做到完全的公平公正，但是我们已经努力去做到公平公正了
至于对于测试数据代码是否能正确运行出结果，这个大家自己去验证就行了

〇〇

原帖由 lugionline 于 2011-4-10 21:55 发表
你去试下我上面提到的多阶段路径就知道了

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

可能数据少了看不出来，但是数据多的话...你全连通的100个节点可以很快算出来，但是上面这个例子可能根本算不出结果，

希望我没猜错

类似http://www.itpub.net/thread-1414049-1-1.html
4楼的数据?

rollingpig

这个是太难了。
我是以网状来看的，而不是链状。

比如说，各大洲之间，以各大国城市，存在一个大网，这些基本全联通。这些城市就是主节点(A*)。

然后各国的大城市，可以看做二级节点(B*)。

然后是各国的小城市，可以看做三级节点(C*)。

C1-B1-A1-A2-B2-C2

这样的话，把probe level设为5,就基本能够构造出全联通。
当然，这样的话，probe 的性能本身就不好了。

原帖由 lugionline 于 2011-4-10 21:55 发表
你去试下我上面提到的多阶段路径就知道了

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

可能数据少了看不出来，但是数据多的话...你全连通的100个节点可以很快算出来，但是上面这个例子可能根本算不出结果，

希望我没猜错

rollingpig

你的理解是对的。

连通性较强时，递归with中的裁剪很有用。

加了routeprobe, 可以使本来不连通的，变成连通。根据给定的level,比如说，level 4 可以到不连通的三级，这种情况下，覆盖国内城市网，没有任何问题。覆盖州际网，效果会稍差。

但是，比起大家给出的现有算法来说，probe+递归with+裁剪已经是相当不错了。

原帖由 lugionline 于 2011-4-10 21:44 发表


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

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

不知道我的理解对不对

rollingpig

这个，就公路而言，就是G2 京沪高速啊

飞机就不用说了

原帖由 lugionline 于 2011-4-10 21:48 发表
你说 “但是加了动态裁剪，在直通最快的情况（这中情况在实际中最多）下：“

这个我可不同意

城市之间很可能不存在直通距离，比方我不知道上海 到 北京有没有*直通*的路径 （京沪高铁？）

rollingpig

呵呵~

原帖由 lastwinner 于 2011-4-10 22:30 发表


事实上有限的时间内做出评判，很难做到完全的公平公正，但是我们已经努力去做到公平公正了
至于对于测试数据代码是否能正确运行出结果，这个大家自己去验证就行了

rollingpig

我还有一个比较郁闷的地方，就是我考虑路网的复杂性，考虑的已经到3级城市了，所以把probe level设为了4,如果probe level 设为3, 在OO的性能测试中，将有很很好的表象。

rollingpig

用这里1-4楼的测试数据.

http://www.itpub.net/thread-1414049-1-1.html

	SQL3-7 model法	SQL3-32递归with	SQL3-13,level=3,递归+probe	标准解法递归+二分法
#1	0.4	<0.1	<0.1	<0.1
#2	3.7	0.3	0.4	0.4
#2-2	5.3	1.5	0.6	0.3
#2-3	5.3	>30	0.8	0.3
#3	0.4	<0.1	<0.1	<0.1
#4	5	0.1	>30	>30

可以这么分析：
Model 性能比较稳定，数据量跟性能基本呈线性
标准递归with, 不适合某种数据??
递归+probe 不适合纯链状数据。
二分法不适合链状数据

[ 本帖最后由 rollingpig 于 2011-4-11 09:40 编辑 ]