respiratory tract infection or just a flu , never know what happens to me . suffering for days , i do not feel any better .
i have no idea about the situation now . but the germs [or viruses] seem to stop spreading .
how worse can it be ? my lungs may be still ok , but my throat is not so good . in fact , i can hardly say anything for my sore throat , and breath is also a difficult thing for me .
may it be H5N1 or H1N1..smiling , surely i will be fine .
2009/05/09
2009/05/02
信息学奥赛中的最短路算法
凌晨 用了2个小时写了明天讲课的内容提纲.
其实也不算是讲课了...只是把了解的内容整理出来读出来..
其实也不算是明天了..就几个小时以后..睡觉去也~
以下是我写了半天的文档 贻笑大方了
信息学奥赛中的最短路算法
CPY
[写在前面]
最短路算法,是指一类在带权图G=[V,E]中求点对之间最小权值和的路径的算法,是图论算法的重要组成部分.同时由于它与实际问题有着紧密的联系,所以有着广泛的应用.今天我来略讲一下最短路算法.
另外,考虑到竞赛考点的偏向性,本文所讲解的算法,事实上是求最短路的边权和,而要求出这条路径,只须在现有算法基础上略微修改即可实现,不赘述.
[0.预备知识]
[0.1.最优子结构性质]
设P1n是图G=[V,E]中点V1到点Vn的最短路,点Vi与Vj在P1n上,则P1n在点Vi与Vj之间的部分Pij是点Vi与Vj之间的最短路.
[0.2.松弛操作]
设d'[v]是源s到点v之间最短路径的权值上界,对于满足d'[v]>d[u]+w[u,v]的边E[u,v],定义一次松弛操作为d'[v]<--d[u]+w[u,v]的赋值.
下面介绍的Dijkstra算法和Bellman-Ford算法都是建立在松弛的基础上的算法.
[1.SSSP-Single Source Shortest Path 单源最短路]
[1.1.Dijkstra算法]
[1.1.1.算法实现]
令d'[v]=min{d[u]+w[u,v]},每次找出一个使d'[i]最小的点i,令d[i]=d'[i],即求得到源s到i的最短路长度.然后对对于所有以i为起点的边进行松弛操作.将此过程重复n次,就可以得到源s到所有点的最短路长度.
[1.1.2.正确性证明]
由读者完成.
[1.1.3.伪代码]
procedure Dijkstra(Graph,Source)
begin
dis[]<--inf
dis[Source]<--0
queue[]<--Graph-[Source]
while size(queue)<>0 do
begin
for i in queue do
if dis[i]
v<--i
queue<--queue-[v]
for i in queue do
relax(e(v,i))
end
end
[1.1.4.时间复杂度分析与优化]
分析算法可知,朴素的Dijkstra的时间复杂度为O[V^2].在稀疏图中可用二叉堆来存储队列queue,得到O[(V+E)logV]的复杂度.而改用Fibonacci堆存储,可得到O[VlogV+E]的复杂度.但由于Fibonacci堆的实现过于繁琐,所以在竞赛中通常不被使用.
[1.2.Bellman-Ford算法]
[1.2.1.算法实现]
初始时源点d值为0,其余点d值为无穷大.进行V次操作,每次对每条边进行松弛.
[1.2.2.正确性证明]
由读者完成.
[1.2.3.伪代码]
procedure Bellman_Ford(Graph,Source)
begin
dis[]<--inf
dis[Source]<--0
for v do
for e(u,v) do
relax(e(u,v))
end
[1.2.4.时间复杂度分析与优化]
分析知算法复杂度是O[VE].然而实际问题中,通常不需要进行全部V次操作就可得出解,针对此现象,可在每次操作后判断是否在松弛时有赋值操作,若无,可终止算法.这样优化后,复杂度的数学期望可以达到O[ElogV].
[1.3.SPFA-Shortest Path Faster Algorithm]
[1.3.0.简短的说明]
SPFA是Bellman-Ford算法的一种队列实现,优点是减少冗余计算.这里把它作为一种独立的算法提出来讲,
[1.3.1.算法实现]
维护一个队列.初始时队列唯一元素是源点.每次取出队首元素,并松弛以该点为起点的边,将松弛成功的边的终点加入队列.队列为空时算法结束.
[1.3.2.正确性证明]
由读者完成.
[1.3.3.伪代码]
procedure SPFA(Graph,Source)
begin
queue<-[Source]
while size(queue)<>0 do
for i in Graph do
begin
relax(e(queue[start],i))
if relaxed then
queue<-queue+[i]
end
end
[1.3.4.时间复杂度分析]
理论计算表明,SPFA的时间复杂度为O[kE],其中k的数学期望为2.
[1.4.关于以上几种算法]
[1.4.1.小结]
我们已经介绍了求解单源最短路问题的常见算法,现在是一些总结.
由于模型满足最优性原理,上述算法都采用了标号法.标号法是一种优秀的编程思想,在很多类型的问题中都有应用.根据标号的特点可将其分为两种类型.
其一,标号设定算法.在算法的执行过程中不断把临时标号变成永久标号.例如Dijkstra算法.
其二,标号修正算法.算法是迭代的,标号总是临时的.算法思想是不断逼近最优解,只有当算法结束时才能确定想要的结果.例如Bellman-Ford算法.
标号修正算法由于要考虑终止条件与迭代次数,效率通常不如标号设定算法高,也不易被初学者掌握,但它的求解范围通常更广.
[1.4.2.思考]
[1.4.2.1]完成以上两种算法的[正确性证明]
[1.4.2.2]为什么Dijkstra算法不可以处理带有负权边的图?为什么Bellman-Ford算法可以?
[1.4.2.3]对于带有负权回路的图,Bellman-Ford算法该怎样判断?
[1.4.3.可用单源最短路算法求解的问题变体]
[1.4.3.1.单目标最短路问题]将图中的边全部反向,然后求解单源最短路问题.
[1.4.3.2.两点间最短路问题]求解单源最短路问题.目前还未发现比此更优的算法.
[1.4.3.3.所有点对间最短路问题]以每一个点为源,依次求解单源最短路问题.
[2.APSP-All Pairs Shortest Path 多源最短路]
[2.1.Floyd-Warshall算法]
[2.1.0.简介]
考虑最短路的最优子结构性质.设d[i,j,k]是点ij间在点集[1..k]内的最短路长度,那么显然有状态转移方程d[i,j,k]=min(d[i,k,k-1]+d[k,j,k-1],d[i,j,k-1]),边界条件是d[i,j,0]=w(i,j).由于在计算时k是递增的,所以可以忽略第三个维度.这是一种基于动态规划的最短路算法.
[2.1.1.算法实现]
初始时d[i,j]=w(i,j).枚举k,对所有点对ij,检查并更新d[i,j]的值.
[2.1.2.伪代码]
procedure Floyd-Warshall
begin
d[]<--inf
for e(i,j) do
d[i,j]=w(i,j)
for k=1->n do
for i=1->n do
for j=1->n do
d[i,j]=min{d[i,j],d[i,k]+d[k,j]}
end
[2.1.3.时间复杂度分析]
显然算法复杂度为O[V^3]
[2.2.Johnson算法]
[2.2.1.坦白]
据说这算法不是特难,我也很久前就听说过,不过一直没有研究.
目前在竞赛范围内很少有Johnson算法的应用.由于算法实现所需的代码量大,且耗时的优化程度不明显,Johnson算法通常可用Floyd-Warshall算法代替.
这个我没写过.读了wiki的介绍略懂,大概能实现出来,然而还没有熟悉到可以讲出来的程度.所以这算法不讲了....
若有读者对此有兴趣,请参阅wiki上对其的介绍http://en.wikipedia.org/wiki/Johnson's_algorithm
[3.习题]
USACO train Chapter 1 Section 2.4 的5道题目
[4.参考文献]
算法艺术与信息学奥赛 刘汝佳 黄亮 Page304-314
TEXT Shortest Paths USACO Chapter 1 Section 2.4
2009/05/01
Reply to Aquarhead
在给某洵前些天的帖子写回复 搞笑的是写了半天 submit后的提示是[Failed to add your comment].
汗颜 那天晚上跟你白说了 生物行为实质上是原子行为 一切宏观物理行为都是粒子行为 那么经典物理中 给出一个系统中所有粒子的状态 以及它们之间作用规律 就可以计算出任意delta t之后的系统状态 当然 这要求一个强大的处理能力 比如云计算 呵呵
原因未知 反正我网络正常 只是写得稍长些么 WP的评论也没有字数限制啊
-_-||.
懒得找地方存 扔在下面了.
但事实上没必要计算 只要当前存在这样一个确定的系统状态 那么任意delta t之后的系统状态就是确定的 因此一切都有了确定的状态和状态转移方向
两个星期前我和某女分手 现在我熬夜给你留言 1g1g.com正在随机播放的是周传雄的向北飞 七个月之后某洵被上海交大保送录取[复旦保送只限上海和浙江..] 这些这些 就都是被注定了的
换句话说 这世界是宿命论的具体体现 一切行为 都只是在完成被期待要完成的 挺像TheMatrix里面Oracle对Neo所说的对Choice的解释
问题是有个东西叫量子力学 其中有个东西叫不确定性原理 说的是一个物体的动量和位置不确定度的乘积是个定值 换句话说 这2个物理量不可能同时以很小的误差值来确定
那么回到上面说的理论 不过这回 无法确定一个系统当前的状态 也无法确定任意delta t之后的系统状态 那么理论基础没了 什么都没了 呵呵
话说我曾经提出上面的<确定性>理论 后来对量子力学略懂之后 就有了上一段的补充[也就是对原理论的推翻..] 然而我疯狂地研究了好久量子力学以后 并没有从思考中获得哪怕是一点进一步的结论 也就是说 我并未懂得什么>_<
待以后再说吧..Feynman物理学讲义就快读完第一卷了 该继续读下去呢 还是re读呢
2009/04/27
2009/04/20
2009/04/14
2009/04/09
2009/04/02
元素周期表与编码
无聊的化学课.突然就想起了M67提到过的用元素周期表实现编码的那作文.话说我初中也玩过类似的,不过当时是用的元素名称的汉字~
反正无聊,顺手写了几个常用的字符串的编码,录如下.
我的邮箱名
Assassin.cpy.pku
As S As Si N C P Y P K U
33 16 33 14 7 6 15 39 15 19 92
某2男的名字
Yuanzhe[Yizer] Huguang
Yzr Hg
Y Zr Hg
39 40 80
不过某楼貌似就没对应的元素了- -|
可爱的蓝色单词
Accept
Ac Ce Pt
89 58 78
不过没有Google,没有Ubuntu,没有Matrix,没有ACMilan...
顺便,没有J啊..郁闷.喜欢的女孩子的名字打不出来了....
订阅：
博文 (Atom)
