结对编程作业

博客链接

Github项目地址

AI/大比拼接口+原型设计仓库地址（供测试使用）
AI代码与原型设计（游戏）实现代码分别存放在两个仓库（Github使用相关，具体commit记录↓）
陈曼的Github项目地址（AI代码）
杨立芬的Github项目地址（原型设计（游戏）实现代码）

具体分工

	AI算法	单元测试	原型设计	UI	博客编写	github
陈曼	✔	✔			✔	✔
杨立芬			✔	✔	✔	✔

2.1- 原型设计

[2.1.1]结对作业的设计说明

原型设计概述
本次设计为一款简单可玩的数字华容道游戏微信小程序，可供各类用户群体用于充实闲暇时间以及锻炼思考能力等，具备计时计数、选择难度（更换阶数）、AI自动复原、查看历史得分的功能。主题色为蓝色，未加入过多的装饰。页面简单，仅包含注册登录页面、游戏页面与历史得分页面。
原型设计总体展示
页面设计说明

注册页面----点击“注册”，进入登录页面
登录页面----点击“允许”，拉取个人信息后可进入“进入游戏”页面
进入游戏页面----点击“START”按钮，进入游戏界面
游戏页面
游戏的各项功能均包含在此页面中：
--点击“开始游戏”，不切换页面，随机生成游戏棋盘，游戏过程中棋盘下方同步进行计时计数。游戏胜利后会弹出控件提示“您已过关啦！”
--点击“重置”，将无序的棋盘恢复到未打乱的状态
--点击“选择难度”，屏幕下方弹出控件，可选择3-8阶的棋盘供游戏使用
--点击“自动”，玩家遇到困难时由进行AI自动复原当前棋盘
--点击“历史得分”，跳转进入历史得分页面，即可显示历史得分（包括步数与耗时）。历史得分按照每10分一档依次分为“永恒钻石”“尊贵铂金”“荣耀黄金”“秩序白银”“倔强青铜”五个段位。

部分功能展现

难度选择--3-8阶棋盘可供选择
历史得分--可查看往次游戏的历史得分
AI自动复原--由AI帮助玩家复原当前棋盘
棋盘重置--将打乱的棋盘复原为有序的状态

[2.1.2]原型设计工具

MOCKINGBOT(墨刀)
墨刀是一款在线原型设计与协同工具，能够搭建产品原型，演示项目效果。墨刀同时也是协作平台，项目成员可以协作编辑、审阅。

[2.1.3]描述结对的过程及展示结对照片

结对过程
这学期开学之前互相躺在对方的好友列表里，没有见过面，老师布置完结对作业后，一方收到一条来自未来队友的邀请，然后就结为队友啦。过程中约着一起出门讨论、做任务。线上也会交流讨论，有了一个huofa
结对照片

遇到的困难及解决办法

困难描述
1.历史得分功能的实现遇难，查找了无数资料，尝试了cookies、文件读写等方法都没有成功。
2.原型设计进度缓慢，第一次使用原型设计工具，对于各种操作不熟练，且由于没有提前做好设计工作，导致工作量加大
解决尝试
1.自己的解决尝试当然就是不断地查资料试错，最后询问了同学后尝试使用数据缓存的方式，同样也是不断地面向百度，不断地尝试。
2.后续的工作提前做好设计，多练习。
是否解决

已解决（功能简略，还需改进
已解决，后期使用熟练，效率也高了

有何收获
独立解决问题的能力增强了，完成这次作业的过程中没有人细致的教，都靠自己尝试，熬了很多的夜，但好在最后实现了。最终的成品并没有想象中的好，这也是自己需要继续努力的方向。同时，也让自己注意到自身统筹能力还是不够，想一部分做一部分，徒增工作量。

2.2 - AI与原型设计实现

[2.2.1]代码实现思路：

网络接口的使用
- Postman测试工具的使用：
  参考资料：https://www.jianshu.com/p/97ba64888894
- Java后端Get请求、Post请求：
  参考资料：https://blog.csdn.net/brushli/article/details/18075321

从接口获取题目。

public String urlAnalysis() throws IOException {
        String result="";
        URL url=new URL(stuid);
        HttpURLConnection httpConn=(HttpURLConnection) url.openConnection();
        httpConn.setConnectTimeout(3000);
        httpConn.setDoInput(true);
        httpConn.setRequestMethod("GET");
        int code = httpConn.getResponseCode();
        if (code == HttpURLConnection.HTTP_OK) {
            InputStream inputStream = httpConn.getInputStream();
            // 创建字节数组输出流，用来输出读取到的内容
            ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
            // 创建缓存大小
            byte[] buffer = new byte[1024];
            int len = -1;// 设置读取的长度
            while ((len = inputStream.read(buffer)) != -1) {// 当输入流中没有数据时，返回-1
                outputStream.write(buffer, 0, len);
            }
            // 将数组转成字符串
            result = outputStream.toString();
            //System.out.println(result);
            inputStream.close();
            outputStream.close();
        }
        return result;
    }

提交答案。

    public static String sendRequestManager(String url, String body) throws IOException {
        StringBuilder sb = new StringBuilder();
        String result = "";
        BufferedWriter writer = null;
        BufferedReader bd = null;

        URL u = new URL(url);
        HttpURLConnection hc = (HttpURLConnection) u.openConnection();
        hc.setRequestMethod("POST");
        hc.setConnectTimeout(5000);
        hc.setReadTimeout(5000);
        hc.setRequestProperty("Content-Type", "application/Json; charset=UTF-8");
        hc.setDoInput(true);
        hc.setDoOutput(true);

        try {
            writer = new BufferedWriter(new OutputStreamWriter(hc.getOutputStream(), "UTF-8"));
            writer.write(body);
            writer.close();

            if (hc.getResponseCode() == 200){
                bd = new BufferedReader(new InputStreamReader(hc.getInputStream(), "utf-8"));
                String s = null;
                while ((s = bd.readLine()) != null) {
                    sb.append(s);
                }
                bd.close();
            }else if (hc.getResponseCode() == 301 || hc.getResponseCode() == 302) {
                // 得到重定向的地址
                String location = hc.getHeaderField("Location");
                URL u1 = new URL(location);
                HttpURLConnection hc1 = (HttpURLConnection) u1.openConnection();
                hc1.setRequestMethod("POST");
                hc1.setConnectTimeout(5000);
                hc1.setReadTimeout(5000);
                if (hc1.getResponseCode() == 200) {
                    bd = new BufferedReader(new InputStreamReader(hc1.getInputStream(), "utf-8"));
                    String s = null;
                    while ((s = bd.readLine()) != null) {
                        sb.append(s);
                    }
                    bd.close();
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if (bd != null) {
                bd.close();
            }
            if (writer != null) {
                writer.close();
            }
        }
        result = sb.toString();
        System.out.println(result);
        return result;
    }

代码组织与内部实现设计（类图）

1.Analysis包：

- URLAnalysis类：包含stuid数据变量，urlAnalysis方法，从接口获取题目，返回一个字符串。
- JSONAnalysis类：包含jsonAnalysis方法，处理json。把获得的参数存入数据变量img，uuid，step，swap。
- BaseUtil类：处理base64编码。包含GenerateImage方法，base64编码转为图像，save_problemimage方法保存从接口获取的问题图片。
- PostAnswer类：Post请求提交答案。
  ImageUtil包：
- BaseImages类：包含静态代码块和静态数据，类加载时完成图像处理。
- ImageToBufferedImage类：包含方法把Image转为BufferedImage。
- CutImage类：把一张图切9份。
- CmpImage类：对比图片。
- ImageToMat类：图片转矩阵。
  Puzzle包：
- Main类：主函数。
- playPuzzle类：传入问题序列，获得解。
说明算法的关键与关键实现部分流程图
- 核心算法-bfshash
  bfs搜索，用哈希（HashMap）判重，优化后加入启发式搜索。
- 流程图
- 首先，每个状态用int表示，用Map<Integer, Boolean>mymap记录状态是否出现过，用启发式搜素，每个状态设置估价函数，bfsHash方法传入一个开始状态和空格位置，向可移动的方向广度搜索，如果移动后的状态未出现过就加入优先队列（优先队列按估价函数排序），每次循环从优先队列中取出估价值最高的状态，继续进行广度搜索，直到到达目标状态。
- 启发式搜索：
- A算法：参考资料：人工智能-马少平P25
估价函数f(n)=g(n)+h(n)，g(n)为从初始状态到当前状态的步数，h(n)为当前状态不在位的块数。（书上的目标序列为123804765）
已知g(n)比例越大，越倾向广度优先，广度优先找的一定是最优解；h(n)比例越大，越倾向贪心，效率更高，最优性下降，应对h(n)进行限制，使最优性和效率平衡。
- A*算法：参考资料：人工智能-马少平P41

估价函数f(n)=g(n)+h(n)，g(n)为从初始状态到当前状态的步数，h(n)为每一个将牌与其目标位置之间的曼哈顿距离。（原书G、I有印刷错误）

- 加入强制交换：先记录到目前状态的操作序列。每次循环先取出状态节点，然后判断是否达到强制交换步数，若达到则进行强制交换，换完判断该状态是否有解。
- 如何判断是否有解：该状态的逆序对数若为偶数则有解，若为奇数则无解，注意判断时去除0（空格）。
- 加入自由交换：当强制状态无解情况下才进行自由交换，所以自由交换一定要改变状态的逆序对数奇偶性，当两个互换位置的差值为1,3,5,7时才能互换。在可以互换的基础上，计算每个互换方案的估价值，取估价值最高的方案作为自由交换策略。
- 交换后：若交换后直接达到目标状态，需要在操作序列里加一个任意字符，因为达到目标状态的这一步是没有前一步操作的，返回的操作序列步数少了一步。（虽然手动测试是可以还原目标的）若交换后未达到目标状态，清空优先队列和记录操作序列的Map，这是为了防止出现交换后向可移动的方向交换的序列都在之前出现过，会导致无解。把当前状态放入优先队列，继续启发式搜索，直到达到目标状态。
贴出你认为重要的/有价值的代码片段，并解释
- 强制交换和自由交换。

if(JSONAnalysis.step==tempN.step){//步数从0开始算
    JSONAnalysis.step=-1;//保证只出现一次强制交换
    findRoute(tempN.num);//记录前半段路径

    arr=Integer.toString(tempN.num);
    if(arr.length()<9)  arr="0"+arr;//空格在最前时
    arr=swap(arr.toCharArray(),JSONAnalysis.swap.get(0)-1,JSONAnalysis.swap.get(1)-1);
    if(!haveAnswer()){//强制交换无解
        best=makeBestExchange();//找自由交换的最好方案
        arr=swap(arr.toCharArray(),best[0],best[1]);
    }
    if(arr.equals(brr)){//交换后为目标状态
        route.put(des,-1);
        operation_to_the_state.put(des,null);
        special_add=1;//特判
        return tempN.step+1;
    }
    que.clear();//清空队列，从当前状态重新开始搜索
    mymap.clear();//交换后的状态向所有方向交换的状态可能在之前出现过
    operation_to_the_state.clear();
    route.clear();//若不清空会导致无解
    int t=Integer.parseInt(arr);
    int zero=0;
    for(int i=0;i<arr.length();i++)
        if(arr.charAt(i)=='0') {
            zero=i;
            break;
        }
    Node tempM=new Node(t,tempN.step+1,zero,'f');
    route.put(t,-1);
    mymap.put(t,true);
    que.add(tempM);//放入新的开始节点
    continue;
}

性能分析与改进
- 改进1：核心算法bfs改进到启发式A算法，上述已说明。
- 改进2：关于图像处理，开始用直方图原理，getData方法可以获得两张图的相似度。占了70%。

改成cmpimg方法。图片是完全相同的，没必要获得相似度，只要对比每个像素是否相同，若出现不同像素返回false。改进后的图像对比块只占了33%，效果拔群。

- 改进3：请求前先处理图片，加入静态代码块。静态代码块在类被加载的时候就运行了，而且只运行一次，并且优先于各种代码块以及构造函数。
- 改进4：A算法改进到A*，扩展结点数更少，此时算法admissible，必定获得最优解，同时效率更高。

3、4同时进行，性能分析为：

图片对比占到40%，但不是负优化，因为A*的改进让核心玩法块占用时间更少了，接近0%。
另附此时返回所用时间：

从7s优化到1s。

- 改进5：发现在循环测试中只有第一次请求需要3-5s
  
  测试性能后发现JFrame初始化很慢，于是优化了切割图像的方法，不再需要继承JFrame，用BufferedImage自带的getSubImage分割。这边应该还有静态代码块调用顺序的问题，当时没发现。
- 改进6：String.format方法效率很低，主要在估价函数里用到。直接换掉，整型循环除10取最后一位算估价值也一样。
- 改进7：图片比较中一个个像素比较改为每5个像素比较。
展示出项目部分单元测试代码，并说明测试的函数，构造测试数据的思路

@org.junit.Test
    public void requestTest() throws IOException {
        new BaseImages();
        JSONAnalysis js=new JSONAnalysis();
        ImageToMat im=new ImageToMat();
        PlayPuzzle pl=new PlayPuzzle();
        js.jsonAnalysis();//获得题目
        pl.playPuzzle(im.findAnsImage());//获得答案
        Assert.assertEquals("true",new PostAnswer().postAnswer().getString("score"));

    }

测试核心算法bfshash和图片处理cmpimg函数。
测试覆盖率：

@org.junit.Test
    public void playPuzzleTest() throws Exception {
            int[] mat={0,3,1,9,4,7,5,0,2,8};
            JSONAnalysis.step=17;
            JSONAnalysis.swap=new ArrayList<>();
            JSONAnalysis.swap.add(1);
            JSONAnalysis.swap.add(1);
            PlayPuzzle p=new PlayPuzzle();
            p.playPuzzle(mat);
        }

测试playPuzzle。
测试覆盖率：

[2.2.2]贴出Github的代码签入记录，合理记录commit信息。(2分）

[2.2.3]遇到的代码模块异常或结对困难及解决方法。(4分）

问题描述

1.用BufferedImage存图像数组，循环测试的时候会一直切割一张图。

2.static代码块不最先执行，请求发送后才执行完。

解决尝试

1.用Image。

2.在发送请求之前调用一次静态代码块所在对象的构造函数。

是否解决

已解决。

有何收获

1.Image是一个抽象类，BufferedImage是Image的一个具体实现，BufferedImage生成的图片在内存里有一个图像缓冲区。

2.参考static执行顺序详解：https://twocups.cn/index.php/2020/01/22/16/

[2.2.4]评价你的队友。(2分）

值得学习的地方

有责任心，做事踏实认真。原型设计、小程序的界面和功能也实现的很完善。

需要改进的地方

可以多看点算法~

[2.2.5]提供此次结对作业的PSP和学习进度条

PSP表格

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planning	计划
· Estimate	· 估计这个任务需要多少时间	10	10
Development	开发
Analysis	· 需求分析 (包括学习新技术)	720	1200
· Design Spec	· 生成设计文档	60	90
· Design Review	· 设计复审	40	60
· Coding Standard	· 代码规范 (为目前的开发制定合适的规范)	20	20
· Design	· 具体设计	360	120
· Coding	· 具体编码	600	720
· Code Review	· 代码复审	40	60
· Test	· 测试（自我测试，修改代码，提交修改）	450	500
Reporting	报告
· Test Report	· 测试报告	40	30
· Size Measurement	· 计算工作量	15	15
· Postmortem & Process Improvement Plan	· 事后总结, 并提出过程改进计划	30	60
	合计	2385	2885

学习进度条

第N周	新增代码（行）	累计代码（行）	累计学习耗时（小时）	重要成长
第1周	169	169	10	postman使用，java html接口请求
第2周	330	499	14	bfs，A、A*算法，如何构造估价函数
第3周	229	728	20	图像处理方式，BufferedImage和Image类的区别，用getSubimage切割图像，getRGB获得像素rgb值
第4周	189	917	20	静态代码块使用，github徽章、分支管理、pull request使用