调和树标号算法

之前我不是做过优美树的标号算法么,最近因为这个东西做得没什么好的思路了,就换了个题目来做,就是调和树。

调和标号的定义比优美标号稍微复杂一些,因为我只做树的标号,所以在这里就只写一下在树上的定义。

对于一棵树T=(V,E),令n=Card(E),调和标号是一个满射f:V \rightarrow \{0,1,\ldots,n-1\},使得

g:E \rightarrow \{0,1,\ldots,n-1\}, \{v_1, v_2\} \mapsto f(v_1)+f(v_2) \mod n

是一个一一对应。

貌似是Graham和某人猜想所有树都是调和树(也就是说至少有一个调和标号),这个听说跟additive combinatorics有些什么关系,但是这个我不怎么管就是了。

然后这可以像优美树那样,用组合优化的方法来做。实际上在记载了目前最好的已发表结果(当然是指直接计算验证这个方向而不是理论推导的方向)的论文[1]中,的确也是这样做的。那篇论文用几乎同一个算法做了优美树和调和树的验证,优美树到27个顶点,调和树到26个顶点。

因为我之前优美树的那个算法做到了35个顶点(在一大帮志愿者的帮助下,谢谢你们!),所以我想同一个框架的算法应该对调和树也是有效的,也就是说先弄一个回溯的简单算法将容易的筛去,然后用局部搜索算法来解决剩下的。

实践证明没有想象中的那么有效。因为调和树标号的限制比较平均,不像优美树那样0和n一定要在一起,所以局部搜索和回溯的效率要低得多。我将回溯随机化了一下(优美树里边是没有随机化的),性能有些提升,但是也有限。

然后因为当时实习的时候,CT跟我讲过可以用constraint programming的方法来做做看,于是我就试着用CSP的方法来做。不过也有一点很麻烦的地方,就是变量之间会有联系,这样的话constraint propagation的效率就不高。为了解决这个问题,我尝试了一种混合的方法。因为对应于树叶的变量是相互比较独立的,可以做比较高效的constraint propagation,于是我就先用回溯的方法把内部节点都标好号,然后把叶子当前的constraint写出来,然后用一个比较简单的constraint propagation的方法(但是也有forward checking)来做这个CSP。

加了这个之后,貌似效果还是不错的,不过还是计算常数上的改变,貌似指数底数是没什么变化(总时间大约是O(3.75^n),对比之下,优美树是大约O(3.09^n))。不过基本上也是我目前能够做到的最好的了,再改进也可能只是常数上的了,因为在本质上貌似调和树就比优美树要难做些。我查了一下,貌似调和树是NPC,但是优美树还没有证明到底是不是NPC,这样的话调和树比优美树要难也是可以想象的。

现在我验证了不多于28个顶点的树都是调和树,在我的Core 2 Duo T7200上用了4天时间(一个核)。就已经超过以前的记录了。现在在算29个顶点的,按照上面的底数估算的话就大概要15天的CPU时间。

这次这个东西就不打算请志愿者帮忙了,先做一下,反正也没什么很大的重要性,暂时当作游戏吧~~~

为了吸引更多流量,稍微装一下13:

Recently I have proposed an algorithm that calculates a harmonious labelling of a given tree. This algorithm is a combination of a constraint satisfaction programming composant, a naïve backtracking procedure and a local search procedure. With this algorithm, I am able to check every tree with less than 28 nodes for harmonious labelling (took 4 days on a core of C2D T7200), which provides a limited verification of the conjecture of Graham and Sloan stating that every tree has a harmonious labelling.

This algorithm takes O(3.75^n) to find a harmonious labelling for all trees with n nodes. Therefore the empirical time complexity is exponential, which correspond to the fact that it is in NPC.

[1] Graceful and harmonious labellings of trees, REL Aldred, BD McKay – Bull. Inst. Combin. Appl, 1998 – Citeseer

Advertisements

4 thoughts on “调和树标号算法

  1. Pingback引用通告: All Trees with at most 30 vertices have a harmonious labelling | fwjmath的相空间

发表评论

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