数学建模竞赛新手教程(4)--实战

altf

数学建模竞赛新手教程(4)--实战

路过 [声明]此文志在推广数学建模，欢迎大家引用、转载、剽窃、摘用。
实战----血管的三维重建


　　2001年9月未，我们终于迎来了全国大学生数学建模竞赛。那时候西山居有一个游戏刚刚出炉，里面有一首歌叫做爱的废墟

====================================================

蓝蓝的天空是谁的身体
让云掠夺而去留下感情的证据
当感情在你的心里慢慢的扭曲
我的爱对你是不是委屈加上了恐惧

伤心的流星 凄凉的逃避
留下星星收拾这不负责任的结局
是谁把天空撕裂出星星的伤口
抹杀了我的自由还有浪漫的温柔


如果说天外的雨 是星星为我落下的泪滴
我不知道在你心里 是否还有受伤的痕迹
如果说心中的雨 是来自一处残破的屋宇
我不知道呵护的记忆 是否会成为埋藏爱的废墟

==================================================
　　不知道为什么，我比较喜欢忧伤的感觉，就象这首歌给人的感觉一样，那样容易让人产生力量
　　在竞赛开始的前一天，我和两位搭挡就开始往招待所里面搬运必要的作战武器了。
列个清单吧：
>数学手册一套(5册)每一册都有一个拳头那么厚
>高等数学教科书(东点军校出版)，概率论(复旦大学)，数值分析(东点军校)，Matlab的一些
参考书，C语言教程(谭浩强的那本)，等等等等
>三台自己的电脑，都是赛扬533、566之类的配置，且均有网卡、UPS不间断电源及网线(当时用的是同轴电缆)，一个Modem。软件有Matlab，VisualC++，Microsoft Word，Windows 2000操作系统(当时还没有学会Visio，其它软件好像就没有什么了)
>从学院的机关里借了一台HP的Lasier Jet6.0打印机
>.......
　　这么多东西当然不是人力所能承受的，还好学校给了辆不大不小的车。

　　一却准备就绪，我们就入住了学校南门外的招待所里(以前条件一般，具说现在已经改建的上档次了哈哈，一般人住不上)。老师告诉我们第二天早上8:00从网上Down题目，但不知道是谁传来了一个消息，说晚上题目就有可能从网上上着。于是整个晚上我们都没有睡安稳，时不时上一下网，看一看能不能下载赛题了。太是最终还是在第二天早上8:00才搞到题目/

　　数学建模竞赛一般有三道题目，其中有两道是本科组的，两道是专科组的。专科组与本科组有一道题是相同的。题目分别是：血管的三维重建,公交车调度问题。

　　这两道题得选一道做。选哪一道呢？仔细研究了一下，我们发现，公交车调度是一个最优化的问题，而血管的三维重建偏重于算法。与是我们三人毫不犹豫的选择了血管的三维重建。附带说一句，原因是什么呢？因为我们曾在一年前也做过一个最优化的问题，那一次是钢管运输问题，做的奇差，于是大家心有余悸，尽量不选这类题目。(下面附上此题目)
==================================================
题目见此帖：http://www.shumo.com/newbbs/dispbbs.asp?boardID=3&ID=87
==================================================

　　血管的三维重建，遇见的第一个困难就是----怎么把这些bmp的图像给读进来，存为二进制的矩阵?一开始，我们去图书馆找到了《bmp文件格式》的书，准备利用C程序把bmp给读出来。刚准备着手去做的时候，我们却意外的发现Matlab中有现成的函数imread可以使！真是天助我也，马上把所有100张bmp图片给读了进来，把每一个切片图的bmp文件转化为一个512×512的0,1矩阵。并利用save函数，打开ASCII开关，把每一个矩阵存都存为了txt的文档。这样，C程序就可以直接使用了。

　　在上面的过程中，我们发觉题中给的bmp的命名不太好，它是从0 ,1 ,2 ......到99的，我们把这些名字改为了01,02,03,04,....99，把所有的文件名都改成了两位的，方便操作。

　　接下来就是如何得出结果了。首先我们在图书馆里查了很久，看有没有论文解决相类似的问题。不但要查中文的，还要查英文的。顺便说一句，英语真的很重要，在网上，英文更是当之无愧的霸主，想利用网络查找资料，英语不好则寸步难行。我们发现了医学上的CT成像技术有可以借鉴的地方。这些资料不一定有用，但能够很好的开拓我们的思路，花时间在上面是值得的。

　　然后，我们想啊想啊，不停的想来想去，并且用ACDSEE把这100张bmp的图像放幻灯版似的正放倒放，还用像皮什么的模拟成血管，弯来弯去。最后，凭直觉猜测---能够被切片包含的半径最大的圆的半径等于原始球（形成包络的球） 的半径。

　　于是我们开始了分头的工作，一方面一个人去证明这个结论。另一方面，开始编程实现这个想法。

　　在编写程序的过程中，我们还延升出了两个假设：可以被切片包含的圆的半径一定小于等于原始球的半径；不能被包含于切片的圆的半径一定大于原始球的半径。呵呵，利用这两个假设，就很容易的用二分法搞定了这个程序。不过程序运行起来可不轻松。我们把程序分到三个机子上工作，每一个机子上算一部分图，这也算是并行式算法了吧(并行算法可是东点军校的招版菜)。就是这么算，也用了一个晚上的时间。在其间，我们还修改了一点算法，重新算了一遍。的确，算法是要不断改进的，请看这句:[因为所给数据精度有限，所以包含于切片中的以原始球的半径为半径的圆可能不止一个]，这就是在算法实现过程中发现的。一开始，是很难想到这些细节的。

　　还提一个细节，用Windows console程序，或是用Dos程序(turbo c)编写这个程序很难。因为我们最小就要用到512*512的矩阵，在算法编写的过程中，为了方便，还会用到更大的矩阵。但是Dos是不支持这么大的矩阵数组的，所以建议大家都编写32位的Windows程序。

我们提了这些假设，要完全科学的证明可真不容易。有时候，他认为理所当然的事情，我认为应该证明出来；我认为逻辑混乱的证明，他确认为完全正确。呵呵，于是，我们争论一会儿，证明一会儿，再交流一会儿，再争论。一次，我争论的冒火，心就好像要爆炸了，心想，这竞赛我不做了！我回学校！我为什么要和你们合作？我为什么要迁就你们？我不干了！我强忍着，没有说话，走到窗前，仰头看了看外面的蓝天，突然间想起了那首歌--[蓝蓝的天空，是谁的身体...]，我慢慢的哼起来，一刹那，一切都清静了。我默默的坐到电脑旁，继续编起了程序...

　　第一天晚上睡了4个小时，那个晚上睡了2个小时。算完之后，就只有一天了。第三天晚上，没有睡觉，因为要赶论文。

　　由于我们不怎么会用Word，图表的编号、排版都是纯手工的，太苦了，唯有身在其中方能体会呀。经过了大量体力劳动，论文完工了，来不及仔细检查，就打出来上交了。刚交完，我们就发现了的图的编号命名出了点儿错误，唉，大家谨记我们的教训！

顺便说一点儿做数学建模题的小经验。

1.     随时记下自己的假设。有时候在自己很合理的假设下开始了下一步的工作，我们就应顺手把这个假设给记下来，否则到了最后会搞忘记的。而且这也会让我们的解答更加严谨。

2.随时记录自己的想法，并且不留余地的完全的表达自己的思想。在比赛后，老师讲评优秀论文时，有很多同学常常抱怨，这个想法我也想到了的啊，就是没有表达出来，或是没有表达清楚。但常常就是这一点别人没有表达清楚的东西，促出了一篇优秀论文。

3.要有自己的特色。这么多数学建模竞赛论文，凭什么让老师们投自己一票？当然得有自己的特色了。通俗点儿，就是要有自己的闪光点。

copyleft.中国数学建模网http://www.shumo.com
---------------------------to_be_coninue--------------------------------

altf

不要沉了啊！

newblue

新手,顶一下