wcwswswws的日记

wcwswswws

sgu468 就是那到骑士遍历棋盘

      sgu做到290道了,这个月的目标也算达成了。

      这道题就是骑士遍历问题:给定n*n的棋盘,从任意一点出发,按马的规则,求一条遍历棋盘的路径。本质上这是个哈密尔顿路,因为在棋盘上有很多优化的方法。这道题其实也算是论文题,如果知道Warnsdorff’s rule的话就很容易了。如果知道这个启发式规则还不能ac就是在度数相同的点中处理的先后顺序的排法上乱搞,或者继续找论文。我是把输入分成2类,一类是坐标和小的排在前能出解,一类是坐标和大的排在前能出解。

      最后推荐一篇论文"A METHOD FOR FINDING HAMILTON PATHS AND KNIGHT’S TOURS",这个在ACM的数据库中就能查到……

posted on 2011-10-29 00:37 世界厕所所长 阅读(292) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理