文件名称:Knight

  • 所属分类:
  • Windows编程
  • 资源属性:
  • [Windows] [Visual C] [源码]
  • 上传时间:
  • 2012-12-30
  • 文件大小:
  • 355kb
  • 下载次数:
  • 0次
  • 提 供 者:
  • Jim***
  • 相关连接:
  • 下载说明:
  • 别用迅雷下载,失败请重下,重下不扣分!

介绍说明--下载内容均来自于网络,请自行研究使用

1.  问题描述

在一个n*n的棋盘上,一个放在棋盘上某个位置的马是否可以恰好访问每个方格一次,并且回到起始位置上?

2.  回溯法的一般思路

深度优先搜索,若寻找到满足要求的解,则输出;否则推回上一层往下一个方向搜索。

3.  求解问题的回溯算法描述

对于当前所在位置(x,y),依次枚举n个方向搜索,直到找到一组可行解为止。使用剪枝有3处:第一、使用Warnsdorff s rule,枚举当前解得时候优先选择下一步可行步数最少的方向;第二、若第一点中的方向存在不止一个,则优先选择离中心位置较远的方向;第三、每次都从中心点开始出发,求出一条合法路径后再平移映射回待求路径。

4.  算法实现的关键技巧

在棋盘较大的时候,使用递归会使得函数暴栈,故应当使用非递归方法实现。程序实现时应细心记录清楚当前状态在栈顶。

-1 Descr iption of the problem

On the board a n* n chessboard, a horse of a location can be just visit each square once and return to the starting position?

The general idea of backtracking

The depth-first search, to find solutions to meet the requirements, then output Otherwise, push back on the layer down a direction to search.

3 backtracking algorithm for solving the problem described

Sequentially enumeration for the current location (x, y) of the n-th direction search until it finds a set of feasible solutions so far. 3: use pruning first, Warnsdorff s rule, enumerate the current direction when Select Next feasible steps at least Second, if the first point in the direction of the existence of more than one, the Select from the center the direction of the remote location each time starting from the center point of departure, the unknown path mapped back to the pan and then obtained a legitimate path.

Algorithm key skills

In the checkerboard larger when using the recursive ma
(系统自动生成,下载前可以参看下载内容)

下载文件列表





Knight.dsw

Knight.ncb

Knight.opt

Knight.plg

main.cpp

Debug\Knight.exe

.....\Knight.ilk

.....\Knight.pch

.....\Knight.pdb

.....\main.obj

.....\vc60.idb

.....\vc60.pdb

Knight.dsp

Debug

相关说明

  • 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
  • 本站是交换下载平台,提供交流渠道,下载内容来自于网络,除下载问题外,其它问题请自行百度更多...
  • 请直接用浏览器下载本站内容,不要使用迅雷之类的下载软件,用WinRAR最新版进行解压.
  • 如果您发现内容无法下载,请稍后再次尝试;或者到消费记录里找到下载记录反馈给我们.
  • 下载后发现下载的内容跟说明不相乎,请到消费记录里找到下载记录反馈给我们,经确认后退回积分.
  • 如下载前有疑问,可以通过点击"提供者"的名字,查看对方的联系方式,联系对方咨询.

相关评论

暂无评论内容.

发表评论

*主  题:
*内  容:
*验 证 码:

源码中国 www.ymcn.org