|
 |
| 4月6日,4月13日 贪吃蛇问题 王晓东教授 |
【问题简述】给定游戏的迷宫结构、贪吃蛇的初始位置以及食物的位置序列(x1,y1),...,(xk,yk)等初始参数
1、编程找出贪吃蛇依序吃到所有食物的最优游动序列。这里的最优是指游动序列的长度最短或转向次数最少
2、贪吃蛇吃到食物的顺序不受限制，编程找出贪吃蛇吃到所有食物的最优游动序列。这里的最优是指游动序列的长度最短或转向次数最少
3、考虑食物位置的随机性，设计出在食物位置随机生成情况下，贪吃蛇以最快速度依序吃到最多食物的算法。
★讨论结果： 解题报告下载
对于无障碍的情况，严寒凝找到了求可行解的构造法；当蛇身长度不超过min(m,n)时，李榕滨找到了求最少转弯数的O(n^4)的动态规划算法。有兴趣的同学可以进一步考虑用分治策略将其推广到有障碍的情况。
有障碍情况下的最优解目前为止没有想出很好的办法，只能宽度优先搜索。但由于本题的状态空间庞大，即使按位存储蛇的形状，也只能做到20个长度。在结果步数不多的情况下可以考虑用迭代式的深度优先，节省空间耗费。
当食物随机出现时，可以考虑使用遗传规划，参见严寒凝的解题报告。
★相关问题：两道与本题类似的题目：uva 841 Snake zju1361 Holedox
|
| 4月20日,4月27日 Petri网 刘传才博士 |
|
讲义及作业下载
|
| 5月4日,5月11日 图论 陈国龙博士 |
1、街道清扫规划 2、灾情巡视路线问题 3、计算机网络的最短传输时间
很好的图论题，就是复杂了一些，具体情况参见解题报告，也欢迎讨论。
|
| 5月18日,5月25日 数据挖掘 叶东毅教授 |
|
决策信息表无损压缩问题，考虑相容与不相容两种情况，设计求核属性的算法，求最小压缩子集的近似算法以及求所有压缩子集的算法（可以转化为范式化简问题）
|
| 6月1日,6月8日 组合计数 胡山立教授 |
比较基础的组合计数问题，包括Catalan数及其推广、差分多项式、母函数等内容。这里给出李翼的解答。
★未解决的问题：大城市公务员在他家(A)以北m个街区,以东n个街区(B)工作，假设街区成正方块网格，如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
|
| 6月29日,7月5日 TSP问题 朱文兴博士 |
TSP问题的各种多项式时间可解情况分析，k-pyramid环游的多项式算法及基于PQ树的环游问题。
参考文献：Combinatorial Approximation Algorithms
|
| 7月8日 福州一中模拟考试 |
| 7月14日 师大附中模拟考试 |
| 7月17日 福州八中模拟考试 |
|
|
|
为了备战NOI2003，提高福建省代表队选手的水平，福建省计算机奥林匹克竞赛科学委员会从今年4月份起对福建省代表队选手进行培训。培训采用授课、讨论和测试相结合的方式进行。本次培训欢迎非省队选手参加，欢迎大家积极参与讨论。如果您有更优的算法，请告诉我。
| |
|
