引言

[singlepic=18468]

上图:艺术陈列馆问题(Art Gellery Problem),是一个NP-Complete问题。这里显示了一种解,四个摄像头覆盖了整个艺术陈列馆的每个角落。

P和NP就不讲了,Assert(不明白P和NP的读者不会到达这里看到这一段话)。
P是否等于NP的问题目前仍有争论,我对算法理解不深,暂时没有自己的看法。具体的讨论可以参见:WikiPedia的P=NP?讨论。不过做点猜想的话,我觉得,从数学美的角度来看,我觉得P=NP。当然,从理性思考角度来看,就像“你觉得有没有外星人”这个问题一样,理性思考的人会毫不犹豫地给出“当然有”的答案,P不应该等于NP。当然大部分计算机科学家认为P≠NP。

If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss… —— Scott Aaronson, MIT

这段话给出的启示还是很令人震惊的:任何懂得欣赏交响乐的人都可以成为莫扎特一样的音乐神童,任何懂得步步演绎问题的人都可以成为高斯一样的数学天才,因为P=NP,则说明解决问题和理解、认识和描述问题本身没有本质区别。
谈点自己的看法:Google的出现其实为我们提出了一种佐证,当你把一个问题描述清楚的时候,基本也就解决了。当你真正遇到一个问题,只要想清楚应该用什么关键字去搜索,问题的答案正在Google上等着你。

The main argument in favour of P≠NP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. […] The resolution of Fermat’s Last Theorem also shows that very simply [sic] questions may be settled only by very deep theories. —— Moshe Y. Vardi, Rice University

最简单的问题却要通过最复杂的理论来解决。

Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required. —— Anil Nerode, Cornell University

避免偏见,应当总是向两个方向努力。

NP-Complete问题

Cook在1971年给出并证明了有一类问题具有以下性质:

  1. 这类问题中任何一个问题至今未找到多项式时间算法;
  2. 如果这类问题中的一个问题存在有多项式时间算法,那么这类问题都有多项式时间算法(就是多项式时间内,这类问题可互相规约)。

这类问题中的每个问题称为NP完全(NP-Complete,NPC)。

NP-Hard问题

如果判定问题A满足A∈NP且NP中的任何一个问题都可在多项式时间内规约为A,则称A为NP完全(NP-Complete,NPC)。若NP中的任何一个问题都可以在多项式时间规约为判定问题A,则称A为NP难(NP-Hard,NPH)。
显然NPC⊆NPH。
NP完全和NP难问题的区别是NP难问题无需判断A是否属于NP。验证一个问题A是否为NPC的关键有两点:

  1. 一是NP中任何一个问题是否可在多项式时间内规约为A;
  2. 其次,是否存在一个字符串,其规模为实例规模的多项式函数,以及是否存在一个多项式时间的验证算法。

由于NPC里包含很多著名的组合最优化问题,经过几代数学家的努力,迄今没有找到多项式时间算法,人们猜想NPC中的任何一个问题没有多项式时间算法,即P∩NPC=∅。
这里有个图可以帮助你理解这几种问题的相互关系。可以看到,如果P=NP,数学上是比较美的。

[singlepic=18467]

一种实践方法

当然上面讲的都是理论。实践当中没有这么复杂,当你遇到一个问题,想判断这个问题是否是NPC时,只需要找一个类似的已知的NPC问题,然后想一个这两个问题之间的多项式时间转换方法即可。
这里有一个列表,包含已知的著名NP-Complete问题的列表。重要的NPC问题现在已知3000+。

同济大学 计算机软件与理论 0720080247 李征

1. 矩阵乘法最优算法
1.1 矩阵与计算机科学
数学的重要性显而易见。数学是各种科学的基础,计算机也不例外。对于计算机学科起着关键性作用的数学分支主要是离散数学,因为计算机处理的数据还是二进制的离散量,对于连续量的处理还处在模拟的阶段。
此外,计算机科学中大量分支涉比如系统结构和计算机网络等等,都需要一定的逻辑学和图论作为其研究的支撑。作为离散数学的核心,矩阵的重要性不言而喻。众多的复杂计算机模型都可以用简单的矩阵来表示,而矩阵的运算也经常代表着重要的计算机物理含义。本文研究的搜索引擎排名评价体系就是其中之一。

1.2 矩阵乘法的理论下界
设A是一个m行n列矩阵

[singlepic=14397,,center]

B是另一个n行q列矩阵

[singlepic=14400,,center]

矩阵A和B的乘积是一个m行q列矩阵

[singlepic=14401,,center]

其中

[singlepic=14402,,center]

从定义出发计算矩阵的乘积,需要n次乘法运算和n-1次加减运算,得到的是计算矩阵乘法的计算复杂度的上界。当m、n和q被认为是同阶的数的时候,算法复杂度是O(n^3)。
两个矩阵相乘的任何可能的算法,运算次数至少不低于矩阵与向量相乘(当q=1时退化的情况)。此时,需要mn次乘法运算和m(m-1)次加减运算,当m和n同阶时,算法复杂度是O(n^2)。
由此可以得出结论,正确的矩阵相乘算法,其复杂度介于O(n^3)与O(n^2)。

1.3 几个典型的矩阵乘法算法
1.3.1 Winograd矩阵乘法算法
S. Winograd于1967年提出了一个矩阵乘法算法,其核心思想是修改向量内积计算方法,对重复计算部分进行预处理,然后将计算结果多次使用,从而达到简化计算的目的。
Winograd矩阵乘法算法实质是增加约50%的加减法代价以换取减少约50%乘法运算,但是其算法复杂度仍然是O(n^3),并没有降低算法复杂性的阶。
1.3.2 Strassen矩阵乘法算法
Strassen算法是另外一个矩阵乘法算法,这个算法突破了O(n^3)的计算复杂度阶,由V. Strassen在1969年提出。
Strassen算法主要用于方阵的计算。Strassen观察了简单2阶方阵乘法的计算特点,使用7次乘法计算就能算出结果,而不是平常的8次,从而降低了整个算法计算复杂度阶。
Strassen算法的计算复杂度是O(n^(log2 7) )=O(n^2.31 )。

1.4 一个最优矩阵乘法算法
1989年,我的研究生导师蒋昌俊教授提出了一个新的矩阵乘法算法,称为凝聚算法。凝聚算法把矩阵相乘的计算复杂度降到了理论下界O(n^2)。
凝聚算法从非负整数矩阵出发,即当A和B的元素都是非负整数时,可以通过设置足够大的x和y,分别通过求x的m-1次多项式和y的q-1次多项式的值,把矩阵A的各列的元素和矩阵B的各行的元素凝聚在一起,分别得到n维向量[a1,a2,…,an]和[b1,b2,…,bn],其中ak和bk分别是矩阵A的第k列元素和矩阵B的第k行元素的“凝聚”结果。通过向量的内积运算,又可以将上述两个向量的各个分量进一步凝聚成一个整数c。最后,以y为除数作q-1次整数求余运算,就把整数c散列成q个整数c1,c2,…,cq,再把ck对x作m-1次整除求余运算,又将ck散列成m个数,就得到了积矩阵C的第k列元素c1k,c2k,…,cmk。算法的关键之处在于设置x和y为足够大的整数,以便使整除求余的散列能够正确地反映前面通过多项式求值和向量内积运算的凝聚效果。

第一步:对x和y的取值是算法的关键,如果x和y的取值不合理,将得不到正确的反散列。

[singlepic=14403,,center]

第二步:对从1到n的k,用Horner方法计算:

[singlepic=14404,,center]

第三步:c=a1b1+a2b2+⋯+anbn

第四步:作除法,依次求商d1,d2,…,d(q-2),rq和余数r1,r2,…,r(q-1),使得:

[singlepic=14405,,center]

第五步:
对从1到q的j作除法,依次求商kj1,kj2,…,k(j(m-2)),rjm和余数rj1,rj2,…,r(j(m-1)),使得

[singlepic=14406,,center]

for i=1 to m do
for j=1 to q do
cij=r(j(m-i1+))
repeat
repeat

整个计算过程中各种操作的数量是

  • 比较:mn+nq-2
  • 乘法:mn+mq+nq
  • 除法:mq-1
  • 加减:mn+mq+nq-n

当m、n和q被认为同阶时,凝聚算法计算过程中有2n^2-2次比较运算,3n^2次乘法运算,n^2-1次除法运算和3n^2-n次加减运算,计算复杂度为O(n^2)。

2. 矩阵乘法最优算法在搜索引擎排名中的应用
2.1 一种互联网结构建模
万维网(World Wide Web,WWW)是指在因特网上以超文本为基础形成的信息网。万维网为用户提供了一个可以浏览的图形化界面,用户通过它可以查阅Internet上的信息资源。WWW是通过互联网获取信息的一种应用,我们所浏览的网站就是WWW的具体表现形式,但其本身并不就是互联网,万维网只是互联网的组成部分之一。互联网常用的服务包括:WWW、Email、FTP、Usenet、IM等。
在“谁发明了浏览器” 文中介绍了蒂姆-伯纳斯-李(Tim Berners-Lee)于1990年发明了首个网页浏览器--World Wide Web。在1991年蒂姆-伯纳斯-李建立世界上第一个网站,它于1991年8月6日上网,它解释了万维网是什么,如何使用网页浏览器和如何建立一个网页服务器等等。综合各种资料,1991年8月6日被认为是是万维网诞生的日子。
WWW的基础是超文本和链接,链接也使得一个一个网站被相互链接起来,成为了全球规模的巨大网络。链接分为两种,一种称为内部链接,指从一个网站某个网页,链接到同一网站的另一个网页的链接;另一种称为外部链接,指从一个网站某个网页,链接到另一个网站的某个网页的链接。实际当中考虑的链接是外部链接,因为外部链接反映了整个互联网的拓扑关系。
搜索引擎是一种互联网应用,搜索引擎是自动从Internet搜集信息,经过一定整理以后,提供给用户进行查询的系统。英特网上的信息浩瀚万千,而且毫无秩序,所有的信息像汪洋上的一个个小岛,链接是这些小岛之间纵横交错的桥梁,而搜索引擎,则为你绘制一幅一目了然的信息地图,供你随时查阅。
对于搜索引擎来说,网站及其链接关系可以用图来描述。

[singlepic=14407,,center]

图1 八个网站相互链接的例子

通过邻接矩阵A可以描述整个网络的拓扑结构。邻接矩阵A定义为

[singlepic=14398,,center]

我们认为,一个网站本身是存在指向本身的链接的,因此aii=1。
图1中的示例的邻接矩阵为

[singlepic=14399,,center]

2.2 互联网站价值评价标准
用户通过搜索引擎找到他们所需要的网站和页面,而搜索引擎也被用户寄予厚望,希望能够在排在最前面的搜索结果中得到他们觉得最有价值的目标页面。
互联网络是一个开放的系统,如何去衡量信息的可靠性呢?当然,CNN或者人民日报谈论一个问题,和一个普通博客谈论一个问题,当然是不一样的。即,信息是有权值的。
为每一个网站人工去赋一个权值明显是不现实的。互联网站数目超过了1亿个,而且每个网站不停地在更新,一个固定的权值也是不合适的。
Google设计了PageRank算法。PageRank是一个动态的评价体系,能够动态地对网站和网页提供的信息的重要程度进行评估,并据此作为一项标准,排序用户搜索结果。
一般人们认为,可靠的信息来自于新闻网站、大公司和百科全书。这些网站被人工选出,赋予最高的PageRank权值。然后根据这些网站的外部链接,将自己的PageRank递减地传递下去,被这些网站链接的网站获得了第二级的PageRank,如此传递下去,就可以链接到每一个网站(除了那些没有意义的信息孤岛网站)。
如果我们得到了整个互联网的邻接矩阵A,那么我们可以通过计算A^k,得到经过k次链接后,哪些网站得到了传递过来的PageRank。

2.3 矩阵乘法最优算法在搜索引擎排名中的应用
互联网邻接矩阵是一个超级规模的矩阵,超过1亿维。在这里,我们探讨一下做一次相乘,凝聚算法能够带来的性能提升。
假设:互联网站数目n=1×10^8个,超级计算机(例如2008年6月9日IBM公司的“走鹃”)每秒进行运算1×10^15次。

  • Winograd算法(1967):2n^3+3n^2-4n+1,2×10^9秒=63.4年
  • Strassen算法(1969):6n^2.31-6n^2,18059秒=5小时
  • 凝聚算法(1989):9n^2-n-3,90秒

由此可见,如果能够将凝聚算法应用在搜索引擎领域,会带来巨大的性能提升。

3. 参考资料
[1]. 矩阵乘法的一个最佳算法. 蒋昌俊, 吴哲辉, 1989, 科学通报第4期, 251-254
[2]. “矩阵乘法的一个最佳算法”一文的进一步研究. 蒋昌俊, 吴哲辉, 1994, Vol. 11, No. 2, 149-153

查看本文PDF版本:凝聚算法在搜索引擎应用设想

分治技术的基本思想与特点
分治技术的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。
分治法所能解决的问题一般具有以下几个特征:

  • 该问题的规模缩小到一定的程度就可以容易地解决;
  • 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
  • 利用该问题分解出的子问题的解可以合并为该问题的解;
  • 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

分支-限界技术的基本思想
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在搜索问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。
在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

贪心技术的基本思想与特点
贪心技术的基本思想是从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。
该技术的特点是:

  1. 不能保证求得的最后解是最佳的;
  2. 不能用来求最大或最小解问题;
  3. 只能求满足某些约束条件的可行解的范围。

在一般(非0/1)背包问题中,选择什么样的度量标准包,才能使该问题获得最优解?并以该度量为标准,给出背包问题的贪心算法。
在一般背包中,度量物品放入优先顺序的标准是该物品的单位重量的价值度。其用贪心算法描述为:

  1. 将物品按其单位重量的价值由高至低排序。
  2. 选择单位重量价值最高的物品放入背包中,直至背包满或该类物品已全部放入。
  3. 若背包未满,重复2的过程。

利用回溯技术,给出n-皇后问题的解法,并画出4-皇后问题的深度优先搜索树
启发式搜索9宫问题
写出矩阵相乘的凝聚算法,并分析其各种基本运算的次数与算法的复杂性
设n=3,(W1,W2,W3)=(3,4,5),(P1,P2,P3)=(2,4,8),M=9,用动态规划法求解0/1背包问题
设f(i, j)表示背包容量为j,可选择放入的物品为i、i+1、……时背包可入物品价值的最优解,则f(1,9)为所求问题的解,并且
1) f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi}, 当j>=Wi
2) f(i,j)=f(i+1,j), 当j
f(3,0)=f(3,1)=…=f(3,4)=0,f(3,5)=f(3,6)=…=f(3,9)=8
当y<4时,f(2,y)=f(3,y)=0。
当y=4时,f(2,y)=max{f(3,4),f(3,4-4)+4}=4。
当4
当y=9时,f(2,y)=max{f(3,9),f(3,9-4)+4}=max{8,8+4}=12。
所以f(1,9)=max{f(2,9),f(2,9-3)+2}=max{12,8+2}=12,此时选择的物品是2和3。

另一届题目

  1. 写出求解汉诺塔问题的递归过程,并用树结构画出n=3时的递归调用过程,说明汉诺塔问题的算法时间复杂度。
  2. 有集合s={2,5,6,8,7,3,4,1}用分治技术求s中的最大元素和最小元素。设|s|=n,T(n)表示求出s中最大和最小元素需要进行比较的次数,写出T的解析表达式,并证明T(n)=(3/2)*n-2。
  3. 利用凝聚技术写出的矩阵乘法算法,并分析算法的时间开销,证明算法的正确性。

凝聚算法两篇原始论文:

1. C语言
毫无疑问, 第一门语言是C语言. 我上大一的时候一样有疑问, 为什么中国的高校那么迂腐, 都什么年代了, 外面都Java了, 我们还在C… 还不是C++. 其实, 事实证明, 后来毕业的时候, 被人称作计算机的强人都是当年C语言程序设计考试考优的那几个人. 一个人对于C语言的态度, 其实一定程度上反映了这个人对于计算机科学和程序设计的热衷程度. 我们二三年级的班主任经常讲, 从事计算机工作, 一定要对编程抱有兴趣, 否则是无论如何也学不好的. 如果你发现你对编程根本没有兴趣, 建议趁早转专业. C语言考试当中如果有超过5处地方有问题, 就是不合格. 对于谭浩强版C语言书里面的知识点, 不能有任何疑问. 这也就是为什么谭浩强版C语言教材至今仍在中国书店计算机及网络类畅销排行第二名的原因.

2. C++
C++是不能绕开的一门语言. C++是一种思想, 不学C++不知道Java或者C#的好. 苦其心志是必要的, 虽然我对于C++依然反感的很… 太复杂太混乱太危险了. 不过, 我同样认为, 对于计算机系学生来说, 经过自己的体验知道C++为什么太复杂太混乱太危险是很有必要的. 此外, C++应该是你从TC转向Visual Studio 2005的跳板. C++是一门系统编程语言, 不适合用来写应用程序.

3. HTML/XML/CSS
必须精通的技术. 迟早一天, 所有程序都被XML化. 目前的趋势是WPF已经把应用程序界面表示XML化, DBMS也以支持XML作为重要的大版本特性. 何况, 计算机专业要想挣钱, 网站是必须要做的… 之于CSS, 初学者就不要经历我们走过的那些阴沟了吧. 听W3C的没错. 说起来我做网页也有10个年头了, 初中就开始写HTML, 完全是看HTML标准成长起来的一代人, 那时候还幼稚的很, 当发现可以用表格组织网页框架结构的时候, 欣喜若狂, 自认是个天才, 四处找人想分享经验, 才发现高处不胜寒. 如今, Div+CSS已经变成了我标准的工作语言, FrontPage和Dreamweaver则是早就早就不用了的古董了. UltraEdit是我的最爱.

4. JavaScript/AJAX
如果想走网站这条路, 精通JavaScript是必要的. JavaScript是一门类C语言, 学起来比较轻松, 而且因为JavaScript出了名的难以调试, 可以锻炼程序调试技术. JavaScript技术路线走下去就是大红大紫的Ajax了. 其实没什么, JavaScript和DOM戏法而已.

5. 对Visual Basic的态度
我不建议学习Visual Basic. 将VB纳入.NET框架实际上是一个失误. 从那一刻起, VB就已经死去. 计算机系的态度是, 各科课程设计不能使用VB编写.

6. ASP或PHP
网站路线必经之路. 因为ASP是类VB的, 所以我觉得不太值得为了ASP学VB. 因此, 类C的PHP更有价值, 而且PHP这么多年还活得好好的. 有必要把PHP作为轻量级的后台编程语言.

7. Database
MySQL和SQL Server以及Oracle最好都学习一下. 重点是前两个. Oracle实在是用不起. 占用资源太大, 不适合在自己机器上做试验. MySQL是PHP支持最好的数据库, 走网站路线的建议选择.

8. WWW和Hosting
网站路线的人不可避免的要接触域名系统和托管之类的事情. 这其实是一门学问, 书上很少讲, 却是很大很深的学问. 主要包括, 域名系统, 域名怎么解析, A记录, CNAME, MX记录是怎么回事; DNS怎么工作; 什么是虚拟主机等等. 注册一个属于自己的域名, 会对你将来找工作有很大的作用的. 用网站技术建立自己的个人主页, 然后才能搞明白Google好在哪里(Apps), 什么是SEO(又是一门大学问).

9. Java和C#
Java是一头大象了. Servlet, Swing, JSF, JSP… 名称太多太多了点… 还是C#干净点… 选择那条路, 与其说是技术问题, 不如说是政治问题, 我觉得C#好一点, 必经Sun终归要被并购掉… 微软语言的成败, 不是有语言特性决定, 而是微软平台的成败决定. 因此, C#也有风险. Java路线的话, 后面有网站后台的Servlet和JSP, C#路线则是ASP.NET. 不学PHP也无所谓. 就是主机贵一些.

10. 操作系统
这也是一个政治问题… Windows 2003/2008是肯定要会玩的, 必经和XP/Vista那么近似, 如何在机器上架设Web服务器, 安装动态语言, 架设DBMS是基本功. 因此, 需要精通IIS/Apache/Tomcat. Linux肯定要学. 哪个发行版本我不在乎, 基本Shell命令要烂熟于心.

11. 计算机硬件
有了这些, 可以出去打工赚点小钱, 出去打工, 为自己配一台好电脑吧. 搞清楚CPU阵营, 显卡阵营, 主板阵营, 硬盘品种, 怎么超频. 组成原理, 系统结构, 汇编语言是要好好学的. 为了你将来的水平成长.

12. 设计模式
编程到这里, 基本已经饱受不恰当的系统设计折磨之苦了. 看看设计模式, 看看代码大全, 让自己变成一个爱干净的人, 代码里没有意义的空行甚至空格也不要有. 注释, 用英文写起来啦. 这是, 你就是别人眼里的高手了.

13. 算法
为了生存, 为了面试, 算法是必须精通的一步. 算法导论是一个不错的选择, 别问我英文版好还是中文版好, 都买下来, 随着MIT视频教程, 仔仔细细拿出一年时间来, 学好算法.

差不多了. 毕业吧.

记得当年注册Gmail的时候就对于Gmail的随机单词验证码生成图片比较感兴趣, 因为每次刷新, 获得的随机单词都像是一个单词, 而不是随机字符的组合, 不过就是不认识…
一度认为Google手工找了一堆难词, 然后在当中随机… 今天看Ruby Cookbook的时候极其偶然的发现一个例子, 生成可读单词的算法.
其实就是两个集合, 集合c当中保存aeiou这5个原音字母, 集合v中保存剩下的字母. 然后按照vcvcvc这样的顺序随机出字母组成一个词, 就得到一个可读的类单词.
用在验证码上不错哦~

今天中午就接到MSRA的第二个电话面试,有点奇怪,因为前面几个电话都是晚上,我一直以为微软的前辈们都按照美国时间工作…结果今天在我午睡正香的时候打来了电话,开始问了几个项目的事情,我晕晕乎乎答得语无伦次,我明白他想知道关于开发中遇到的难题,然后我是怎么克服的,无奈实在不清醒…都想不起来了,结果我想他没有得到太多想得到的吧。之后,给我出了一个简单的算法题目要求写出来,听工程院实习的同学讲,当面面试的时候都会直接写在白板上,然后由微软的人录入编译的,这样放给我自己做,我觉得还算是降低难度了吧。

题目是这样的:有一个矩阵,每个元素是一个数,要求,从左上角出发到达右下角,每次只能向右或向下,要求全路线经过的元素和最小,求出路径及这个和的值。要求分别用递归和非递归方法实现之。
结果图:
matrix1.jpg
我花了一下午,写出了这个程序,幸运的是,两种方法的结果竟然相同…
哈哈~~玩笑话,放出代码:

[code=’c#’]
using System;
using System.Collections.Generic;
using System.Text;

namespace Matrix
{
class Program
{
///

/// 矩阵元素的最大值,用于生成随机矩阵
///

private static int MAX_ELEMENT = 10;
///

/// 矩阵的高度
///

private static int MATRIX_X = 4;
///

/// 矩阵的宽度
///

private static int MATRIX_Y = 15;

///

主函数

/// 命令行参数 static void Main(string[] args)
{
//初始化一个目标矩阵
int[,] matrix = new int[MATRIX_X, MATRIX_Y];
//初始化一个方向矩阵
string[,] direction = new string[MATRIX_X, MATRIX_Y];
//随机生成目标矩阵的元素
Generate(ref matrix, MATRIX_X, MATRIX_Y);
Console.WriteLine(“Target Matrix is:”);
//打印矩阵
PrintMatrix(matrix, MATRIX_X, MATRIX_Y);

//递归法
Console.Write(“\r\nMethod No.1 Result\r\nMinCost=” + Step(direction, matrix, MATRIX_X, MATRIX_Y, MATRIX_X – 1, MATRIX_Y – 1));
//打印结果
PrintDirection(direction, MATRIX_X, MATRIX_Y);

//清空方向矩阵
direction = new string[MATRIX_X, MATRIX_Y];
//非递归法
PrintMinCostRoute(direction, matrix, MATRIX_X, MATRIX_Y);
}

///

随机生成目标矩阵

/// 目标矩阵的引用 /// 矩阵宽度 ///矩阵高度 static private void Generate(ref int[,] matrix, int x, int y)
{
//如果未初始化,先初始化之
if (matrix == null)
{
matrix = new int[x, y];
}
//随机生成元素
Random random = new Random();
for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { matrix[i, j] = random.Next(MAX_ELEMENT - 1) + 1; } } } ///

非递归寻找最小值及路径

///路径矩阵 ///目标矩阵 ///矩阵宽度 ///矩阵高度 static private void PrintMinCostRoute(string[,] direction, int[,] matrix, int x, int y)
{
//动态规划备忘录矩阵
int[,] cost = new int[x, y];
//初始化各节点为整型变量最大值
for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { cost[i, j] = int.MaxValue; } } //从左上角逐次扩大矩阵 for (int i = 0; i < (x >= y ? x : y); i++)
{
//左上角
if (i == 0)
{
//就是本身
direction[0, 0] = “S”;
cost[0, 0] = matrix[0, 0];
}
else
{
//顺次检查当前方阵周围的元素
for (int k = 0; k < i + 1; k++) { //如果范围合法 if (i < x && k < y) { //检查比较当前的最小值和从上面过来的值 if (cost[i, k] >= (cost[i – 1, k] + matrix[i, k]))
{
//上面更小则更新
cost[i, k] = cost[i – 1, k] + matrix[i, k];
direction[i, k] = “U”;
}
if (k >= 1)
{
//检查比较当前的最小值和从左面过来的值
if (cost[i, k] >= (cost[i, k – 1] + matrix[i, k]))
{
//左面更小则更新
cost[i, k] = cost[i, k – 1] + matrix[i, k];
direction[i, k] = “L”;
}
}
}
//如果范围合法
if (i < y && k < x) { //检查比较当前的最小值和从上面过来的值 if (cost[k, i] >= (cost[k, i – 1] + matrix[k, i]))
{
//上面更小则更新
cost[k, i] = cost[k, i – 1] + matrix[k, i];
direction[k, i] = “L”;
}
if (k >= 1)
{
//检查比较当前的最小值和从上面过来的值
if (cost[k, i] >= (cost[k – 1, i] + matrix[k, i]))
{
//左面更小则更新
cost[k, i] = cost[k – 1, i] + matrix[k, i];
direction[k, i] = “U”;
}
}
}
}
}
}
Console.Write(“\r\n\r\nMethod No.2 Result\r\nMinCost=” + cost[x – 1, y – 1]);
PrintDirection(direction, x, y);
}

///

一步递归求某位置的最小值

///路径矩阵 ///目标矩阵 ///矩阵宽度 ///矩阵高度 ///位置x坐标 ///位置y坐标 /// 这个位置的最小值
static private int Step(string[,] direction, int[,] matrix, int x, int y, int pos_x, int pos_y)
{
//Debug用
//Console.WriteLine(“pos_x=” + pos_x + “,pos_y=” + pos_y);
//第一行的元素
if (pos_x == 0)
{
//第一个元素,递归结束,返回本身的值
if (pos_y == 0)
{
//特殊位置,路径指向Self=”S”
direction[pos_x, pos_y] = “S”;
//返回本身的值
return matrix[pos_x, pos_y];
}
//第一行非第一个,必然从左边走过来
else
{
//路径指向Left=”L”
direction[pos_x, pos_y] = “L”;
//左边一个的最优值加上本身得到最优值
return Step(direction, matrix, x, y, pos_x, pos_y – 1) + matrix[pos_x, pos_y];
}
}
//第一列的元素,必然从上边走过来
if (pos_y == 0)
{
//路径指向Up=”U”
direction[pos_x, pos_y] = “U”;
//上边一个的最优值加上本身得到最优值
return Step(direction, matrix, x, y, pos_x – 1, pos_y) + matrix[pos_x, pos_y];
}
//避免重复计算,先取到上面一个和左边一个的最优值
int up = Step(direction, matrix, x, y, pos_x – 1, pos_y);
int left = Step(direction, matrix, x, y, pos_x, pos_y – 1);
//如果从上面走合算
if (up <= left) { //路径指向Up="U" direction[pos_x, pos_y] = "U"; //上边一个的最优值加上本身得到最优值 return up + matrix[pos_x, pos_y]; } //如果从左面走合算 else { //路径指向Left="L" direction[pos_x, pos_y] = "L"; //左边一个的最优值加上本身得到最优值 return left + matrix[pos_x, pos_y]; } } ///

打印矩阵

/// ///矩阵宽度///
///矩阵高度
static private void PrintMatrix(int[,] matrix, int x, int y)
{
for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { Console.Write(matrix[i, j].ToString() + " "); } Console.Write("\r\n"); } } ///

打印所走的路径矩阵及走法

///路径矩阵 ///路径矩阵宽度 ///路径矩阵高度 static private void PrintDirection(string[,] matrix, int x, int y)
{
//打印路径矩阵
Console.WriteLine(“\r\nThe Direction Matrix:”);
for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { Console.Write(matrix[i, j] + " "); } Console.Write("\r\n"); } //打印走法 Console.Write("The Route is:"); //走法的逆序存放数组 string[] Reverse = new string[x + y - 2]; int pos_x = x - 1; int pos_y = y - 1; //从终点开始向路径矩阵指示的方向回溯走法 for (int i = 0; i < (x + y - 2); i++) { //从左边来的 if (matrix[pos_x, pos_y].Equals("L")) { pos_y--; Reverse[i] = "right"; } //从上边来的 else { pos_x--; Reverse[i] = "down"; } } //倒序打印走法的逆序存放数组,得到真正的从起点出发的走法 for (int i = 0; i < (x + y - 2); i++) { //倒序打印 Console.Write(Reverse[(x + y - 2) - i - 1]); if (i < (x + y - 3)) { //不是最后一个的时候打一个分隔号 Console.Write(","); } } } } } [/code]