201871030125-王芬 实验三 结对项目—《D{0-1}KP 实例数据集算法实验平台》项目报告

实验三 软件工程结对项目

项目	内容
课程班级博客链接	https://edu.cnblogs.com/campus/xbsf/2018CST
这个作业要求链接	https://www.cnblogs.com/nwnu-daizh/p/14604444.html
我的课程学习目标	（1）掌握软件项目结对开发流程；（2）掌握Github发布软件项目的操作方法。
这个作业在哪些方面帮助我实现学习目标	（1）在程序设计方面提高了自己的编程能力；（2）让我了解了团队协作、分工的重要性；（3）结对编程、和同伴如何分工以及与同伴如何更好的交流。
结对方学号-姓名	201871030108-冯永萍
结对方本次博客作业链接	https://www.cnblogs.com/fengyongping/p/14655683.html
本项目Github的仓库链接地址	https://github.com/fengyongping1120/d01fypwf

任务1：阅读《现代软件工程—构建之法》第3-4章内容，理解并掌握代码风格规范、代码设计规范、代码复审、结对编程概念；

（1）代码风格规范：主要是文字上的规定。代码风格的原则是：简明、易读、无二义性，包括对于缩进、行宽、括号、分行、命名、下划线、注释、大小写以及断行与空白的{}行的处理；

(2)代码设计规范：牵扯到程序设计、模块之间的关系、设计模式等。比如针对函数，他的最重要的原则就是：只做一件事，并且要做好。可以使用goto实现单一的出口。还有错误处理方面的一些内容，比如断言的正确使用等规范。

(3)代码复审：看代码是否在代码规范的框架内正确地解决了问题。代码复审的三种形式：自我复审、同伴复审、团队复审。

进行代码复审的目的：

• 找出代码的错误，例如：
  • 编码错误
  • 不符合团队代码规范、
• 发现逻辑错误，程序可以编译通过，但代码逻辑是错的
• 发现算法错误
• 发现潜在的错误和回归性的错误——当前的修改导致以前修复的缺陷又重新出现
• 发现可能需要改进的地方
• 教育（互相教育）开发人员，传授经验，让更多的成员熟悉项目各部分的代码，同时熟悉和应用相关领域相关的实际知识。

(4)结对编程：是指一起分析，一起设计，一起写测试用例，一起做单元测试，一起做集成测试，一起写文档等等。

任务2：两两*结对，对结对方《实验二 软件工程个人项目》的项目成果进行评价，具体要求如下：

（1）对项目博文作业进行阅读并进行评论，评论要点包括：博文结构、博文内容、博文结构与PSP中“任务内容”列的关系、PSP中“计划共完成需要的时间”与“实际完成需要的时间”两列数据的差异化分析与原因探究，将以上评论内容发布到博客评论区。

对方博客链接： https://www.cnblogs.com/fengyongping/p/14598266.html

博客评论截图：

（2）克隆结对方项目源码到本地机器，阅读并测试运行代码，参照《现代软件工程—构建之法》4.4.3节核查表复审同伴项目代码并记录。

（3）依据复审结果尝试利用github的Fork、Clone、Push、Pull request、Merge pull request等操作对同伴个人项目仓库的源码进行合作修改。

项目的开发者：冯永萍

项目的复审者：王芬

1、概要部分

（1）代码符合需求和规格说明么？

代码符合需求

（2）代码设计是否考虑周全？

考虑周全

（3）代码可读性如何？

可以顺利读下去

（4）代码容易维护么？

比较容易维护

（5）代码的每一行都执行并检查过了吗？

是的，都可以执行

2．设计规范部分

（1）设计是否遵从已知的设计模式或项目中常用的模式？

• 遵从

（2）有没有硬编码或字符串/数字等存在？

• 没有

（3）代码有没有依赖于某一平台，是否会影响将来的移植（如Win32到Win64）？

• 没有，不会影响移植，任何平台都可以

（4）开发者新写的代码能否用已有的Library/SDK/Framework中的功能实现？在本项目中是否存在类似的功能可以调用而不用全部重新实现？

• 可以用
• 存在，有些代码是可以调用的

（5）有没有无用的代码可以清除？（很多人想保留尽可能多的代码，因为以后可能会用上，这样导致程序文件中有很多注释掉的代码，这些代码都可以删除，因为源代码控制已经保存了原来的老代码）

• 基本清除完毕了

3．代码规范部分

修改的部分符合代码标准和风格么?

• 符合，全都按照代码标准修改的

4．具体代码部分

（1）有没有对错误进行处理？对于调用的外部函数，是否检查了返回值或处理了异常？

• 对错误都进行了处理，没有异常

（2）参数传递有无错误，字符串的长度是字节的长度还是字符（可能是单/双字节）的长度，是以0开始计数还是以1开始计数？

• 无错误
• 本项目中字符串以0开始计数

（3）对资源的利用是在哪里申请，在哪里释放的？有没有可能导致资源泄露（内存、文件、各种GUI资源、数据库访问的连接，等等）？有没有优化的空间？

• 在对数据库进行操作之前申请数据库连接资源，操作完毕之后释放申请的资源
• 不会导致资源泄露
• 可以优化使用断言来保证我们认为不变的条件

（4）数据结构中有没有用不到的元素？

• 没有

5．效能

（1）代码的效能（Performance）如何？最坏的情况如何？

• 达到了具体任务的要求

（2）代码中，特别是循环中是否有明显可优化的部分（C++中反复创建类，C#中 string 的操作是否能用StringBuilder 来优化）？

• 没有，已经比较优化了

（3）对于系统和网络调用是否会超时？如何处理?

• 目前没有出现超时的现象。假如出现了我们会杀毒；整理系统，减少运行的进程，释放内存、cpu，释放c盘空间；

6．可读性

代码可读性如何？有没有足够的注释？

• 可以顺利读取
• 代码有足够的注释让我们读懂

7．可测试性

代码是否需要更新或创建新的单元测试？针对特定领域的开发（如数据库、网页、多线程等），可以整理专门的核查表。

• 可以继续开发，摆脱传统的命令行方式，更为实用

结对方项目仓库中的Fork、Clone、Push、Pull request、Merge pull request日志数据

• 已完成

任务3：采用两人结对编程方式，设计开发一款D{0-1}KP 实例数据集算法实验平台，使之具有以下功能：

（1）平台基础功能：实验二 任务3；

（2）D{0-1}KP 实例数据集需存储在数据库；

（3）平台可动态嵌入任何一个有效的D{0-1}KP 实例求解算法，并保存算法实验日志数据；

（4）人机交互界面要求为GUI界面（WEB页面、APP页面都可）；

（5）查阅资料，设计遗传算法求解D{0-1}KP，并利用此算法测试要求（3）；

（6）附加功能：除（1）-（5）外的任意有效平台功能实现。

一、需求分析

• 折扣0/1背包问题，动态规划算法，回溯算法；

• 从定的文件中读取出正确的数据并保存；

• 读取数据并对数据进行处理，需要用到数据的切片技术；

• 绘制数据散点图要用到数据的可视化技术；

• 将求解出的数据保存或导出文件

• D{0-1}KP 实例数据集需存储在数据库；

• 平台可动态嵌入任何一个有效的D{0-1}KP 实例求解算法，并保存算法实验日志数据；

• 人机交互界面要求为GUI界面。

二、功能设计

• 绘制任意一组D{0-1}KP数据以重量为横轴、价值为纵轴的数据散点图；
• 对任意一组D{0-1}KP数据按项集第三项的价值:重量比进行非递增排序；
• 用户能够自主选择动态规划算法、回溯算法求解指定D{0-1} KP数据的最优解和求解时间（以秒为单位）；
• 任意一组D{0-1} KP数据的最优解、求解时间和解向量

三、设计实现

• 在实验过程中，此次实验要求的技术与我在此之前的掌握的技术有一定差距。所以我复习了大学三年级第一学期在《算法设计与分析》课程中学习到的动态规划算法与回溯算法求解0/1背包问题的内容，循序渐进，推进实验的进程。

1、动态规划算法

• 动态规划算法的核心思想是：
  • 将大问题划分为小问题进行解决，从而一步一步获得最优解的处理算法。
  • 动态规划算法与分治算法类似，其基本思想也是将代求问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
  • 与分治算法不同的是，适合于动态规划求解的问题，经分解得到的子问题往往不是互相独立的，即下一个子阶段的求解过程是建立在上一个子阶段的解的基础上，进行进一步的求解。

2、回溯算法

• 顾名思义，回溯法一个很显著的特征就是回溯，即在处理完某种情况或出现不能继续进行的情况时，要退回到之前的某个“交叉口”，处理另一种可能。

• 回溯法是一种非常有效的方法，有“通用的解题法”之称。它有点像穷举法，但是更带有跳跃性和系统性，他可以系统性的搜索一个问题的所有的解和任一解。回溯法采用的是深度优先策略。通常，回溯法会定义一个解空间，这个解空间通常是以图或树的形式呈现出来的。背包问题的解空间是树的形式，属于深度优先搜索。

• 回溯法在确定了解空间的结构后，从根结点出发，以深度优先的方式搜索整个解空间，此时根结点成为一个活结点，并且成为当前的扩展结点。每次都从扩展结点向纵向搜索新的结点，当算法搜索到了解空间的任一结点，先判断该结点是否肯定不包含问题的解（是否还能或者还有必要继续往下搜索），如果确定不包含问题的解，就逐层回溯；否则，进入子树，继续按照深度优先的策略进行搜索。当回溯到根结点时，说明搜索结束了，此时已经得到了一系列的解，根据需要选择其中的一个或者多个解即可。

• 回溯法解决问题一般分为三个步骤：

  （1）针对所给问题，定义问题的解空间；

  （2）确定易于搜索的解空间结构；

  （3）以深度优先的方式搜索解空间。

3、遗传算法

• 查阅资料，设计遗传算法求解D{0-1}KP，并利用此算法测试要求（3）；

百度百科中对于遗传算法的解释：https://baike.baidu.com/item/遗传算法/838140?fr=aladdin。

遗传算法（Genetic Algorithms ）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是在70年代初期由美国密西根（ Michigan ）大学的霍兰（ Holland ）教授发展起来的。1975年霍兰教授发表了第一本比较系统论述遗传算法的专著《自然系统与人工系统中的适应性》（《 Adaptationin Natural and Artificial Systems 》）。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。

遗传火算法的实施步骤如下（以目标函数求最小为例）。

第一步：初始化 t←0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体P（t）；

第二步：个体评价 计算P（t）中各个个体的适应度；

第三步：选择运算 将选择算子作用于群体；

第四步：交叉运算 将交叉算子作用于群体；

第五步：变异运算 将变异算子作用于群体，并通过以上运算得到下一代群体P（t + 1）;

第六步：终止条件判断 t≦T：t← t+1 转到步骤2；t>T：终止 输出解。

遗传算法应用步骤：

确定决策变量及各种约束条件，即个体的表现型X和问题的解空间；

建立优化模型 （目标函数最大OR 最小） 数学描述形式 量化方法；

染色体编码方法；

解码方法；

个体适应度的量化评价方法 F(x)

设计遗传算子；

确定有关运行参数。

参考：https://blog.csdn.net/wangqiuyun/article/details/8847307

4、具体要求实现结果及关键代码

项目文件夹基本文件注释如下：

• java文件

• jsp文件

（1）平台基础功能：实验二 任务3；

部分结果截图：

（2）D{0-1}KP 实例数据集需存储在数据库；

结果展示：

代码展示：

        for(int i=1;i<row;i++) {
    		String Row=Integer.toString(i);
    		for(int j=1;j<4;j++) {
	    		String Weight=Integer.toString(weight[i][j]);
			    String Value=Integer.toString(value[i][j]);
				String addsql="INSERT INTO table_kp01(tempname,weight,value) VALUES(?,?,?)";
			    PreparedStatement pst=null;
				pst=conn.prepareStatement(addsql);//预编译SQL
		        pst.setString(1, Row);
				pst.setString(2, Weight);
				pst.setString(3, Value);
				pst.executeUpdate();//执行SQl语句
		    }
		}

（3）平台可动态嵌入任何一个有效的D{0-1}KP 实例求解算法，并保存算法实验日志数据；

调用算法结果展示：

算法实验日志数据结果展示：

算法实验日志数据部分代码：

<%@page import="org.apache.log4j.Logger" %>
private static Logger log1=Logger.getLogger(RES);
private static Logger log2=Logger.getLogger(RUN_TIME);
log1.debug("最优解:"+res);
out.println("</br>");//换行标签
log2.debug("运行时间:"+run_time+"s");

注：本部分内容参考https://jingyan.baidu.com/article/5bbb5a1b2cd10513eba17992.html。

（4）人机交互界面要求为GUI界面（WEB页面、APP页面都可）；

结果展示：

实现结果：

5、采用汉堡包法实施项目结对中两个人的沟通 ，具体如下：

先来一片面包, 做好铺垫, 例如可以从双方的共同点, 团队共同的愿景讲起, 让对方觉得处于一个安全的环境。

再把肉放上，这时就可以把 建设性的意见 (constructive feedback) 油炸好, 加上生菜, 佐料等。

怎么准备这块肉也有讲究:

我们常说 [feedback], 但是在提供反馈时, 不宜完全沉溺于过去的陈年谷子烂芝麻， 给别人做评价, 下结论。 这样会造成一种 [你就是做得不好, 我恨你] 的情绪。

我们可以调整一个角度, 把 [feedback], 变成 [feedforward], 强调 [过去你做得不够, 但是我们以后可以做得更好]

在技术团队里, 我们的反馈还是要着重于 [行为和后果] 这一层面, 不要贸然深入到 [习惯和动机], [本质]. 除非情况非常严峻, 需要触动别人内心深处, 让别人悬崖勒马。

然后再一片面包, 盖上。 这时候可以呼应开头, 鼓励对方把工作做好。

6、 描述结对的过程，提供两人在讨论、细化和编程时的结对照片(非摆拍)。

7、提供此次结对作业的PSP。

PSP	任务内容	计划完成所需要的时间（min）	实际完成所需要的时间（min）
Planning	计划	50	45
Estimate	估计这个任务需要多少时间，并规划大致工作步骤	50	45
Development	开发	680	655
Analysis	需求分析（包括学习新技术）	20	20
Design Spec	生成设计文档	20	30
Design Review	设计复审 (和同事审核设计文档)	15	10
Coding Standard	代码规范 (为目前的开发制定合适的规范)	15	15
Design	具体设计	220	180
Coding	具体编码	280	300
Code Review	代码复审	55	50
Test	测试（自我测试，修改代码，提交修改	55	50
Reporting	报告	30	35
Summer	任务+总结	30	35

任务4：完成结对项目报告博文作业（30分，以下给出评分细目）

博文作业格式符合以下要求：

博文名称：学号-姓名 实验三 结对项目—《D{0-1}KP 实例数据集算法实验平台》项目报告（1分）

• 已完成。

实验总结：

  经过这次实验，我发现在真正的结对的情况下，确实会产生1+1>2的情况，因为另一方会从另外一个角度思考，发现对方代码的不足并及时指正。但也存在双方工作没办法平均分配，双方各有擅长的方面，所以在合作时更多的是取长补短，发会合作的优势。

  因为经常进行面对面交流，所以结对编程的效率相对较好。我认为，结对编程还是对项目的有效进行有了非常大的帮助，首先，有明确的分工，代码设计规范等，不断沟通，完善，当存在问题时，不再是一个人闷头苦想，可以进行有效的沟通、交流共同解决问题；两人共同协作，可以更有效的发现已经撰写好的项目中存在的bug，进行修改。

  通过本次实验我对于github的使用有了更深入的了解，也对于结对编程不再是停留在表面上的理解，让我感受到了团队的力量，也能够一定程度上提高编程的效率。