传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1589|回复: 10
收起左侧

2016 9月 Algorithm,Part1 week4 作业帖

[复制链接] |试试Instant~ |关注本帖
minchen57 发表于 2016-9-7 10:07:31 | 显示全部楼层 |阅读模式

[Coursera]Algorithm,Part1 #4 - 2016-09-02@Princeton University

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

第四次作业,8 Puzzle 作业入口

farewell 发表于 2016-9-28 13:11:29 | 显示全部楼层
1.二维数组复制时复制了reference,temp = blocks时,如果改变temp,blocks也会相应改变,因此要逐项来进行复制
2.为了优化计算过程,排除重复的移动,node中有prev,当当前node的neighbor与prev相同时,该node不被放入PQ,将priority最小的node取出,放入其neighbor,重复此过程
3.判断是否有解的方法比较tricky,通过twin来判断是否有解,当twin有解时,说明该问题无解,在node中加入标志位,如果最后得到的minPQ的标记位是twin的话,说明twin有解,因此该问题无解
Puzzle.png

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

youngyang 发表于 2016-9-24 14:34:28 | 显示全部楼层
读了好久才把A* Search的思路读懂。。
捕获.PNG
回复 支持 反对

使用道具 举报

nhqgoal 发表于 2016-9-28 23:14:19 | 显示全部楼层
用一个长度N^2的char[]表示block, 给Board加一个private Board(char[] blocks){}
回复 支持 反对

使用道具 举报

zzdsg 发表于 2016-9-30 17:23:34 | 显示全部楼层
实在是太不容易了TAT
无标题.png
回复 支持 反对

使用道具 举报

 楼主| minchen57 发表于 2016-10-2 03:24:43 | 显示全部楼层
该用。.equals() 而错用成 =, debug了好久。很奇怪,有一次提交满分后,再次提交居然只有66.。。。搞不明白。看report,说的是Board.java的正确率有问题,test run不完。不合理啊。
anyway 交作业
QQ截图20161001142241.png

回复 支持 反对

使用道具 举报

nsc 发表于 2016-11-1 12:05:25 | 显示全部楼层
week4作业 用时太久 虽然是过了 但还有点小bug 先提交吧
Untitled.png
回复 支持 反对

使用道具 举报

SinkFloat 发表于 2017-3-19 09:41:30 | 显示全部楼层
最后一个case需要16s超时了,不知道怎么再优化,先这样了
8puzzle.png
回复 支持 反对

使用道具 举报

向上的牛牛 发表于 2017-3-30 21:04:10 | 显示全部楼层
有几个test一直报错:

OperationCountLimitExceededException
Number of calls to methods in Board exceeds limit: 100000000

不知道问题出在哪儿...
如何优化?
回复 支持 反对

使用道具 举报

向上的牛牛 发表于 2017-3-30 22:52:10 | 显示全部楼层
交作业.....折腾了好久......
week4.png
回复 支持 反对

使用道具 举报

lavender41 发表于 2017-7-12 02:10:30 | 显示全部楼层
好像应该发在这里

只有 cache manhattan distance 在 search node 中 才能过 最后一个 timing test;
break tie 可以用 manhattan distance;
通过在search node 中加入标记项可以用一个 pq 实现,两个也可以过所有 test;

Week4.PNG
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-23 04:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表