-
最近文章
近期评论
- [坑]POI补完计划#1 | qiancl 在 推箱子游戏的一个箱子推动路径搜索算法 (二) 上的评论
- [坑]POI补完计划#1 – qiancl 在 推箱子游戏的一个箱子推动路径搜索算法 上的评论
- HZF 在 推箱子是PSPACE完全问题 上的评论
- sokoban 在 马拉松简史 上的评论
- 跑步世界 在 马拉松简史 上的评论
文章归档
- 2021 年八月
- 2021 年五月
- 2021 年四月
- 2021 年二月
- 2021 年一月
- 2020 年十一月
- 2020 年十月
- 2020 年九月
- 2020 年八月
- 2020 年七月
- 2020 年四月
- 2020 年三月
- 2020 年一月
- 2019 年十二月
- 2019 年十一月
- 2019 年十月
- 2019 年八月
- 2019 年五月
- 2019 年四月
- 2019 年二月
- 2019 年一月
- 2018 年十月
- 2018 年七月
- 2018 年五月
- 2018 年四月
- 2018 年三月
- 2018 年一月
- 2017 年十二月
- 2017 年十一月
- 2017 年十月
- 2017 年九月
- 2017 年八月
- 2017 年七月
- 2017 年六月
- 2017 年五月
- 2017 年四月
- 2017 年三月
- 2017 年二月
- 2017 年一月
- 2016 年十二月
- 2016 年十一月
- 2016 年十月
- 2016 年九月
- 2016 年八月
- 2016 年七月
- 2016 年六月
- 2016 年五月
- 2016 年四月
- 2016 年三月
- 2016 年二月
- 2016 年一月
- 2015 年十二月
- 2015 年十一月
- 2015 年十月
- 2015 年八月
- 2015 年六月
- 2015 年五月
- 2015 年四月
- 2015 年三月
- 2015 年二月
- 2015 年一月
- 2014 年十二月
- 2014 年十一月
- 2014 年十月
- 2014 年九月
- 2014 年八月
- 2014 年七月
- 2014 年六月
- 2014 年五月
- 2014 年四月
- 2014 年三月
- 2014 年二月
- 2014 年一月
- 2013 年十二月
- 2013 年九月
- 2013 年七月
- 2013 年六月
- 2013 年四月
- 2013 年二月
- 2012 年十二月
- 2012 年十一月
- 2012 年十月
- 2012 年八月
- 2012 年七月
- 2012 年五月
- 2012 年四月
- 2012 年二月
- 2011 年十一月
- 2011 年九月
- 2011 年八月
- 2011 年七月
分类目录
博客链接
功能
月归档:十二月 2013
用深度优先搜索(DFS)确定图的割点
本文地址:http://sokoban.ws/blog/?p=1000 之前的博文《推箱子游戏的一个箱子推动路径搜索算法 (二)》介绍了图论中寻找割点的算法在推箱子路径搜索中的应用。但是对用DFS寻找割点的原理说得不够清楚明白,本文的目的是试图进一步阐明这个算法,并把示意图画的更漂亮一些。 用DFS遍历一个图的所有顶点时,按访问顺序依次标号为1到n,称之为DFS数。顶点v的DFS数记作D(v)。并得到一棵DFS树(黑色边),称DFS树的边为树边(tree edge),其余的边(红色边)称为回头边(back edge)。如下图,图的边都按搜索过程中向外的方向定向,得到一个有向图。树边都是从DFS数小的顶点指向大的,回头边都是从DFS数大的顶点指向小的。 根据上面由深度优先搜索得到的有向图中,可定义每个顶点的低位数(lowpoint):从该顶点出发,只用最多一条回头边,沿有向边能走到的顶点中DFS数最小值。顶点v的低位数记为L(v)。 低位数取值有两种情况:一是没用上回头边,则能走到的DFS数最小的的顶点就是该点自身,对应的路是一个顶点构成的平凡的路。此时L(v)=D(v)。二是用了回头边,则一定是最后一条边是回头边,走到一个DFS数更小的顶点。此时L(v)<=D(v)。 所以,一般地,总有L(v)<=D(v)。 有了这两个参数,就可以确定割点了:对根节点,即DFS数为1的顶点,其为割点当且仅当在DFS树中有两个或以上子节点;其余所有非根节点v是割点的充分必要条件是:v存在一个子节点u(在DFS树中的子节点)满足u的低位数大于等于v的DFS数,即L(u)>=D(v)。 下图标出的顶点的低位数(圈外数字,没标圈外数字的顶点低位数和DFS数相等),绿色顶点为割点。 注:若用 DFS的深度(depth)来替代上面算法中的DFS数,并用深度来计算低位数,则算法一样能有效地找出割点。 [参考文献] 1. Shimon Even, Graph Algorithms (2nd Edition). Cambridge University Press. 2012. p52-54 [文中的图使用http://draw.io制作]
再谈桌面操作系统
本文地址:http://sokoban.ws/blog/?p=984 在 上篇博文谈了以Ubuntu作为常用操作系统三年的体会。还不到半年,现在又变成使用Mac OS X和Windows 7更多了。 主要原因是过去三个月,软硬件使用有下面改变: 一、以前在Ubuntu上为佳能喷墨打印机安装驱动一直未成功。在Mac OS X上系统轻松自动安装驱动。 二、重拾慢跑习惯,买了新GPS手表Nike+ Sportwatch GPS记录跑步路径、步伐和心率等。而这手表只提供Mac和Win下的软件上传手表数据至Nike+网站社区。其它如Garmin 610等手表官方均只提供Mac和Win下管理软件。 据说有第三方程序可在Linux下提取手表数据。 三、买了计步腕带Fitbit Flex,和GPS手表的目的一样,是为了提醒自己少坐多动。据其统计数字,一般15分钟内步行1300步,慢跑则2500步。这玩意同样只提供了Mac和Win的数据上传软件。 四、买了个TomTom便携式导航仪,可每季度免费升级地图,但依然只提供Mac和Win的升级管理程序。 五、买星特朗天文望远镜送TheSkyX天文软件,可在Mac或Win下安装。当然 Linux下亦有功能相仿的自由软件。 六、虽LibreOffice可满足我几乎所有工作上的文档处理需求,但为方便和同事协同工作,还是买了微软的Office 365,可安装到5台Mac或Win电脑上。