[Coursera] Algorithms (princeton) (week4) 加分贴

终于赶上进度了~~

赶due啊赶due

这次作业的锻炼很大！求加分哦，前几次的也没有加呢！

先贴作业：

感觉这次作业算法的部分就直接告诉你了, 难的地方是java programming, software engineering这些....

最麻烦的是Board里面没有moves 和 previous的getter，所以要在Solver里面实现
我的方法是用一个wrapper class：Node，包括Board board，Node prev和int moves。用Board 的neighbors()来实现Solver里面的Node Iterator，然后这个新Iterator的next()里面加入更新prev和moves的内容。

总结了一下optimization的点（这些点里面只要实现很少一部分就能有100分了）：
1. 1d array 代替 2d array，char 代替 int；
－其实用short也是差不多的内存
2. Critical optimization
－因为要筛掉的都是search node的几个相邻board，所以实际上只需要看0的位置就行了。0的位置可以cache在Board类里面，equals()里面可以首先通过0的坐标排除一道，这样比如4个neighbors, 3个不和previous node相同的O(1)时间就可以被equals()否决掉，最后相同的那个才需要O(N^2)时间(需要跑完equals())。从～4N^2 到 ～N^2,快了大概4倍。
－其实完全可以全部都只用0来check，一共只需O(1)时间，但那样equals()的含义就变了；或者新写个方法zeroPositionEquals()；either way API is broken...
－即使花O(N^2)时间来决定每个neighbor是否进入priority queue也是值得的，因为总的算法复杂度主要取决于game tree的复杂度，做这些pruning的工作，尤其是砍掉较高高度的枝叶时，可以提高很多效率。
3. isSolvable()中initial和twin，用一个pq而不是两个
－我还没想出来如何实现，请大家指教！
4. Cache manhattan/hamming distance in Board
－移动格子的时候用O(1)的时间更新一下,只有initial才需要用O(N^2)时间算出来。
5. Break ties
－Manhattan相同的时候，比较hamming。或其他方法，请大家指教！
6. Forget about API，moves和previous写在Board里
－这样作业当然是0分，但是能实现相同的功能，内存占用会少很多....

改不动了先这样啦~memory2维转1维我看到了一堆麻烦......

debug到快死。。

作业一次比一次难了，这次作业让我知道了什么叫垃圾代码，就是思路一样但是实现起来用时一个火箭 一个拖拉机。。。。（还花了这么久，自己代码能力还是太垃圾了自己的写的timing挂了大半，最后还是参考github上面添加了API才通过。