国际象棋中马的周游路线问题新解法

：本文对国际象棋中马的周游路线问题进行了分析，设计了基于回溯法和最优选择法的算法，对回溯过程中不同活结点的通路数量进行排序，并将通路数目最少的活结点作为当前的最优选择，从而进一步提高回溯法的效率。文中给出了算法的具体实现过程，实验结果验证了算法的有效性。

在实际应用中，当要求解国际象棋中某一位置的马，它是否可能只走63 步，就走过除起点外的63 个位置的问题时，通常直接求解是很困难的。原因在于如果直接求解，则无法判断每一步是否为最优通路， 以及在遇到错误通路时不能有折回的余地。所以，本文提出回溯法和最优选择法二者相结合的一种解决方法。回溯法的基本思想是对整个已知的空间进行探索，若在当前所处的结点处仍可搜索到新的结点，则称该结点为活结点， 反之则为死结点。

若遇到死结点， 则应返回到最近的一个活结点处。回溯法即以这种工作方式对通路递归的进行搜索[1,2]。

然而由于题目中涉及的顶点数较多，而且每个位置可选择的位置数又可分为8、6、4、3、2 个，这样处理起来十分麻烦，而且采用单一的回溯法通常会对结点进行重复搜索，效率不高[3]。所以我们对回溯过程中不同活结点的通路数量进行排序，并将通路数目最少的活结点作为当前的最优选择，从而进一步提高回溯法的效率。

本文对国际象棋中马的周游路线问题进行了分析， 设计了基于回溯法和最优选择法的算法， 文中给出了算法的具体实现过程，实验结果验证了算法的有效性。

2. 问题的提出 *基金项目：本文研究得到辽宁省教育厅科学研究一般项目(L2011192)，计算机软件新技术国家重点实验室(南京大学)开放课题(KFKT2011B09)资助。

考虑国际象棋棋盘上某位置的马，它是否可能只Copyright © 2012 Hanspub 22