最近朋友跟我讨论了一个类型的旅行商问题。原版的旅行商问题是说，给定一个图，给定起点和终点，求不重复经过任何节点的最短路径，遍历全部节点。而他的问题是，仍然不许重复经过任何节点，但是不要求路径遍历全部节点，而是遍历某一个给定的关键点集，求最短路径。问题里面对图没有做任何限制，图可能包含数千节点，不过关键点集是充分小的，比如只有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就可以了，没有必要自己编译。并且，如果不需要编译，其实开发人员的机器配置就没有必要那么高，节省的成本可以做更好的服务器机器。其实这种策略也更符合所谓“云计算”。当然更加有趣的是，可以让编译本来就发生在由所有客户机结成的计算网格上面。并且所有的二进制文件也都分布式存储在这些分散的机器上面。服务器仅仅是一台或几台管理信号的中转路由。这样做可能可以进一步降低成本，并且对于每个计算网格而言，本地编译某个模块，然后二进制文件就存储在本地，也没有太多网络开销。当然具体算法如何实现，这个恐怕要仔细研究了。（研究生课题？:）