最近朋友跟我讨论了一个类型的旅行商问题。原版的旅行商问题是说，给定一个图，给定起点和终点，求不重复经过任何节点的最短路径，遍历全部节点。而他的问题是，仍然不许重复经过任何节点，但是不要求路径遍历全部节点，而是遍历某一个给定的关键点集，求最短路径。问题里面对图没有做任何限制，图可能包含数千节点，不过关键点集是充分小的，比如只有5个关键点，这样。

一开始我没听清楚题目，以为这个问题跟斯坦纳树有什么关系。（所以才会写了上面一篇note。。）不过后来知道不许重复经过节点，那么这种想法就没有用了。

不过既然关键点集充分小，求的又是路径，那么几个关键点必然只能依次经过。可以尝试所有关键点的排列，依次求最短路径。比如说5个关键点，也只需要算120次。还算可以接受吧。并且假如采取分支定界，其实还是可以减去很多分支的。当然可以构造出几个关键点无论怎么排列，路径都等长的情况。比如所有两两点间都有路径长度为1的任何图，都是这样。。。不过假如是工程上使用的话，可能还有其他办法可以提前退出，比如求出“足够好”的解，或者算了很长时间，一直没有找到更好的解，之类的。。这个就可以根据需求而定了。

不过朋友比较担心的是割点的问题。割点是说，一旦去掉这个点，则图会被拆成两个独立的联通分量。就是说从图的某些点出发，永远也无法到达图的另外一些点了。。之所以担心这类点，是怕一旦算法的前面走过了这类点，那么由于存在不许重复任何节点的限制，可能导致某些点无法经过了。那么这个割点至少有两种情况。就是这个割点会导致关键点被割掉，或者只会导致非关键点被割掉。

导致非关键点被割掉的那种割点，可以直接收缩为一个点。因为题目并不要求遍历非关键点。并且求出的路径绝不可能进到那个割点后面去（因为1.里面没有关键点，2. 进去就出不来了）。那么至于说会导致关键点被割掉的情况呢？暂且也把他收缩为一个点吧。如果不断这样收缩，整个图就会最终退化为不含割点的图。并且最后一次收缩的割点应该不会超过两个。假如超过两个，那么这个图是无解的。因为总有一些关键点，你要经过一个割点才能进去，然后就出不来了。至于不超过两个，那是说起点和终点可以从割点经过。当然这个是欧拉说的啦。。

比如上面的图，每个椭圆表示里面有一坨点，并且里面的每个点都至少有两个入度。假如上图的三个小椭圆里面都有关键点，那么这个题就无解了。假如任何一个小椭圆里面没有关键点，那么就可以直接去掉。

最后肯定只有不超过两个小椭圆里面是有关键点的。比如上图的红色椭圆。可以暂时收缩成一个点。

所以最后一次收缩的割点，不会超过两个。

那么其实这种收缩可以重复进行，于是可以写出递归代码来解。当然现在问题就转化成，对于没有割点的情况，怎么解这个问题。

当然其实问题的难点，也正是在没有割点的情况下吧。。还是继续前面那种遍历所有关键点顺序的那个思路，这回每次需要考虑的关键点都变少了（好吧也可能没变少，至少不会变多！！）。接下来的事情可以参考旅行商问题的一般解法来求吧。。因为不是我的题目，所以没有继续去查。。同样是做个记录留下来吧。。还是方便以后捡回来。。

大三的时候做了一道斯坦纳树的题，最近几天朋友跟我讨论某个问题，忽然觉得跟那时候的做法很类似，结果发现自己没有留下任何材料。想了半天把那时候的想法回忆起来了。当时没有留记录是因为想法太简单，算法性能太差。不过现在想想无论好坏，啥想法都应该记下来，以后至少可以在这个基础上继续走。

Steiner Tree, 就是说给定一个图，和他的节点的一个子集。求包含该子集内所有节点的最小生成树（不要求包含全图的所有节点）。其实是算法老师留的作业，那时候也没当回事周末随便写了点。结果发现这个居然是一个NPC问题。只好临时想了一种解法。还是沿着prim算法的思路走，每次向已生成好的树里面增加一个新节点。只不过这次，每次都只增加关节节点集里面的节点。而寻找节点的时候，需要用Dijkstra算法。并且找到需要加入的关键点后，也需要把路径上的其他非关键点也加入进正在生成的树上面去。说到Dijkstra算法，复杂度是n^2, 再加上prim算法复杂度也是n^2，复杂度岂不是到达n^4？其实没有。因为每次使用Dijkstra算法，都把某一个点到其他所有点的路径长度都求出来了。而最终的结果，最坏也不过把所有节点两两之间的最短路径求出来，相当于填了一张n×n的表，n是节点数量。用一次Dijkstra算法可以填一行。总共n行所以复杂度是n^3。恩这里算是用到了动态规划。性能还算是可以接受吧。不过这个算法明显求不出精确解。我也没有证明过他求出的解究竟能多逼近，或者在哪些条件下能求出足够逼近的解。只不过是当时老师给的样例输入正好碰上是返回正确结果，就这样交卷了。

恩后来又在网上查了很多资料，貌似斯坦纳树研究的人还是很多的。不过搜到的资料大多是些没法下载的论文。。。所以也就荒废了没有继续看下去。。今后有机会在继续看吧。这次只是把过去的思路记录一下以后方便捡起来。

因为经济的原因，协作开发一直是仅做源代码管理，由开发者checkout代码后自行编译。

但在有大笔资源的情况下，时效应该是更为重要的东西，为什么不考虑二进制管理？

在公司，一个项目编译出来需要3到5个小时。。(会跑来这里写东西的原因也说出来了。。)。。反正提交代码之前每个人都必须做build, 做测试，然后才能提交的，为啥不一开始就把大家build的结果保留下来，需要用的人自取呢？

这正好可以跟系统每天的daily-build和test-suite结合起来，一起完成。

开发过程还是一样，checkout, update，之后提交。但这个时候提交的内容不要直接进main branch. 先在他checkout的版本基础上，patch上他的update，之后做buddy-build和test-suite。如不通过，打回重练。这个过程可以以天或者以周为单位。以天为例吧。每天晚上12点，系统尝试将通过测试的patch进行合并。如果合并失败的话，就把导致合并失败的patch拿掉，直至合并成功为止。如果成功合并，进main branch, 并且做daily-build和test-suite。假如合并之后导致新的bug或build break产生，应该知道这些问题是协作造成的，将受影响的文件或模块相关的patch除去，重新build-test。直至没有bug产生为止。次日早晨发邮件给没进main branch的patch的owner们，让他们解决问题。

关键在于编译。在编译脚本里面可以加上新的机制，允许从服务器下载跟本地版本相符的obj,lib,dll,exe等内容。即编译器需要和源代码管理器协作，确定即将编译的一段代码是否被edit过。如果没有被edit过，检查目前版本的代码在服务器上是否有相应的二进制目标文件。如果有就可以直接下载，如果没有才考虑自己编译。这个过程跟编译顺序相反，是自顶向下，从最终目标开始比较，尽可能下载整个的lib，dll之类，这样就可以避免下载很多可能本地根本用不到的obj文件。

当然，由于二进制文件没有有效的增量备份算法，在服务器上不可能保存所有版本的二进制文件。但至少可以保存最近几天或几周的版本的，还有历史上的几个milestone版本的。

当然在这种机制下必须要求所有人都在最新版本下工作，否则必须新开branch。每天的patch都只能接受从当天版本号基础上checkin。如果有旧版本的patch提交，可以有两种选择，一种是要求开发者更新到最新，然后重新提交patch,另一种是要求开发者开新branch, 并在新branch上做开发。具体选择哪一种看具体需求以及开branch的成本了。

毕竟当项目变大，每个人要处理的模块都是很小的一部分，其余的部分只需要lib,dll就可以了，没有必要自己编译。并且，如果不需要编译，其实开发人员的机器配置就没有必要那么高，节省的成本可以做更好的服务器机器。其实这种策略也更符合所谓“云计算”。当然更加有趣的是，可以让编译本来就发生在由所有客户机结成的计算网格上面。并且所有的二进制文件也都分布式存储在这些分散的机器上面。服务器仅仅是一台或几台管理信号的中转路由。这样做可能可以进一步降低成本，并且对于每个计算网格而言，本地编译某个模块，然后二进制文件就存储在本地，也没有太多网络开销。当然具体算法如何实现，这个恐怕要仔细研究了。（研究生课题？:）

记后记：本文纯属个人心灵探索…观点纯属个人愚见，没有妄加评论别人或者妄图要求别人按照自己想法去做的任何意图…

最近跟几个同学聊天。。都碰上了牛人这个话题。。

先是在buzz上不小心跟不认识的学弟言语冲突。。之后又跟人聊天时对牛人产生了鄙视情绪。。

虚荣心。。虚荣心在做怪。。

膜拜牛人是一种病。当然，有些牛人是不得不拜的。他们达到了神的境界。但是我现在已经堕落到见牛就拜的程度了…承认一个人很牛，表示自己对自己达到他的实力缺乏信心，如果仅是没有胆量或者方向不同（比如程序员崇拜一个诗人）还情有可原，否则其实一种惰性。是的，他很强，我比不上他，我认输。表面上看着很谦虚很大度。其实仅仅是懒惰而逃避罢了。

但是反过来讲，否认牛人，装出一副鄙视全世界的样子，一样是病。“切，那算什么”。其实自己根本做不到。这纯粹就是装B。。。

应该对牛人抱有什么样的态度呢。。应该是对对手的尊敬。要敢于挑战，也要勇于认输。但是认输不是服输。“我早晚要超越你”。

牛人有很多种类。有些牛人确实是牛。他们有伟大的想法，他们创造了奇迹，他们构造了整个世界赖以生存的基础，他们的贡献使每个人受益。对这些牛人，我们深深的膜拜。

但并非所有的牛人都是这样。很多牛人并非是看起来那么牛。之所以如此，是因为人们看到了他的成绩和辉煌，却没有看到他们达成成绩的过程。过程是艰辛的。假如你看到他达到辉煌的困苦历程，你对他的态度不会是崇拜，而会是尊敬。就像魔术，你不知道原理的时候，以为是超自然力，或者魔法，或者什么不可思议的奇迹创造了这一切。你别无选择，对魔术师产生了深深的崇拜，以为他们无所不能。但当你看到他们练习魔术的艰苦，设计魔术的苦思冥想，以及了解了魔术实现的原理，你或许不再崇拜他。他从神坛上走下，他是人。但你仍然保有对他的尊敬，因为他的智慧和勤奋。

然而魔术师不会告诉你魔术的背后。当然这没有错。因为他们依靠这种信息不平等造就的魔力吸引观众。这是他们的职业。

某些种类的牛人也是一样。他们强大，可他们的背后有艰辛，有运气，还有别人的帮助。假如你知道他是怎么做的，并且你付出跟他相同的努力和代价，或许（这要看运气）也能达到他的程度。等你知道这一切，你不再把他当作膜拜的对象，而是敬佩他的付出和代价。

甚至还有一类牛人，他们的牛完全是装出来的。他们采取别人听不懂的措辞，他们故作高深。他们深居简出，不让别人看到他们。于是别人以为他们高深莫测，就认为他们是牛人。（在此强调，并非所有深居简出的牛人都是装牛。。而是说某些种类的装牛会采取此策略。。）对于这类牛，尊重他们装牛的选择，既不鸡肚他们不费什么力就得到牛人的光环，也不非要让他们下不了台，以此为乐，那就对了。因为鸡肚是源于自己的惰性（“如果我像他那样省力讨好该多好”），而扯破面皮则是自己的虚荣心在做怪了（“凭什么我不如他”）。

之前说了句，觉得真正的牛人应该是傻乎乎的那种类型。这是电影看多了吧。。不过我的话，确实是欣赏那些不摆架子，不故弄玄虚的牛人。他们会在自己力所能及的范围内帮你（他们强大的力所能及啊。。），甚至热心的授之以渔，但超出他们的范围的时候他们简单的道歉，并且告诉你解决问题的途径（某个领域专家，图书馆或网络，继续练习和吸取经验，或者只是简单的不可能）。而不是在力所能及的时候卖弄炫耀，在力所不及的时候故弄玄虚。

至于我自己。我承认自己虚荣心重得搬不动。。被人哄一句牛人就轻飘飘了。。说不定他还是冷嘲热讽我都没听出来。。举世誉之而不加劝，举世毁之而不加沮。。这确实很难做到啊。。被人哄也没啥可高兴的，被人讽也没啥可不高兴的。总归自说自话自做自事就对了。

有的时候在想，为什么我这么争强好胜，为什么对“牛人”这个话题这么敏感。我努力学习，努力工作，是不是只是为了让大家觉得我很牛，尊敬我，甚至崇拜我呢。我是不是故意把自己光彩的一面给人看，而藏起自己的窘状和搓态呢。这就是在装逼啊。。。包括我在写这篇博客，都是在掩饰自己的虚荣心啊。不是吗。这篇博，不就是因为自己对“牛人”这个词敏感了，虚荣了，鄙视了，才写出来的吗。。

不能这个样子。。。

学习，工作。是为了什么呢？

付出。

绝对是付出。

这个问题想了好久了。人要吃饭。人要穿衣。人要体面，人要虚荣。但仅仅是为了要这些东西而活着吗。那人跟怪兽有什么区别。[人形怪兽出没注意]

吃饭穿衣是为了活着。活着是为了付出。体面虚荣，游戏音乐，是为了高品质的活着。高品质的活着是为了高品质的付出。归根结底，人是为了付出而活着的。

一定是这样。[我无法证明这一点诶。。摊手]

真正的牛人不是别人怎么看待他，而是他付出的数量和品质。

我不是牛人[因为还没付出过啥]，也不想[不应该想]当牛人[是指受人追捧的那类气场型牛人]。但是我要尽力付出更多。为了这个目的，要开开心心的活着。