[HomeWork] Algorithms, Part I (week 4)

跟课到Week 4，交完结果，结果发现过去的作业帖直到Week 3，所以自开一帖。一起跟课的同学们加油！本周讲得是Priority Queue，作业要求用其API实现A star algorithm去解决puzzle问题，A star algorithm在wiki上有讲解。
这次的作业可能是前四周中最有趣的一个了。
就我来说，这次课程难点就在与两个：
第一，A star algorithm的各种细节，写代码前犹豫了好久，一直在想delMin后的元素会不会改变reference以及没有集合判断重复，会不会陷入死循环等等；结果写完后发现想多了，delMin后形成的东西可以看作一个tree，其中一个leaf用来当链表的头部，用来追踪到root初始状态的路径，另外几个leaves则储存在PQ中；而由于估值函数=move+启发函数，所以一般不会在回到过去的那些delMin了的元素
第二，Board的Memory，虽然很容易实现n^2的量级，但在n=2，3，4等时候最后的常数总是超过，导致failed。。。这我最后也没解决，怎么使常数小于64 bytes。

楼主你week2的作业有拿满分吗？java不支持范型数组，我用了强制类型转换编译会有warning，就怎么也拿不到满分，请问楼主怎么做的呀？

lwx40115 发表于 2018-3-19 09:13
楼主你week2的作业有拿满分吗？java不支持范型数组，我用了强制类型转换编译会有warning，就怎么也拿不到满 ...

用课上讲得casting的方法定义泛型数组是会在Compilation阶段有warming的，但是应该是不扣分的。你检查一下Correctness、Memory、Timing的测试是不是都过了？

yseLong 发表于 2018-3-19 10:31
用课上讲得casting的方法定义泛型数组是会在Compilation阶段有warming的，但是应该是不扣分的。你检查一 ...

See the Assessment Guide for information on how to interpret this report.

ASSESSMENT SUMMARY

Compilation:  FAILED (0 errors, 4 warnings)
API:          PASSED

Findbugs:     FAILED (1 warning)
PMD:          PASSED
Checkstyle:   FAILED (0 errors, 28 warnings)

Correctness:  43/43 tests passed
Memory:       105/105 tests passed
Timing:       136/136 tests passed

Aggregate score: 95.00%
[Compilation: 5%, API: 5%, Findbugs: 0%, PMD: 0%, Checkstyle: 0%, Correctness: 60%, Memory: 10%, Timing: 20%]

yseLong 发表于 2018-3-19 10:31
用课上讲得casting的方法定义泛型数组是会在Compilation阶段有warming的，但是应该是不扣分的。你检查一 ...

难道是我提交次数太多了嘛……

lwx40115 发表于 2018-3-19 11:24
难道是我提交次数太多了嘛……

Findbugs:     FAILED (1 warning)
这不是测试出bug了嘛

lwx40115 发表于 2018-3-19 11:24
See the Assessment Guide for information on how to interpret this report.

ASSESSMENT SUMMARY

还有就是 Compilation:  FAILED 的话，你得看看除了泛型数组还有什么原因

yseLong 发表于 2018-3-19 12:49
还有就是 Compilation:  FAILED 的话，你得看看除了泛型数组还有什么原因

好的，多谢多谢～