| 国际象棋棋盘上马的周游路线问题 |
| |
| 引用本文： | 曹新谱,肖宝麟.国际象棋棋盘上马的周游路线问题[J].重庆大学学报(自然科学版),1988,11(4). |
| |
| 作者姓名： | 曹新谱 肖宝麟 |
| |
| 作者单位： | 国防科技大学
(曹新谱)，重庆大学(肖宝麟) |
| |
| 摘 要： | 本文中研究一类重要的问题-NP-完全问题。对计算困难程度来说,这一类问题的所有问题是等价的。这类问题包含很多实际上重要而又值得研究的问题,例如整数规划问题和哈密顿圈问题。利用分治-合并的思想,本文设计了一个算法,可以很快地在国际象棋棋盘上找到马的周游路线(哈密顿圈)。
|
| 关 键 词： | 哈密顿圈 NP-完全问题 分治-合并 |
THE KNIGHT'S TOUR ON A CHESSBOARD |
| |
| Cao Xinpu Xiao Baolin.THE KNIGHT''S TOUR ON A CHESSBOARD[J].Journal of Chongqing University(Natural Science Edition),1988,11(4). |
| |
| Authors: | Cao Xinpu Xiao Baolin |
| |
| Institution: | Cao Xinpu Xiao Baolin |
| |
| Abstract: | In this paper the NP-complete problems are studied. They contain such important problems as the integer-programming and the Hamiltonian circuit problems which are worth studying but equally difficult to compute. Based on the thought of dividing and conquering-merge, an algorithm is designed, with which the knight's tour on an international chessboard can be quickly found. |
| |
| Keywords: | Hamiltonian circuit NP-complete problems Divide and conquer-merge |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《重庆大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《重庆大学学报(自然科学版)》下载免费的PDF全文 |
