易到达的方格上,从而为最容易到达的方格留下空位。这样,当棋盘的四角都旅行过后,就可以有较大的成功概率来完成骑士旅行。我们可以根据每个方格可能到达程度来开发一个“可访问试探法”,然后总是将骑士移到(当然是骑士的L形走法)最不容易到达的方格上。我们利用一些数字来定义一个二维数组accessibility,这些数字表明一个格了能访问的格数。在一个空棋盘上,每个中心方格可访问格数为8,四角方格的可访问略数为2,其他方格具有的可访问格数为3、4或6,如下所示:
2 3 4 4 4 4 3 3 4 6 6 6 6 4 4 6 8 8 8 8 6 4 6 8 8 8 8 6 4 6 8 8 8 8 6 4 6 8 8 8 8 6 3 4 6 6 6 6 4 2
3
4
4
4
4
3
2 3 4 4 4 4 3 2
编写一个使用可访问试控法的骑士旅行程序,骑士应当总是移 向标有可访问性的方格。如果面临多种选择,那么该棋子可以移向任 何可选的方格。因此,旅行可以从四个角中的任何一个开始(说明: 当骑士在棋盘上旅行时, 程序应当随着方格不断被占而减小可访问数 值。这样,在旅行过程中的任何时候,每一个方格的可访问数值都要 精确地保持为此方格能访问的格数) 。运行程序的这一版本,能否实 现一个完整的旅行?修改此程序并运行64次旅行,每次从棋盘的不 同位置开始。总共能获得多少次完整的旅行? d) 编写骑士旅行的另一个版本, 当遇到难以在两个或多个方格之 间做出选择的情况时, 通过向前查看那些从连接的方格可到达的方格 来决定怎样移动。
程序应当移到那些在下一次移动时,到达的方格具 有最小可访问数值的方格。 3、(骑士旅行:强制算法)在上题中,我们开发了一个骑士旅行问题的 解决方案。这个方法使用了所谓的“可访问试探法”生成许多
方案, 从而提高了执行效率。由于
计算机的性能不断增强,因此我们可以直 接利用计算机的功能和相对低级的算法来解决更多的问题。 我们称这 种方法为强制算法。 a) 使用随机数产生器,使得骑士在棋盘上任意移动(当然是走L 形) 。程序应当运行一次,并将最终的棋盘打印出来,这个骑士走了 多远? b) 前面的程序很有可能产生了一个相对较短的旅行。 现在修改该
程序,尝试1000次旅行。利用一个单下标数组来跟踪每次旅行所走的步数,当程序完成了1000次旅行尝试后,应当用清晰的表格形式打印出这一信息。最佳的结果是什么?
c) 前面的程序很有可能产生了一些“几乎成功”的但不是完整的旅行。现在去除次数限制,简单地让程序运行,直至产生了一个完整的旅行(说明:此版本的程序可能会在功能强大的机器上运行数小时)。以表格形式保存每次旅行所走的步数,当找到第一个完整的旅行时,打印出此表格。在产生一个完整的旅行之前,该程序进行了多少次尝试?使用了多少时间?
d) 把骑士旅行问题的强制算法同可访问试探法进行比较。哪种方法需要对
问题进行更多的研究?哪种算法更难于开发?哪种算法需要更强大的计算机?我们是否能使用试探法(提前)确定得到一个完整的旅行?我们是否能使用强制算法(提前)确定得到一个完整的旅行?从总体上讨论强制算法的优缺点。
4、(八皇后)国际象棋的另一个难题是八皇后问题,可以简单地表述为:是否有可能将八个皇后放在空棋盘上,任何一个皇后都不受其他皇的“攻击”。也就是说,没有两个皇后在同一行、同一列或者同一对角线上。使用上题的思路提出一个解决八皇后问题的试探法。运行你的程序(提示:可以给棋盘上的每个方格设定一值,以表明如果将一个皇后放在这里,会“删除”空棋盘上的多少个方格。每个角上的方格应赋值为22,如图所示)。一旦这些“删除数字”布满64个方格,那么一个合适的试探法应该是:将下一皇后放在具有最小“删除
数字”的方格上。为什么该策略是可行的:
将一皇后放在左上角,有22个方格将被删除 5、 (八皇