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

因为报名人数很多，已经达到230人，都集中在一个帖子会非常乱，加分贴和讨论帖分开，加分贴只需要截图，版主给大家加学分，讨论帖用于课程lecture，exercise，assignment的讨论~~~请勿发错贴


汇报贴(该贴仅为week4加分贴，课程讨论请点这里)

请完成作业的同学多去讨论帖帮助下需要帮助的同学！！！谢谢！

课程汇总 && 介绍：http://www.1point3acres.com/bbs/thread-78774-1-1.html


本周任务：

Exercise. Drill exercises on the lecture material.

Programming Assignment: 8-Puzzle. Your programming assignment is to implement the famous A* search algorithm to solve a combinatorial problem, and to substantially speed it up with an efficient priority queue implementation.

Job Interview Questions. Algorithmic interview questions based on the lecture material.

Suggested readings. Section 2.4, 3.1, and 3.2 in Algorithms, 4th edition.

截图规范：

把本周的Exercises，Programming Assignment结果截图

会有版主给大家加分，每周1学分（50大米）

终于做完了。感觉week4的工程量很大。课程+编程首先是对优先级队列有了认识啊，真的好牛逼，然后老师是用堆排序来实现的。我被其中那个模拟分子运动的程序震撼了。看也看懂了，其实和8puzzle差不多的思想，把所有的情况都塞进PQ，优先级由碰撞时间长短决定，就和8puzzle中优先级由priority = distance + moves 决定。叫做什么启发式算法。这个东西真的很深奥，我基本不懂。只是有一种感觉，就是虽然是遍历所有的情况，但会让计算机首先模拟那些更加有可能成功的情况。
然后就是对二叉搜索树有了理解。。。套话。只不过以前真的不懂啊。感觉BST比堆排序更牛逼啊。
然后就开始写作业了。这次作业是写的荡气回肠。昨晚先开始写的。然后发现看不懂题目。网上千辛万苦得找到了代码。但是最后决定不看，自己编。因为觉得这个问题很有趣。
从上午11点一直写到了5点。终于把代码写好了。而且自己测试没有问题。但上交的时候才知道自己犯了一个错误。我把优先级计算这些操作都写在了 Board 类里面，导致有些成员我在 Solvable类里面无法调用。
比如 private int priority..... 当时绝望了，不想重写啊。于是把网上的那份代码拿来看。采用了他的一个思想，在Solvable类里面，用一个更大的类来包裹 Board类，并且包含了 priority, previous, moves，这样我就不需要完全重写了。
然后我把Board类里面的有关优先级的东西全部删去，把相邻的点对应的board全部塞进队列而不是MinPQ，因为我在Solvable类里面还会对优先级进行操作，此处不需要多此一举，会影响时间和空间效率。
现在终于完成啦。最开心的时候是代码刚刚写完的时候，然后不停地修改，debug，到现在最终成篇，倒是没多少兴奋的感觉了。
但是我能感觉到自己对于面向对象的理解正在逐步加深。
申请目前并不是很理想，只拿到了两所保底大学的AD。周围的同学都拿到了更好的，而我的，还遥遥无期。
英国这一年我发现自己真的对计算机，软件编程比较感兴趣。原因是自己是一个急性格，有什么想法就想直接尝试，直接调试。前段时间搞单片机。你没有杜邦线不行，你没有对应的接口和通信协议不行，你还得有个示波器或者万能表才能勉强的调试，导师还花了220磅帮我买了一个水压传感器。。。。真的好麻烦。不想软件编程，我只需要一台电脑，大多数我能做到的事情，我立刻就能做到。而且调试环境真的良心。
所以希望，研究生可以在一所计算机强校念，不想着以后的工作问题，只想真正的学习计算机，不用再像现在这样是不是分心了。
加油。

先贴作业：

感觉这次作业算法的部分就直接告诉你了, 难的地方是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分，但是能实现相同的功能，内存占用会少很多....

---

---

timing没有全过。。。并且一开始开始看的时候一点想法都没有，参考了其他人的code才一点点顺下来。。。不兹道算不算作弊了哈
真的只有我一个人觉得assignment好难的么QvQ

交作业~~

这次作业一直有个地方不对，后来用了另一个方法弄好了，但是还是不知道为啥原来的不对，再想想。

这次作业好奇怪，写了好久。。

托到现在终于完成了

有个问题总是没能解决。。。待会发到讨论贴求指导。。。