摘要：
在本次作业博客里，我将主要阐述作业3的收获。作业3表面是将之前的程序转换为图形界面（之前程序见http://www.cnblogs.com/shone/p/3348372.html），然而本质是:
1. 熟悉模块化、重构、重写
2. 体验结对编程。
作业以上一次的优秀代码为基础，我们首先敲定了/h, /v, /h /v, /a几个模块的算法，然后进行模块化，成为独立的.dll文件，最后使用PYQT写UI并调用前述dll文件，实现原始需求。博客中老师要求提到的内容，以加粗表示。
上图为我们的成果，并以此作为测试通过的象征，其他功能已经通过测试，不在此赘述。
1. 算法相关
算法部分：http://www.cnblogs.com/shone/p/3348372.html 这篇博客里，我不断地使用归结法，解决了 /h, /v, /h /v问题，但是在/a中败下阵来，苦思冥想而不得解。在本期结对编程中，我请教了大神熊英夫，在他老人家的点化下，我们为 /a 问题找到了一个相对满意的算法：
SAA退火算法。退火算法用来提供近似最优解：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。下面代码中，MaxS表示当前状态下选择的最优化状态，RanS表示一个随意拓展的状态：
void SAA(int v,float T,float r,float Tmin)
{
int i,max,maxS=,ranS,tmp,SMR,sum,ri,j;//State
struct link * p;
srand(time());
sum=value[v];
for(i=;i<;i++){visited[i]=;available[i]=;}
topq=;p=g[v];visited[v]=;
while (p!=NULL)
{
if (!visited[p->t]){available[p->t]=;}
p=p->next;
}
while()
{
max=-;
ri=;
for (i=;i<num;i++)
{
if (visited[i]) {continue;}
if (available[i])
{
tmp=estimate(i);
if (tmp>max)
{
max=tmp;
maxS=i;
}
ri++;
}
}
if (ri==) {break;}
ranS=rand()%ri+;
for (i=;i<num;i++)
{
if (available[i]&&!visited[i])
{
ranS--;
if (ranS==)
{
ranS=i;
break;
}
}
}
if (visited[ranS]||!available[ranS]) {return ;}
SMR=;
tmp=estimate(maxS);
if (sum+tmp>totalmax) {totalmax=sum+tmp;pseudoexpand(maxS);}
if (tmp>){SMR=;}
else
{
if (exp(tmp/T)>(rand()%)/10000.0){SMR=;}
}
T*=r;
tmp=SMR==?estimate(maxS)-estimate(ranS):estimate(ranS);
if (sum+estimate(ranS)>totalmax) {totalmax=sum+estimate(ranS);pseudoexpand(ranS);}
if (exp(tmp/T)>(rand()%)/10000.0){SMR=;}
T*=r;
switch(SMR)
{
case :sum+=expand(maxS);break;
case :sum+=expand(ranS);break;
}
if (T<Tmin){break;}
if (sum>totalmax) {totalmax=sum;printf("%d\n",totalmax);for (j=;j<;j++){chosen[j]=visited[j];}}
}
}
上面的代码使用了5次相同的退火过程，每个过程1000*点数V次初始温度。退火算法并不能保证是最优解。下面的patch（）函数从较优解提升为最优解。patch（）函数将正值的点打包，得到局部不可扩充最优解，代码：
void patch()
{
int i,j,sum,yes;
struct link * p,*q;
while()
{
yes = ;
for (i=;i<num;i++)
{
if (value[i]>&&!chosen[i])
{
for (j=;j<;j++) {visited[j]=;}
q = DFS(i);
p = q;
if (p==NULL)
{
continue;
}
sum = p->s;
if (sum>=)
{
yes = ;
while (q!=NULL)
{
chosen[q->t] = ;
q = q->next;
}
}
}
}
if (yes==) {break;}
}
} struct link * DFS(int v)
{
struct link * p;
struct link * q;
struct link * tmp;
int result=-;
p = g[v];
visited[v] = ;
q = (struct link *)malloc(sizeof(struct link));
q->next = NULL;q->s = value[v];q->t = v;
while (p!=NULL)
{
//printf("%d %d %d\n",p->t,visited[p->t],chosen[p->t]);
if (chosen[p->t])
{
visited[v] = ;
q->next = NULL;q->s = value[v];q->t = v;
return q;
}
if (visited[p->t]||value[p->t]>)
{
p=p->next;
continue;
}
if (value[p->t]<&&!chosen[p->t])
{
tmp = DFS(p->t);
if (tmp!=NULL&&result<tmp->s+value[v])
{
result = tmp->s+value[v];
q->next = tmp;
q->s=tmp->s+value[v];
}
}
p = p->next;
}
visited[v] = ;
if (q->next!=NULL) return q;
return NULL;
}
当patch（）可用，我们可以直接得到状态MaxS和RanS。patch（）无用时，最优解已经可以在退火过程被选取。又因为/v, /h只是图形对称的问题，到此与/a有关的问题便得到解决。
2. 模块化与重构
模块化的意义：我们希望将作业2实现的代码独立出来。模块化能够使得之前的命令行与现在的GUI使用同一份代码，这将提高代码的重用性，提高程序开发的效率，让我们少写一点代码，多一点时间打游戏。同时，专事专做，正确率高，在一定程度上也保障了相关代码的安全。
模块化的方式：代码模块化，可以使用class library，dll等方式。这里面，我们选择后者。
我的代码变化在哪里呢？
主要是两方面：
1. 补充\a的算法（见前文）
2. 补充图形用户界面。因为我们的代码都是正确的，考虑到一致性的需要，当我们坐在一起编程时，便选择一人的代码为基础，共同进行改进。总体上来说，各个模块化的函数按需进行重构，涉及到文件读取、控制的代码需要重写，并与GUI结合。
3. 增加对动态链接库的调用。
重构与重写：
这里面，原始的命令行代码分为被调用函数和main函数两部分。前者是模块化的函数，处理\a, \h等等情况，是可共用部分，进行重构，导出到dll中。而main中进行文件读取、对调用函数进行调用的与控制流程相关的代码，则需要根据GUI重写。这里面使用python实现。
3. 我使用的代码规范
我（们）再编程中特意注意了代码规范，尽力写出可读性强、风格良好的代码。代码风格是内在问题，变化最大的是代码外观：排版与格式。
第一方面，我全面阅读了《C语言代码规范》和老师给的博客，并按照其处理缩进、下划线,/类/函数名都用Pascal形式，所有的变量都用Camel形式。
第二方面，由于使用Visual Assist插件，基本的代码缩进、字体、颜色等方面已经可以自动保证。
近期学习到的是老师的博客，在这篇博客中，说明{}各占一行是一个更加清晰的方法，而且不论是VS还是VA插件都默认如此。我之前的习惯是{不独立占行，而}独立占行。我之前认为这样能保证代码的简洁明了。但是博客中提出了“ }else{”这样的例子，这样就不再清晰，因此，我优化了{}的使用。
另外，注释是我忽略的地方，我明确了了什么是有用的注释，以及注释恰当的位置。
4. 结对编程
我们实践了结对编程，结对编程中队员可以不断地彼此提醒、鼓励并进行代码复查，提高代码正确性和编程效率，从开发层次、心理感受、管理上都是很好的方法。
我最开始的小伙伴叫熊英夫，男，我航计院人氏。后来在助教大人的允许下，我们收留了因同伴退课而无家可归的小伙伴柴泽华。柴泽华，男，我航计院人氏，人称柴哥。
我的小伙伴们十分优秀。
优点：
熊英夫是编程的大牛，除了小地方由我们提示外，熊英夫对于算法和Python都是我们中最出色的。除此之外，他还很谦虚，很接受我们的建议，丝毫不因为技术水平高而拒绝交流。最后，他很肯干，写了大比例的代码。
柴哥是个比较搞笑的人，这算一个优点吧。除此之外，他经常提醒我们的进度，并且经常和我交流博客的写法问题。
小伙伴们需要改进的地方：
我们不得不承认谁都有可以改进的地方。首先，我们三人的编程水平都是可以增强的，尤其是\a问题上也是费了很大劲才得到结论。其次，我们对于代码重构的知识了解甚少，做得时候并不十分专业和流畅。第三，我们都有拖延症，不到deadline不提交...
整个过程中，我从小伙伴们学到的最大的收获是退火算法，当然我也发挥了我的价值，比如使用两种语言分别处理算法部分和UI部分。
你的设计是如何保证 不同的 maxsum.exe 命令行最后在一个GUI 的界面显示的? (C++ 的设计模式中有 singleton 的概念, 说明一个类的实例如何在一个进程中保持单例, 我们这里谈的是软件如何在操作系统中保持 singleton)
这样的功能，可以通过建立管道来实现，程序端监听，命令行向程序发送消息，若程序无标签，则新建并显示；若已经有标签，则在其右侧显示出一个标签出来。
但是我们在学习导出dll，调用dll，以及退火算法上耗费了大量的时间，上述的思想已经不再有时间实现..于是我们直接显示了file1和file2两个标签，抛弃命令行，直接在GUI编辑和运行。这里的实现方式是：在UI部分相对简单的前提下（运行效率要求不高），使用PYQT，先使用ERIC4提供的QTdesigner绘制框架再通过ERIC4向python编译，再用自己写的窗口类继承setui。
5.表格
|
Personal Software Process Stages |
时间百分比(%) |
实际花费的时间 (分钟) |
原来估计的时间 (分钟) |
|
|
Planning |
计划 |
|||
|
· Estimate |
· 估计这个任务需要多少时间，把工作细化并大致排序 |
100 |
30 |
30 |
|
Development |
开发 |
80 |
||
|
· Analysis |
· 需求分析 (包括学习新技术) |
200 |
120 |
60 |
|
· Design Spec |
· 生成设计文档 |
0 |
0 |
|
|
· Design Review |
· 设计复审 (和同事审核设计文档) |
同时进行 |
||
|
· Coding Standard |
· 代码规范 (制定合适的规范) |
同时进行 |
||
|
· Design |
· 具体设计 |
|||
|
· Coding |
· 具体编码 |
100 |
180 |
180 |
|
· Code Review |
· 代码复审 |
同时进行 |
||
|
· Test |
· 测试（自我测试，修改代码，提交修改） |
100 |
30 |
30 |
|
Reporting |
总结报告 |
|||
|
· Test Report |
· 测试报告 |
|||
|
· Size Measurement |
· 计算工作量 |
100 |
20 |
20 |
|
· Postmortem & Improvement Plan |
· 事后总结, 并提出改进 |
100 |
60 |
60 |
|
Total |
总计 |
|
总用时 440 |
总估计的用时 500 |