(zz)“卤莽”软体升级,能更快的发现“对称”

matrix 发表于 2008年6月13日 14时35分 星期五
来自五次方程式部门

密歇根大学计算机科学家开发的一款开源软件(中文),能将寻找复杂方程式中对称的时间,从数日缩减为数秒。找寻对称是一种能突显通往答案捷径的方法。例如,验证火车时刻表的安全性、确认软件与硬件设计中的臭虫,或着加速一般搜寻任务。

名为saucy(卤莽)的软件由研究人员在2004年开发出来,它能加速基础计算机科学问题的解法,能迅速解答所谓的图自同构问题(graph automorphism problem)。当前软件升级增加了新算法,能更快的发现最短路径和对称。它将复杂方程式转换成图,并在顶点的排列中寻找相似性。在实验测试中,在不到0.5秒内,新软件在全世界路由器的网际网络连接图中捕捉到1083,687个不同的对称。图中的对称性意味着路由器可以被移来移去而不会改变(网络的)运作。在搜寻 Illinois州城市与乡镇之间公路网对称性的过程中,新的算法在0.5 秒内捕捉了104843个对称,而先前最强的演算法花了16分钟。

论文(PDF)

source: http://software.solidot.org/article.pl?sid=08/06/13/0641226

下载了论文来看~~~还是勉强看得明白的~~~算法的思路上还算自然~~~这个算法快的原因一个是面对稀疏图~~~这样的话同一个时间要考虑的结点数目就少了很多~~~另一个原因(据他们说是主要原因)就是观察到大多数图的自同构对称都只涉及到很少几个顶点~~~图的自同构对称置换可以构成一个置换群~~~称为Aut(G)~~~而他们观察到这个群可以由少数几个各自只涉及为数不多的顶点的置换生成出来~~~于是就有了他们的算法~~~

最近课上得差不多了~~~开始钻研图论~~~

Advertisements

2 thoughts on “(zz)“卤莽”软体升级,能更快的发现“对称”

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s