Monthly Archives: December 2009

相亲相爱一家人

 

 

(男)我喜欢一回家就有暖洋洋的灯光在等待,
(女)我喜欢一起床就看到大家微笑的脸庞,
(男)我喜欢一出门就为了家人和自己的理想打拼,
(女)我喜欢一家人心朝着同一个方向眺望。哦!

(男)我喜欢快乐时马上就想要和你一起分享,
(女)我喜欢受伤时就想起你们温暖的怀抱,
(男)我喜欢生气时就想到你们永远包容多么伟大,
(女)我喜欢旅行时为你把美好记忆带回家。

(女)因为我们是一家人,
(男)相亲相爱的一家人,
(男)有缘才能相聚,
(女)有心才会珍惜,
(男)何必让满天乌云遮住眼睛。

(女)因为我们是一家人,
(男)相亲相爱的一家人,
(男)有福就该同享,有难必然同当,
(男合)用相知相守换地久天长。

(女)我喜欢一回家就把乱糟糟的心情都忘掉,
(女)我喜欢一起床就带给大家微笑的脸庞,
(男)我喜欢一出门就为了个人和世界的美好打拼,
(女)我喜欢一家人梦朝着同一个方向创造。哦!
(女)当别人快乐时好像是自己获得幸福一样,
(女)当别人受伤时我愿意敞开最真的怀抱,
(男)当别人生气时告诉他就算观念不同不必激动,
(男)当别人需要时我一定卷起袖子帮助他。

(女合)因为我们是一家人,
(男合)相亲相爱的一家人,
(合)有缘才能相聚,有心才会珍惜,
(合)何必让满天乌云遮住眼睛。

(女合)因为我们是一家人,
(男合)相亲相爱的一家人,
(合)有福就该同享,有难必然同当,
(合)用相知相守换地久天长。
(男)处处为你忧心,一直最忧我情,
(男)请你相信这份感情值得感激,哦

(女合)因为我们是一家人,
(男合)相亲相爱的一家人,
(男)有缘才能相聚,有心才会珍惜,
(男)何必让满天乌云遮住眼睛。

(合)因为我们是一家人,
(男合)相亲相爱的一家人,
(合)有福就该同享,有难必然同当,
(合)用相知相守换地久天长。 

 

 

 

铭记于内心的最宝贵的财富:小个协会。

双调欧几里德旅行商问题

终于弄懂双调欧几里德旅行商问题,《Introduction to algorithms》真是够强大,佩服地五体投地! 


1.问题描述。

   货郎问题(Traveling Salesman
Problem,简称“TSP”)也叫货郎担问题,中国邮路问题,旅行商问题等,是计算机算法理论历史上的经典问题。在过去几十年中,它成为许多重要算法思想的测试平台,同时也促使一些新的理论领域的产生,比如多面体理论和复杂性理论。
货郎问题:给定n个结点和任意一对结点{i,j}之间的距离为dist(i,j),要求找出一条闭合的回路,该回路经过每个结点一次且仅一次,并且该回路的费用最小,这里的费用是指每段路径的距离和。
货郎问题求解其精确解是NP难的,并且求解任意常数因子近以度的解也是NP难的。若将问题限定在欧氏平面上,就成为欧氏平面上的货郎问题,也叫欧几里德旅行商问题(Eculid
Traveling Salesman
Problem)。但是,即使是欧氏平面上的货郎问题也是NP难的。因此通常用来解决TSP问题的解法都是近似算法。其中第一个欧几里德旅行商问题的多项式近似算法是Arora在1996年使用随机平面分割和动态规划方法给出的。

    J.L. Bentley 建议通过只考虑双调旅程(bitonic
tour)来简化问题,这种旅程即为从最左点开始,严格地从左到右直至最右点,然后严格地从右到左直至出发点。下图(b)显示了同样的7个点的最短双调路线。在这种情况下,多项式的算法是可能的。事实上,存在确定的最优双调路线的O(n*n)时间的算法。

    

注:在一个单位栅格上显示的平面上的七个点。
a)最短闭合路线,长度大约是24.89。这个路线不是双调的。b)相同点的集合上的最短双调闭合路线。长度大约是25.58。 

英文原版(来自《算法导论》):  
     
想了很久,硬是没有想到此问题的解法,还是得看看答案。 
搜了很多关于此问题的博客,几乎都误导了我,方程都给错了,我很无语。只有这个博客符合题意: 

英文原版的解法: 

经典的动态规划问题!!